search

CosmWasm / storey

Experimental storage abstractions for blockchain key-value stores
Apache License 2.0
5 stars 1 forks source link

Allow accessing column entry by position #65

Open webmaster128 opened 1 month ago

webmaster128 commented 1 month ago

Right now, column entries can only efficiently be accessed by the auto-incrementing ID (called "key" and "ix" in code). This is nice as it allows creating append focussed maps much easier to use than today.

However, this does not allow for selecting a random element. If you know len(), and you want to get an item between 0 and len()-1, you don't know which ID to look for. In order to serve a large number of use cases from the NFT space, we should add both efficient access by ID as well as efficient access by position. This then makes the following operations fast:

In order to allow implementing that, we need some sort of secondary index.

I'm not quite sure how to effiently implement that. The challenge is somewhat similar to implementing LinkedList::get in Java. This guy recommends "some sort of tree". The best model I found so far to make that happen is a Skip List, especially "Indexable skiplist".

uint commented 1 month ago

That's all good.

I'm wondering if it would make sense to step back, write down a list of use cases, look at it, and then figure out if we want one or more separate abstractions for them.