Splay list

A splay list is a skip-list with adaptive rebalancing. Every key tracks how often it's been touched, and the structure periodically resets each node's height so that hot keys end up high in the tower and cold keys stay near the bottom. The effect is that a key with hit ratio p settles at depth log₂(1/p) instead of the uniform log₂(n) a plain skip list gives.

The name borrows from the splay tree, where accessed nodes get rotated toward the root. Skip lists don't rotate, so the analogous trick is to raise the node's tower instead. The 2020 paper from Aksenov et al. formalized the height update: a node with hit ratio u/T settles at height K − 1 − log₂(T/u), where K is the head's current height. A key accessed 50% of the time lives at depth 1; a key accessed 25% of the time at depth 2. The structure converges toward depth log(1/p) per-key automatically as the workload shifts.

The constant-factor improvement is real but bounded. A splay list isn't a B+tree — the cache-line layout is wrong, every level descent is a pointer chase, and the absolute search latency is still well above what an in-memory B+tree gives. The point is to skew the cost distribution: hot keys get a search depth proportional to how hot they are, instead of paying for the size of the whole structure.

In concurrent implementations the rebalance fires only on read-only paths (search, contains, position queries). Promoting a node that's about to be removed leaves dangling references at upper levels after EBR reclaims it, so the remove path skips rebalance entirely. The gregburd/skiplist library implements this as an opt-in SKIPLIST_SPLAY_REBALANCE flag, with a configurable rebalance interval (default: every 64 accesses).