But I’ve actually tried to use splay trees in production code. The performance benefits versus a simple Patricia tree seemed totally absent in actual practice even for things like very frequent adjacent queries. The structure is neat but paying attention to memory layout and cache line size is far, far more important.
>paying attention to memory layout and cache line size is far, far more important.
Totally agree. For scenarios where I know I am going to have fewer than ~100k of something (assume an array of structs), I typically just do a linear scan over memory. If its a bunch of objects in memory or a cold access to storage, the trees become far more practical.
From what I can gather on your comment, it seems that if you are given a splay tree, and a batch of transactions i.e.
GET 1
SET 10 "hello"
GET 15
Correct, but the whole idea is that over time the same subset of hot nodes is going to trickle to the top of the tree, so you are just rewriting node offsets in your temporary list as you process the batch. A node may be logically modified 100x per batch, and only written to storage once.