【作者】赵海
一、存储引擎简介
接触数据库比较深的人可能对存储引擎并不陌生，但是大多数数据库管理员可能对存储引擎并不熟悉，因为大多数关系型数据库的学习者并不需要关心存储引擎的选择和应用，我们熟知的 Oracle 、 SQL Server 等数据库基本只有一种存储引擎，没有给大家选择和设计的机会，接触 MySQL 以及其他一些 NOSQL 数据库比较多的人对存储引擎就会深有感受。
那么存储引擎是什么？它主要解决什么问题呢？
二、B 树存储引擎
关系数据库当中最常见的是 B 树存储引擎。B 树存储引擎是一种利用 B 树、 B+ 树等数据结构对数据库进行增、删、改、查的存储引擎技术。利用 B 树存储引擎的常见数据库有 Oracle 、 DB2 、 MySQL 等关系型数据库。
2.1 B 树存储引擎的数据结构
基于平衡二叉树的改进版本有很多，常见的有 B 树、 B+ 树、 B* 树等。本文我们不做全部探究，只针对最常用最基本的 B 树 &B+ 树的数据结构特点进行展开。
2.1.1 B 树索引数据结构
相信大家在大学的课程当中都学过二叉树以及平衡二叉树数据结构， B 树数据结构其实是在此基础上的一种升级和改进。最早是由德国计算机科学家 Rudolf Bayer 等人于 1972 年在论文 《 Organization and Maintenance of Large Ordered Indexes 》提出。具体特征如图 2.1.1 所示， B 树事实上是一种平衡的多叉查找树，也就是说最多可以开 m 个叉（ m>=2 ），我们称之为 m 阶 b 树：
B 树
总的来说， m 阶 B 树满足以下条件：a. 每个节点至多可以拥有 m 棵子树。b. 根节点，只有至少有 2 个节点（极端情况，就是一棵树就一个根节点 ) 。c. 非根非叶的节点至少有 Ceil(m/2) 个子树 ( 图中 5 阶 B 树，每个节点至少有 3 个子树 ) 。d. 非叶节点中信息包括 [n,A0,K1, … ,Kn,An] ，其中 n 表示该节点保存的关键字个数， K 为关键字且 Ki （对应到关系型数据库当中的信息，就是二位表当中记录的主键信息）。e. 从根到叶子的每一条路径都有相同的长度，也就是指向这些节点的指针为空。
B 树的查询过程和二叉排序树类似，从根节点依次比较每个节点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针。上文提到 B 树是基于平衡二叉树的升级或者改进版本，那么介绍到这里可能大家也比较清楚了，为什么要改进呢？B 树的节点子树可以更多，这就意味着同样的数据元素规模， B 树的高度会更低，检索的时间复杂度就会低，如果这个检索在数据库当中大多数情况是落在磁盘上的寻址，那么这个改进的意义就更大了。
2.1.2 B+ 树索引数据结构
作为 B 树的加强版称之为 B+ 树，图 2.2.1 所示，从图中所示的状况我们可以很直观感受到：B+ 树与 B 树最大的不同是所有数据记录都保存在叶子节点中，叶子结点是有指针将所有数据连接起来的。
具体来说， B+ 树与 B 树的差异在于：a. 有 n 棵子树的节点含有 n 个关键字（也有认为是 n-1 个关键字） ; b. 所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接 ; c. 非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字 .
由于采用了这样的结构， B+ 树对比 B 树有以下两方面优点：
首先，索引节点上由于只有索引而没有数据，所以索引节点上能存储比 B 树更多的索引，这样树的高度就会更矮。那么查询的时间复杂度就会更低。
再有，因为数据都集中在叶子节点了并且叶子节点增加前后指针，指向同一个父节点的相邻兄弟节点，给范围查询提供遍历。而如果使用 B 树结构，由于数据既可以存储在内部节点也可以存储在叶子节点，范围查询可想而知是很繁琐的。
2.2 B 树存储引擎数据操作原理
2.2.1 B 树存储引擎数据检索算法
对于基于二叉树数据结构基础之上形成的树的存储结构，那么其查询数据最核心的算法就是二分法查找算法，即通过键值的比较排除一定比例的可能性，从而缩小数据查找的范围，最终通过几次比较定位到要查找的数据。直观表现期间，我们还是以图为例：
按照图示，我们查找的数据是 L ，
首先，将根节点的数据块从磁盘读入内存，读出 P 值，比较发现小于 P ；
接着，遍历根节点左指针指向数据块，读出 C 、 F 、 J 、 M 值，顺序比较后，找到 J&M 之间的指针；
最后，遍历指针指向数据块，读出 K 、 L 值，定位所查询的数据 L 。
根据以上算法，那么本次查找经历了三次磁盘的读取，三次内存数据的比较。由此看见， B 树检索的时间复杂度主要取决于树的深度以及节点内保存的数据数量的多少。
对于 B+ 树的检索，其实算法与 B 树非常类似，其主要区别在于 B+ 树的所有检索操作都不会在非叶子节点结束，每一个检索都会经历相同的长度，那就是从根节点到叶子节点，途中经历的非叶子节点只保留索引信息，只有叶子节点才会保留所有键值数据。这种算法把所有遍历的复杂度留在了叶子节点的扫描上，减少了检索途中的 IO 次数，保证了叶子节点扫描的局部优势，同时也保障了所有检索操作的时间复杂度相对的稳定性。因此大部分关系型数据库选择的是 B+ 树作为其存储引擎。
2.2.2 B 树存储引擎数据插入算法
形成一棵 B 树，那么必须遵循 B 树的基本规则（也就是其数据结构的特点），那么插入节点的时候，必须也得遵循其固有的数据结构特征（ a. 每个节点至多可以拥有 m 棵子树。c. 非根非叶的节点至少有 Ceil(m/2) 个子树 ( 图中 5 阶 B 树，每个节点至少有 3 个子树 ) 。这样就形成了 B 树插入的基本算法：
首先、根据插入节点的键值来检索其合适的节点位置，具体算法与检索算法相同；
其次、当找到具体节点位置的时候需要做判断：插入数据节点是否已经溢出（节点当中的键值数量是否符合 B 树规则），如果没有溢出，则直接插入数据。如果已经溢出，那么寻找这些键值当中的关键中间值，以其为界分裂节点产生新的子树。
具体如图所示，由于插入数据 [V] ，导致节点 [P,Q,R,S,T,U,V] 数据量不满足平衡性要求，这时将其分裂为两个节点，同时将中间的节点 S 提升到父节点中形成 [N,S,W] ，同时修改子树指针。
B+ 树的插入算法与 B 树非常类似，但是由于 B+ 树的非叶子节点只有索引信息没有键值信息，所以 B+ 树的节点分裂是在叶子节点上完成，同时非叶子节点需要更新其索引信息以及相应的指针信息。
2.2.3 B 树存储引擎数据删除算法
相对于插检索和插入算法来讲， B 树的删除算法相对比较复杂，代价也比较高，因为删除节点键值的操作非常有可能导致 B 树结构不符合既有的规则条件，那么就需要再平衡。
首先，我们需要知道 B 树达到平衡的重要条件：无论是内部节点还是叶子节点，其存储的键值数量在 [t-1,2t-1] 之间，如果数量不满足此条件，需要做重平衡操作。如果少于 t-1 ，需要借用或合并数据；反之，如果数据量大于 2t-1 ，则需要分裂成两个节点（这里我们用 t 表示 B 树的深度参数）。
接着，在明确了 B 树平衡的重要条件基础之上，我们来看 B 树删除节点时的具体算法步骤：
(1). 查询到键值所在的叶子节点，删除该叶子节点的数据。
(2). 如果删除叶子节点之后的数据数量，满足 B+ 树的平衡条件，则直接返回不用往下走了。
(3). 如果删除叶子节点之后的数据数量，不满足 B+ 树的平衡条件，就需要做平衡操作：
a. 如果该叶子节点的相邻节点的数据量可以借用，就借用过来满足平衡条件；
b. 否则，就只能与相邻的兄弟节点合并成一个新的子节点了。
(4). 在上面平衡操作中，如果是进行了合并操作，就需要向上修正父节点的指针，如果父节点也不再平衡，那么就按照前面的步骤也对父节点进行重新平衡操作，这样一直到整体平衡为止。
2.3 B 树存储引擎优劣分析
通过对 B 树存储引擎的数据结构以及数据操作原理的介绍，相信大家对其优缺点已经有所感悟。文到此处，有必要根据 B 树本身的特点来给大家明确其优缺点之间的内在关系。
首先，通过对 B 树和 B+ 树的检索算法特点来看，从使用的角度上来说， B 树索引存储结构多用于 OLTP 型的数据库，因为这类数据库主要以事务，或是行级别的读取和存储为主的（比如 MYSQL ）。换言之，这种类型的数据库更多的操作是小批量或单行级别的随机读取和更新，并且还有事务方面的需求。在此前提条件之下，之所以有 B+ 树的诞生，取决于以下两点：a. 磁盘读写代价更低。B 树的内部结点并无指向关键字具体信息的指针。所以其内部结点相对 B 树更小。若是把全部同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来讲 IO 读写次数也就下降了。b. B+ 树只要遍历叶子节点就能够实现整棵树的遍历。并且在数据库中基于范围的查询是很是频繁的，而 B 树实现这样的操作需要的代价非常高，效率非常低。
其次，通过对 B 树和 B+ 树的更新和删除算法特点来看，虽然算法相对哈希及其他存储引擎实现的算法来讲会显得非常复杂，代价很高。但是从另外一个侧面来看，正是由于它没有通过大量的数据追加实现更新和删除，它就无需去管理那些不同时间戳版本的重复数据。有效地利用了磁盘空间和内存空间，这个也与我们 OLTP 型关系型数据库的规模以及通用服务器硬件的配置非常匹配。
以上两点是我们通过 B 树的特点本身来分析出它最适合的应用场景，同时也是因为他的优点导致了它在其他场景下的一些劣势。正是因为它的平衡树的结构导致它无法处理一些大小变化无常的数据，无明显线性顺序的数据；正是因为它的插入和删除的高代价，它也不适合批量的顺序写入场景，甚至写多读少的场景也不适合。
2.4 总结展望
三、Hash 存储引擎
哈希存储引擎是一种利用哈希表的持久化实现对数据进行增、删、改以及随机读取的技术。利用哈希存储引擎的常见数据库有 Redis 、 Memcache 。
3.1 Hash 存储引擎基本架构
3.1.1 Hash 存储引擎的存储格式
3.1.2 Hash 索引的存储格式
哈希索引树
3.2 Hash 存储引擎数据操作原理
3.2.1 Hash 存储引擎的数据操作原理
哈希存储引擎数据库文件结构
3.2.2 Hash 存储引擎的数据文件操作原理
3.3 Hash 存储引擎优略分析
3.3.1 Hash 存储引擎的优势
3.3.2 Hash 存储引擎的劣势
3.4 总结展望
哈希存储引擎是一种在 NOSQL 数据库当中经常会用到的数据存储引擎技术，尤其是一些内存类数据库。具体数据库在其实现及使用哈希存储引擎的过程当中，涉及的可能不仅仅是文中所述的这些关于数据特点、数据操作特点方面的策略，可能还会涉及到缓存的算法、数据的持久化以及其他的一些方面的策略选择。本文希望通过这些原理性的讨论和分析展示给大家一个基本视图，也希望各位同业针对更多更深层次的内容进行发展性研究探讨并分享。
四、LSM-Tree引擎简介
本节将介绍LSM-Tree (Log-Structured Merge-Tree) 存储引擎，大多 NoSQL 数据库核心思想都是基于 LSM 来做的，只是具体的实现不同。例如 LevelDB 、 RocksDB 、 Hbase 、 Cassandra 等。LSM 树通过尽可能减少写磁盘次数，实际落地存储的数据按 key 划分，形成有序的不同文件；结合其 “ 先内存更新后合并落盘 ” 的机制，尽量达到顺序写磁盘，尽可能减少随机写；对于读则需合并磁盘已有历史数据和当前未落盘的驻于内存的更新。LSM 树存储支持有序增删改查，写速度大幅提高，但随机读取数据时效率低。
4.1 LSM-Tree 存储引擎设计原理
4.1.1 LSM-Tree 合并思想
LSM 树由两个或以上的存储结构组成，比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中，称为 C0 tree ，具体可以是任何方便健值查找的数据结构，比如红黑树、 map 之类，甚至可以是跳表。另外一个存储结构常驻在硬盘中，称为 C1 tree ，具体结构类似 B 树。C1 所有节点都是 100% 满的，节点的大小为磁盘块大小。
LSM-Tree 存储结构 1
LSM-Tree 存储结构 2
如上图所示，数据库采用了基于 LSM Tree 结构作为数据库的存储引擎，数据被分为基线数据（ SSTable ）和增量数据（ MemTable ）两部分，基线数据被保存在磁盘中，当需要读取的时候会被加载到数据库的缓存中，当数据被不断插入（或者修改时）在内存中缓存增量数据，当增量数据达到一定阀值时，就把增量数据刷新到磁盘上，当磁盘上的增量数据达到一定阀值时再把磁盘上的增量数据和基线数据进行合并。这个本身是 LSM 的核心设计思想，非常朴素，就是将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，从而大幅度提升性能。关于树的节点数据结构，不同数据库在基于 LSM-Tree 思想实现具体存储引擎的时候，可以根据自己的特点去定义。
4.1.2 LSM-Tree WAL
谈及 LSM （ Log Structured Merge Tree ）树存储引擎，从字面意思上，其实我们基本能看到两层意思，第一个是 Merge ，就是我们上一节说到的合并思想；另外一个就是 Log ，就是我们接下来要说的 WAL 文件，从下面展示的基于 LSM 存储引擎的写的流程当中，我们可以看到 WAL 就是数据库的一个日志文件。
LSM-Tree 写数据流程图
当插入一条数据时，数据先顺序写入磁盘保存的 WAL 文件中，之后插入到内存中的 Memtable 当中， Memtable 实际上保存的数据结构就是我们所述的内存当中的小树。这样就保证了数据的持久化，即使因为故障宕机，虽然内存里面的数据已经丢失，但是依然可以通过日志信息恢复当初内存里面的数据信息，并且都是顺序写，速度非常快。当 memtable 写入文件 SSTable 后，这个 log 文件的内容就不再需要了。而新的 memtable 会有新的 log 文件对应。
4.1.3 LSM-Tree SSTable
SSTable （ Sorted String Table ）是一种拥有持久化，有序且不可变的的键值存储结构，它的 key 和 value 都是任意的字节数组，并且了提供了按指定 key 查找和指定范围的 key 区间迭代遍历的功能。SSTable 内部包含了一系列可配置大小的 Block 块，典型的大小是 64KB ，关于这些 Block 块的 index 存储在 SSTable 的尾部，用于帮助快速查找特定的 Block 。当一个 SSTable 被打开的时候， index 会被加载到内存，然后根据 key 在内存 index 里面进行一个二分查找，查到该 key 对应的磁盘的 offset 之后，然后去磁盘把响应的块数据读取出来。当然如果内存足够大的话，可以直接把 SSTable 直接映射到内存中，从而提供更快的查找。在 LSM-Tree 里， SSTable 有一份在内存里面，其他的多级在磁盘上。
LSM-Tree SSTable
SSTable 在后台是要经过不断地排序合并，文件随着层次的加深，其大小也逐步变大。同时它也是可以启用压缩功能的，并且这种压缩不是将整个 SSTable 一起压缩，而是根据 locality 将数据分组，每个组分别压缩，这样的好处当读取数据的时候，我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。如图下图所示的情况， leve0 的 SSTable 达到数据量的阀值之后，会经过排序合并形成 Level1 的 SSTable ， Level1 的 SSTable 达到阀值之后，会经过排序合并成为 Level2 的 SSTable 文件。
LSM-Tree SSTable’s merge
以上图中所示的文件合并过程是一个排序合并的过程，因此每一层都包含大量 SSTable 文件，但是键值值范围不重复，这样查询操作只需要查询这一层的一个 SSTable 文件即可。
4.2 LSM-Tree 存储引擎读写算法
4.2.1 LSM-Tree 数据写入过程
说到 LSM-Tree 存储引擎的写入，分为实时的写入以及滞后的刷盘以及合并两部分过程。实时的写入主要涉及到 WAL 日志以及 MemTable ，我们前面说过 WAL 是一个顺序日志文件，而 MemTable 是内存当中的 Skip-List 的数据结构，实时写入的时候：
首先，将数据顺序写入 WAL Log 文件，由于是顺序追加，没有检索的过程，会非常快。
然后，将数据写入 MemTable ，也涉及到在 Skip-List 当中追加链的操作，内存处理也非常快。
当内存 Memtable 当中的数据达到一定的规模触及阀值条件的时候，后台会启动排序及合并操作，将 MemTable 当中的数据排序并刷入磁盘形成 SSTable ，同时周期性的将 SSTable 文件再进行排序分组，形成更大的 SSTable 文件，并转入下一个 Level 存储。
4.2.2 LSM-Tree 数据修改过程
LSM-Tree 存储引擎的更新过程其实并不存在，它不会像 B 树存储引擎那样，先经过检索过程，然后再进行修改。它的更新操作是通过追加数据来间接实现，也就是说更新最终转换为追加一个新的数据。只是在读取的时候，会从 Level0 层的 SSTable 文件开始查找数据，数据在低层的 SSTable 文件中必然比高层的文件中要新，所以总能读取到最新的那条数据。也就是说此时在整个 LSM Tree 中可能会同时存在多个 key 值相同的数据，只有在之后合并 SSTable 文件的时候，才会将旧的值删除。
4.2.3 LSM-Tree 数据删除过程
LSM-Tree 存储引擎的对数据的删除过程与追加数据的过程基本一样，区别在于追加数据的时候，是有具体的数据值的，而删除的时候，追加的数据值是删除标记。同样在读取的时候，会从 Level0 层的 SSTable 文件开始查找数据，数据在低层的 SSTable 文件中必然比高层的文件中要新，所以如果有删除操作，那么一定会最先读到带删除标记的那条数据。后期合并 SSTable 文件的时候，才会把数据删除。
4.2.4 LSM-Tree 数据读取过程
对于 LSM-Tree 的读取操作，按照 Memtable 、 SSTable 的架构来讲，那么肯定是先扫描 MemTable 当中的元素，然后扫描 SSTable 文件当中的数据，然后找到相应数据。虽然我们讲过 SSTable 本身是有序的数据元素片段，而且对于读取概率较大的数据基本会在 Memtable 当中，但是这依然会造成巨大的扫描，读取效率会非常低下。
LSM-Tree Index
虽然 LSM-Tree 的设计思想并不是为了随机读的性能而设计，但是为了改善随机读的效率，那么在其数据结构的设计当中，其实是有考虑索引设计的。正如图 2.3.3 所示，在每一个 SSTable 文件的尾部是有记录数据位置的索引信息的。这些信息是可以被流失读入内存当中，然后形成一个稀疏索引，那么检索的时候如果从 MemTable 当中没有检索到数据，接下来需要访问 SSTable 的时候，是可以先通过这个稀疏索引定位到 SSTable 的具体位置，然后在准确读取数据，这样的话就会大大提高随机读取的效率。
4.3 LSM-Tree 存储引擎优略分析
4.3.1 LSM-Tree 的优势
我们通过对 B-Tree 存储引擎的学习，应该了解到 B-Tree 存储引擎的随机检索能力是非常强的，一方面它可以通过平衡树的算法，通过少数几次二分法思想的查找就可以在索引定位数据的位置；另外一方面它也不用担心像哈希存储引擎那样需要考虑冲突的解决办法，需要考虑哈希函数的健壮性问题。对于数据存取的模式来讲， B+Tree 则是将数据拆分为固定大小的 Block 或 Page, 一般是 4KB 大小，和磁盘一个扇区的大小对应， Page 是读写的最小单位，更适合固定大小的结构化数据结构的存取。总结以上两点， B-Tree 存储引擎应该在结构化的数据的随机读取方面是无可比拟的。
但是，在高吞吐写的场景下， B-Tree 就显得力不从心了。主要原因就是它的插入、更新、删除的这些操作都是建立在检索的前提之下的，虽然这种操作更适合事务型的业务场景，但是对于事务型不是非常强，但是吞吐量巨大的场景并不适合。这就是 LSM-Tree 诞生的根本原因， LSM-Tree 正是为了克服这个问题，通过将数据增删改全部转化为顺序写入从而显著提高写的性能。这个特点在分布式系统上更为看重，当然针对读取普通的 LSM-Tree 结构，在使用索引或者缓存优化后的也可以达到 O （ logN ）的复杂度。因此对于持续写入数据量大，数据和时间相关，编码到 key 值中很容易使 key 值进行排序的这种场景是最适合 LSM-Tree 存储引擎的。这个时候大家可能会联想到哈希存储引擎，其实也容易区分：首先，哈希存储引擎的索引需要一次性全部 Load 到内存当中；其次，哈希存储引擎的 Key 是无法正常排序的；再次，不是所有的数据都可以用哈希函数套用的，也不是所有键值数据都能很好处理冲突问题。
4.3.2 LSM-Tree 的劣势
基于 LSM-Tree 分层存储能够做到写的高吞吐，带来的副作用是整个系统必须频繁的进行 compaction ，写入量越大， Compaction 的过程越频繁。而 compaction 是一个 compare & merge 的过程，非常消耗 CPU 和存储 IO ，在高吞吐的写入情形下，大量的 compaction 操作占用大量系统资源，必然带来整个系统性能断崖式下跌，对应用系统产生巨大影响，当然我们可以禁用自动 Major Compaction ，在每天系统低峰期定期触发合并，来避免这个问题。
另外 LSM-Tree 的更新、删除全部是通过增加新数据间接实现，那么 Key 值必然存在多版本，而且事务锁的机制与 B-Tree 相比而言会宽松很多，而且键值重复很多，这也就导致了它不适合事务要求非常强的结构化数据处理场景。
4.4 总结展望
总结来看，我们通过对 LSM-Tree 存储引擎的合并思想、数据处理算法等的了解，基本了解了它诞生的缘由， LSM-Tree 存储引擎就是为了高吞吐量数据写入场景而设计。在了解了它的最大优点之后，各个数据库在利用它实现自己的读写算法的同时也会根据特殊场景、特殊配置等采取各种改进方式来发挥它的优势的同时避免劣势的放大，因此具体实现方式上有很多 LSM-Tree 的变种，本文就不做具体讨论，希望同业能基于此而深入研究并分享更多具体实现方面的分享。
【 参考文献】
[1] https://github.com/facebook/rocksdb/wiki/Performance-Benchmarks
[2] https://www.shangmayuan.com/a/c8d86c0f17564902a28441ce.html
[3] https://my.oschina.net/u/4271740/blog/4300371
[4] https://stackoverflow.com/questions/2574661/existing-implementation-of-btree-or-btree-in-java
[5] Kai Ren, Qing Zheng, Joy Arulraj, Garth Gibson: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data
[6] https://mongoing.com/?s=storageEngine
[7] https://www.storageengine.com/
[9] Patrick O'Neil1, Edward Cheng2 Dieter Gawlick3: The Log-Structured Merge-Tree (LSM-Tree)
[10] https://www.cnblogs.com/fxjwind/archive/2012/06/09/2543357.html
[11] https://cloud.tencent.com/developer/article/1441835
[12] http://www.codinglabs.org/html/theory-of-mysql-index.html
如有任何问题，可点击文末阅读原文，到社区原文下评论交流 觉得本文有用，请转发、点赞或点击“在看”，让更多同行看到
资料/文章推荐：
欢迎关注社区 "数据库"技术主题 ，将会不断更新优质资料、文章。地址：
https://www.talkwithtrend.com/Topic/597
长按二维码关注公众号
*本公众号所发布内容仅代表作者观点，不代表社区立场
