1、數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社專題專題3：樹形索引技術：樹形索引技術1223樹樹B樹樹3B樹樹數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹2- -3樹：樹：是具有下列特性的樹：是具有下列特性的樹： 一個結點包含一個結點包含1個個或者或者2個個關鍵碼。關鍵碼。 每個內部結點有每個內部結點有2個個子女（包含一個關鍵碼）或者子女（包含一個關鍵碼）或者3個個子女（包含兩個關鍵碼）。子女（包含兩個關鍵碼）。 所有葉子結點都在樹的所有葉子結點都在樹的同一層同一層。數據結構（數據結構（C+版）第版）第2版版

2、清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹示例樹示例18 331223 3048101520 21243145 4750 52形狀上有什么特性形狀上有什么特性?包含包含1個個或者或者2個個關鍵碼；關鍵碼；有有2個個子女或者子女或者3個個子女；子女；葉子結點在葉子結點在同一層同一層。數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹示例樹示例結點的值有什么特性結點的值有什么特性?18 331223 3048101520 21243145 4750 52左子樹左子樹所有結點的值均小于第一個關鍵碼的值；所有結點的值均小于第一個

3、關鍵碼的值；中間子樹中間子樹所有結點的值均大于第一個關鍵碼的值，且小于第所有結點的值均大于第一個關鍵碼的值，且小于第二個關鍵碼的值；二個關鍵碼的值；右子樹右子樹所有結點的值均大于第二個關鍵碼的值。所有結點的值均大于第二個關鍵碼的值。數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331223 3048101520 21243145 4750 529.3 樹形索引樹形索引2 3 樹樹查找操作查找操作211821332123比較次數不超過樹的深度。比較次數不超過樹的深度。由于由于2-3樹是樹高平衡的，而且每一個內部結點至少樹是樹高平衡的，而且每一個內部結點至少有有2個子

4、女，所以樹的最大深度是個子女，所以樹的最大深度是 。 1log2+ +n數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹插入操作插入操作新記錄將插入到相應的新記錄將插入到相應的葉子葉子結點中。結點中。18 331223 3048101520 21243145 4750 52葉子結點只包含葉子結點只包含1個記錄個記錄插入新記錄插入新記錄 14數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹插入操作插入操作新記錄將插入到相應的新記錄將插入到相應的葉子葉子結點中。結點中。葉子結點只包含

5、葉子結點只包含1個記錄個記錄插入新記錄插入新記錄 18 331223 30481020 21243145 4750 5214 15數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹插入操作插入操作新記錄將插入到相應的新記錄將插入到相應的葉子葉子結點中。結點中。18 331223 3048101520 21243145 4750 52葉子結點只包含葉子結點只包含2個記錄個記錄插入新記錄，分裂提升插入新記錄，分裂提升 55數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹插入操作插入操作

6、新記錄將插入到相應的新記錄將插入到相應的葉子葉子結點中。結點中。18 331223 3048101520 21243145 4750 52 55葉子結點只包含葉子結點只包含2個記錄個記錄插入新記錄，分裂提升插入新記錄，分裂提升 插入插入數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹插入操作插入操作新記錄將插入到相應的新記錄將插入到相應的葉子葉子結點中。結點中。18 331223 3048101520 21243145 47葉子結點只包含葉子結點只包含2個記錄個記錄插入新記錄，分裂提升插入新記錄，分裂提升 分裂分裂505552數據結構（

7、數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹插入操作插入操作新記錄將插入到相應的新記錄將插入到相應的葉子葉子結點中。結點中。18 331223 30101520 21243145 47葉子結點只包含葉子結點只包含2個記錄個記錄插入新記錄，分裂提升插入新記錄，分裂提升 提升提升505548 52數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331223 3048101520 21243145 4750 529.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況1：從包含：從包含2個記錄的葉子結點刪除個記錄的葉

8、子結點刪除1個記錄。個記錄。 解決方法：直接刪除這個記錄。解決方法：直接刪除這個記錄。 數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331223 30481015243145 4750 529.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況1：從包含：從包含2個記錄的葉子結點刪除個記錄的葉子結點刪除1個記錄。個記錄。 解決方法：直接刪除這個記錄。解決方法：直接刪除這個記錄。 21數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331223 3048101520 21243145 4750 529.3 樹形索引樹形索引2 3

9、樹樹刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 解決方法：向兄弟結點借一個記錄，同時修改雙親解決方法：向兄弟結點借一個記錄，同時修改雙親結點的記錄。結點的記錄。 數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331221 3048101520233145 4750 529.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 解決方法：向兄弟結點借一個記錄，同時修改雙親解決方法：向兄弟結點借一個記錄，同時修改雙親

10、結點的記錄。結點的記錄。 數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331221 3048101520233145 4750 529.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 解決方法：兄弟結點不夠借，需要合并相鄰結點，解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點。并影響雙親結點。數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331220 21481015303145 4750 529.3 樹形索引樹形索引2 3 樹樹

11、刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 解決方法：兄弟結點不夠借，需要合并相鄰結點，解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點。并影響雙親結點。數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社18 331220 21481015303145 4750 529.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 解決方法：兄弟結點不夠借，需要合并相鄰結點，解決方法：兄弟結點不夠借，需要合并相鄰結點，并

12、影響雙親結點，并影響雙親結點，合并操作可能影響祖先結點合并操作可能影響祖先結點。數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社20 2148333145 4750 529.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 10 1218 30解決方法：兄弟結點不夠借，需要合并相鄰結點，解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點，并影響雙親結點，合并操作可能影響祖先結點合并操作可能影響祖先結點。數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社4

13、8333045 4750 529.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 解決方法：兄弟結點不夠借，需要合并相鄰結點，解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點，這可能并影響雙親結點，這可能減少樹的高度減少樹的高度。2520數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況2：從包含：從包含1個記錄的葉子結點中刪除這個記錄。個記錄的葉子結點中刪除這個記錄。 解決方法：兄弟結點不夠借，需要合并相鄰結點

14、，解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點，這可能并影響雙親結點，這可能減少樹的高度減少樹的高度。45 4750 5233 4820 252-3樹的優點：能夠以相對較低的代價保持樹高平衡。樹的優點：能夠以相對較低的代價保持樹高平衡。 數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況3：從內部結點刪除一個記錄。：從內部結點刪除一個記錄。 解決方法：將被刪除記錄用解決方法：將被刪除記錄用右邊子樹右邊子樹中的中的最小最小關鍵碼關鍵碼Y代替（代替（ Y一定在某個葉子結點中），然后再刪除一定在某個葉子結點

15、中），然后再刪除Y。18 331223 3048101520 21243145 4750 52數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社9.3 樹形索引樹形索引2 3 樹樹刪除操作刪除操作情況情況3：從內部結點刪除一個記錄。：從內部結點刪除一個記錄。 解決方法：將被刪除記錄用解決方法：將被刪除記錄用右邊子樹右邊子樹中的中的最小最小關鍵碼關鍵碼Y代替（代替（ Y一定在某個葉子結點中），然后再刪除一定在某個葉子結點中），然后再刪除Y。20 331223 3048101521243145 4750 52數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社

16、B樹樹9.3 樹形索引樹形索引m階階B樹：樹：是滿足下列特性的樹：是滿足下列特性的樹： 所有葉子結點都在同一層上，并且不帶信息，葉子所有葉子結點都在同一層上，并且不帶信息，葉子的雙親稱為終端結點。的雙親稱為終端結點。 樹中每個結點至多有樹中每個結點至多有m棵子樹；棵子樹； 若根結點不是終端結點，則至少有兩棵子樹；若根結點不是終端結點，則至少有兩棵子樹； 除根結點外，其他非終端結點至少有除根結點外，其他非終端結點至少有 m/2 棵子樹；棵子樹；B樹是樹是23樹的推廣，樹的推廣，23樹是一個樹是一個3階的階的B樹樹 。數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社所有非終端

17、結點都包含以下數據：所有非終端結點都包含以下數據： （n，A0，K1，A1，K2，Kn，An）其中，其中，n（ m/2 1nm 1）為為關鍵碼的個數；關鍵碼的個數；Ki（1in）為關鍵碼，且為關鍵碼，且KiKi+1（1in-1）；Ai（0in）為指向子樹根結點的指針，且指針為指向子樹根結點的指針，且指針Ai所指所指子樹中所有結點的關鍵碼均小于子樹中所有結點的關鍵碼均小于Ki+1大于大于Ki。B樹樹9.3 樹形索引樹形索引數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社1 181 111 271 393 47 53 641 99FFFFFFFFFFFF2 43 781 35

18、9.3 樹形索引樹形索引B樹示例樹示例葉子結點葉子結點查找失敗的結點查找失敗的結點終端結點終端結點在同一層上在同一層上外結點外結點指針指針包含其子女結點的塊號包含其子女結點的塊號數據結構（數據結構（C+版）第版）第2版版清華大學出版社清華大學出版社B+樹樹m階階B樹：樹：是滿足下列特性的樹：是滿足下列特性的樹： 含有含有m個關鍵碼，每一個關鍵碼對應一棵子樹。個關鍵碼，每一個關鍵碼對應一棵子樹。 關鍵碼關鍵碼Ki是它所對應的子樹的根結點中的最大（或是它所對應的子樹的根結點中的最大（或最小）關鍵碼。最小）關鍵碼。 所有終端結點中包含了全部關鍵碼信息，以及指向所有終端結點中包含了全部關鍵碼信息，以及指向關鍵碼記錄的指針。關鍵碼記錄的指針。 所有終端結點按關鍵碼的大小鏈在一起，形成單鏈所有終端結點按關鍵碼的大小鏈在一起，形成單鏈表，并設置頭指針。表，并設置頭指針。 9.3 樹形索引樹形索引數據結構（數