B-tree hinting?

leonardo · July 30, 2021, 8:09pm

Hi, I'm still alive There's a small discussion on HN:
https://news.ycombinator.com/item?id=28008541

About B-tree path hints:

tidwall/btree/blob/master/PATH_HINT.md

# 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

This file has been truncated. 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?

cuviper · July 31, 2021, 12:26am

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.