3 ms·

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

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 https://en.wikipedia.org/wiki/Optimal_binary_search_tree

bob1029 5y ago
> 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.
- pjscott 5y ago
  Today I learned! That sounds fascinating; is there anything written down about it somewhere?
  - bob1029 5y ago
    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 https://news.ycombinator.com/item?id=28010167 This tells me there isnt much precedent for this idea.

bob1029 5y ago

> 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.

pjscott 5y ago
Today I learned! That sounds fascinating; is there anything written down about it somewhere?
- bob1029 5y ago
  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 https://news.ycombinator.com/item?id=28010167 This tells me there isnt much precedent for this idea.