A similar idea is finger search (https://en.wikipedia.org/wiki/Finger_search), where you can turn a traversal of a tree from O(log(number of items in the tree)) into O(log(number of items between the finger and the key)).