[bza]

> As for writes, a new key could go anywhere in the index

This forces index tree rebalancing to occur on many (even most) writes, which is hugely detrimental to performance.

[lmm]

Which tree structure is this for? Many tree structures (e.g. the classic red-black tree) perform much better (doing less rebalancing) for randomized inserts than for ordered ones.