数据库索引技术之Lsm树

上次咱们分享了驳回哈希索引成功的存储引擎，它总是将写操作始终追加到数据文件，就跟写日志一样。这种日志结构式的存储引擎，数据记载顺序由写入期间选择，同一键的旧记载由新记载取代。

由于数据在写入时，智能切分红一个个文件。数据库要求在后盾对文件启动兼并，以缩小文件数，进而放慢查问。假设待兼并文件里的数据是有序的，咱们就可以驳回归并排序算法来提高兼并效率。

虽然这看起来会违反顺序写的准则，但也有方法处置，咱们稍后引见。

如今，咱们将数据文件格局改成这样：①文件中的一切记载，依照 键( key)来排序;②排序保障了每个键只在文件中发生一次性，不会有重复的旧记载。权且将这种格局叫做 排序字符串表( sorted string table )简称SSTable 。

相比普通日志结构式的数据文件，SSTable 有几个清楚长处：

高效兼并

假设您学过归并排序算法，应该知道兼并两个有序序列是一个 既便捷又高效 的操作：

一一遍历待兼并文件，将最小的键拷贝到输入文件即可。假设同一个键在多个文件中发生，则以写入期间比拟新的记载为准，其余均可摈弃。兼并后失掉的 SSTable文件，数据也是按键排好顺序的，而且重复键均已去重。

SSTable 文件保留某段期间内写入的数据，一个 SSTable 数据跟另一个比拟，要么较新，要么较旧。因此可以用这个个性启动去重，重复键以较新的SSTable 为准。

兼并时则必需保障 SSTable 是相邻的，否则就乱套了。假定有三个 SSTable ，按时段依次是 A 、B 、C ，其中 C 最新。假设先将 A 和C 兼并失掉 X ，就无法再跟 B 兼并了。由于 X 中的数据有的来自 A ，有的来自 C ，不好判别是比 C 新还是比 C 旧。

兼并操作十分高效，算法期间复杂度是 ，基本同等于将数据从源文件拷贝到指标文件即可。

读取待兼并文件时是 顺序读 ，写结果文件时又是 顺序写，对磁盘十分友好。文件系统可以先预读待兼并数据，而后缓存起来;又可以搜集待写入数据，而后再批量写;磁盘 IO 操作便清楚缩小。

兼并环节对内存要求极低，就算文件远远大于可用的物理内存也毫不碍事。

稠密索引

您或许会这么想，既然 SSTable 数据是有序的，查问时能否可以用 二分查找法 启动搜查呢?

虽然二分查找法的期间复杂度是 ，但对磁盘操作来说还不够好。由于磁盘十分慢，IO 操作应该尽或许地缩小，最好是只口头一次性 IO就能拿到数据。但二分查找要求口头 次 IO 操作，而且每次读取的位置都不一样，对磁盘很不友好。

既然不能用二分查找法间接搜查磁盘数据，那就只能在内存中保养数据索引了。

由于磁盘中的 SSTable 是按键排序的，咱们可以驳回 排序树(比如红黑树)来组织索引，这样可以允许范围查问。举个例子，查问键在 A 和 B之间的数据，可以先经过排序树索引，找到第一个大于等于 A 的数据的偏移量;再从该位置开局一一读取，直到数据键大于 B 。

实践上，内存索引没有必要蕴含所有的键，每隔必定距离挑一个键即可：

如上图，索引只蕴含局部键，大略呈平均散布。当咱们查问 bananas 时，咱们查找内存中的索引，并没有找到该键。虽然如此，咱们可以确定 bananas落在 banalize 和 bandboxy 这两个键之间。

因此，只需从 banalize 键偏移量开局，始终遍历数据即可。假设 SSTable 蕴含 bananas ，那咱们遍历大批数据后即可找到;假设不蕴含bananas ，咱们遍历到第一个比 bananas 大的键后即可中止。

稠密索引普通每隔若干 KB 数据才保养一个索引项，内存经常使用量大大降落，但查问时却要读取更少数据。

好在磁盘数据是按块读取的，就算数据不够一个块，也得整块读取;而且由于磁盘寻址的起因，读一块和若干块的期间差异其实很小。因此，就算查问时要求多读一些数据，对性能也不会发生太大的负面影响。

节俭磁盘带宽

由于查问时或许要求扫描两个索引项之间的所有数据记载(如上图阴影局部)，因此可以将它们组织成逻辑数据块，紧缩之后再写到磁盘，索引条目则指向每个紧缩块的扫尾。

由于相邻数据条目通常比拟相像，至少他们的键都有相反的前缀，因此紧缩后的尺寸能清楚降落。这一方面浪费了磁盘空间，另一方面则降落了磁盘 IO 带宽。

虽然紧缩、解紧缩要求消耗必定的 CPU 资源，好在 CPU 通常不是存储系统的重要瓶颈，磁盘 IO 才是。

因此，紧缩是一种典型的以期间换空间的技术选用，经过就义 CPU 资源来缓解带宽资源。在 Web畛域，主机也经常对数据启动紧缩，以浪费带宽资源，缩短传输期间。

LSM树

SSTable 查问体现不错，但数据库写操作必需是乱序的，怎么能力将数据排序保留呢?

在磁盘中保养排序结构倒也可行，B树( b-tree )就可以做到，但太复杂了。

假设是在内存里，事件就便捷多了。妇孺皆知，咱们有很少数据结构可供选用，比如 红黑树( red-black tree )和 AVL树。这些数据结构在乱序拔出的前提下，也能允许有序遍历。

这样一来，咱们可以这么设计：

写操作抵达后，将其保留到内存中的平衡树结构(比如红黑树)。这棵在内存中保养的平衡树称为 memtable 。

当 memtable 数据增长到达必定阈值(通常是若干 MB )，就将其转成 SSTable 文件并写到磁盘。由于 memtable平衡树数据是按键排序，转写环节很高效——中序遍历数据并顺序写到磁盘即可。

虽然 memtable 转写效率很高，还是会阻塞数据库写操作，不论期间多短。为了不阻塞写操作，咱们可以调配一个新的 memtable来写，而后在后盾缓缓转写旧的 memtable (如图阴影局部)。

那么，数据库读操作又该如何处置呢?您或许曾经想到答案了：咱们要求先查问 memtable ，而后再查问 SSTable 。再啰嗦一句， SSTable必需从数据最新的那个开局，一一查问。

那随着期间推移，SSTable 中应该会有不少被覆写或许删除的有效记载。这时，数据库可以在后盾对 SSTable启动兼并，以去除有效记载，浪费磁盘空间。于此同时，兼并操作也可以减低 SSTable 个数，提高查问效率。

操作日志

这个打算看起来不错，但您或许也发现一个疑问：假设数据库挂掉了，保留在 memtable 中的写操作不就丢了吗?

为了处置这个疑问，咱们可以在磁盘中保养一个日志文件，来记载写操作。每个写操作除了保留到 memtable 外，还要追加写到日志文件。这样就算memtable 因缺点失落了，也可以经过重放日志文件来重建。

留意到，日志文件中的数据是按写入期间排序的，而不是依照数据键排序的。不过不要紧，由于日志文件只是为了缺点时可以重建 memtable ，一旦memtable 耐久化到 SSTable，对应的日志文件就可以安保监禁了。

查问优化

LSM树 查问一个不存在的键或许很慢，由于数据库要审核一切 SSTable ，能力确定待查键不存在。假设 SSTable文件数量很多，查问效率必要求大打折扣。

为了优化这类查问，数据库通常会额外保养一个 布隆过滤器 ( bloom filter)。这样一来，查问时先审核布隆过滤器，假设确定待查键不存在，就不用审核 memtable 和 SSTable 了。

布隆过滤器可以 大抵 保养一个汇合，而且十分浪费内存。您可以将它当作一个不凡成功的汇合，可以查问一个元素能否在汇合内。大抵的意思是布隆过滤器或许会误判——查问存在而实践上不存在。但假设查问不存在，就必定是不存在的，不会误判。

总结

LSM树 索引长于键值对存储场景，在 LevelDB 和 RocksDB 等数据库外部均有运行。它的设计思绪很便捷：

驳回内存红黑树 memtable 保留最近写入的数据;

写 memtable 的同时，将操作日志写到磁盘，以便缺点复原;

活期将 memtable 数据刷到磁盘 SSTable ;

SSTable 数据曾经有序，配合稠密索引，撑持高效查问;

至此，咱们曾经把握了三种干流数据库索引技术中的两种，下节咱们将继续聊 B树 索引。