Splay trees aren't a dynamic programming thing (and aren't used in any database storage backends I know of). They are, however, conjectured to be no more than a constant factor slower than a dynamically optimal binary search tree.

https://en.wikipedia.org/wiki/Optimal_binary_search_tree

> Splay trees aren't a dynamic programming thing

My mistake - I meant to write "dynamic optimality".

As for the "not used in any database storage backends", I have personally started experimenting with them due to higher-order effects they can provide relative to their optimization technique.

The fact that the most recently accessed node is always at the root also means that incremental tree updates are well-bounded in terms of # of nodes that would need to be rewritten to disk. This allows for much more efficient usage of storage-friendly things like append-only log structures.

Today I learned! That sounds fascinating; is there anything written down about it somewhere?

I actually don't think there is any specific reference I have ever encountered. It was something that just popped into my head one day when I was trying to figure out a way to write small batches of key-value data into a log.

Once you put 2+2 together on it, its like a lot of concepts seem to snap into place all at once. You also get incredible locality of access - each batch can sometimes fit within a single I/O block depending on system loading and data patterns, so traversing the tree to any node modified in the previous flush to disk would involve a single I/O.

Edit: If you search "splay tree append only log" on google, you will find one of my previous HN comments on the first page of results: https://news.ycombinator.com/item?id=28010167 This tells me there isnt much precedent for this idea.