跳转至

Chapter 10 Indexing

文本统计：约 2976 个字

参考

索引 - Zhroyn 的学习笔记

10.1 Basic Concepts

索引是数据库用来提高查询效率的一种机制，可以根据指定数据快速定位到记录。

搜索键 (Search Key) 是用来在文件中查找记录的数据，由单个或多个列组合而成。

索引文件中的记录 (record) 只由搜索键和指向包含该搜索键的记录的指针组成，所以索引文件一般远小于原始数据文件。

索引可以分为两种基本类型：

  • 有序索引 (Ordered Index)：索引项按搜索键值排序存储
  • 哈希索引 (Hash Index)：搜索键按照哈希函数均匀分布

查询也可以分为两种类型：

  • 精确查询 (Point Query)：查询特定值的记录
  • 范围查询 (Range Query)：查询特定范围内的记录

索引的指标有访问时间 (Access Time)、插入时间 (Insertion Time)、删除时间 (Deletion Time) 和空间开销 (Space Overhead) 等。

有序索引可以分为两种类型：

  • 主索引 (Primary index)：搜索键在索引中的顺序与文件中相同，也称为聚集索引 (Clustering index)。主索引的搜索键通常是主键【非必要】，带有主索引的有序顺序文件也被称为索引顺序文件 (Index-sequential file)

  • 辅助索引 (Secondary index)：搜索键在索引中的顺序与文件中不同，也称为非聚集索引 (Non-clustering index)

索引还可以分为稠密索引和稀疏索引两种类型：

  • 稠密索引 (Dense index)：数据文件中的每个搜索键值都有一个对应的索引记录 Index record appears for every search-key value in the file.

  • 稀疏索引 (Sparse index)：索引记录仅包含部分搜索键值，适用于文件记录按搜索键顺序排列的情况，可以通过先找到最接近的索引项再顺序查找的方法来检索，相比于稠密索引，它所占空间更少，然后维护成本更低，但是要比稠密索引来的慢。稀疏索引可以选择链接每个block中最小的 search-key

Note

Sparse indexes（稀疏索引）通常只能用于 clustered indexes（聚集索引），不能用于 secondary indexes（二级索引）。

多级索引 (Multilevel Index)：当主索引过大而放不进内存时，可以在主索引上再建立一层稀疏索引，称为 outer index，而将主索引作为顺序文件存入磁盘中，称为 inner index。如果此时 outer index 还是过大，还可以继续建立分级。

10.2 B+ -Tree

10.2.1 B+ -Tree Index

顺序索引文件的缺点：

  • 性能随文件增长而下降：随着文件的增长，会创建许多溢出块，这会导致性能下降。

  • 需要定期重组整个文件：为了保持性能，必须定期对整个文件进行重组。

B+树索引文件的优点：

  • 自动局部重组：在插入和删除操作时，B+树能够通过小范围、局部的变化自动重组自身，以应对数据变化。

  • 无需重组整个文件：为了维持性能，不需要对整个文件进行重组。

B+树的（次要）缺点：

  • 额外的插入和删除开销：与顺序索引文件相比，B+树在插入和删除操作时会有额外的开销。

  • 空间开销：B+树可能会占用更多的存储空间。

B+ 树有如下性质：

  • 从根节点到叶子节点的路径长度相同
  • 不是根节点的内部节点有 \(\lceil n/2\rceil\) 到 \(n\) 个子节点， 如果根节点不是叶子节点，则至少有两个子节点
  • 不是根节点的叶子节点有 \(\lceil (n-1)/2\rceil\) 到 \(n-1\) 个值，如果根节点是叶子节点，则有 \(0\) 到 \(n−1\) 个值

一个满的节点的结构如下所示：

有 \(n−1\)个搜索键值 \(K_i\)，以及 \(n\) 个指向子树的指针 \(P_i\) ，其中 \(K_1<K_2<⋯<K_{n−1}\)。

对于叶子节点来说：

  • \(P_i\) 指向键值为 \(K_i\) 的文件记录
  • \(P_n\) 指向下一个叶子节点。

对于内部节点来说：

  • \(P_1\) 指向所有键值都小于 \(K_1\) 的子树
  • \(P_i(2≤i≤n−1)\) 指向所有键值大于等于 \(K_{i−1}\) 且小于 \(K_i\) 的子树
  • \(P_n\) 指向所有键值大于等于 \(K_{n−1}\) 的子树

由 B+ 树的性质可得，两层最少有 \(2×⌈n/2⌉\) 个值，三层最少有 \(2×⌈n/2⌉×⌈n/2⌉\) 个值，等等。因此，有 \(K\) 个搜索键的 B+ 树的高度不会超过 \(⌈\log⁡⌈n/2⌉(K/2)⌉+1\)，约等于 \(⌈\log⁡⌈n/2⌉(K)⌉\)。

B+树的高度和大小估计

定义 person 表：

person( pid     char(18) primary key,
        name    char(8),
        age     smallint,
        address char(40) );

此外设块大小为 4KB，共有 100 万条记录。

由表的定义可得，每个记录的大小为 \(18+8+2+40=68\) 字节，每个块可以存储 ⌊4096/68⌋=60⌊4096/68⌋=60 条记录，100 万条记录需要 \(1000000/60=16667\) 个块。

搜索键的大小为 18 字节，指针的大小为 4 字节，一个节点的大小为 4KB，因此扇出率 (fan-out) 为 \(n=⌊(4096−4)/(18+4)+1⌋=187\)，内部节点可以指向 94-187 个子节点，叶子可以存储 93-186 个搜索键。

Indexing in Main Memory

从而可得，不同高度的 B+ 树的搜索键数量范围为：

  • 2 levels: \(\min⁡=2∗93,\max⁡=187∗186\)
  • 3 levels: \(\min⁡=2∗94∗93,\max⁡=187∗187∗186\)
  • 4 levels: \(\min⁡=2∗94∗94∗93,\max⁡=187∗187∗187∗186\)

对于节点中 search-key 的查找，我们一般采用二分查找，但是读入cache的数据有用的仅仅只是 search-key，这样很多数据是无效的，这对CPU来说并不友好，可以对其采用一个微结构，可以在这个节点中增加一个小节点，这样可以优化 cache access

10.2.2 B+-Tree Update

【这个部分在ADS中也有详细阐述】

插入的步骤是：

  1. 找到搜索键应该所在的叶子节点，插入该叶子节点
  2. 如果叶子节点的搜索键数量超过 \(n−1\)，则分裂该节点，将前 \(⌈n/2⌉\) 个值留在原节点中，剩余的值放入新节点，再将新节点插入父节点
  3. 如果父节点的搜索键数量超过 \(n−1\)，则递归分裂父节点，直到根节点

删除的步骤是：

  1. 找到搜索键所在的叶子节点，删除指定的键值对
  2. 如果删除后节点内的项过少，则需要根据兄弟节点的情况进行调整：
  • 如果兄弟节点的项和该节点能够合并，则合并进一个节点 (merge siblings)，然后删除另一个节点
  • 如果兄弟节点的项也较多，则从兄弟节点借一个项 (redistribute pointers)，然后更新父节点的搜索键
  1. 如果删除后根节点只剩一个子节点，则将该子节点作为新的根节点

10.2.3 B+-Tree File Organization

B+-Tree File Organization:

  • Leaf nodes in a B+-tree file organization store records, instead of pointers 叶子节点存储记录而不是指针
  • Helps keep data records clustered even when there are insertions/deletions/updates

Leaf nodes are still required to be half full, Since records are larger than pointers, the maximum number of records that can be stored in a leaf node is less than the number of pointers in a non-leaf node.

To improve space utilization, involve more sibling nodes in redistribution during splits and merges, e.g. Involving 2 siblings in redistribution (to avoid split / merge where possible) results in each node having at least \(\lfloor2n/3\rfloor\) entries

Warning

If a record moves, all secondary indices that store record pointers have to be updated. Node splits in B+-tree file organizations become very expensive.

Solution: use primary-index search key instead of record pointer in secondary index

  • Extra traversal of primary index to locate record

10.2.4 Bulk Loading and Bottom-Up Build

当需要批量加载条目时，直接逐个插入的操作非常低效，此时有两种替代方法：

  • 顺序插入：先将所有条目按照搜索键排序，然后顺序插入 B+ 树中，这样不会频繁切换块，插入后大多数叶子节点是半满的
  • 自底向上构建：先将所有条目按照搜索键排序，然后逐层向上构建 B+ 树，写入磁盘的过程可以同时进行，预计代价只有一次 seek 加上与结果块个数相同的 block transfer，写出去是顺序写的

当需要批量插入条目时，也可以自底向上构建：先将插入条目按照搜索键排序，与原 B+ 树的底层叶子节点合并，然后再逐层向上构建新的 B+ 树。这样预计代价只有两次 seek 加上与结果块个数相同的 block transfer。

Example

Bottom-up B+-tree construction：

排序的过程可以使用外排序【ADS中也有提及】

Bulk insert index entries 干脆将这次批量插入的部分与原来的数据进行归并

10.3 Write Optimized Indices

10.3.1 LSM Tree

B+ 树在面对写密集型任务时表现不太理想，因此这里介绍一种可以降低写代价的 LSM tree (Log-Structured Merge Tree)。

在 LSM tree 中，数据被分为多个层级，每个层级都是一个有序的 B+ 树。当写入数据时，首先将数据写入内存中的 \(L_0\) 树，当 \(L_0\) 满了之后，会使用自底向上构建的方法将其合并到磁盘上的 \(L_1\) 树中，当 \(L_1\) 满了之后，会继续合并到 \(L_2\) 树中，以此类推。每一层的阈值呈倍数增长。

LSM tree 的优点是：

  • 插入只需要使用顺序 I/O，因此写入速度很快
  • 叶子节点大多是满的，因此避免了空间浪费
  • 与普通 B+ 树相比，降低了每次插入的 I/O 次数

LSM tree 的缺点是：

  • 查询时可能需要查找多个层级，因此查询速度较慢
  • 相同的数据可能会出现在多个层级中，占用了更多的空间

LSM tree 的变体是 Stepped-­merge index，它在磁盘上每层最多可以容纳 \(k\) 个树，当一层有了 \(k\) 个树后，就会将它们合并为下一层树。与普通的 LSM tree 相比，它的写入代价更低，但查询代价也更高了。

对查找的优化

Compute Bloom filter for each tree and store in-memory，Query a tree only if Bloom filter returns a positive result

利用k个哈希函数，将相应的k个位置置1，后续查询该值是否存在的时候，计算出k个哈希位置，检查是否都为1。成立不代表一定可以查到，但是不成立就一定查不到

当需要删除条目时，LSM 的做法是插入一条说明它被删除的条目。这样以后，每次查询条目时，还必须要确保没有对应删除条目存在才能返回。在合并时，如果遇到删除条目和原条目同时存在，就将它们同时删去。

LSM tree 最初作为 disk-based indices 被引入，但对减少 flash-based indices 的擦除也很有帮助。

10.3.2 Buffer Tree

Buffer tree 会将 B+ tree 的内部节点中的一定位置留空作为 buffer，插入时会先将记录存储在 buffer 中，等到 buffer 满了以后，再将记录批量移动到下一层节点，可以用于任意树索引结构。

Buffer tree 可以减少查询的开销，但是相比 LSM tree，会有更多的随机 I/O。

10.3.3 Bitmap Indices

位图索引适用于记录数目固定，待查询属性的取值较少的情况。

设一个位图索引的键是属性 \(A\)，则它对该属性的取值 \(v\) 的位图就是一串定长的二进制码，其中 1 代表在对应的记录中该属性的值等于 \(v\)，0 代表不等于。【也就是说位图是针对与取值的，长度与记录的数目相同】

当使用 Bitmap indices 时，对于多属性查询，只需要对 bitmap 使用按位与、或即可很快地得到结果，bitmap 所占空间也极小。

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！