作者介绍

戌米(笔名)，金融分布式数据库DBA，爱好分布式数据库底层技术，哔哩哔哩UP主：戌米的论文笔记。

我们知道，数据库有三大模块：存储、事务、SQL。其中存储这一模块，负责数据在磁盘和内存上的存储、检索和管理，并向上层提供细粒度的数据操作接口。

因为存储和其它模块的耦合较少，我们可以把它具象为一个专用的数据库组件，称为存储引擎。目前很多数据库都支持可插拔的存储引擎，比如MySQL支持InnoDB、MyISAM、Memory和基于RocksDB的MyRocks等存储引擎，这给存储引擎的迭代发展提供了空间。

而存储这块最重要的就是存储的结构，内存、缓存、读写流程的任何设计，都是建立在存储结构的基础上的，由此存储结构和存储引擎的特性和性能方面关系十分密切。

但相比于浩如烟海的存储引擎，可用的存储结构却没有几个。B树作为一个非常适合于磁盘的存储结构，自关系型数据库的兴起后，一直占据着存储领域的主流。但近些年随着分布式技术的兴起和固态硬盘以及多核CPU的发展，另一种存储结构LSM树越来越火热，成为了学术界和工业界的关注焦点。

本文，就来跟大家讨论一下这两类主流存储结构的共性和特性，试着去找出存储结构发展的趋势，并介绍一下它们各自为了迎合这种趋势又发展出了哪些变种与优化。

接下来的内容，会分为以下几节来做介绍（相比于视频，这里对章节顺序和部分内容作出了调整，个人认为，这样在逻辑上更易理解）：

一、存储引擎与存储结构（明确讨论对象的概念）

二、存储结构的共性特点（B树和LSM树具备了哪些特性，使得它们能从一众数据结构中脱颖而出成为存储结构，这些特性又指明了它们还有哪些不足？）

三、存储结构的分类和发展历程（说完了共性，再说差异，B树和LSM树的本质差异在哪？回顾发展历史，为什么B树在当年独占鳌头，而LSM近些年会异军突起？）

展开全文

四、B树及其变种（具体说一下B树的一些变种及其体现出的发展趋势）

五、LSM树及其优化（具体说一下LSM树的主流结构及一些优化方法）

六、总结（剧透一下：B树和LSM树分别是in-place update和out-of-place update模式的集大成之作，而分布式、固态硬盘、多核CPU三种技术的发展使存储结构从in-place update向out-of-place update方向发展，LSM树也因此得到了越来越多的使用，而以Bw树为代表的新型B树融合了两种模式的特性，可能是未来的一个发展方向）

七、Reference & 相关阅读

一、存储引擎与存储结构

对于一个存储引擎而言，它需要存储的主要是数据文件和索引文件。

而我们要把抽象的一条条数据转换为具体的文件来存储，具体探究一下这个转换的细节，也就是数据文件的组织形式。

目前数据文件的组织形式主要有三种：索引组织表、堆组织表和哈希组织表。

索引组织表：数据文件和索引文件合并存储在一起。

（索引组织表 图源《数据库系统内幕》）

堆组织表：数据文件是一个“无序堆”数据结构，其中的数据记录一般是不需要有特定的顺序的，所以这里的“堆”实际上，其实也可以通俗理解成“一堆数据”。虽然堆组织表的数据文件是无序的，但我们可以通过索引文件里的索引结构，来快速得到数据在堆中的位置，从而进行快速的访问。

哈希组织表：把记录分散存储在一个个桶中，每条记录主键的哈希值来确定记录属于哪个桶。记录哈希值的部分就是索引文件，记录哈希结果的部分就是数据文件。因为目前主流的存储引擎基本都没有使用哈希组织表，所以我们后面的讨论一般不会涉及哈希组织表。

（堆组织表或哈希组织表 图源《数据库系统内幕》）

堆组织表因为数据的插入是无序的，而索引组织表需要按索引的顺序插入数据，所以我们一般认为堆组织表的写入性能强于索引组织表，读取性能弱于索引组织表。

但数据文件的组织形式对性能的影响还是较小的。InnoDB存储引擎用的是索引组织表，而Oracle和PostgreSQL则是堆组织表，但我们很少从这个角度去区分它们的性能，因为它们都使用B树索引。

而索引作为我们读写数据的主要入口，索引文件的组织形式其实和存储引擎的性能关系更加密切，比如我们把索引文件的组织形式从B树换为LSM树，那么性能差异就会大得多了。

所以我们要关注的重点实际是索引文件的组织形式，我们后面的内容就把索引文件的组织形式专门称为存储引擎的存储结构。

这里大家可能感觉有点绕，其实没那么复杂，就是和大家说明一下，数据文件和索引文件都有其组织形式，也就是数据结构。但数据文件的存储结构要么依托于索引文件（索引组织表），要么对性能的影响没有那么大（堆组织表），所以我们关注的重点、后文讨论的对象都是索引文件的组织形式，也就是“存储结构”。

二、存储结构的共性特点

明确了存储结构的概念，我们问出这样一个问题：为什么B树和LSM树能用作存储结构呢？

实际上，我们在内存中是有多种数据结构可供选择的，从基础的数组和链表，到哈希表，再到二叉搜索树、平衡二叉树、红黑树、跳跃表等。但这些结构都不适合用作磁盘上的存储结构，为什么呢？

我们考虑一下存储结构需要具有的特性，我先把我的答案列出来，主要有两点：

① 存储结构要适合磁盘存储。我们讨论的存储结构是在磁盘这种介质上的，磁盘IO的特性大家都知道，顺序IO性能是要远远优于随机IO的。所以存储结构的IO次数越少越好，并且应该尽量一次读取一块连续的区域。从这个角度上看，存储结构的单元越大越好。

② 存储结构要允许并发操作。我们希望存储结构是支持高并发的，从读取角度，增加并发引起的问题较少；但写入角度下并发的问题就大了。举个例子，大家如果用过共享文档就知道，一个共享的文档虽然可以同时被多个人打开，但同时只能被一个人修改，多个人同时修改的话只有一个能生效。共享文档就可以看做一个大文件，它的写入并发最高仅为1。存储结构需要支持增删改的高并发，从这个角度上看，存储结构的单元应该越小越好。

这里提前声明一点，我们这里说的存储结构的并发操作，并不是我们平时了解的数据库事务并发，这里锁的对象是内存中的数据结构，是一个物理上的概念，而不是逻辑上用户的数据。

大家可能对这里还有一点迷惑，先别急，保留一下印象就好，等会我会具体解释的。

根据这两个特性，我们再审视一下上面提到的那些内存数据结构。

有①没②，也就是只适合磁盘存储，但不适合并发操作的数据结构有：大文件、数组。它们都是连续的一大块存储区域，但如果要修改，影响面很大，基本要锁住整个数据结构。

有②没①，也就是适合并发操作，但不适合磁盘存储的数据结构有：链表、各种二叉树、跳跃表、红黑树、哈希表这些。它们的修改、写入操作影响小，但数据结构的粒度也非常小，一次一般只操作几个字节，不适合磁盘IO。

那么什么数据结构同时具备这两个特性呢？自然就是我们的B树和LSM树啦。

（B树结构图 图源网络）

B树的结构我就不多介绍了，大家可以看一下这张图回想一下B树的结构。B树是以页为单位组织的，InnoDB存储引擎中页的大小为16K，一般可以指出几百上千个指针，因而具有高扇出、低高度的特点，从而保证了B树是连续IO，并且IO次数极少，符合特性①。

到了特性②，聪明的读者可能会想，我知道，B树要修改的单位也是页，所以并发控制的锁上在页上，B树的并发程度也很高，满足②。

但并没有那么简单，虽然B树修改的单位确实是页，但B树存在SMO操作，导致B树的并发能力并不理想。

SMO操作是什么呢？它全称Structure Modification Operation，也就是结构修改操作。大家回想一下B树的结构，在我们向一个页中增加数据超过其大小，或者删除数据使其空间少于二分之一，是不是就会造成页的分裂或合并，影响关联节点或其父节点。并且，这种影响可能还会向上传递，甚至有可能造成根节点的分裂或合并。

所以如果我们想要保证出现SMO操作时读写的安全的话，就需要对有可能受SMO操作影响的节点加锁。

如果你不太清楚上面的逻辑的话，可以去了解一下B树或B+树分裂与合并的相关知识，网上的内容很多，我这里就不细说了。

好的，现在就可以给大家解释存储引擎的并发操作和事务并发操作的不同了。假设都使用锁机制来控制它们的并发的话，我们给这两种用途的锁起了不同的名字：Lock和Latch。

Lock是用来维持数据库事务的ACID特性的，它是事务级隔离的，锁住的对象是用户的数据，是一个逻辑概念，我们熟知的Lock主要有共享锁和排他锁，一般称作S锁和X锁。

而Latch则是用来保护我们读取过程中加载到内存中数据结构的，它是线程级隔离的，主要是防止两个线程同时修改一块内存结构，或者一个线程读取另一个线程正在修改的内存结构。

大家可能还是有点难以理解，我举个例子吧，假设我们修改