一文了解数据库索引：哈希、B-Tree 与 LSM

本文节选自 深入浅出分布式基础架构-数据库篇 https://url.wx-coder.cn/kl3ms 。

数据库索引

索引（Index）是帮助数据库系统高效获取数据的数据结构，数据库索引本质上是以增加额外的写操作与用于维护索引数据结构的存储空间为代价的用于提升数据库中数据检索效率的数据结构。索引可以帮助我们快速地定位到数据而不需要每次搜索的时候都遍历数据库中的每一行。典型的索引譬如在内存中维护一个二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 O(log2n)的复杂度内获取到相应数据。

左侧为数据记录的物理地址，右侧为查找树，需要注意的是，逻辑上相邻的记录在磁盘上也并不是一定物理相邻的。实际的数据库应用中我们往往使用 B+ 树或者 LSM 来替代二叉查找树或者红黑树来构建索引系统，并且充分利用 虚拟存储管理 https://url.wx-coder.cn/PeNqS 一节中介绍过的局部性原理、磁盘预读与页缓存等概念。

值得一提的是，本节并未涵盖搜索引擎中常用的与文本索引相关的技术，譬如倒排索引、TF-IDF 等，如果有兴趣可以参考本篇 搜索引擎 https://url.wx-coder.cn/O07eI 一章。

存储管理基础

本部分节选自 深入浅出 Linux 操作系统 https://url.wx-coder.cn/Q0AmI 。

计算机存储设备可被粗略分为内存储器（Main Memory）与外存储器（External Memory）两大类，内存存取速度快，但容量小，价格昂贵，而且不能长期保存数据，在不通电情况下数据会消失；外存储器存取速度相对较慢，却可以吃持久化存储。如果进行更加细致地划分，每个计算机系统中的存储设备都被组织成了一个存储器层次结构，在这个层次结构中，从上至下，设备变得访问速度越来越慢、容量越来越大，并且每字节的造价也越来越便宜。

存储器层次结构的主要思想是一层上的存储器作为低一层存储器的高速缓存。因此，寄存器文件就是 L1 的高速缓存，L1 是 L2 的高速缓存，L2 是 L3 的高速缓存，L3 是主存的高速缓存，而主存又是磁盘的高速缓存。在某些具有分布式文件系统的网络系统中，本地磁盘就是存储在其他系统中磁盘上的数据的高速缓存。

主存

主存是一个临时存储设备，在处理器执行程序时，用来存放程序和程序处理的数据。从物理上来说，主存是由一组动态随机存取存储器（DRAM）芯片组成的。从逻辑上来说，存储器是一个线性的字节数组，每个字节都有其唯一的地址（即数组索引），这些地址是从零开始的。一般来说，组成程序的每条机器指令都由不同数量的字节构成。

现代 DRAM 的结构和存取原理比较复杂，这里抽象出一个十分简单的存取模型来说明 DRAM 的工作原理。从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取 A0 再取 A1 和先取 A0 再取 D3 的时间消耗是一样的。

寄存器与高速缓存

寄存器文件在层次结构中位于最顶部，也就是第 0 级或记为 L0。一个典型的寄存器文件只存储几百字节的信息，而主存里可存放几十亿字节。然而，处理器从寄存器文件中读数据的速度比从主存中读取几乎要快 100 倍。针对这种处理器与主存之间的差异，系统设计者采用了更小、更快的存储设备，即高速缓存存储器（简称高速缓存），作为暂时的集结区域，用来存放处理器近期可能会需要的信息。

L1 和 L2 高速缓存是用一种叫做静态随机访问存储器（SRAM）的硬件技术实现的。比较新的、处理能力更强大的系统甚至有三级高速缓存：L1、L2 和 L3。系统可以获得一个很大的存储器，同时访问速度也很快，原因是利用了高速缓存的局部性原理，即程序具有访问局部区域里的数据和代码的趋势。通过让高速缓存里存放可能经常访问的数据的方法，大部分的存储器操作都能在快速的高速缓存中完成。

磁盘

磁盘是一种直接存取的存储设备 (DASD)。它是以存取时间变化不大为特征的。可以直接存取任何字符组，且容量大、速度较其它外存设备更快。磁盘是一个扁平的圆盘(与电唱机的唱片类似)，盘面上有许多称为磁道的圆圈，数据就记录在这些磁道上。磁盘可以是单片的，也可以是由若干盘片组成的盘组，每一盘片上有两个面。如下图中所示的 6 片盘组为例，除去最顶端和最底端的外侧面不存储数据之外，一共有 10 个面可以用来保存信息。

当磁盘驱动器执行读 / 写功能时。盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读 / 写头 ( 又叫磁头 ) 下通过时，就可以进行数据的读 / 写了。一般磁盘分为固定头盘 ( 磁头固定 ) 和活动头盘。固定头盘的每一个磁道上都有独立的磁头，它是固定不动的，专门负责这一磁道上数据的读 / 写。活动头盘 ( 如上图 ) 的磁头是可移动的。每一个盘面上只有一个磁头 ( 磁头是双向的，因此正反盘面都能读写 )。它可以从该面的一个磁道移动到另一个磁道。所有磁头都装 在同一个动臂上，因此不同盘面上的所有磁头都是同时移动的 ( 行动整齐划一 )。当盘片绕主轴旋转的时候，磁头与旋转的盘片形成一个圆柱体。各个盘面上半径相 同的磁道组成了一个圆柱面，我们称为柱面。因此，柱面的个数也就是盘面上的磁道数。

磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号 ( 磁道上的盘块 )。读 / 写磁盘上某一指定数据需要下面 3 个步骤: (1) 首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称为定位或查找。 (2) 如上图 11.3 中所示的 6 盘组示意图中，所有磁头都定位到了 10 个盘面的 10 条磁道上 ( 磁头都是双向的 )。这时根据盘面号来确定指定盘面上的磁道。 (3) 盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下。经过上面三个步骤，指定数据的存储位置就被找到。这时就可以开始读 / 写操作了。访问某一具体信息，由 3 部分时间组成：

• 查找时间 (seek time) Ts: 完成上述步骤 (1) 所需要的时间。这部分时间代价最高，最大可达到 0.1s 左右。
• 等待时间 (latency time) Tl: 完成上述步骤 (3) 所需要的时间。由于盘片绕主轴旋转速度很快，一般为 7200 转 / 分 ( 电脑硬盘的性能指标之一 , 家用的普通硬盘的转速一般有 5400rpm( 笔记本 )、7200rpm 几种 )。因此一般旋转一圈大约 0.0083s。
• 传输时间 (transmission time) Tt: 数据通过系统总线传送到内存的时间，一般传输一个字节 (byte) 大概 0.02us=2*10^(-8)s

磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘 IO 代价主要花费在查找时间 Ts 上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间 Ts 。所以，在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取 / 写入块 (block) 中某数据时，首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构。

哈希索引

哈希索引即是基于哈希技术，如上图所示，我们将一系列的最终的键值通过哈希函数转化为存储实际数据桶的地址数值。值本身存储的地址就是基于哈希函数的计算结果，而搜索的过程就是利用哈希函数从元数据中推导出桶的地址。

• 添加新值的流程，首先会根据哈希函数计算出存储数据的地址，如果该地址已经被占用，则添加新桶并重新计算哈希函数。
• 更新值的流程则是先搜索到目标值的地址，然后对该内存地址应用所需的操作。

哈希索引会在进行相等性测试（等或者不等）时候具有非常高的性能，但是在进行比较查询、Order By 等更为复杂的场景下就无能为力。

B-Tree

B-Tree 与 B+Tree

在 数据结构与算法/查找树 https://url.wx-coder.cn/9PnzG 一节中我们介绍了 B-Tree 的基本概念与实现，这里我们继续来分析下为何 B-Tree 相较于红黑树等二叉查找树会更适合于作为数据库索引的实现。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数。

根据 B-Tree 的定义，可知检索一次最多需要访问 h 个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次 I/O。而检索的时候，一次检索最多需要 h-1 次 I/O（根节点常驻内存），其渐进复杂度为 $O(h)=O(log_dN)O(h)=O(log_dN)$，实际应用中，出度 d 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3）。而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的 I/O 渐进复杂度也为 O(h)，效率明显比 B-Tree 差很多。

B+Tree 是 的变种，有着比 B-Tree 更高的查询性能，其相较于 B-Tree 有了如下的变化：

• 有 m 个子树的节点包含有 m 个元素（B-Tree 中是 m-1）。
• 根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。
• 所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。
• 叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。

一般在数据库系统或文件系统中使用的 B+Tree 结构都在经典 B+Tree 的基础上进行了优化，增加了顺序访问指针：

如上图所示，在 B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的 B+Tree。做这个优化的目的是为了提高区间访问的性能，例如下图中如果要查询 key 为从 3 到 8 的所有数据记录，当找到 3 后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

索引顺序

B-Tree 索引可以很好地用于单行、范围或者前缀扫描，他们只有在查找使用了索引的最左前缀（Leftmost Prefix）的时候才有用。不过 B-Tree 索引存在一些限制：

• 如果查找不从索引列的最左边开始，索引就无法使用；同样，不能查找字符串结尾；
• 不能跳过索引中的列；
• 不能使用任何在第一个范围条件右边的列作为条件；

因此 B-Tree 的列顺序非常重要，上述使用规则都和列顺序有关。对于实际的应用，一般要根据具体的需求，创建不同列和不同列顺序的索引。假设有索引 Index(A,B,C):

# 使用索引
A>5 AND A<10 - 最左前缀匹配
A=5 AND B>6 - 最左前缀匹配
A=5 AND B=6 AND C=7 - 全列匹配
A=5 AND B IN (2,3) AND C>5 - 最左前缀匹配，填坑

# 不能使用索引
B>5 - 没有包含最左前缀
B=6 AND C=7 - 没有包含最左前缀

# 使用部分索引
A>5 AND B=2 - 使用索引 A 列
A=5 AND B>6 AND C=2 - 使用索引的 A 和 B 列

使用索引对结果进行排序，需要索引的顺序和 ORDER BY 子句中的顺序一致，并且所有列的升降序一致(ASC/DESC)。如果查询连接了多个表，只有在 ORDER BY 的列引用的是第一个表才可以(需要按序 JOIN)。

# 使用索引排序
ORDER BY A - 最左前缀匹配
WHERE A=5 ORDER BY B,C - 最左前缀匹配
WHERE A=5 ORDER BY B DESC - 最左前缀匹配
WHERE A>5 ORDER BY A,B - 最左前缀匹配

# 不能使用索引排序
WHERE A=5 ORDER BY B DESC,C ASC - 升降序不一致
WHERE A=5 ORDER BY B,D - D 不在索引中
WHERE A=5 ORDER BY C - 没有包含最左前缀
WHERE A>5 ORDER BY B,C - 第一列是范围条件，无法使用 BC 排序
WHERE A=5 AND B IN(1, 2) ORDER BY C - B 也是范围条件，无法用 C 排序

LSM Tree

B-Tree 这种数据库索引方式是传统关系型数据库中主要的索引构建方式，然而 BTree 通常会存在写操作吞吐量上的瓶颈，其需要大量的磁盘随机 IO，很显然，大量的磁盘随机 IO 会严重影响索引建立的速度。对于那些索引数据大的情况(例如，两个列的联合索引)，插入速度是对性能影响的重要指标，而读取相对来说就比较少。譬如在一个无缓存的情况下，B-Tree 首先需要进行一次磁盘读写将磁盘页读取到内存中，然后进行修改，最后再进行一次 IO 写回到磁盘中。

LSM Tree 则采取读写分离的策略，会优先保证写操作的性能；其数据首先存储内存中，而后需要定期 Flush 到硬盘上。LSM-Tree 通过内存插入与磁盘的顺序写，来达到最优的写性能，因为这会大大降低磁盘的寻道次数，一次磁盘 IO 可以写入多个索引块。HBase, Cassandra, RockDB, LevelDB, SQLite 等都是基于 LSM Tree 来构建索引的数据库；LSM Tree 的树节点可以分为两种，保存在内存中的称之为 MemTable, 保存在磁盘上的称之为 SSTable。

LSM-tree 的主要思想是划分不同等级的树。以两级树为例，可以想象一份索引数据由两个树组成，一棵树存在于内存，一棵树存在于磁盘。内存中的树可以可以是 AVL Tree 等结构；因为数据大小是不同的，没必要牺牲 CPU 来达到最小的树高度。而存在于磁盘的树是一棵 B-Tree。

数据首先会插入到内存中的树。当内存中的树中的数据超过一定阈值时，会进行合并操作。合并操作会从左至右遍历内存中的树的叶子节点与磁盘中的树的叶子节点进行合并，当被合并的数据量达到磁盘的存储页的大小时，会将合并后的数据持久化到磁盘，同时更新父亲节点对叶子节点的指针。

之前存在于磁盘的叶子节点被合并后，旧的数据并不会被删除，这些数据会拷贝一份和内存中的数据一起顺序写到磁盘。这会操作一些空间的浪费，但是，LSM-Tree 提供了一些机制来回收这些空间。磁盘中的树的非叶子节点数据也被缓存在内存中。数据查找会首先查找内存中树，如果没有查到结果，会转而查找磁盘中的树。有一个很显然的问题是，如果数据量过于庞大，磁盘中的树相应地也会很大，导致的后果是合并的速度会变慢。一个解决方法是建立各个层次的树，低层次的树都比 上一层次的树数据集大。假设内存中的树为 c0, 磁盘中的树按照层次一次为 c1, c2, c3, ... ck-1, ck 。合并的顺序是 (c0, c1), (c1, c2)...(ck-1, ck) 。