索引¶

基本概念¶

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

搜索键 (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)：数据文件中的每个搜索键值都有一个对应的索引记录
稀疏索引 (Sparse index)：索引记录仅包含部分搜索键值，适用于文件记录按搜索键顺序排列的情况，可以通过先找到最接近的索引项再顺序查找的方法来检索

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

B+ 树索引¶

B+ 树的查询¶

B+ 树有如下性质：

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

B+ 树中的每个节点都有 \(n - 1\) 个搜索键值 \(K_i\)，以及 \(n\) 个指向子树的指针 \(P_i\)，其中 \(K_1 < K_2 < \cdots < K_{n-1}\)。

对于叶子节点来说：

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

对于内部节点来说：

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

由 B+ 树的性质可得，两层最少有 \(2 \times \lceil n/2 \rceil\) 个值，三层最少有 \(2 \times \lceil n/2 \rceil \times \lceil n/2 \rceil\) 个值，等等。因此，有 \(K\) 个搜索键的 B+ 树的高度不会超过 \(\lceil \log_{ \lceil n/2 \rceil}(K/2) \rceil + 1\)，约等于 \(\lceil \log_{ \lceil n/2 \rceil}(K) \rceil\)。

B+ 树的高度和大小估计

定义 person 表：

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

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

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

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

从而可得，不同高度的 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\)

B+ 树的更新¶

插入的步骤是：

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

删除的步骤是：

找到搜索键所在的叶子节点，删除指定的键值对
如果删除后节点内的项过少，则需要根据兄弟节点的情况进行调整：

如果兄弟节点的项和该节点能够合并，则合并进一个节点 (merge siblings)，然后删除另一个节点
如果兄弟节点的项也较多，则从兄弟节点借一个项 (redistribute pointers)，然后更新父节点的搜索键

如果删除后根节点只剩一个子节点，则将该子节点作为新的根节点

B+ 树的构建¶

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

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

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

写优化索引¶

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 相比，它的写入代价更低，但查询代价也更高了。

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

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

Buffer Tree¶

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

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

Bitmap Indices¶

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

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

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