第9章-專題3-樹形索引技術(shù)

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

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

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

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

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

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

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

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

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

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

1≤n≤m

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

111

271

393475364199FFFFFFFFFFFF243781

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

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

9.3樹