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

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

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

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

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

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

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

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

。所有非終端結(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）為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針Ai所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki+1大于Ki。B樹(shù)9.3樹(shù)形索引1181

111

271

393475364199FFFFFFFFFFFF243781

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

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

9.3樹(shù)