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.
When searching a large
targettable with a sorted index, if thesourcekeys being searched for are also sorted, it is not necessary to restart every search on thetargetwith 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 intargetwhich"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::treeaway from aBTreeMapif some combination ofnth,Cursor, etc. doesn't suffice in terms of API needed for finger search.