About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Thu, 29 Nov 2007

B(something)-tree vs. RB-tree.

This simple benchmarks test btree vs rbtree search and insert speeds, when nodes are allocated in memory.
Btree is (likely) a b+tree where each data node is located at the bottom layer (probably it is a bit different, algorithm does not strickly follow rules described in btree papers. 1 million entries were inserted or searched in the tree.
Graphs below show speed of the given operation depending on number of keys in the btree node (when number of keys is smaller than 20 linear search ofthe key is used, otherwise binary search).



B(something)-0tree vs. RB-tree. Search speed.



B(something)-0tree vs. RB-tree. Insert speed.

As you see, btree search is about 2-2.5 times slower than rbtree. This can be clearly described by the fact, that rbtree contains data in each node, while btree only in the lowest nodes, so each btree search requires to travel over all layers (this is roughly equal to log2(number of keys in each node)) multiplied by number of keys in each node (in the worst case), while rbtree needs to perform the same amount of searches only in the worst case, while generally it requires about 2 times less traverses.

Btree insert speed can be even slightly faster than rbtree, since during insertion tree grows from low levels and each new allocation reserves space for several keys, thus greatly reducing number of needed splits or rotations.

I will run the same tests for the case, when all nodes are allocated from disk storage, which should show clear win of the btree approach.
Stay tuned.

/devel/fs :: Link / Comments (0)

Comments are closed for this story.