When to choose RB tree, B-Tree or AVL tree?

Question

As a programmer when should I consider using a RB tree, B- tree or an AVL tree? What are the key points that needs to be considered before deciding on the choice?

Can someone please explain with a scenario for each tree structure why it is chosen over others with reference to the key points?

Solution 1

Take this with a pinch of salt:

B-tree when you're managing more than thousands of items and you're paging them from a disk or some slow storage medium.

RB tree when you're doing fairly frequent inserts, deletes and retrievals on the tree.

AVL tree when your inserts and deletes are infrequent relative to your retrievals.

Solution 2

In memory B-Tree has the advantage when the number of items is more than 32000... Look at speedtest.pdf from stx-btree.

Comments

[pschang]

Just to add some more detail: B-trees can have variable number of children which allow it to hold many records but still maintain a short height tree. RB Tree has less strict rules around rebalancing which make insertions/deletions quicker than AVL tree. Conversely, AVL tree is more strictly balanced so lookups are faster than RB tree.

[Dan Bechard]

To be fair, OP asked when should I consider using, not when should I consider implementing. While the last paragraph is true, it doesn't provide much value in the context of this question. Even with libraries, you need to understand the algorithms in order to effectively choose which structure best suits your business needs.

[Admin]

RB trees also have better performance O(1) on the rebalance which makes them more suitable for persistent datastructures with roll-back and roll-forward.