b-tree 的目标是最小化磁盘访问次数。如果文件系统集群大小为 4k,则节点的理想大小为 4k。此外,节点应正确对齐。未对齐的节点将导致读取两个集群,从而降低性能。
对于基于日志的存储方案,选择 4k 节点大小可能是最糟糕的选择,除非在日志中创建间隙以改进对齐。否则,99.98% 的时间一个节点存储在两个集群上。对于 2k 节点大小,发生这种情况的几率略低于 50%。但是,小节点存在一个问题:b-tree 的平均高度增加,读取磁盘集群的时间没有得到充分利用。
较大的节点大小会降低树的高度,但也会增加磁盘访问的次数。较大的节点也会增加维护节点内条目的开销。想象一个节点大小足以封装整个数据库的 b 树。您必须在节点本身中嵌入更好的数据结构,也许是另一个 b-tree?
我花了一些时间对仅附加日志格式的 b-tree 实现进行原型设计,最终完全拒绝了这个概念。为了弥补由于节点/集群错位造成的性能损失,您需要有一个非常大的缓存。更传统的存储方法可以更好地利用 RAM。
最后一击是我评估随机排序刀片的性能时。这会降低任何磁盘支持的存储系统的性能,但基于日志的格式会受到更多影响。即使是最小条目的写入也会强制将多个节点写入日志,并且内部节点在写入后不久就会失效。结果,日志迅速被垃圾填满。
BerkeleyDB-JE (BDB-JE) 也是基于日志的,我也研究了它的性能特征。它遇到了和我的原型一样的问题——垃圾的快速堆积。BDB-JE 有几个“更干净”的线程,它们将幸存的记录重新附加到日志中,但保留了随机顺序。结果,新的“干净”记录已经创建了充满垃圾的日志文件。系统的整体性能下降到唯一运行的就是清理程序,它占用了所有系统资源。
基于日志的格式非常有吸引力,因为它可以快速实现一个健壮的数据库。阿喀琉斯之踵是更清洁的,这是不平凡的。缓存策略也很难正确。