why does Aerospike choose to pick RB tree for Indexing instead of traditional b+ tree approach ?
B+ tree is a good choice if the index is on disk. It will result in less number of I/Os as the fanout is high and height of the tree will be less. You can walk the leaf nodes serially. Note that I am making a very generalized statement. There are many exceptions to it.
Our indexes are in memory, and we don’t really need all the properties of B+ tree. RB tree has a good average case behavior when there are whole bunch of inserts, deletes, and reads. The tree rebalancing cost is relatively cheap.
1 Like
True, But then why b+ tree for Secondary indexes ???
secondary index is not B+Trees, they are BTrees