Comparing complexity of a BTree index to an SSTable index(Cassandra)

When we compare a BTree index to an SSTable index, we should consider the write complexity:

• When writing randomly to a copy-on-write BTree, we will incur random reads (to do the copy of the leaf node and path). So while the writes my be sequential on disk, for datasets larger than RAM, these random reads will quickly become the bottle neck. For a SSTable-like index, no such read occurs on write - there will only be the sequential writes.
• We should also consider that in the worse case, every update to a BTree could incur log_b N IOs - that is, we could end up writing 3 or 4 blocks for every key. If key size is much less than block size, this is extremely expensive. For an SSTable-like index, each write IO will contain as many fresh keys as it can, so the IO cost for each key is more like 1/B.

In practice, this make SSTable-like thousands of times faster (for random writes) than BTrees.

We should also re-consider we read costs. We are correct than a BTree is O(log_b N) random IOs for random point reads, but a SSTable-like index is actually O(#sstables . log_b N). Without an decent merge scheme, #sstables is proportional to N. There are various tricks to get round this (using Bloom Filters, for instance used in Cassandra)