There are a lot of fun twists on this idea that are floating around. A few databases based on Bw-Trees (sled, OpenBw-Tree) have iterators just cache the last tree node locally to avoid any index traversal while zipping through the tree sequentially.
The actual benefit is workload-dependent for most types of index-lookup caching. 5% perf hit on a miss is actually a fairly significant cost for this kind of structure, and if access patterns tend to traverse different children from the root onward most of the time, it will be a net negative. Non-test datasets tend to dwarf those used by engineers while tuning their systems most of the time, and the larger the dataset, the worse the hit for random-access workloads. The question that interests me is how to dynamically detect access patterns that would justify certain types of lookup optimizations, and do them in a way that still plays nicely with memory reclamation and correctness requirements for the overall system.
I’m actually implementing a b-tree storage manager right now. One of the things I realized only after writing the search and mutation code, and moving on to cursors, is that it makes a lot of sense to put the former inside the latter — that is, make search/insert/delete be operations on cursors.
Partly this is because my cursor class stores its path: a list of (page#, key index) pairs leading from the root to the current position.
So in my code as of yesterday, the BTree methods find, insert and remove are just trivial wrappers around the corresponding Cursor methods. The BTree object keeps a Cursor instance that it delegates these to. Or of course the application code can create and call it’s own Cursor instances.
In a lot of ways this is like having the user keep a cursor object around, since a cursor remembers its path (see my other comment.) The difficulty would be for the library keep a cursor’s state up to date when modifications are made to the tree not using that cursor.
It’s like a cursor, but it’s still only a hint. The DB is free to ignore it as soon as it determines that it’s wrong.