第9章-專題3-樹形索引技術

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

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

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

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

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

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

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

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

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

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

1≤n≤m

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

111

271

393475364199FFFFFFFFFFFF243781

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

所有終端結點按關鍵碼的大小鏈在一起，形成單鏈表，并設置頭指針。

9.3樹