4

我正计划编写一个简单的键/值存储,其文件架构类似于 CouchDB,即仅附加的 b+树。

我已经阅读了在 B+trees 上可以找到的所有内容以及在 CouchDB 内部可以找到的所有内容,但是我没有时间研究源代码(使用非常不同的语言使其成为自己的权利)。

所以我有一个关于 B+tree 节点大小的问题,即:给定键长度是可变的,是保持节点相同的长度(以字节为单位)更好还是给它们相同数量的键更好/child-pointers,不管它们有多大?

我意识到在传统数据库中,B+tree 节点以字节为单位保持固定长度(例如 8K),因为数据文件中的空间是在固定大小的页面中管理的。但是在文档可以是任意长度并且更新的树节点被写入之后的仅附加文件方案中,具有固定大小的节点似乎没有优势。

4

1 回答 1

12

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

对于基于日志的存储方案,选择 4k 节点大小可能是最糟糕的选择,除非在日志中创建间隙以改进对齐。否则,99.98% 的时间一个节点存储在两个集群上。对于 2k 节点大小,发生这种情况的几率略低于 50%。但是,小节点存在一个问题:b-tree 的平均高度增加,读取磁盘集群的时间没有得到充分利用。

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

我花了一些时间对仅附加日志格式的 b-tree 实现进行原型设计,最终完全拒绝了这个概念。为了弥补由于节点/集群错位造成的性能损失,您需要有一个非常大的缓存。更传统的存储方法可以更好地利用 RAM。

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

BerkeleyDB-JE (BDB-JE) 也是基于日志的,我也研究了它的性能特征。它遇到了和我的原型一样的问题——垃圾的快速堆积。BDB-JE 有几个“更干净”的线程,它们将幸存的记录重新附加到日志中,但保留了随机顺序。结果,新的“干净”记录已经创建了充满垃圾的日志文件。系统的整体性能下降到唯一运行的就是清理程序,它占用了所有系统资源。

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

于 2010-12-25T04:16:45.253 回答