How cw key value storage works?
As mentioned before, the storage in Cosmos-SDK is based on a key-value store, where each value is saved under a key. The storage is structured using a tree model, specifically, the cosmos/iavl tree structure.
Here is an explanation of how key-value storage works:
This is a very simplified explanation to help you understand KV store iterators.
Letter inside circles are keys, and each key corresponds to a value.
Let's assume these are the saved key value pairs:
- J -> value1
- JF -> value2
- JPV -> value3
- JPVA -> value4
- JPVD -> value5
- JPVX -> value6
Retrieving a single value with a known key is a cheap operation, taking only O(1) time. But what if you need to iterate over keys? In this case, iteration can be done via prefixes.
- J key, prefixes: J
- JF key, prefixes: J, JF
- JPV key, prefixes: J,JP, JPV
- JPVA key, prefixes: J,JP, JPV, JPVA
- JPVD key, prefixes: J,JP, JPV, JPVD
- JPVX key, prefixes: J,JP, JPV, JPVX
range(J) returns all keys because all have J as prefix range(JF) returns only JF
This is where it gets interesting: range(JPV) returns JPV, JPVA, JPVD, JPVX in order As you can see J or JF is not returned, because values after JPV is requested.
But why JPVA returned?
Keys are saved to storage as fixed-length strings. For example, the representation of JPVA in storage (assuming keys are 8 characters long) would be JPVA0000. When a range request is made, the background process iterates over all keys from JPV00000 to JPVFFFFF, and JPVA (along with other keys) falls into this range. Additionally, a range query can be run in reverse.
These are the only two functionalities there are: get single value, iterate.
Most of the time complex relations between data structures must be established, but all we have this limited key value storage.
This is done by building indexes.