Currently IAVL does not take advantage of data locality on disk. The way IAVL store nodes on disk is with a hash that gets stored in a random location on disk and makes it so that IAVL needs to do a random search of disk in order to find the data. With the recent work from osmosis on fast node we saw a large performance improvement with a trade off on writes.

Secondly, there are two key formats, live keys and orphan keys referenced by node hash which also indexes the orphan nodes.

A next step would be to modify IAVL to structure data on disk in a logical manner to reduce random searches and reduce random compaction of disk data.

There are two things that can be done in order to take advantage of this.

Work Scope:

Phase 1:

• modify the key format from a hash of the data to be write_version|node_path_in_tree.

Phase 2:

• make every node store the version of its children.
• remove orphan indexing and hashes

(Proposed by @ValarDragon)