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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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