B+树节点大小

Question

我计划编写一个简单的密钥/值存储，其文件结构类似于CouchDB，即一个仅附加的b+tree。

我已经阅读了在B+trees上可以找到的所有内容，以及在CouchDB的内部文件中可以找到的所有内容，但是我还没有时间研究源代码(使用一种非常不同的语言，这本身就是一个特殊的项目)。

因此，我有一个关于B+tree节点大小的问题，即:给定密钥长度的是可变的，还是让节点保持相同的长度(以字节为单位)更好，还是给它们相同数量的键/子指针更好，而不管它们有多大？

我认识到在传统的数据库中，由于数据文件中的空间是在固定大小的页面中管理的，所以B+tree节点保持在一个固定的字节长度(例如8K)。但是，在仅附加文件的方案中，文档可以是任意长度，更新的树节点是在后面写入的，因此拥有一个固定大小的节点似乎没有好处。

Answer 1

B树的目标是最小化磁盘访问的次数.如果文件系统集群大小为4k，那么节点的理想大小是4k。此外，节点应该正确地对齐。一个不对齐的节点会导致两个集群被读取，从而降低性能。

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

较大的节点大小会降低树的高度，但也会增加磁盘访问的次数。较大的节点也增加了维护节点内条目的开销。假设有一个b树，节点大小足够大，足以封装整个数据库。您必须在节点本身内嵌入更好的数据结构，也许是另一个b树？

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

最后一个打击是当我评估随机顺序插入的性能时。这会降低任何磁盘支持的存储系统的性能，但是基于日志的格式会受到更多的影响。即使是最小项的写入也会迫使多个节点被写入日志，并且内部节点在被写入后不久就失效。结果，日志迅速地装满了垃圾。

BerkeleyDB(BDB)也是基于日志的，我也研究了它的性能特性。它遇到了和我的原型一样的问题--垃圾的快速堆积。BDB有几个“更干净”的线程，这些线程将幸存的记录重新附加到日志中，但是随机顺序被保留下来。因此，新的“干净”记录已经创建了满是垃圾的日志文件。系统的整体性能下降到了这样一个程度:运行的唯一东西是更干净的，而且它占用了所有的系统资源。

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