Benchmarks, doing range scans of 10.000 keys on databases with 1 million and 10 million keys:

For these database sizes, B-trees have a speedup of 2-3 orders of magnitude. More importantly, and as expected, the old map-based database has a dependence on the number of keys in the database while B-trees do not.

The tradeoff is that read/write operations are three times more costly, but I think that's well worth it.

I ran some Cosmos SDK benchmarks using the B-tree MemDB, via make test-sim-benchmark. These used SIM_NUM_BLOCKS=250, SIM_BLOCK_SIZE=200, and LevelDB with pruning strategies PruneNothing (persist every version to disk) and PruneSyncable (persist every 100 blocks to disk). I believe the SDK currently uses PruneSyncable by default.

It appears that IAVLs use of MemDB in PruneSyncable mode, as a temporary working set that's periodically flushed to disk, does not trigger the slow path in MemDB. It is unclear why, but appears to be related to cleanup of orphaned nodes, which possibly hits LevelDB instead of MemDB. In this case the new B-tree appears to have a slight slowdown, as expected. However, when we use MemDB as the main database we do hit the slow path, and the B-tree version is five times faster.

Overall memory usage is about the same in both cases.