[RiverBucketShoe]

Splay trees: https://en.wikipedia.org/wiki/Splay_tree recently searched items are always near the top.

[jonstewart]

Nuts! I was going to say splay trees. Completely silly these days, like most trees, given caching hierarchies and bursty memory accesses, but a really neat data structure all the same.