作者回复: 你提到了性能问题,的确是这样的。在高性能的lsm树实现中,不仅仅是内存中要有两棵,磁盘上还要有多棵。
具体工业界是怎么真正实现一个高性能的lsm树,后面我会再具体介绍。
作者回复: 你说的很对,取决于使用场景。有的系统的确是使用哈希表的。还有使用红黑树和跳表的都有。
作者回复: 你这个问题很好!我提炼出来有三个点:
1.wal的日志文件能否保证在物理空间上是顺序的?
这个是可以做到的。日志文件都是追加写模式,包括可以提前分配好连续的磁盘空间,不受其他文件干扰。因此是可以保证空间的连续性。
2.wal的日志文件和其他数据文件在一个磁盘,那么是否依然会面临磁头来回移动寻道寻址的问题?
这个问题的确存在,如果日志文件和数据文件在同一个盘上,的确可能面临一个磁头来回移动的情况。因此,尽量不要在一个磁盘上同时开太多进程太多文件进行随机写。包括你看lsm的写磁盘,也是采用了顺序写。
3.如果第二个问题存在,那么wal依然高效么?
wal依然是高效的。一方面,如果是wal连续写(没有其他进程和文件竞争磁头),那么效率自然提升;另一方面,往磁盘的日志文件中简单地追加写,总比处理好数据,组织好b+树的索引结构再写磁盘快很多。
作者回复: 全内存数据库的确是一个研究热点。Redis的广泛流行也是这个潮流的一个例子。
b+树即使能全部缓存到内存中,但你思考一下它插入删除的效率(分裂合并节点),它不会比红黑树这些结构效率高。因此,纯内存的环境下,红黑树和跳表这类结构更受欢迎。
作者回复: 很好!你提到了bitcask,它是用哈希表作为内存索引的。其他的一些nosql实现,还有选择红黑树和跳表的。因此你会发现,对于内存中高效检索的技术选型,不同应用会根据自己的需求,选择我们在基础篇介绍过的适用技术。
作者回复: 1.check point的信息是独立存在的,和wal的日志文件是不同文件。
2.check point的触发条件可以有多个,比如说间隔时长达到了预定时间,比如说wal文件增长到一定程度,甚至还可以主动调用check point相关命令强制执行。
作者回复: 这是一个好问题!对于SSD,这些理论和方法是否依然有效?答案是yes。
考虑这么两点:
1.SSD是以page作为读写单位,以block作为垃圾回收单位,因此,批量顺序写性能依然大幅高于随机写!
2.SSD的性能和内存相比依然有差距,因此,先在内存处理好,再批量写入SSD依然是高效的。
作者回复: 你提了一个非常好的问题!把c1树的全部叶子节点处理一次的确效率不高,因此实际上会有多棵不同大小的磁盘上的树。包括工业界还有其他的优化思路。后面会介绍。
此外,直接把c0树的叶子节点放在c1树后面,这样的话叶子节点就不是有序的了,就无法高效检索了。
作者回复: 是新的磁盘空间。因为c1树要保证在磁盘上的连续性,如果是利用原c1树的旧空间的话,可能会放不下(因为合并了c0树的数据)。
作者回复: 在内存数据库里面,Redis是一个典型的代表,它的确就是使用跳表的。
另外两点:
1.b+树块内的查找,可以使用二分查找,而不是顺序查找,这样能加快检索效率。
2.你说的是否“c0和c1树写错”的地方,这个的确没有写错哦,你可以仔细想一想,为什么c1树有这个特点“叶子节点是全满的”。
作者回复: 是的。如果你有关注一些内存数据库,你会发现,有好些是使用跳表和红黑树来实现的。比如Redis。
可见,b+树不是万能的。我们理解了存储介质的特性以后,能帮助我们在合适的场景做出正确的技术选型。