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

* 数据结构（C++版）第2版 清华大学出版社 专题3：树形索引技术 1 2 2－3树 B树 3 B＋树 9.3 树形索引 2 – 3 树 2-3树：是具有下列特性的树： ⑴ 一个结点包含1个或者2个关键码。 ⑵ 每个内部结点有2个子女（包含一个关键码）或者3个子女（包含两个关键码）。 ⑶ 所有叶子结点都在树的同一层。 9.3 树形索引 2 – 3 树示例 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 形状上有什么特性? 包含1个或者2个关键码； 有2个子女或者3个子女； 叶子结点在同一层。 9.3 树形索引 2 – 3 树示例 结点的值有什么特性? 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 左子树所有结点的值均小于第一个关键码的值； 中间子树所有结点的值均大于第一个关键码的值，且小于第二个关键码的值； 右子树所有结点的值均大于第二个关键码的值。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 9.3 树形索引 2 – 3 树——查找操作 21 182133 2123 比较次数不超过树的深度。 由于2-3树是树高平衡的，而且每一个内部结点至少有2个子女，所以树的最大深度是 。 ? ? 1 log 2 + n 9.3 树形索引 2 – 3 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 叶子结点只包含1个记录 插入新记录 14 9.3 树形索引 2 – 3 树——插入操作 新记录将插入到相应的叶子结点中。 叶子结点只包含1个记录 插入新记录 18 33 12 23 30 48 10 20 21 24 31 45 47 50 52 14 15 9.3 树形索引 2 – 3 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 叶子结点只包含2个记录 插入新记录，分裂－提升 55 9.3 树形索引 2 – 3 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 55 叶子结点只包含2个记录 插入新记录，分裂－提升 插入 9.3 树形索引 2 – 3 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 叶子结点只包含2个记录 插入新记录，分裂－提升 分裂 50 55 52 9.3 树形索引 2 – 3 树——插入操作 新记录将插入到相应的叶子结点中。 18 33 12 23 30 10 15 20 21 24 31 45 47 叶子结点只包含2个记录 插入新记录，分裂－提升 提升 50 55 48 52 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况1：从包含2个记录的叶子结点删除1个记录。 解决方法：直接删除这个记录。 18 33 12 23 30 48 10 15 24 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况1：从包含2个记录的叶子结点删除1个记录。 解决方法：直接删除这个记录。 21 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。 18 33 12 21 30 48 10 15 20 23 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。 18 33 12 21 30 48 10 15 20 23 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 18 33 12 20 21 4