Is it possible to use a flat structure storage in the Runtime?

Question

The Runtime storage in Substrate is based on a tree structure rather than a flat structure. While this allows for efficient integrity verification, it incurs data retrieval overhead. According to the documentation:

Accessing trie data is costly. Each read operation takes O(log N) time, where N is the number of elements stored in the trie. To mitigate this, we use a key-value cache.

To optimize data retrieval, I'm interested in exploring alternative storage approaches. Specifically:

• Is it possible to use a flat structure storage in the Runtime? If so, what are the necessary steps to implement it?
• Are there any other recommended approaches or strategies to improve data retrieval performance in Substrate?

I appreciate any insights, recommendations, or references regarding alternative storage options and techniques to improve data retrieval efficiency in Substrate's Runtime storage.

Answer 1

Most of the merklized structures I can think of, are usually based on multiple nodes linked/hashed together with no cycle (tree, patricia trie, or mmr). Meaning that runtime like the ones produce by cumulus it will be difficult or a rather big change.

Note that some key value indexing for key value database are not flat but also log(N), eg for paritydb we got a hashmap like indexing (this one is flat but I don't know how to define a merkle proof for it), but also a btree indexing. One possibility to improve perf would be to attach the merklized info directly into the db indexing.

There may be some way to produce proof based on different crypto, but that is a lot out of my scope and I guess would be not straight forward to integrate with substrate (we use different merkle state structure at different chain height as a way to maintain history of state).

Edit: can also envision some head of chain direct key value db storage like ethereum snapshot, but it only cover part of the use case (read access when syncing).