第9章-专题3-树形索引技术

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 树形索引树形索引数据结构（数