【11.4】索引--动态索引

动态索引结构:

• 索引结构本身也可能发生改变
• 在系统运行过程中插入或删除记录时

目的:

• 保持较好的性能
• 例如较高的 检索 效率

一、 B 树

一种平衡的多分树 (Balanced Tree)

1.1 m 阶 B 树的结构定义：

1. 每个结点至多有 m 个子结点
2. 除根结点和叶结点外，其它每个结点至少有 𝑚/2 个子结点
3. 根结点至少有两个子结点

• 唯一例外的是根结点就是叶结点时没有子结点
• 此时 B 树只包含一个结点

4. 所有的叶结点在同一层
5. 有 k 个子结点的非根结点恰好包含 k-1 个关键码

1.2 B 树的性质

1. 树高平衡，所有叶结点都在同一层
2. 关键码没有重复，父结点中的关键码是其子 结点的分界
3. B 树把(值接近)相关记录放在同一个磁盘 页中，从而利用了访问局部性原理
4. B 树保证树中至少有一定比例的结点是满的

• 这样能够改进空间的利用率
• 减少检索和更新操作的磁盘读取数目

1.3 B 树的结点结构

B 树的一个包含 j 个关键码，j+1 个指针的结 点的一般形式为:

• 其中 Ki 是关键码值，K1<K2<…<Kj，
• Pi 是指向包括 Ki 到 Ki+1 之间的关键码的子树的指针。
• 还有指针吗?

2-3 树 = 3 阶 B 树 ( 阶应该 ≥ 𝟑 )

1.4 B 树的查找

• 交替的两步过程

1. 把根结点读出来，在根结点所包含的关键 码 K1，…，Kj 中查找给定的关键码值。找到则检索成功
2. 否则，确定要查的关键码值是在某个Ki和Ki+1 之间，于是取 pi 所指向的结点继续查找

• 如果pi 指向外部空结点，表示检索失败

1.5 B 树插入

注意保持性质，特别是等高和阶的限制

1. 找到最底层，插入
2. 若溢出，则结点分裂，中间关键码连同 新指针插入父结点
3. 若父结点也溢出，则继续 分裂。分裂过程可能传达到根结点(则树升高一层)

外部空结点(即失败检索)处在第 I 层的 B 树，插入的关键码总是在第 I-1 层

B 树操作的访外次数

1.6 B 树的删除

删除的关键码不在叶结点层，跟叶中后继对换

删除的关键码在叶结点层

• 删除后关键码个数不小于 m/2 -1 ,直接删除
• 关键码个数小于 m/2 -1
• 如果兄弟结点关键码个数不等于 m / 2 - 1 ，从兄弟结点移若干个关键码到该结点中来(父结点中 的一个关键码要做相应变化)
• 如果兄弟结点关键码个数等于 m / 2 - 1，合并

5 阶 B 树删除示例

二、 B 树的性能分析

思考

1. 是否存在符合定义的 2 阶 B 树?是否有实用价值?为什么?
2. B 树删除时使用先借用再合并的方法， 为何在插入的时候不使用先送给兄弟结点 再考虑分裂的方法?
3. B 树的定义中关于度数的定义为从𝑚/2到𝑚之间 ，是否可以调整为其他范围?

三、B+ 树

是B 树的一种变形，在叶结点上存储信息

• 所有的关键码均出现在叶结点上
• 各层结点中的关键码均是下一层相应结点中最大关键 码(或最小关键码)的复写

3.1 B+ 树的结构定义

m 阶 B+ 树的结构定义如下:

1. 每个结点至多有 m 个子结点
2. 每个结点(除根外)至少有 m/2 个子结点
3. 根结点至少有两个子结点
4. 有 k 个子结点 的结点必有 k 个关键码

3阶B+ 树的例子(一般阶 ≥ 3)

B+ 树的查找

• 在上层已找到待查的关键码，并不停止
• 而是继续沿指针向下一直查到叶结点层的这个关键码

3.2 B+ 树的插入

插入——分裂

• 过程和 B 树类似
• 注意保证上一层结点中有这两个结点的最大关键码 (或最小关键码)

3 阶 B+ 树插入15

3.3 B+ 树的删除

• 当关键码下溢出时，与左或右兄弟进行调整(甚至合并)
• 关键码在叶结点层删除后，其在上层的复本可以保留， 作为一个“分界关键码”存在
• 也可以替换为新的最大关键码(或最小关键码)

3.4 另一种 B+ 树

叶结点中关键码数目与非叶的不同

• 内部非叶结点构成 B 树
• 叶的阶与 B+ 树一致
• 例如，叶结点阶 5，内部阶 4

四、B 树 B+ 树性能比较

4.1 B+ 树的存储效率实际上更高

• 假设一个主文件有 N 个记录，假设一个页块可以存 m 个(关键码，子结点页块地址)二元对
• 假设 B+ 树平均每个结点有 0.75m 个子结点
• 充盈度为 (1+0.5)/2 = 75%

• 可以容纳 m 个(关键码，子结点页块指针) ，假设关键码所占字节数 不指针相同
• 可以容纳 B 树的(关键码，隐含指针，子结点页块指针)最多为2m/3 ( B 树为 0.67m 阶)。
• 假设 B 树充盈度也是 75%，则 B 树结点有 0.5m 个子结点

4.2 B+ 树应用得更为广泛

• B+ 树的存储效率更高、检索层次更少(树较矮)
• 因此，B+ 树应用得更为广泛
• 数据库系统主码(primary key)索引
• 基于B+树的磁盘文件虚拟存储存取管理 VSAM (Virtual Storage Access Method)，取代了基于多分树的 ISAM

VSAM 的组成

4.3 思考

1. 是否存在2阶B+ 树?
2. 为什么相比于 B+ 树，B 树存储效率低?
3. 查阅数据库的相关文献，看看 B+树的作用。

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾