【11.4】索引--动态索引

动态索引结构:

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

目的:

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

一、 B 树

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

1.1 m 阶 B 树的结构定义:

  1. 每个结点至多有 m 个子结点
  2. 除根结点和叶结点外,其它每个结点至少有 𝑚/2 个子结点
  3. 根结点至少有两个子结点
  • 唯一例外的是根结点就是叶结点时没有子结点
  • 此时 B 树只包含一个结点
  1. 所有的叶结点在同一层
  2. 有 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+树的作用。

参考资料

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

药企,独角兽,苏州。团队长期招人,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn