The Regular B-tree

The B-tree is for some queer reasons seldom used as a in-memory applications. Too bad, because it’s a good one. I’m talking primarily about the B-tree that stores small, fixed size items in fixed size nodes. Such a structure lacks the generalist character of, say, BSTs, but when it matches the task it can be several times faster while using several times less memory.

Back in the day I’ve decided I’ll write myself such a B-tree. Rightly or wrongly, at that time I felt I did not like how the data structure shifts half a node for an average insertion and so I wrote a B-tree that doesn’t do that.

Couple of years later I’ve learned there were other B-trees for in-memory use and I thought of comparing mine with them. A couple of designs were floating around, one called “google” for reasons, the other “STX” (probably they did not like what STD typically means).

I tried the two and I’ve discovered they needed tweaking to render best results on my machine. I’ve also played with my design, trying various types of intra node searching — binary and linear.

The plot below shows the random insertions times I got. Mind you, it’s a very old plot. Ten years old or older and indicative of the machine I was using then.

There are two “google” and “STX” lines, correspond the original and tweaked flavors. There’s the blue line showing the node binary search version of my design, the gray line showing non root node binary search and root node linear search version and the green linear search version.

The figure shows the comparative insertion times and it’s the only interesting one. The three designs are far better matched in the search time and indistinguishable in memory usage.

I have compared the B-trees with other data structures at the time — again, many years have passed since then.

Here’s the hash table plot:

The hash set was not exactly faster, while using notable more memory.

There was a better data structure, one that still is very good, though not used as much as it should be. The Judy array.

I imagine the spikes are Judy transitioning between its many trie node coding classes.

The Judy integer set is very good in space too, it can beat the B-trees handily, though unlike for B-trees, the memory foot print is very dependent on input.