This file has been truncated. show original
# B-tree Path Hints
I use a thing I call path hints in my B-tree [C](https://github.com/tidwall/btree.c) and [Go](https://github.com/tidwall/btree) implementations. It's a search optimization.
## The B-tree
A standard [B-tree](https://en.wikipedia.org/wiki/B-tree) is an ordered tree-based data structure that stores its items in nodes. The B-tree has a single root node, which may have children nodes, and those children nodes may also have children nodes.
<img width="322" alt="image" src="https://user-images.githubusercontent.com/1156077/127664015-14ca38bb-1a3b-4d2f-80ff-27be0bd3d886.png">
Searching for items in a B-tree is fast. [O(log N)](https://en.wikipedia.org/wiki/Big_O_notation) to be exact.
This is because the [binary search algorithm](https://en.wikipedia.org/wiki/Binary_search_algorithm) is used.
A binary search works by first comparing the item at the middle-most index of the root node with the target item.
If the middle item is greater than the target item, then it divides the node in two and does the binary search on the left part of the node. If the middle is less, it searches the right part. And so on. If the target item is found, then the search stop. If the item is not found, then the search is passed to the child node at the appropriate index. This traversal terminates when item is found or there are no more child nodes.
<img width="600" alt="image" src="https://user-images.githubusercontent.com/1156077/127664822-6ab4f8f6-8ab5-477e-8e17-f52346f02819.png">
## The Path