广东海洋大学信息学院数据结构课件第九章 索引技术.ppt

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 48 10 15 30 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 18 33 12 20 21 48 10 15 30 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 20 21 48 33 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 10 12 18 30 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 48 33 30 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。 25 20 9.3 树形索引 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。 45 47 50 52 33 48 20 25 2-3树的优点：能够以相对较低的代价保持树高平衡。 9.3 树形索引 2 – 3 树——删除操作 情况3：从内部结点删除一个记录。 解决方法：将被删除记录用右边子树中的最小关键码Y代替（ Y一定在某个叶子结点中），然后再删除Y。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 9.3 树形索引 2 – 3 树——删除操作 情况3：从内部结点删除一个记录。 解决方法：将被删除记录用右边子树中的最小关键码Y代替（ Y一定在某个叶子结点中），然后再删除Y。 20 33 12 23 30 48 10 15 21 24 31 45 47 50 52 B－树 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 树形索引 1 18 1 11 1 27 1 39 3 47 53 64 1 99 F F F F F F F F F F F F 2 43 78 1 35 9.3 树形索引 B－树示例 叶子结点 查找失败的结点 终端结点 在同一层上 外结点 指针 包含其子女结点的块号 B+树 m阶B＋树：是满足下列特性的树： ⑴ 含有m个关键码，每一个关键码对应一棵子树。 ⑵ 关键码Ki是它所对应的子树的根结点中的最大（或最小）关键码。 ⑶ 所有终端结点中包含了全部关键码信息，以及指向关键码记录的指针。 ⑷ 所有终端结点按关键码的大小链在一起，形成单链表，并设置头指针。 9.3 树形索引 L 9.3 树形索引 B+树示例 50 90 20 50 60 80 90 12 16 20 26 30 50 55 60 62 70 80 82 86 90 内部结点 只存储关键码 终端结点 存储记录 引导查找 本课程选用 主教材王红梅.数据结构（C＋＋版）.清华大学出版社 本课程辅导及实验教材王红梅.数据结构学习辅导与实验指导.清华大学出版社 本课程课件 在课程教材所自带课件基础上，根据大纲需要进行修改。 关于教材及课件 数据结构（C++版） 清华大学出版社 第九章 索引技术 本章的基本内容是： 索引的基本概念 线性索引技术 树形索引 9.1 索引的基本概念 数据结