lance-format / lance-format/lance
Finger search for btree index usage
@jbapple is already working on this.
Since Sep 4, 2025.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
When searching a large target table with a sorted index, if the source keys being searched for are also sorted, it is not necessary to restart every search on the target with the full range of the index as a potential target. For instance, if you were looking for ["alpha", "bravo", "charlie"] in a sorted list of strings, after finding "alpha", you know that "bravo" cannot be in any of the slots before the slot in target which "alpha" was found.
This can be accomplished by doing an exponential search starting from the target's "alpha" slot until "bravo" is exceeded, then doing a binary search between the two bounding slots. In the literature on trees, this is sometimes called "finger search". It reduces the total search cost from O(x log(y)) to O(x log(y/x)).
This could potentially require changing BTreeLookup::tree away from a BTreeMap if some combination of nth, Cursor, etc. doesn't suffice in terms of API needed for finger search.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.