Hi, I'm still alive https://news.ycombinator.com/item?id=28008541
About B-tree path hints:
# 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
show original
That are in C++11 (I didn't know it) too (search for 'hint'):https://en.cppreference.com/w/cpp/container/map/insert
Is it a good idea to add similar methods to Rust stdlib BTreeMap/BTreeSet for hinting?
2 Likes
I could imagine something like this on Entry or the oft-proposed Cursor API. Internally, it could also help if the Extend implementation kept its own "hint" that incoming items might be somewhat sorted.
2 Likes
system
October 29, 2021, 12:27am
#3
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.
There's a small discussion on HN: