A similar idea is finger search (https://en.wikipedia.org/wiki/Finger_search), w... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		ntonozzi on July 30, 2021 \| parent \| context \| favorite \| on: B-tree Path Hints 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)).

namibj on July 30, 2021 | [–]

A related thing: exponential search. It's the sorted-array equivalent.

uyt on July 30, 2021 | [–]

I was going to link the same thing except I would say he is talking about exactly that without knowing the academic name for it.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact