跳转至

Chapter 10 : Indexing

约 2693 个字 7 行代码 12 张图片 预计阅读时间 14 分钟

数据库系统中的索引（Indices）在数据库的高效查询上起到十分关键的作用，否则的话每次查询都要读取涉及到的关系内的全部内容，这样就会产生过多的开销。我们会用到以下两类基本的索引：

  • 顺序索引（Ordered Indices）：基于排序后的值
  • 哈希索引（Hash Indices）：基于值在一些桶（Buckets）里的均匀分布，值被分配到的桶是由哈希函数决定的

我们可以用以下指标来衡量这些方法：

  • 访问类型：包括寻找带有指定属性，或者指定属性值范围的记录
  • 访问时间：寻找单个或多个数据项所需的时间
  • 插入时间：包括寻找新数据插入的正确位置，以及更新索引结构所需的时间
  • 删除时间：包括寻找要被删除的数据项，以及更新索引结构所需的时间
  • 空间开销：索引结构占据的额外空间，假如该空间不大的话，那么值得用这点空间换取性能的提升

单个或多个用于查找文件内记录的属性被称为搜索键（Search Key），每一个索引对应一个特定的搜索键

Ordered Indices

顺序索引（Ordered Indices）按排好的顺序存储搜索键的值，并和每个被记录包含的搜索键关联起来。而这些记录也有可能是按顺序排序的。如果是由搜索键定义文件内的顺序的话，那么称对应的索引为聚集索引（Clustering Index) 或主索引（Primary Index），而对应的文件被称为索引顺序文件（Index-Sequential Files）

通常，聚集索引的搜索键是一个主键（但也可能不是）。而对于搜索键顺序和文件内顺序不同的索引，我们称之为非聚集索引（Nonclustering Index）或辅助索引（Secondary Index）

Dense Index Files

稠密索引（Dense Index）指的是对于文件内的每个搜索键值都有对应的索引项

  • 在稠密聚集索引里，索引记录包含了搜索键值和指向第一条带有该搜索键值的记录的指针，而其余具有相同搜索键值的记录就按顺序排在这第一条记录的后面
  • 在稠密非聚集索引里，索引必须将全部指向带有相同搜索键值的记录的指针存储在列表里

Sparse Index Files

稀疏索引（Sparse Index）指的是索引文件里只有部分搜索键值有对应的索引项

  • 此时只允许聚集索引
  • 每个索引项包含了搜索键值和指向第一条带有该搜索键值的记录的指针
  • 为了找到记录，就要找到小于等于我们要找的搜索键值中最大的搜索键值对应的索引项。然后从这条记录出发，顺着指针在文件中寻找，直到找到想要的记录

这种设计中，处理数据库请求的主要成本是将数据块从硬盘带到主存所需的时间。如果索引小到能够放入主存的话，那么搜索的时间就会降低不少

Multilevel Index

当索引数量很大的时候，查找索引的过程就特别耗时间。为了解决这个问题，我们可以将索引看作文件中的记录，然后为这个索引构建一个稀疏索引。其中原来的索引称为内部索引，而新构建的索引称为外部索引，如下所示：

要找到某条记录，我们现在外层索引上使用二分查找，找到不超过该记录的搜索键值的最大搜索键值对应的记录，对应有一个指向内部索引块的指针。然后在这个内部索引块内找到不超过该记录的搜索键值的最大搜索键值对应的记录，对应有一个指向文件块的指针，这个文件块包含了我们想要寻找的记录。

当索引变得很大很大时，我们可以使用更多级的索引，这称为多级索引（Multilevel Indices）。相比只用二分查找而言，在多级索引上寻找记录能够显著减少 I/O 操作

B+ Tree Index

索引顺序文件组织的主要缺点是：随着文件规模的增长，索引查找和数据顺序扫描的性能会下降。尽管可通过对文件的重新组织来解决这一问题，但是频繁的重复组织是不能被接受的。因此，我们转而采用 B+ 树这一被广泛使用的索引结构，它能够保证在插入和删除数据的情况下仍然能维持效率

B+ 树我们在 ADS 当中也有所涉及，基本定义也大致相同（除了叶子节点的个数有一些不同），复杂度分析也可以见 ADS 笔记

B+ Tree Node Structures

B+ 树的节点结构有 \(n−1\) 个搜索键值 \(K_1,K_2,\cdots,K_{n−1}\)，以及 \(n\) 个指针 \(P_1,P_2,\cdots,P_n\)，且搜索键值是排好序的，即对于 \(i<j\)，有 \(K_i<K_j\)（如果有重复键就是 \(K_i\leq K_j\)）成立

  • 叶子节点（Leaf Node）：对于 \(i=1,\cdots,n−1\)，\(P_i\) 指向搜索键值为 \(K_i\) 的文件记录；而 \(P_n\) 指向下一个叶子节点，以实现高效的顺序文件处理。叶子节点至少有 \(\lceil \frac{n−1}{2}\rceil\) 个值

    • 对于叶子节点 \(L_i,L_j(i<j)\)（即 \(L_i\) 在 \(L_j\) 的左边），\(L_i\) 内的每一个搜索键值 \(v_i​\) 均比 \(L_j\) 内的每一个搜索键值 \(v_j\)​ 小

  • 非叶子节点（Nonleaf Nodes）（有时也称为内部节点（Internal Nodes））构成了叶子节点的多级（稀疏）索引

    • 非叶子节点的结构和叶子节点的类似，只是它的指针指向的都是树里的节点
    • 每个非叶子节点（不包括根节点）的孩子数量的范围为 \([\lceil\frac{n}{2}\rceil,n]\)，而根节点孩子数量的范围为 \([2,n]\)
    • 节点的指针数称为扇出（Fanout）
    • 假如某个节点包含 \(m(m\leq n)\) 个指针，指针 \(P_i\) 指向搜索键值比 \(K_i\)​ 小而且不小于 \(K_{i−1}\) 的子树；指针 \(P_m\) 指向搜索键值不小于 \(K_{m−1}\) 的子树；指针 \(P_1\)​ 指向搜索键值比 \(K_1\)​ 小的子树

B+ Tree File Organization

索引顺序文件组织的主要缺点就是随文件规模增长，性能不断降低。因此，我们将 B+ 树直接作用在文件上来解决这一问题。具体来说，就是将文件中的真实记录存储在 B+ 树的叶子节点上，我们称这样的文件组织为 B+ 树文件组织。由于记录通常比指针大，因此能被存储在叶子节点内的记录的最大数量比非叶子节点的指针数量更少；可即便如此，我们仍然要求叶子节点有一半内容是满的。一种 B+ 树文件组织如下所示：

在使用 B+ 树文件组织时，空间利用尤为重要，因为一条记录占据的空间远比一个搜索键或指针来的大。我们可以通过在分裂或合并时的重分配（Redistribution）操作中考虑更多的兄弟节点来提升空间的利用，这种方法在叶子节点和非叶子节点上均可行。总的来说，如果在重分配时考虑到 \(m\) 个节点（\(m−1\) 个兄弟节点），那么每个节点确保获得至少 \(\lfloor \frac{(m−1)n}{m}\rfloor\)个项。然而，考虑更多节点会让更新成本变得更高

Other Issues in Indexing

对于 B+ 树这样的文件组织，有时会遇到即使没有更新记录内容，也会导致记录位置被改变的情况。比如 B+ 树的某个叶子节点发生分裂了，那么就会有一些记录被移动到新的节点上，这时所有存储指向这些被移动过的记录的指针的二级索引就要被更新，即使它们对应的记录内容没有发生改变，而这会带来较大的开销

为了解决这一问题，在二级索引中，我们不再存储指向这些被索引记录的指针，而是存储一级索引的搜索键属性（就是说上层的索引不要存最底层的记录，只要存下一层的索引就行了）。虽然这样会让访问成本更高（需要额外的步骤），但是这能减少文件重组织的成本

Indexing Strings

为字符串属性创建 B+ 树索引可能会出现字符串可能会很长，导致节点的低扇出，从而让 B+ 树变得很高的问题。我们可以通过前缀压缩（Prefix Compression）（仅存储搜索键值的前缀部分，但足以区分搜索键值）提升扇出

Bulk Loading and Bottom-Up Build

批量加载（Bulk Loading）是指一次向索引插入多个项的操作。一种实现方法是：

  • 创建一个包含关系中的索引项的临时文件
  • 然后按搜索键为文件内容排序（后面会介绍一些高效的排序算法）
    • 这样做的好处是：如果按排好的顺序插入项的话，那么这些项也是连续进入某个节点的，那么只需要向该节点写入一次即可
    • 如果 B+ 树是空的话，那么所有节点仅需一次写入即可。具体来说，可通过自底向上（Bottom-Up）的 B+ 树构造实现更快的构造。大多数数据库系统都会用到排序和自底向上构造的技术
  • 扫描排好序的文件，将项插入到索引中

Bottom-Up B+ Tree Build

  • 首先对索引条目进行排序
  • 然后从叶子层开始逐层创建 B+ 树
  • 构建的 B+ 树使用顺序 I/O 操作写入磁盘

Example

我们假设我们有一个扇出为 4，条目分别为 23, 25, 27, 29, 1, 5, 7, 9, 11, 31, 37, 41, 45, 15, 17, 19 的 B+ 树，构建过程如下：

然后我们插入 21, 33, 35, 39, 43, 47, 49, 3, 13：

Multiple-Key Access

前面讲到的搜索键大多是由单个属性构成的，而对于由多个属性构成的搜索键，我们称为复合搜索键（Composite Search Keys）。假如对属性 \(A_1,\cdots,A_n\) 索引，那么搜索键值可以被表示为 \((a_1,\cdots,a_n)\) 的元组形式。此时搜索键值的顺序遵循词典序（Lexicographic Ordering）

对于某些查询，使用复合搜索键构成的索引能够提升查询效率。比如对于以下查询：

1
2
select ID from instructor
where dept_name = 'Finance' and salary = 80000;

我们创建复合搜索键 \((\text{dept\_name},\text{salary})\)，并在其基础上建立起有序索引（比如 B+ 树索引），从而实现高效的查找

实际上，上述复合搜索键还适用一个为相等条件，一个为范围条件的查询，以及单属性的查询，比如：

1
2
3
4
5
select ID from instructor
where dept_name = 'Finance' and salary < 80000;

select ID from instructor
where dept_name = 'Finance';

但是这种搜索键不适用于两个属性均为范围条件的查询，这是因为满足条件的这些记录可能位于不同的硬盘块内，而文件内的记录是有序的，因此会带来很多的 I/O 操作

Write Optimized Indices

B+ 树索引结构的一大缺点是随机的写操作对性能带来了负面影响。在 SSD 上，虽然随机 I/O 操作相当快，但写操作的成本还是很大。因此，我们需要写优化的索引结构，来处理高写入 / 插入率带来的工作量，我们下面介绍两种方式：LSM 树和缓冲树

LSM Trees

LSM 树，全称日志结构合并树（Log-Structured Merge Tree），是由多棵 B+ 树构成的，包括一棵在内存里的树 \(L_0\)，以及在硬盘里的树 \(L_1,L_2,\cdots,L_k\) 构成的，其中 \(k\) 称为层级。下图展示了 \(k=3\) 时的 LSM 树：

  • 索引的查找过程为：先对每棵树进行单独的查找操作，然后合并查找结果。

  • 向 LSM 树插入一条记录时，

    • 首先将该记录插入到在内存中的 \(L_0\)（系统为其分配了相当大的内存空间）。如果内存空间已满的话，那么就要将数据从内存移到硬盘里的 B+ 树上
    • 具体来说，如果 \(L_1\)​ 是空的话，那么就将整个 \(L_0\)​ 写入到 \(L_1\)​ 上；否则的话，按键的升序扫描 \(L_0\)​ 的叶子层级，然后将里面的项和 \(L_1\)​ 的叶子层级里的项合并起来（同样需要扫描）。然后用自底向上的构建方法，根据合并后的项来创建新的 B+ 树，用这棵新的树替代旧的 \(L_1​\)
    • 上述方法的好处是能确保新树的叶子节点是顺序定位的，以避免随机 I/O 操作；同时确保叶子是满的，减少了空间开销。

    • 但拷贝树需要不小的成本，我们有如下办法：

      • 使用多级树，其中树 \(L_{i+1}\)​ 的最大容量是 \(L_i\) 的 \(k\) 倍，因此每个记录之多被写入 \(k\) 次。级数和 \(\log_⁡k(I/M)\) 成正比，其中 \(I\) 是总项数，\(M\) 是 \(L_0\)​ 的项数
      • 除了 \(L_0\)​ 外，每级树都有至多 \(b\) 棵树（原来只有 1 棵树），这种变体称为按步合并索引（Stepped-Merge Index），它能够显著降低插入成本，但增加了查询成本

  • 删除操作中除了找到并删除索引项外，还要插入一个删除项（Deletion Entry），用于表明哪个索引项被删掉了。插入删除项的过程和插入一个普通索引项的过程是相同的

    • 所以查找操作就要多出一步了：如果某些项存在删除项，那么在查找指定搜索键时需要同时找到原来的索引项以及删除项。如果发现删除项的话，那么就不返回原来的索引项
  • 更新操作和删除类似，也要插入一个更新项。更新在合并操作中完成

Buffer Trees

缓冲区树是在 B+ 树的基础上，让每个内部节点（包括根节点）都有一个关联的缓冲区。节点的结构如下所示：

  • 插入：
    • 在插入索引记录时，不是先遍历叶子节点，而是先将其插入到根节点的缓冲区中
    • 如果缓冲区满了的话，那么缓冲区内的每个索引记录被推向下一级合适的孩子节点的缓冲区内，以此类推
    • 在被向下推之前，所有在缓冲区内的记录都是按搜索键排好序的
    • 如果下一级节点是叶子节点的话，那么索引记录就按正常方法插入到叶子节点中就行了
    • 如果叶子节点满了的话就执行分裂操作，此时有可能会让内部节点分裂，对应的缓冲区同样需要分裂
  • 查找：
    • 相比普通的 B+ 树查找，多了这样一步：在遍历内部节点时，检查一下结点的缓冲区内是否有要查找的搜索键值
    • 范围查找同样适用
  • 删除和更新：
    • 和 LSM 树类似，也要插入删除项和更新项
    • 也可以使用一般的 B+ 树算法，但这样会带来更大的 I/O 成本

在最坏情况下，缓冲区树在 I/O 运算次数的上界会比 LSM 树更低。且对于读操作而言，缓冲区树会比 LSM 树快不少。然而对于写操作而言，缓冲区树的表现更差，因为它要求更多的随机 I/O，因此花费更多的寻道时间。因此当写操作更多时，优先使用 LSM 树；当读操作更多时，优先使用缓冲区树

Bitmap Indices

位图索引（Bitmap Indices）是一类适用于对多个键的简单查询的索引。在使用位图索引前，需要为关系中的每条记录标号（从 0 开始）。如果记录的大小固定，且被分配在某个文件内的连续块上，这一操作还是很容易的，此时记录编号就可以被转换为块编号。

位图（Bitmap）就是一组位，对于关系 \(r\) 的属性 \(A\)，位图索引包含了 \(A\) 可取的每个值，而位的数量对应记录的数量。对于某个值 \(v_j\)​ 的位图，如果编号为 \(i\) 的记录的属性值为 \(v_j\)​，那么该位图的第 \(i\) 位置 1，否则置 0

评论