可靠存储的索引设计，对比LSM-Tree和B-Tree

首先

许多数据库系统使用日志（log）来记录顺序写入，用于提高写性能、数据持久化等等；这套系统叫做日志机制。在日志机制的基础上，如果高效地查找数据库中特定键的值，需要其他的机制（也就是索引机制）来辅助执行。

最朴素的存储与查找的实现

db_set(){
     echo "$1,$2" >> database
 }
 
 db_get(){
     grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
 }           

会生成这样的文件

# database
 c,[1, 2, 3]
 a,[6, 7]
 a,[15, 34, 1]
 d,"1gfvaw1fva"           

一个追加的日志机制看起来非常浪费空间，为什么不原地更新呢。我们简单论证一下日志机制的优越性

1. 追加写的速度远比随机写快。
2. 因为日志文件是只增不改的，所以可以并发读。
3. 因为日志文件是追加式的，并发和崩溃恢复就很方便。
4. 可以通过合并段文件（当单个日志文件过大，就新建一个日志文件，称为分段）来避免空间浪费和碎片化。

我们需要解决的问题，其实不只是快速查找，一共有以下这些问题，我们提前列出来，然后看看不同的索引结构，对这些问题的处理有何差别。

• 快速读已存在的key
• 快速读不存在key
• 快速范围搜索
• 快速写
• 快速删
• 压缩日志（文件大小）
• 索引持久化

哈希索引

由于目前的数据都是key/value式的，很容易就想到使用类似map、dict的结构来实现索引：

在数据写入文件的时候，在内存中维护着 key的hash值 -> key、写入数据时文件大小（offset）和数据的大小（limit）。（暂不考虑hash冲突）

对于写操作，就如上所示。如果已有这个key，则更新索引。没有则添加索引。因为key、offset、limit的大小都是有限的（比如256、int64、int64），所以很容易使用数组来高效实现。

对于读操作，顺着key的hash值找到offset和limit，直接可以定位到文件的某一位置，只需要一次磁盘寻址。

以上是哈希索引的主要内容。针对压缩日志，哈希索引一般这么处理：

当单个日志文件增长到一定大小，就新开一个日志文件和这个日志文件对应的哈希表（每个日志文件都对应着一个哈希表），将所有的写操作转移到新的日志文件之中。

之后对旧日志文件进行压缩，并对压缩后的日志建立新的哈希表。在压缩的过程中，因为是只读的，所以读请求依旧可以使用旧日志文件。当日志文件多了之后，还可以合并多个日志文件。

例如上面那个文件，压缩之后会变成这样。实际中压缩的效率会更加高。

# database
 c,[1, 2, 3]
 a,[15, 34, 1]
 d,"1gfvaw1fva"           

哈希索引简单清晰，但是也存在一些问题。比如哈希表必须全部放入内存、哈希冲突处理起来复杂、区间查询效率不高等等。对于索引持久化，哈希所以可以把旧日志文件的旧哈希表持久化，通过最新的日志文件重构最新的哈希表。

SSTables和LSM-Tree

上面的索引依靠hash来建立，所以是无序的，必须要放在内存中才能实现高效的随机访问。想想，其他数据结构中，有序的数据机构的随机访问效率一般也比较高。比如有序数组、各种查找树等。有序的key/value日志，称为排序字符串表。事实上不只是随机访问效率高，我们一个一个来梳理好处：

1. 由于其有序，即使存放在磁盘之中，也能比较高效地进行二分查找（哈希表由于哈希冲突，磁盘查找并不方便）。
2. 由于其有序，我们可以建立稀疏的内存索引，有效地减小了内存的占用。
3. 由于有序，当段文件过大过多时，也可以通过K路归并来实现日志压缩，占用较小的内存。
4. 由于有序，范围查找相当方便

好了，既然有这么多好处，我们来考虑一下怎么在日志体系下应用排序字符串表（毕竟我们也不想丢失日志体系的好处）

我们在内存中维护一个平衡查找树的数据结构（比如红黑树），这个树有时被称为内存表。

对于写操作，往磁盘中写入日志（不排序），往内存表中写入key和value。当内存表的大小超过一定阈值之后，开一个新的内存表，将旧内存表转化为排序字符串表，存入磁盘。这个存入磁盘的排序字符串表，称为SSTable（内存表和SSTable都来自于Google的Bigtable论文）。

对于读操作，先尝试在内存表中查找，然后是最新的SSTable，然后是次新的SSTable，直到找到目标或者为空。

后台进程周期性合并与压缩SSTable

数据库崩溃后，通过日志文件恢复内存表（SSTable在磁盘中，不用恢复）

这套算法本质上被LevelDB和RocksDB使用。算法的最初结构是建立在更加早期的日志结构文件系统之上，被称为Log-Structured Merge-Tree（LSM-Tree）。

还有一些策略能决定压缩和合并的时机，比如对数据使用分层压缩（LevelDB和RocksDB使用）与大小分级（HBase），能起到性能优化的效果，但是这里不多赘述。

B-trees

B-tree也是有序的，但是除了有序之外，其他地方都和LSM-Tree不一样。

之前看到的结构，都是对数据分段，一般大小在几M或者更大。但是B-tree将数据分页，每页为4k（可以更大）。页是内部读写的最小操作单位。4k这个数字，比较接近底层硬件的布局，因此性能也不错。

每个页面都通过地址进行标识，每个页面都负责了一定的范围。某一个页面被指定为根页面，父页会引用子页（比如一个根页的范围是0-1000，其10个子页分别覆盖100的范围，其共100个孙页，每个负责10的范围。在这个例子中，只有孙页记录了数据，其他页只记录引用），父页对子页的引用按照子页的范围排序，叶子页的记录安排key排序。

对于更新操作，首先搜索包含该键的子页，然后更新子页，再将子页重新写回硬盘。（看出来，都是以子页为单位操作）

对于新增操作，首先找到符合其键范围的子页，然后将其添加到此页之中。如果某个范围内的子页已经没有额外的空间了，那么将会把该子页拆分为两个两页，并更新父页的引用。

对于读操作，先从根页开始，通过二分找到合适的范围区间，然后进入到下一个页，直到达到叶子页，找到记录或为空。

对于删除操作，比较复杂，暂且不谈也罢。

通过在添加键的时候分裂页面，可以保持数的平衡。一个页包含的子页引用数量称为分支因子，一般分支因子在几百个。分支因子为512的4KB页的四级树可以存储256TB（5124∗4KB/1024KB/1024MB/1024GB=256TB512^4 * 4KB / 1024KB / 1024MB / 1024GB = 256TB5124∗4KB/1024KB/1024MB/1024GB=256TB)

如果数据库在页面分裂时崩溃（此时需要写两个页，并更新父页对子页的引用），会产生数据不一致。因此对于B-tree树的实现，依旧会借助日志体系，被称为预写日志（write-ahead-log，WAL），帮助B-tree恢复状态。另一种更加常见的操作，是使用写时复制。先将两个新的子页写入其他的位置，然后再更新父页，丢弃旧子页。

并发访问时，通常使用锁存器（轻量级的锁）保护树的数据结构完成。

B-tree树太过常见了，所以研究特别多，有很多优化，这里列举一些

• 压缩键的信息。比如字符串型，对于根页，可能只需要记录前两位字符串即可。
• 尽可能将兄弟叶子页按顺序保存在磁盘上。但是这个事情会随着树的增长产生困难。
• 建立到左右兄弟页的引用，方便进行大规模的遍历。（B+树特性）
• 只有叶子节点才记录数据，非叶子节点只记录索引（B+树特性）

暂时的小结

对比一下三种存储模式。需要注意的是，到这里为止，我们比较的都是key/value型的数据（关系型数据库，也可以把主键视为key，其他视为value），所在的计算机架构都严格区分了内存和磁盘的功能与性能。如果抛开以上两个定语，则目前为止的比较也就不再准确。

哈希索引	LSM-tree	B-tree
读已存在的key	高效（哈希冲突）	一般	高效
读不存在key	低效，可借助布尔过滤器	低效，可借助布尔过滤器	高效
范围搜索	极低效	一般，需要访问多个SSTable，但是每个表的访问相对迅速	高效
写	极高效	极高效	高效
删	极高效	极高效	高效
压缩日志	高效	高效	一般
索引持久化	无、恢复时重构索引	有、恢复时重构少量索引	有且稳定
内存空间	大	一般	较低
磁盘空间	一般	较小	较大

对比B-tree和LSM-tree

B-tree比LSM-tree成熟，但是两者目前都很有吸引力。一般而言认为LSM-tree写入更快，B-tree读的表现更加快且稳定。但是还有一些很细节的点，需要我们去考虑。

LSM-tree	B-tree
写放大（一次写入请求导致的多次磁盘写），由于SSD只能承受有限次数的擦除覆盖，所以写放大与成本直接挂钩。	较差	一般
磁盘空间的紧凑程度。更加紧凑的数据存储，能在有限的I/O带宽中支持更多的读写请求，减小存储空间倒是次要的。	较好	一般
磁盘的I/O始终是有限的，如果一个数据库除了处理请求，还有别的线程消耗I/O，则可能会影响处理请求的速度。	有后台压缩程序	没这种顾虑
一些特殊操作，其速度可能够不上请求的速度，会拖慢请求。	压缩程序可能会跟不上顺序写，需要额外的监控措施。	保持树平衡，问题较小
并发控制	较方便	一般
事务隔离	不清楚	较方便

关系型数据库

我们回到关系型数据库，看看上文的哪些是关系型数据库中用到的，那些是可以用到但是有更好的方案的。这样学习完，算是对整个知识体系有了更加切实的体会。

二级索引

在InnoDB存储引擎中，我们使用把表的主键（聚集索引）视为key，并对其应用B-tree结构来持久化存储。而对于我们之后添加的索引（非聚集索引），则需要额外构建查找树，这棵树的key一般是我们频繁查询的列，value是对应记录的主键或者磁盘地址。

在使用二级索引的性能提升时，别忘了为了维护二级索引所带来的在写、保证事务性上的开销。

二级索引中的多列索引

关系型数据库中的多列索引被称为级联索引。其不过简单的将多个列按顺序组合在一起成为key。因此查询时也要按列的顺序去查询。

还有一种多列索引，被称为多维索引，常用于地理空间数据等。例如PostGIS实现的R树（这块我也没深入研究）

作者：浪狼郎

链接：https://juejin.cn/post/7143109104213426206