07 | NoSQL检索：为什么日志系统主要用LSM树而非B+树？
该思维导图由 AI 生成，仅供参考
如何利用批量写入代替多次随机写入？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
LSM树（Log Structured Merge Trees）是一种适用于日志系统和大数据应用场景的存储结构和检索技术。相比于传统的B+树，LSM树通过延迟写磁盘、批量写入、WAL技术和滚动合并等机制，解决了频繁写入和系统崩溃恢复的问题，从而提高了性能。LSM树的设计思路和优化方案使得数据存储和检索更加高效，适用于大规模数据的持续生成和频繁写入的场景。 LSM树的检索过程包括对C0和C1树的查询。C0树存储最新的数据，适合针对近期数据的高效检索；而C1树则用于存储历史数据。在查询过程中，系统会先在C0树中查询，如果未找到则转向C1树。对于C1树中的过期数据，系统采取延迟写入和批量操作的方式进行处理，以提高检索效率。 LSM树相对于B+树具有三个特点：将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并；采用批量写入和预写日志WAL技术保证内存数据在系统崩溃后可以被恢复；数据采取类似日志追加写的方式写入磁盘，以提高写入效率。这些特点使得LSM树在写入性能上有显著提升，适用于写大于读的应用场景，尤其在日志系统和监控系统等领域。 LSM树的优势使其成为许多NoSQL系统的检索引擎，并且在工业界得到广泛应用。对LSM树的优化进一步提升了检索性能。通过深入了解工业界中实际使用的LSM树的实现，读者可以更全面地认识LSM树的特点和应用。 文章中提到了LSM树的设计思路和优化方案，以及其在写入性能上的显著提升，适用于写大于读的应用场景。同时，还介绍了LSM树的检索过程和优化特点，为读者提供了对LSM树的深入了解和认识的机会。
《检索技术核心 20 讲》，新⼈⾸单¥59
全部留言(34)
- 最新
- 精选
xzy请问，如果wal所在的盘和数据在同一个盘，那怎么保证wal落盘是顺序写呢，我理解也得寻道寻址作者回复: 你这个问题很好！我提炼出来有三个点: 1.wal的日志文件能否保证在物理空间上是顺序的? 这个是可以做到的。日志文件都是追加写模式，包括可以提前分配好连续的磁盘空间，不受其他文件干扰。因此是可以保证空间的连续性。 2.wal的日志文件和其他数据文件在一个磁盘，那么是否依然会面临磁头来回移动寻道寻址的问题? 这个问题的确存在，如果日志文件和数据文件在同一个盘上，的确可能面临一个磁头来回移动的情况。因此，尽量不要在一个磁盘上同时开太多进程太多文件进行随机写。包括你看lsm的写磁盘，也是采用了顺序写。 3.如果第二个问题存在，那么wal依然高效么？ wal依然是高效的。一方面，如果是wal连续写(没有其他进程和文件竞争磁头)，那么效率自然提升；另一方面，往磁盘的日志文件中简单地追加写，总比处理好数据，组织好b+树的索引结构再写磁盘快很多。
2020-04-10224
兰柯一梦感觉取决于系统需要提供什么样的功能，如果系统需要提供高效的查询不需要范围scan那么C0用hashmap都可以，如果需要scan那么平衡树或者skiplist比较合适。leveldb是使用skiplist来实现的，这里的checkpoint主要目的是定期将数据落盘后用来对log文件进行清理的，使得系统重启时不需要重放过多的log影响性能作者回复: 你说的很对，取决于使用场景。有的系统的确是使用哈希表的。还有使用红黑树和跳表的都有。
2020-04-1021
innocent为了性能内存中的树至少有两棵吧作者回复: 你提到了性能问题，的确是这样的。在高性能的lsm树实现中，不仅仅是内存中要有两棵，磁盘上还要有多棵。 具体工业界是怎么真正实现一个高性能的lsm树，后面我会再具体介绍。
2020-04-11210
Joe Black请问WAL文件有什么特殊之处吗？还是说就是一个以append only方式打开的文件？写入日志后，是否每次都要同步到磁盘呢？如果不同步，那可能只在操作系统页面缓存吧？一断电不就也没了？另外老师说可以提前给日志文件分配空间，这个是具体怎么分配呢？seek过去写一下再seek回去吗？作者回复: 你思考得很细致。关于wal技术，我补充一下: 1.wal文件自身是个普通的文件。不过在如何处理这个文件上，也有一些特殊的方案。比如说预分配空间，就是为了保证这个文件在物理上是连续的，提高写入效率。预分配空间可以使用fallocate来实现。 此外，为了避免不停的删除旧数据，追加新数据造成的文件操作性能问题，wal文件采用的是“循环写”机制。就是讲文件看着是一个循环数组，如果写入到文件尾了，那么就回到文件头继续写(前提是文件前面的数据已经被处理，标为无效)。 2.wal文件的写入其实也是批量写，而不是每来一条记录就直接写磁盘。因此的确有可能出现wal文件也是不完整的现象。如果连wal文件都没有记录下来的数据，那么就是会丢失的数据。当然，wal文件会尽可能地完成文件落盘，而不是像c0树会在内存中保存那么久才落盘。
2020-05-239- taotaowang有个疑问想请教老师 Lsm树读写性能都优于B+树，那关系型数据库为什么不采取这种数据结构存储呢？
作者回复: 你的问题很好！进行对比和分析是很好的学习了解知识点的方式。 lsm不是没有缺点的，它的读效率会比较差，并且存在写放大问题。这是因为，为了保证内存数据能高效写入磁盘(具体我会在17讲中分析)，其实磁盘上是有多棵树(c1树到ck树)，而不是只有一棵c1树。这会造成一次写操作会被放大n倍的问题。并且在查询的时候，如果查询数据不是最近的数据，那么会多次查询磁盘上的多棵树，使得lsm树的查询性能没有b+树好。这也是为什么它更适合用在写多读少的日志或监控系统中的缘故。 另一方面，其实现在的b+树的工业实现也会借鉴lsm树的一些设计思想来提高效率。比如使用wal+内存来提高检索效率，然后在修改叶子节点的时候也是批量操作。如果两个新数据都是写入同一个叶子节点，那么效率就会比原先的每个数据修改一次叶子节点效率更高。
2020-04-298 - xzy你好，这里还有个问题：如果是ssd，顺序写和随机写的差异不大，那么是否还有必要写wal， 毕竟写wal相当于double写了数据，那直接就写数据是否性能还会更好呢
作者回复: 这是一个好问题！对于SSD，这些理论和方法是否依然有效?答案是yes。 考虑这么两点: 1.SSD是以page作为读写单位，以block作为垃圾回收单位，因此，批量顺序写性能依然大幅高于随机写！ 2.SSD的性能和内存相比依然有差距，因此，先在内存处理好，再批量写入SSD依然是高效的。
2020-04-108 
奕当内存的C0 树满时， 都要 把磁盘的 C1 树的全部数据 加载到内存中合并生成新树吗？ 我感觉这样性能不高啊。 还有就是 类型日志系统，都是天然按照时间排序；这样的话 ，就可以直接把 C0 树的叶子节点直接放到 C1 树的叶子节点后面啊，没有必要在进行合并生成新树了作者回复: 你提了一个非常好的问题！把c1树的全部叶子节点处理一次的确效率不高，因此实际上会有多棵不同大小的磁盘上的树。包括工业界还有其他的优化思路。后面会介绍。 此外，直接把c0树的叶子节点放在c1树后面，这样的话叶子节点就不是有序的了，就无法高效检索了。
2020-04-1027
快跑随着越来越理解B+树和LSM树， B+树是写入的时候就找好key的位置，读取的时候直接根据索引查找key的值 LSM是写入是可能一个key存在不同层的树上，读取的时候，需要合并key不同树上的值。 相当于B+树是写入时merge，LSM是读取时候merge作者回复: 总结得很好，所以你会看到，不同的设计其实有不同的取舍，这些取舍就会导致它们的特性和适用场景不同。
2021-02-256- 奕填充块写满了，我们就要将填充块作为新的叶节点集合顺序写入磁盘， 这个时候 填充快写的磁盘位置会是之前C1 叶子节点 清空块的位置吗？ 还是另外开辟有个新的空间，当新的树生成后，在把旧的C1树 磁盘数据空间在标记为删除？
作者回复: 是新的磁盘空间。因为c1树要保证在磁盘上的连续性，如果是利用原c1树的旧空间的话，可能会放不下(因为合并了c0树的数据)。
2020-04-106 
峰考虑的点 1 随机和顺序存取差距不大 2 什么样的有序结构适合高并发的写入 对于2，必须插入的时候只影响局部，这样上锁这样开销就只在局部细粒度上，如果是树可能存在需要调整树高的各种旋转或者分裂合并操作。对于1，在说不用像b树那样降低树高，底层数据节点搞比较大的块，可以充分利用指针这种随机读取的力量，当然块太小有内存碎片之类的问题，以及jvm老年代跨代引用新生代之类问题，所以hbase中跳表的实现是基于chunk的。 感觉自己好像逻辑不是很通，自己还想的不够透彻，其实也在思考全内存的数据库和基于b树这样的数据库在它的缓存可以容纳全部块，不用换入换出，这两种情况下全内存数据库的优势在哪里。作者回复: 全内存数据库的确是一个研究热点。Redis的广泛流行也是这个潮流的一个例子。 b+树即使能全部缓存到内存中，但你思考一下它插入删除的效率(分裂合并节点)，它不会比红黑树这些结构效率高。因此，纯内存的环境下，红黑树和跳表这类结构更受欢迎。
2020-04-104