專題3：樹形索引技術(shù)122－3樹B樹3B＋樹9.3樹形索引2–3樹2-3樹：是具有下列特性的樹：⑴一個(gè)結(jié)點(diǎn)包含1個(gè)或者2個(gè)關(guān)鍵碼。⑵每個(gè)內(nèi)部結(jié)點(diǎn)有2個(gè)子女（包含一個(gè)關(guān)鍵碼）或者3個(gè)子女（包含兩個(gè)關(guān)鍵碼）。⑶

所有葉子結(jié)點(diǎn)都在樹的同一層。9.3樹形索引2–3樹示例18331223304810152021243145475052形狀上有什么特性?包含1個(gè)或者2個(gè)關(guān)鍵碼；有2個(gè)子女或者3個(gè)子女；葉子結(jié)點(diǎn)在同一層。9.3樹形索引2–3樹示例結(jié)點(diǎn)的值有什么特性?18331223304810152021243145475052左子樹所有結(jié)點(diǎn)的值均小于第一個(gè)關(guān)鍵碼的值；中間子樹所有結(jié)點(diǎn)的值均大于第一個(gè)關(guān)鍵碼的值，且小于第二個(gè)關(guān)鍵碼的值；右子樹所有結(jié)點(diǎn)的值均大于第二個(gè)關(guān)鍵碼的值。183312233048101520212431454750529.3樹形索引2–3樹——查找操作2118<21<3321<23比較次數(shù)不超過樹的深度。由于2-3樹是樹高平衡的，而且每一個(gè)內(nèi)部結(jié)點(diǎn)至少有2個(gè)子女，所以樹的最大深度是。??1log2+n9.3樹形索引2–3樹——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223304810152021243145475052葉子結(jié)點(diǎn)只包含1個(gè)記錄插入新記錄

149.3樹形索引2–3樹——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。葉子結(jié)點(diǎn)只包含1個(gè)記錄插入新記錄

18331223304810202124314547505214159.3樹形索引2–3樹——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223304810152021243145475052葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

559.3樹形索引2–3樹——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。1833122330481015202124314547505255葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

插入9.3樹形索引2–3樹——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。1833122330481015202124314547葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

分裂5055529.3樹形索引2–3樹——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223301015202124314547葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

提升50554852183312233048101520212431454750529.3樹形索引2–3樹——?jiǎng)h除操作情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。解決方法：直接刪除這個(gè)記錄。18331223304810152431454750529.3樹形索引2–3樹——?jiǎng)h除操作情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。解決方法：直接刪除這個(gè)記錄。21183312233048101520212431454750529.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。1833122130481015202331454750529.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。1833122130481015202331454750529.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。18331220214810153031454750529.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。18331220214810153031454750529.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，合并操作可能影響祖先結(jié)點(diǎn)。2021483331454750529.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。10121830解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，合并操作可能影響祖先結(jié)點(diǎn)。483330454750529.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹的高度。25209.3樹形索引2–3樹——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹的高度。45475052334820252-3樹的優(yōu)點(diǎn)：能夠以相對較低的代價(jià)保持樹高平衡。9.3樹形索引2–3樹——?jiǎng)h除操作情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。解決方法：將被刪除記錄用右邊子樹中的最小關(guān)鍵碼Y代替（Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。183312233048101520212431454750529.3樹形索引2–3樹——?jiǎng)h除操作情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。解決方法：將被刪除記錄用右邊子樹中的最小關(guān)鍵碼Y代替（Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。203312233048101521243145475052B樹9.3樹形索引m階B樹：是滿足下列特性的樹：⑴所有葉子結(jié)點(diǎn)都在同一層上，并且不帶信息，葉子的雙親稱為終端結(jié)點(diǎn)。⑵樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；⑶若根結(jié)點(diǎn)不是終端結(jié)點(diǎn)，則至少有兩棵子樹；⑷除根結(jié)點(diǎn)外，其他非終端結(jié)點(diǎn)至少有m/2

棵子樹；B樹是2－3樹的推廣，2－3樹是一個(gè)3階的B樹

。所有非終端結(jié)點(diǎn)都包含以下數(shù)據(jù)：（n，A0，K1，A1，K2，…，Kn，An）其中，n（m/2

1≤n≤m

1）為關(guān)鍵碼的個(gè)數(shù)；Ki（1≤i≤n）為關(guān)鍵碼，且Ki＜Ki+1（1≤i≤n-1）；Ai（0≤i≤n）為指向子樹根結(jié)點(diǎn)的指針，且指針Ai所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki+1大于Ki。B樹9.3樹形索引1181

111

271

393475364199FFFFFFFFFFFF243781

359.3樹形索引B樹示例葉子結(jié)點(diǎn)查找失敗的結(jié)點(diǎn)終端結(jié)點(diǎn)在同一層上外結(jié)點(diǎn)指針包含其子女結(jié)點(diǎn)的塊號B+樹m階B＋樹：是滿足下列特性的樹：⑴含有m個(gè)關(guān)鍵碼，每一個(gè)關(guān)鍵碼對應(yīng)一棵子樹。⑵關(guān)鍵碼Ki是它所對應(yīng)的子樹的根結(jié)點(diǎn)中的最大（或最?。╆P(guān)鍵碼。⑶所有終端結(jié)點(diǎn)中包含了全部關(guān)鍵碼信息，以及指向關(guān)鍵碼記錄的指針。⑷

所有終端結(jié)點(diǎn)按關(guān)鍵碼的大小鏈在一起，形成單鏈表，并設(shè)置頭指針。

9.3樹