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

IT行业相对于一般传统行业，发展更新速度更快，一旦停止了学习，很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习，精进自己的技术，尤其是初学者。今天golang学习网给大家整理了《一文了解数据库索引：哈希、B-Tree 与 LSM》，聊聊MySQL、数据库、b-tree、lsm-tree，我们一起来看看吧！

本文节选自深入浅出分布式基础架构-数据库篇 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 上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间

# 使用索引
A>5 AND A6 - 最左前缀匹配
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)

文中关于mysql的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《一文了解数据库索引：哈希、B-Tree 与 LSM》文章吧，也可关注golang学习网公众号了解相关技术文章。