上次分享了hash索引实现的存储引擎，它总是对数据文件不断追加写操作，就像写日志一样。在这种日志结构的存储引擎中，数据记录的顺序由写入时间决定，具有相同键的旧记录被新记录替换。写入数据时，SSTable会自动分文件。数据库需要在后台合并文件，减少文件数量，加快查询速度。如果要合并的文件中的数据是有序的，我们可以使用合并排序算法来提高合并效率。虽然这看起来违背了顺序写的原则，但是还是有办法解决的，后面会介绍。现在，我们把数据文件的格式改成这样：①文件中的所有记录都按照键（key）排序；②排序保证每个key在文件中只出现一次，不会有重复的旧记录。我们把这种格式的排序字符串表（sortedstringtable）简称为SSTable。与普通的日志结构数据文件相比，SSTable有几个明显的优势：高效的合并如果你学过合并排序算法，你应该知道合并两个有序的序列是一个简单高效的操作：遍历要合并的文件一个一个,并将最小的密钥复制到输出文件中。如果同一个key出现在多个文件中，则以写入时间较新的记录为准，其他的可以丢弃。合并后得到的SSTable文件中，数据也进行了key排序，对重复的key进行了去重。SSTable文件保存的是某一段时间内写入的数据，一个SSTable的数据与另一个SSTable的数据进行比较，要么新，要么旧。所以这个特性可以用来去重，duplicatekey是基于较新的SSTable。合并的时候一定要保证SSTables是相邻的，不然会乱的。假设有3个SSTable，按照时间段分别是A、B、C，C是最新的。如果先把A和C合并得到X，就不能再和B合并了。因为X中的数据一部分来自A，一部分来自C，所以很难判断它比C新还是旧。合并操作非常高效，算法的时间复杂度为，基本上相当于将数据从源文件复制到目标文件。读要合并的文件时是顺序读，写结果文件时是顺序写，对磁盘非常友好。文件系统可以先预读要合并的数据，然后缓存；也可以收集要写入的数据，然后批量写入；磁盘IO操作显着减少。合并过程对内存的要求非常低，即使文件比可用物理内存大得多也是如此。稀疏索引你可能会这样想，既然SSTable的数据是有序的，那么查询的时候能不能用二分查找的方式来查找呢？虽然二分查找法的时间复杂度为，但对于磁盘操作来说还不够好。由于磁盘很慢，所以要尽量减少IO操作，最好只进行一次IO就可以拿到数据。但是二分查找需要进行IO操作，每次读取的位置都不一样，对磁盘很不友好。由于二分查找法不能直接查找磁盘数据，只能在内存中维护数据索引。由于磁盘中的SSTables是key排序的，我们可以使用排序树（比如红黑树）来组织索引，可以支持范围查询。比如查询key在A和B之间的数据，可以先用排序树索引找到第一个大于等于A的数据的偏移量；然后从这个位置开始一个一个读取，直到datakey大于B。事实上，内存索引并不需要包含所有的键。隔一定距离挑一个key即可：如上图所示，索引只包含一些key，大致均匀分布。当我们查询bananas时，我们查找内存中的索引并没有找到键。尽管如此，我们可以确定bananas介于键banalize和bandboxy之间。因此，只需从banalize键偏移量开始并遍历数据。如果当前SSTable中包含bananas，我们遍历少量数据就可以找到；如果不包含bananas，遍历到第一个比bananas大的key就可以停止了。稀疏索引一般每几KB的数据只维护一个索引项，这样可以大大减少内存占用，但查询时需要读取更多的数据。幸运的是，磁盘数据是按块读取的。即使一个块的数据不够，也必须读取整个块；而且由于磁盘寻址的因素，读取一个block和读取几个block的时间差其实很小。因此，即使查询时需要读取更多的数据，也不会对性能造成很大的负面影响。节省磁盘带宽由于查询时可能需要扫描两个索引条目之间的所有数据记录（如上图阴影部分），可以将它们组织成逻辑数据块，压缩后写入磁盘，索引条目指向每个压缩块的开始。由于相邻的数据条目通常是相似的，至少它们的键具有相同的前缀，因此可以显着减小压缩后的大小。这样一方面节省了磁盘空间，另一方面降低了磁盘IO带宽。虽然压缩和解压需要占用一定的CPU资源，但幸运的是，CPU通常不是存储系统的主要瓶颈，磁盘IO才是。因此，压缩是一种典型的时间换空间的技术选择，通过牺牲CPU资源来缓解带宽资源。在Web领域，服务器经常对数据进行压缩，以节省带宽资源，缩短传输时间。LSMtreeSSTable查询性能不错，但是数据库写操作一定是乱序的，数据怎么排序保存？维护磁盘中的排序结构也是可行的，B树（b-tree）可以做到，但是上去太复杂了。如果是在内存中，事情就简单多了。众所周知，我们有很多数据结构可以选择，比如红黑树（red-blacktree）和AVL树。这些数据结构在乱序插入的前提下也可以支持有序遍历。这样，我们就可以这样设计：写操作到来后，在内存中保存成一个平衡树结构（比如红黑树）。这种在内存中维护的平衡树称为内存表。当memtable数据的增长达到一定的阈值（一般是几MB），就会转换成SSTable文件写入磁盘。由于memtable平衡树数据是key排序的，所以传输过程非常高效——只需按顺序遍历数据，顺序写入磁盘即可。虽然memtable的传输效率很高，但是不管时间多短，它仍然会阻塞数据库的写操作。为了不阻塞写操作，我们可以分配一个新的memtable来写，然后在后台慢慢的转移旧的memtable（如阴影部分）。那么，数据库读取呢？您可能已经有了答案：我们需要先查询memtable，然后再查询SSTable。说得更冗长，必须从最新的数据开始，一条一条地查询SSTable。随着时间的推移，SSTable中应该会有很多无效的记录被覆盖或者删除。这时数据库可以在后台合并SSTables，去除无效记录，节省磁盘空间。同时合并操作也可以减少SSTable的数量，提高查询效率。操作日志方案看起来不错，但是你可能也会发现一个问题：如果数据库挂了，memtable中保存的写操作不会丢失吗？为了解决这个问题，我们可以在磁盘上维护一个日志文件，来记录写操作。每个写操作除了保存到memtable之外，还会附加到日志文件中。这样，即使memtable因故障丢失，也可以通过重放日志文件来重建。请注意，日志文件中的数据按写入时间排序，而不是按数据键排序。不过没关系，因为日志文件只是用来在失败的情况下重建memtable。一旦将memtable持久化到SSTable中，就可以安全地释放相应的日志文件。查询优化的LSM树查询不存在的键可能会很慢，因为数据库必须检查所有SSTables以确定要查找的键不存在。如果有大量的SSTable文件，查询效率肯定会大大降低。为了优化此类查询，数据库通常维护一个额外的布隆过滤器（bloomfilter）。这样查询的时候先检查Bloomfilter，如果确定要检查的key不存在，就不需要检查memtable和SSTable了。布隆过滤器可以粗略地维护一个集合并且非常节省内存。你可以把它看成是一个有特殊实现的集合，你可以查询某个元素是否在集合中。粗略地说，就是布隆过滤器可能会误判——查询不存在时就存在。但查询不存在，则一定不存在，不会出现误判。小结LSM树索引擅长键值对存储场景，应用于LevelDB、RocksDB等数据库。它的设计思路很简单：使用内存红黑树memtable来保存最近写入的数据；将操作日志与memtable同时写入磁盘，便于故障恢复；定期flushmemtable数据到磁盘SSTable；SSTable数据已经有序，稀疏索引支持高效查询；至此，我们已经掌握了三种主流数据库索引技术中的两种，下一节继续讲B树索引。
