B-tree Path Hints
In the mid 80s to 90s, there was a lot of interest around &quot;query responsive&quot; data structures. There still is, I&#x27;m sure, but that was what I studied and I&#x27;ve moved on since then.<p>Of these, the fibbonaci and pairing heaps were the most well known products, I reckon.<p>They essentially move &quot;Active&quot; parts of the data structure upwards near the top of the tree. The use case is different (being heaps), but I wouldn&#x27;t be surprised if that line of R&amp;D has continued, or if there&#x27;s a huge gap in performance that can be reclaimed with &quot;intelligent&quot; guesses like this one.<p>I&#x27;m rambling and conjecturing, but maybe someday branch prediction will get a huge boost to their already tangible smarts and we&#x27;ll see another explosion in practical CPU throughput, combined with a little help from algs and data structures, of course.