[mike_hearn]

RocksDB and other LSM tree backed databases do have cheap deletes and updates, although you could argue that's because they make everything else expensive. If you have spare cores it can be a good trade though.