B-tree Path Hints
It's a cool idea, but you have to keep in mind that binary searches are not optimal for b-tree nodes unless the node is really big. If you have a smaller node, < 32 or 64 elements, a simple linear search is faster. The reason has something to do with processor cache, branch mis-prediction, and pipelining.<p>A linear search can also be optimized to use SIMD, which is a big win.<p>If you really want to use a path hint, you could just say "start my linear search at the point where I left off last time", and if the first element is too big, wrap around to the beginning. But that might not buy you much.