Also, you have to be paying one hell of a compaction penalty if this isn't a grow-only dataset. By ordering your keys you're at least minimizing the overhead of compaction on write by utilizing the happy-path for how LevelDB moves data out of the write buffer and into the SSTs.

But deletes are going to have a big impact still, and (working from my failing memory of LevelDB internals) I think might actually be the pathologically sad case.