Indexing Mechanism in AeroSpike



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.


True, But then why b+ tree for Secondary indexes ???


secondary index is not B+Trees, they are BTrees


@nOOb to be clear, secondary indexes are in-memory as well.