As a result, the log rapidly fills up with garbage.īerkeleyDB-JE (BDB-JE) is also log based, and I studied its performance characteristics too. A write of even the smallest entry forces several nodes to be written to the log, and the internal nodes are invalidated shortly after being written.

This kills performance of any disk-backed storage system, but log based formats suffer much more. The final blow was when I evaluated the performance of randomly-ordered inserts. A more traditional storage approach can make better use of the RAM. To compensate for performance losses due to node/cluster misalignment, you need to have a very large cache. I spent some time prototyping a b-tree implementation over an append-only log format and eventually rejected the concept altogether. You have to embed a better data structure within the node itself, perhaps another b-tree? Imagine a b-tree where the node size is large enough to encapsulate the entire database. Larger nodes also increase the overhead of maintaining the entries within the node. Larger node sizes reduce the height of the tree, but they too increase the number of disk accesses.

However, there's a problem with a small node size: average height of the b-tree is increased and the time spent reading a disk cluster is not fully utilized. With a 2k node size, the odds of this happening are just under 50%. Otherwise, 99.98% of the time one node is stored on two clusters.

With a log based storage scheme, choosing a 4k node size is probably the worst choice unless gaps are created in the log to improve alignment. A misaligned node will cause two clusters to be read, reducing performance.

Also, the nodes should be properly aligned. If the file system cluster size is 4k, then the ideal size for the nodes is 4k. The goal of a b-tree is to minimize the number of disk accesses.

Tree size disk