B+树节点大小

B树的目标是最小化磁盘访问的数量。如果文件系统群集大小为4K,则节点的理想大小为4K。此外,节点应正确对齐。不对齐的节点将导致读取两个集群,从而降低性能。

对于基于日志的存储方案,选择4K节点大小可能是最糟糕的选择,除非在日志中创建间隙以改进对齐。否则,99.98%的时间一个节点存储在两个集群上。当节点大小为2K时,发生这种情况的几率只有50%以下。但是,有一个小节点大小的问题:B树的平均高度增加了,读取磁盘群集所花费的时间没有被充分利用。

较大的节点大小会降低树的高度,但也会增加磁盘访问的数量。较大的节点也会增加维护节点内条目的开销。设想一个B-树,其中节点大小足以封装整个数据库。您必须在节点本身中嵌入一个更好的数据结构,也许是另一个B树?

我花了一些时间在只附加日志格式上构建了B树实现的原型,最终完全拒绝了这个概念。为了补偿由于节点/集群错位而造成的性能损失,您需要有一个非常大的缓存。更传统的存储方法可以更好地利用RAM。

最后一次打击是我评估随机排列的插入物的性能。这会降低任何磁盘备份存储系统的性能,但基于日志的格式会受到更大的影响。即使是最小条目的写入也会强制将多个节点写入日志,并且内部节点在写入后不久就会失效。结果,日志很快被垃圾填满。

BerkeleyDB-je(bdb-je)也是基于日志的,我也研究了它的性能特点。与我的原型一样,它也面临着同样的问题——垃圾的快速堆积。bdb-je有几个“cleaner”线程,它们将保留的记录重新附加到日志中,但保留了随机顺序。因此,新的“干净”记录已经创建了满是垃圾的日志文件。系统的整体性能下降到只有更干净的系统才能运行,而且它占用了所有系统资源。

基于日志的格式非常有吸引力,因为可以快速实现一个健壮的数据库。阿基里斯之踵更干净,这是不平凡的。缓存策略也很难纠正。