Skip to content

Chapter 11 索引

11.0 引言

  • 主码: 数据库中每条记录的唯一标识, 如身份证号码
  • 辅码: 数据库中可重复出现的值 (属性), 如姓名, 性别
    辅码索引将辅码值与具有这个辅码值的多条记录的主码值关联起来
  • 索引: 将关键码和对应记录位置关联起来的过程, (关键码,指针)对
  • 索引文件: 用于记录这种联系的文件
  • 稠密索引和稀疏索引:

11.1 线性索引

支持二分检索

线性索引太大, 存储在磁盘中, 一次检索可能多次访问磁盘, 影响效率, 使用二级线性索引.

按照磁盘块对一级索引分块.

二级索引往往存储在内存, 通常只需两次访问磁盘: 一次读入一级线性索引文件, 一次读入数据库记录.

11.2 静态索引

11.3 倒排索引

按属性值建立索引, 每个索引项包括一个属性值和具有该属性值的各关键码或记录地址

11.4 动态索引

  • 文件创建时生成
  • 结构随插入删除而改变
  • 目的是保持最佳的检索性能

11.4.1 B树

定义: \(m\) 阶 B-树是一棵 \(m\) 路查找树, 或者为空, 或者:

  • 上界: 树中每个结点至多有 \(m\) 个子结点
  • 下界: 根结点至少有两棵子树, 其它非叶子结点至少有 \(\lceil m/2 \rceil\) 棵子树
  • 有 \(k\) 棵子树的结点有 \(k-1\) 个关键码
  • 叶节点都位于同一层, 有 \(\lceil m/2 \rceil-1\) 到 \(m-1\) 个关键码

结点结构:

示例:

B树的查找

B树检索长度

自顶向下检索到叶节点需要 \(h\) 次读盘 (\(h\) 为高度), 根据指针获取数据还需要一次访外.

B树的插入

找到最底层插入, 若溢出则结点分裂, 中间关键码连同新指针插入父结点, 若父结点溢出则继续分裂(分裂可能传到根节点, 导致树升高一层)

访外次数

默认: 内存足够大, 检索时读入的结点在向上分裂时不必再从磁盘读入

  • 读盘次数与查找相同
  • 最少写盘次数: 一次(不分裂), 仅将插入关键码所在结点写到外存
  • 有结点分裂的情况下，插入操作最少写盘次数：只在最底层分裂一次，那么就是写3次：两个新结点，这两个结点的父结点。
  • 如考虑对主数据文件访问, 则再加一次

B树删除


合并: 将该节点，父亲节点的一个分隔键，兄弟节点合并成一个新节点，分割键左右的两个指针合并成指向新节点的一个新指针

11.4.2 B+树

在叶节点存储信息, 所有关键码均在叶节点, 各层结点中的关键码是下一层相应节点中最大关键码的复写

插入删除与 B 树类似

11.4.3 B树性能分析

包含 \(N\) 个关键码的 B 树有 \(N+1\) 个外部空指针

假设空指针数为 \(l\) , 节点数为 \(n\) , 关键码数为 \(N\)

边的总数为 \(l+n-1\)

\(n\) 个结点关键码个数分别为 \(x_1+x_2+...+x_n=N\), 每个结点发出的边数是关键码数+1, 因此

边的总数为 \(N+n\)

联立得 \(l=N+1\)

假设外部指针在第 \(k\) 层. 第 \(0\) 层根至少 \(1\) 个结点, 第 \(1\) 层至少 \(2\) 个结点, 第 \(2\) 层至少 \(2\cdot \lceil m/2 \rceil\) 个结点...

\[ N+1\geq2\cdot\lceil m/2\rceil^{k-1} \]

推出:

\[ k\leq1+\log_{\lceil m/2\rceil}(\frac{N+1}{2}) \]

检索效率:

  • 存取次数 \(k\leq1+\log_{\lceil m/2\rceil}(\frac{N+1}{2})\)
  • 结点分裂次数

11.5 红黑树


  • 红黑树是满二叉树: 空树叶也看成结点
  • \(k\) 阶红黑树的路径长度:
    从根到叶的简单路径长度, 介于 \([k,2k]\)
    也即树高介于 \([k+1,2k+1]\)
  • \(k\) 阶红黑树内部结点数:
    • 最少时是一棵完全满二叉树
    • \(2^k-1\)(全黑)
  • \(n\) 个内部结点红黑树最大高度: \(2\log_2(n+1)+1\)
    证明: 设红黑树阶为 \(k\), 高位 \(h\)
    则 \(h\leq 2k+1\), \(n\geq2^k-1\)
    故 \(h\leq 2\log_2(n+1)+1\)

11.5.1 红黑树的插入

先用普通二叉搜索树的方法插入, 将插入的 \(X\) 设为红色.

问题: \(X\) 的父亲可能也为红色, 造成红-红冲突

分情况讨论:

  • 如果 \(X\) 的父亲是黑色的, 直接插入
  • 如果 \(X\) 的父亲是红色的, 显然 \(X\) 的祖父是黑色的(否则红红)

Case1: 如果 \(X\) 的叔父(祖父相连的另一结点是红色的), 如图

通过将父亲和叔父变为黑色, 祖父变为红色, 继续从祖父开始向上迭代.

分析一下结点到黑色叶子结点路径长度相同的性质是否仍然满足, 对于\(A,D\) 子树, 没有新的黑色结点(注意秩的计算是不包括本身的), 因此无影响. 祖父的秩增加了 \(1\). 对于外部的结点, 由于这棵子树的黑色结点数量不改变(把原来的 C 换到了 AD) 因此性质仍然满足 .

Case 2: \(X\) 的叔父是黑色的, \(X\) 是右儿子, 左旋变为 Case 3

Case 3: \(X\) 的叔父是黑色的, \(X\) 是左儿子

思考: 红红的出现说明什么? 说明这条链太长了, 注意到是 LL 链所以可以右旋 \(C\) , 再将 B 染为黑色, C 染为红色

(有点像图的同构? 原来的 C-> B, 原来的 C 右边增加一个等高红结点)

11.5.2 红黑树的删除

BST的删除

  • 没有儿子, 直接删除
  • 有一个儿子, 用儿子替代
  • 有两个儿子, 找到右子树的最小节点(即从右子树根出发递归找左儿子), 用该节点替代, 再删除该节点 (该节点最多只有一个右儿子) (或者找左子树的最大节点)

红黑树的删除

与 BST 类似, 不过需要调整保证红黑树性质

  • 有两个儿子: 与右子树最小值交换数据(注意不用交换颜色, 红黑树的颜色是为了维持平衡的, 要把它和数据分开来看, 看作是数据填入树中) 转化为下述情况
  • 有一个儿子: 显然儿子结点为红色, 否则 \(X\) 到叶子结点的路径阶一个为 \(1\) 一个为 \(2\) , 由于红红限制 \(X\) 一定为黑色, 因此用儿子替换 \(X\) 然后染成黑色即可.
  • 没有儿子: 如果 \(X\) 是红色或根节点可以直接删除, 否则 \(X\) 为黑色, 需要分类讨论:

Case 1: \(X\) 的兄弟为红

想一想, \(X\) 要被删除了, 左边的黑色结点少了不平衡, 因此需要先左旋 B 然后重新染色保持红黑树性质.

转化为后面的 Case.

Case 2: \(X\) 的兄弟 \(W\) 为黑, \(W\) 的两个儿子也为黑. (注意空结点也是黑结点)

为了让左右黑色数量平衡, 将 \(D\) 染为红色, 这样两边都少了一个黑色结点, 如果 \(B\) 是红色, 那么将 \(B\) 染成黑色就可以使得子树外的结点到该子树的黑色结点树不变, 但是如果 \(B\) 是黑色的话, 这个子树就相当于少了一个黑色结点, 让 B 继续往上迭代. (我们要把删除看作子树少了一个黑色结点, 这种状态称为双黑, 是可以传递上去的)

Case 3: \(X\) 的兄弟 \(W\) 为黑, \(W\) 的左儿子为红, 右儿子为黑.

为了方便, 我们旋转一下统一到 Case 4

Case 4: \(X\) 的兄弟 \(W\) 为黑, \(W\) 的右儿子为红, 无论左儿子颜色

为了保持平衡, 我们要把树往左转一转(因为左边比较矮), 你应该注意到 A 删除完后和 C 的阶是一样的(本来应该要跟 D 一样, 删除后少了一个跟 C 一样), 这时候左右就都少了 1 了, 然后把 B, E 染成黑色, 恢复原状. D 要改成跟 B 一样的颜色保证外部子树到这里面的黑色结点数不变

删除的时候只有 Case 2 至多迭代 log 次

11.5.3 总结

一个思想: 哪里不平衡往哪里转

一个套路: 尽量把对称的情况全部转化为同一个情况, 减少讨论复杂度

插入: 看父亲和叔父脸色, 删除: 看兄弟和兄弟的孩子脸色