數(shù)據(jù)結(jié)構(gòu)之索引

1、B樹與B+樹2基本概念 輸入順序文件輸入順序文件 主碼與輔碼主碼與輔碼 索引與索引文件索引與索引文件 稠密索引與稀疏索引稠密索引與稀疏索引B樹與B+樹3輸入順序文件 輸入順序文件輸入順序文件( entry-sequenced file )按照記錄按照記錄進(jìn)入系統(tǒng)的順序存儲(chǔ)記錄進(jìn)入系統(tǒng)的順序存儲(chǔ)記錄輸入順序文件的結(jié)構(gòu)相當(dāng)于一個(gè)磁盤中未排序的線輸入順序文件的結(jié)構(gòu)相當(dāng)于一個(gè)磁盤中未排序的線性表性表因此不支持高效率的檢索因此不支持高效率的檢索B樹與B+樹4主碼 主碼主碼( primary key )是數(shù)據(jù)庫(kù)中的每條記錄的唯是數(shù)據(jù)庫(kù)中的每條記錄的唯一標(biāo)識(shí)一標(biāo)識(shí)例如，公司職員信息的記錄的主碼可以是職員的身

2、例如，公司職員信息的記錄的主碼可以是職員的身份證號(hào)碼份證號(hào)碼 如果只有主碼，不便于各種靈活檢索如果只有主碼，不便于各種靈活檢索B樹與B+樹5輔碼 輔碼輔碼( secondary key )是數(shù)據(jù)庫(kù)中可以出現(xiàn)重復(fù)是數(shù)據(jù)庫(kù)中可以出現(xiàn)重復(fù)值的碼值的碼 輔碼索引把一個(gè)輔碼值與具有這個(gè)輔碼值的每輔碼索引把一個(gè)輔碼值與具有這個(gè)輔碼值的每一條記錄的主碼值關(guān)聯(lián)起來(lái)一條記錄的主碼值關(guān)聯(lián)起來(lái)大多數(shù)檢索都是利用輔碼索引來(lái)完成的大多數(shù)檢索都是利用輔碼索引來(lái)完成的B樹與B+樹6索引 索引索引( indexing )是把一個(gè)關(guān)鍵碼與它對(duì)應(yīng)的數(shù)據(jù)記錄的是把一個(gè)關(guān)鍵碼與它對(duì)應(yīng)的數(shù)據(jù)記錄的位置相關(guān)聯(lián)的過程位置相關(guān)聯(lián)的過程 索引

3、技術(shù)是組織大型數(shù)據(jù)庫(kù)的一種重要技術(shù)索引技術(shù)是組織大型數(shù)據(jù)庫(kù)的一種重要技術(shù) 數(shù)據(jù)庫(kù)組織存儲(chǔ)在外存中的大量記錄數(shù)據(jù)庫(kù)組織存儲(chǔ)在外存中的大量記錄高效率的檢索高效率的檢索插入、更新、刪除插入、更新、刪除B樹與B+樹7索引文件 索引文件索引文件( index file )是是用于記錄這種聯(lián)系（關(guān)用于記錄這種聯(lián)系（關(guān)鍵碼與它對(duì)應(yīng)的數(shù)據(jù)記錄的位置）的文件組織鍵碼與它對(duì)應(yīng)的數(shù)據(jù)記錄的位置）的文件組織結(jié)構(gòu)。結(jié)構(gòu)。 索引文件的記錄索引文件的記錄（關(guān)鍵碼，指針）對(duì)（關(guān)鍵碼，指針）對(duì)將每個(gè)關(guān)鍵碼和一個(gè)指針關(guān)聯(lián)將每個(gè)關(guān)鍵碼和一個(gè)指針關(guān)聯(lián)指針指向主要數(shù)據(jù)庫(kù)文件（也稱為指針指向主要數(shù)據(jù)庫(kù)文件（也稱為“主文件主文件”）中）中

4、的完整記錄的完整記錄B樹與B+樹8索引文件 索引文件并不需要重新排列記錄在磁盤中的順?biāo)饕募⒉恍枰匦屡帕杏涗浽诖疟P中的順序（不用重排主文件）序（不用重排主文件）一個(gè)數(shù)據(jù)庫(kù)可能有多個(gè)相關(guān)的索引文件一個(gè)數(shù)據(jù)庫(kù)可能有多個(gè)相關(guān)的索引文件每個(gè)索引文件往往支持一個(gè)關(guān)鍵碼字段每個(gè)索引文件往往支持一個(gè)關(guān)鍵碼字段可以通過該索引文件高效訪問記錄中該關(guān)鍵碼值可以通過該索引文件高效訪問記錄中該關(guān)鍵碼值B樹與B+樹9稠密索引 對(duì)每一個(gè)記錄建立一個(gè)索引項(xiàng)，這樣建對(duì)每一個(gè)記錄建立一個(gè)索引項(xiàng)，這樣建立的索引被稱為稠密索引立的索引被稱為稠密索引( dense index ) 數(shù)據(jù)庫(kù)文件中的記錄不按照關(guān)鍵碼的順數(shù)據(jù)庫(kù)文件中的

5、記錄不按照關(guān)鍵碼的順序排列時(shí)（比如按照加入的順序排列）序排列時(shí)（比如按照加入的順序排列）B樹與B+樹10稀疏索引 對(duì)一組記錄建立一個(gè)索引項(xiàng)，這種索引稱之為對(duì)一組記錄建立一個(gè)索引項(xiàng)，這種索引稱之為稀疏索引稀疏索引( spare index )當(dāng)記錄在磁盤中是按照關(guān)鍵碼的順序存放當(dāng)記錄在磁盤中是按照關(guān)鍵碼的順序存放可以把記錄分成多個(gè)組（塊）可以把記錄分成多個(gè)組（塊） 稀疏索引索引項(xiàng)的指針指向的是這一組記錄在稀疏索引索引項(xiàng)的指針指向的是這一組記錄在磁盤中的起始位置磁盤中的起始位置 B樹與B+樹1110.1 線性索引 基本概念基本概念 線性索引的優(yōu)點(diǎn)線性索引的優(yōu)點(diǎn)B樹與B+樹12基本概念 線性索引線性

6、索引(linear index)的索引文件的索引文件一組簡(jiǎn)單的關(guān)鍵碼一組簡(jiǎn)單的關(guān)鍵碼(key)/指針指針(pointer)對(duì)的序?qū)Φ男蛄辛蠦樹與B+樹13基本概念（續(xù)） 線性索引文件按照關(guān)鍵碼的順序進(jìn)行排序線性索引文件按照關(guān)鍵碼的順序進(jìn)行排序 文件中的指針指向存儲(chǔ)在磁盤上的文件記錄起始位置文件中的指針指向存儲(chǔ)在磁盤上的文件記錄起始位置或者主索引中主碼的起始位置或者主索引中主碼的起始位置B樹與B+樹14基本概念（續(xù)） 線性索引的索引文件線性索引的索引文件存儲(chǔ)在內(nèi)存中，把索引存儲(chǔ)在內(nèi)存中能大大地存儲(chǔ)在內(nèi)存中，把索引存儲(chǔ)在內(nèi)存中能大大地提高檢索速度提高檢索速度存儲(chǔ)在磁盤中存儲(chǔ)在磁盤中 根據(jù)線性索引的

7、文件大小和內(nèi)存的空間限制根據(jù)線性索引的文件大小和內(nèi)存的空間限制B樹與B+樹15線性索引的優(yōu)點(diǎn) 對(duì)變長(zhǎng)的數(shù)據(jù)庫(kù)記錄的訪問對(duì)變長(zhǎng)的數(shù)據(jù)庫(kù)記錄的訪問 可以對(duì)數(shù)據(jù)進(jìn)行高效檢索可以對(duì)數(shù)據(jù)進(jìn)行高效檢索 二分檢索二分檢索 順序處理順序處理比較操作比較操作批處理的操作批處理的操作 節(jié)省空間節(jié)省空間 (相對(duì)其它索引結(jié)構(gòu)相對(duì)其它索引結(jié)構(gòu))B樹與B+樹1610.2 靜態(tài)索引 基本概念基本概念 10.2.1 多分樹多分樹B樹與B+樹17基本概念靜態(tài)索引靜態(tài)索引 索引結(jié)構(gòu)在文件創(chuàng)建、初始裝入記錄時(shí)生成索引結(jié)構(gòu)在文件創(chuàng)建、初始裝入記錄時(shí)生成 一旦生成就固定下來(lái)，在系統(tǒng)運(yùn)行一旦生成就固定下來(lái)，在系統(tǒng)運(yùn)行(例如插入和例如插入

8、和刪除記錄刪除記錄)過程中索引結(jié)構(gòu)并不改變過程中索引結(jié)構(gòu)并不改變 只有當(dāng)文件再組織時(shí)才允許改變索引結(jié)構(gòu)只有當(dāng)文件再組織時(shí)才允許改變索引結(jié)構(gòu) B樹與B+樹1810.2.1 多分樹 組織索引一般不用二叉樹而采用多分樹組織索引一般不用二叉樹而采用多分樹 大大減少訪問外存的次數(shù)大大減少訪問外存的次數(shù) B樹與B+樹19多分樹圖例B樹與B+樹20上圖訪問一個(gè)葉結(jié)點(diǎn)上圖訪問一個(gè)葉結(jié)點(diǎn) 查找二叉樹查找二叉樹訪問訪問六次六次外存外存 查找多分樹查找多分樹訪問訪問兩次兩次外存外存 B樹與B+樹21 結(jié)點(diǎn)更大結(jié)點(diǎn)更大以更少的外存訪問次數(shù)來(lái)完成查找以更少的外存訪問次數(shù)來(lái)完成查找 需要較大的緩沖區(qū)需要較大的緩沖區(qū)讀入一

9、個(gè)結(jié)點(diǎn)也需較多時(shí)間讀入一個(gè)結(jié)點(diǎn)也需較多時(shí)間 一個(gè)結(jié)點(diǎn)最好能放在一個(gè)磁盤塊中一個(gè)結(jié)點(diǎn)最好能放在一個(gè)磁盤塊中B樹與B+樹22 “數(shù)據(jù)基本區(qū)數(shù)據(jù)基本區(qū)”多分樹的葉結(jié)點(diǎn)區(qū)域多分樹的葉結(jié)點(diǎn)區(qū)域存放數(shù)據(jù)記錄存放數(shù)據(jù)記錄 “索引區(qū)索引區(qū)”多分樹的非葉結(jié)點(diǎn)區(qū)域多分樹的非葉結(jié)點(diǎn)區(qū)域存放各子樹結(jié)點(diǎn)中的最大存放各子樹結(jié)點(diǎn)中的最大(或最小或最小)的關(guān)鍵碼的關(guān)鍵碼B樹與B+樹23 溢出、溢出區(qū)溢出、溢出區(qū)新記錄要插入的結(jié)點(diǎn)已滿新記錄要插入的結(jié)點(diǎn)已滿把溢出的記錄存放到另開辟的溢出區(qū)把溢出的記錄存放到另開辟的溢出區(qū)不改變索引的結(jié)構(gòu)不改變索引的結(jié)構(gòu) 記錄送入溢出區(qū)的兩種方式記錄送入溢出區(qū)的兩種方式 保持順序，把最后一個(gè)記錄送

10、往溢出區(qū)保持順序，把最后一個(gè)記錄送往溢出區(qū)不保持順序，把新插入的記錄送入溢出區(qū)不保持順序，把新插入的記錄送入溢出區(qū) B樹與B+樹2410.4 動(dòng)態(tài)索引 B樹樹 B+樹樹B樹與B+樹25基本概念 動(dòng)態(tài)索引結(jié)構(gòu)動(dòng)態(tài)索引結(jié)構(gòu) 索引結(jié)構(gòu)本身也可能發(fā)生改變索引結(jié)構(gòu)本身也可能發(fā)生改變 在系統(tǒng)運(yùn)行過程中插入或刪除記錄時(shí)在系統(tǒng)運(yùn)行過程中插入或刪除記錄時(shí) 目的目的 保持較好的性能保持較好的性能 例如較高的檢索效率例如較高的檢索效率B樹與B+樹26B樹 B樹樹(Balanced Tree) 一種平衡的多分樹一種平衡的多分樹 B樹與B+樹27B樹是一棵樹是一棵平衡多叉查找樹平衡多叉查找樹。一棵一棵 m 階的階的 B

11、樹，或者是空樹，或者是滿足下列性質(zhì)的樹，或者是空樹，或者是滿足下列性質(zhì)的 m 叉樹叉樹 :(1) 樹中每個(gè)結(jié)點(diǎn)樹中每個(gè)結(jié)點(diǎn)至多至多有有 m 棵子樹棵子樹 ；(2) 根結(jié)點(diǎn)根結(jié)點(diǎn)至少至少有有兩兩棵子樹棵子樹 ；所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層次，可用來(lái)所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層次，可用來(lái)“查找失敗查找失敗”處理。處理。(3) 除根結(jié)點(diǎn)之外的非終端結(jié)點(diǎn)除根結(jié)點(diǎn)之外的非終端結(jié)點(diǎn)至少至少有有 m/ /2 棵子樹棵子樹 ；B-樹B樹與B+樹28 18 11 27 39 47 53 64 99FFFFFFFFFFFF 43 78 35葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)查找失敗的結(jié)點(diǎn)查找失敗的結(jié)點(diǎn)終端結(jié)點(diǎn)終端結(jié)點(diǎn)在同一層上在同一層

12、上外結(jié)點(diǎn)外結(jié)點(diǎn)指針指針包含其子女結(jié)點(diǎn)的塊號(hào)包含其子女結(jié)點(diǎn)的塊號(hào)B-樹B樹與B+樹292- -3樹：樹：是具有下列特性的樹：是具有下列特性的樹： 一個(gè)結(jié)點(diǎn)包含一個(gè)結(jié)點(diǎn)包含1個(gè)個(gè)或者或者2個(gè)個(gè)關(guān)鍵碼。關(guān)鍵碼。每個(gè)內(nèi)部結(jié)點(diǎn)有每個(gè)內(nèi)部結(jié)點(diǎn)有2個(gè)個(gè)子女（包含一個(gè)關(guān)鍵碼）或者子女（包含一個(gè)關(guān)鍵碼）或者3個(gè)個(gè)子女（包含兩個(gè)關(guān)鍵碼）。子女（包含兩個(gè)關(guān)鍵碼）。 所有葉子結(jié)點(diǎn)都在樹的所有葉子結(jié)點(diǎn)都在樹的同一層同一層。2-3樹B-樹是樹是23樹的推廣，樹的推廣，2-3樹是一個(gè)樹是一個(gè)3階階B-樹樹 。B樹與B+樹3018 331223 3048101520 21243145 4750 52形狀上有什么特性形狀上有什

13、么特性?2-3樹示例B樹與B+樹31包含包含1個(gè)個(gè)或者或者2個(gè)個(gè)關(guān)鍵碼；關(guān)鍵碼；有有2個(gè)個(gè)子女或者子女或者3個(gè)個(gè)子女；子女；葉子結(jié)點(diǎn)在葉子結(jié)點(diǎn)在同一層同一層。18 331223 3048101520 21243145 4750 522-3樹示例B樹與B+樹32結(jié)點(diǎn)的值有什么特性結(jié)點(diǎn)的值有什么特性?18 331223 3048101520 21243145 4750 522-3樹示例B樹與B+樹33左子樹左子樹中所有結(jié)點(diǎn)的值均小于第一個(gè)關(guān)鍵碼的值；中所有結(jié)點(diǎn)的值均小于第一個(gè)關(guān)鍵碼的值；中間子樹中間子樹中所有結(jié)點(diǎn)的值均大于第一個(gè)關(guān)鍵碼的值，中所有結(jié)點(diǎn)的值均大于第一個(gè)關(guān)鍵碼的值，且小于第二個(gè)關(guān)鍵碼的

14、值；且小于第二個(gè)關(guān)鍵碼的值；右子樹右子樹中所有結(jié)點(diǎn)的值均大于第二個(gè)關(guān)鍵碼的值。中所有結(jié)點(diǎn)的值均大于第二個(gè)關(guān)鍵碼的值。18 331223 3048101520 21243145 4750 522-3樹示例B樹與B+樹3418 331223 3048101520 21243145 4750 52211821332123比較次數(shù)不超過樹的深度。比較次數(shù)不超過樹的深度。由于由于2-3樹是樹高平衡的，而且每一個(gè)內(nèi)部結(jié)點(diǎn)至少樹是樹高平衡的，而且每一個(gè)內(nèi)部結(jié)點(diǎn)至少有有2個(gè)子女，所以樹的最大深度是個(gè)子女，所以樹的最大深度是 。 1log2+ +n2-3樹查找B樹與B+樹35新記錄將插入到相應(yīng)的新記錄將插入到相

15、應(yīng)的葉子葉子結(jié)點(diǎn)中。結(jié)點(diǎn)中。18 331223 3048101520 21243145 4750 52葉子結(jié)點(diǎn)只包含葉子結(jié)點(diǎn)只包含1個(gè)記錄個(gè)記錄插入新記錄插入新記錄 112-3樹插入B樹與B+樹36新記錄將插入到相應(yīng)的新記錄將插入到相應(yīng)的葉子葉子結(jié)點(diǎn)中。結(jié)點(diǎn)中。葉子結(jié)點(diǎn)只包含葉子結(jié)點(diǎn)只包含1個(gè)記錄個(gè)記錄插入新記錄插入新記錄 18 331223 30481520 21243145 4750 5210 112-3樹插入B樹與B+樹37新記錄將插入到相應(yīng)的新記錄將插入到相應(yīng)的葉子葉子結(jié)點(diǎn)中。結(jié)點(diǎn)中。18 331223 3048101520 21243145 4750 52葉子結(jié)點(diǎn)只包含葉子結(jié)點(diǎn)只包含

16、2個(gè)記錄個(gè)記錄插入新記錄，分裂提升插入新記錄，分裂提升 552-3樹插入B樹與B+樹38新記錄將插入到相應(yīng)的新記錄將插入到相應(yīng)的葉子葉子結(jié)點(diǎn)中。結(jié)點(diǎn)中。18 331223 3048101520 21243145 4750 52 55葉子結(jié)點(diǎn)只包含葉子結(jié)點(diǎn)只包含2個(gè)記錄個(gè)記錄插入新記錄，分裂提升插入新記錄，分裂提升 插入插入2-3樹插入B樹與B+樹39新記錄將插入到相應(yīng)的新記錄將插入到相應(yīng)的葉子葉子結(jié)點(diǎn)中。結(jié)點(diǎn)中。18 331223 3048101520 21243145 47葉子結(jié)點(diǎn)只包含葉子結(jié)點(diǎn)只包含2個(gè)記錄個(gè)記錄插入新記錄，分裂提升插入新記錄，分裂提升 分裂分裂5055522-3樹插入B樹

17、與B+樹40新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18 331223 30101520 21243145 47葉子結(jié)點(diǎn)只包含葉子結(jié)點(diǎn)只包含2個(gè)記錄個(gè)記錄插入新記錄，分裂提升插入新記錄，分裂提升 提升提升505548 522-3樹插入B樹與B+樹4118 331223 3048101520 21243145 4750 52情況情況1：從包含：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。個(gè)記錄。 解決方法：直接刪除這個(gè)記錄。解決方法：直接刪除這個(gè)記錄。 2-3樹刪除B樹與B+樹4218 331223 30481015243145 4750 52情況情況1：從

18、包含：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。個(gè)記錄。 解決方法：直接刪除這個(gè)記錄。解決方法：直接刪除這個(gè)記錄。 212-3樹刪除B樹與B+樹4318 331223 3048101520 21243145 4750 52情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。 解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。結(jié)點(diǎn)的記錄。 2-3樹刪除B樹與B+樹4418 331221 3048101520233145 4750 52情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄

19、。個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。 解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。結(jié)點(diǎn)的記錄。 2-3樹刪除B樹與B+樹4518 331221 3048101520233145 4750 52情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。 解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。并影響雙親結(jié)點(diǎn)。2-3樹刪除B樹與B+樹4618 331220 21481015303145 4750 52情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪

20、除這個(gè)記錄。個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。 解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。并影響雙親結(jié)點(diǎn)。2-3樹刪除B樹與B+樹4718 331220 21481015303145 4750 52情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。 解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。并影響雙親結(jié)點(diǎn)。2-3樹刪除B樹與B+樹4820 2148333145 4750 52情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄

21、。個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。 10 1218 30解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。并影響雙親結(jié)點(diǎn)。2-3樹刪除B樹與B+樹4948333045 4750 52情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。 解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能并影響雙親結(jié)點(diǎn)，這可能減少樹的高度減少樹的高度。25202-3樹刪除B樹與B+樹50情況情況2：從包含：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。個(gè)記錄的葉子結(jié)點(diǎn)

22、中刪除這個(gè)記錄。 解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能并影響雙親結(jié)點(diǎn)，這可能減少樹的高度減少樹的高度。45 4750 5233 4820 252-3樹的優(yōu)點(diǎn)：能夠以相對(duì)較低的代價(jià)保持樹高平衡。樹的優(yōu)點(diǎn)：能夠以相對(duì)較低的代價(jià)保持樹高平衡。 2-3樹刪除B樹與B+樹51情況情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。 解決方法：將被刪除記錄用解決方法：將被刪除記錄用右邊子樹右邊子樹中的中的最小最小關(guān)鍵碼關(guān)鍵碼Y代替（代替（ Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。18 3312

23、23 3048101520 21243145 4750 522-3樹刪除B樹與B+樹52情況情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。 解決方法：將被刪除記錄用解決方法：將被刪除記錄用右邊子樹右邊子樹中的中的最小最小關(guān)鍵碼關(guān)鍵碼Y代替（代替（ Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。20 331223 3048101521243145 4750 522-3樹刪除B樹與B+樹53B+樹 是是B樹的一種變形樹的一種變形 在葉結(jié)點(diǎn)上存儲(chǔ)信息的樹在葉結(jié)點(diǎn)上存儲(chǔ)信息的樹所有的關(guān)鍵碼均出現(xiàn)在葉結(jié)點(diǎn)上所有的關(guān)鍵碼均出現(xiàn)在葉結(jié)點(diǎn)上 各層結(jié)點(diǎn)中的關(guān)鍵碼均是下一層

24、相應(yīng)結(jié)點(diǎn)中各層結(jié)點(diǎn)中的關(guān)鍵碼均是下一層相應(yīng)結(jié)點(diǎn)中最大關(guān)鍵碼（或最小關(guān)鍵碼）的復(fù)寫最大關(guān)鍵碼（或最小關(guān)鍵碼）的復(fù)寫 B樹與B+樹54B+樹的結(jié)構(gòu)定義m m階階B B+ +樹的結(jié)構(gòu)定義如下：樹的結(jié)構(gòu)定義如下：(1)(1)每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)至多至多有有m m個(gè)子結(jié)點(diǎn)；個(gè)子結(jié)點(diǎn)；(2)(2)每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)( (除根外除根外) )至少至少有有 個(gè)子結(jié)點(diǎn)；個(gè)子結(jié)點(diǎn)；(3)(3)根結(jié)點(diǎn)根結(jié)點(diǎn)至少至少有有兩兩個(gè)子結(jié)點(diǎn)；個(gè)子結(jié)點(diǎn)；(4)(4)有有k k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必有個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必有k k個(gè)關(guān)鍵碼。個(gè)關(guān)鍵碼。2mB樹與B+樹552階B+樹的例子B樹與B+樹56B+樹的查找 查找應(yīng)該到葉結(jié)點(diǎn)層查找應(yīng)該到葉結(jié)點(diǎn)

25、層在上層已找到待查的關(guān)鍵碼，并不停止在上層已找到待查的關(guān)鍵碼，并不停止而是繼續(xù)沿指針向下一直查到葉結(jié)點(diǎn)層的這而是繼續(xù)沿指針向下一直查到葉結(jié)點(diǎn)層的這個(gè)關(guān)鍵碼個(gè)關(guān)鍵碼 B+樹的葉結(jié)點(diǎn)一般鏈接起來(lái)，形成一個(gè)雙鏈樹的葉結(jié)點(diǎn)一般鏈接起來(lái)，形成一個(gè)雙鏈表表 適合順序檢索（范圍檢索）適合順序檢索（范圍檢索） 實(shí)際應(yīng)用更廣實(shí)際應(yīng)用更廣B樹與B+樹57B+樹的插入 插入插入分裂分裂 過程和過程和B樹類似樹類似 注意保證上一層結(jié)點(diǎn)中有這兩個(gè)結(jié)點(diǎn)的最大注意保證上一層結(jié)點(diǎn)中有這兩個(gè)結(jié)點(diǎn)的最大關(guān)鍵碼（最小關(guān)鍵碼）關(guān)鍵碼（最小關(guān)鍵碼）B樹與B+樹583階B+樹插入插入插入1515B樹與B+樹593階B+樹插入插入插入1515后后B樹與B+樹60