Allow accessing column entry by position
- Dominant language
- Rust
- Stars
- 6
- Forks
- 3
- PR merge metrics
- No merged PRs in 30d
Description
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:
- get first element
- get last element
- get nth element
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](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#get-int-) in Java. [This guy recommends](https://www.quora.com/In-linked-list-data-structures-should-there-be-a-way-to-access-elements-by-index) "some sort of tree". The best model I found so far to make that happen is a [Skip List](https://en.wikipedia.org/wiki/Skip_list), especially "Indexable skiplist".
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by locating the column-entry implementation and its existing key/ix access paths, then trace how length and positional lookup would relate. Compare the proposed secondary-index approaches, including an indexable skip list, against efficient first-, last-, and nth-element access while preserving ID access. Done means the issue's required positional operations are implemented efficiently alongside ID lookup.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100