第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比较次数不超过树的深度。由于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树的优点：能够以相对较低的代价保持树高平衡。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树

。所有非终端结点都包含以下数据：（n，A0，K1，A1，K2，…，Kn，An）其中，n（m/2

1≤n≤m

1）为关键码的个数；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树