If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet.
One way to look at treaps is to start with a skip list. A skip list has variable-size nodes, which is kind of annoying. If you transform the variable-size node into a linked list, you end up with something that is essentially a binary tree, but now you have redundant information in multiple tree nodes. If you remove all redundancy you get the treap. This is not how one usually thinks of treaps, and it is not how they were invented, but it's good to be aware of the correspondence.
For a given set of keys and hash function, the treap is effectively unique (unlike binary search trees) irrespective of the insertion order, which is sometimes a good property to have.
Anyone actually use this combo (I don't know much about this) that show is good?
---
If I were to build a rdbms today, and not for OLAP but OLTP, is this a good combination? I have imagine building my relational language about this stuff, and have wondered if building a paged "columnar" layout could be the best:
DeletedBitArray(00100100...)
Page1(SizeOfBlock) =
col1 = 1, 2, 3,
col2 = "hello" "cruel" "world"
Page2(SizeOfBlock) =
col1 = 1, 2, 3,
col2 = "hello" "cruel" "world"
All you have to do to keep an item alive is to access it using a splay tree. Cleanup is as simple as deciding how many older log segment files to chop.
In practical use cases you generally don't even have to worry about potential downsides. The sequential integer insert thing giving you log(N) is so rare. Most live systems are touching tons of items in arbitrary order so the probabilities work themselves out.
This is already happening as a natural part of the utilization patterns. Just looking at something in a splay tree will cause it to be relocated to the root (the most live part of the log). That is the dynamic part of the data structure. You are doing a huge part of the GC effort simply by reading the database.
There are clearly applications where this would not be a good fit (i.e. data warehousing where you want to keep old shit on purpose). Even with the natural cleanup mechanism, you may still need to save stuff you haven't accessed in a while. Linked list nodes built on top being an example of an area that would need careful attention to avoid chopping up data structures unexpectedly.
>That'd have horrific write amplification.
This is precisely why I recommend batching as part of the approach in my original post above. With batching, you can take a total rewrite of all nodes in a linked list and squeeze them into a single I/O operation that flows into exactly the # of storage blocks required. In implementations without batching, you are talking about block I/O per linked list node that needs updating. Clearly this is a total non-starter for drive lifetime & performance.
I've played around with the idea but eventually settled on binary searched arrays for the small stuff and red/black trees for the rest.
One thing that bothers me about skiplists is having a static number of levels, which will either be too few or too many for most situations.
You should be inserting a new level whenever you add an element to the highest. I like skiplists, they're fun to teach but I'd say the part that irks me the most is their O(log n) is through "amortization", or sometimes its a long search, sometimes its a short search, so it "averages out in the end".
From a purely academic side, its difficult to explain why you'd use one data structure over another. We can say THIS structure has an O() for THIS operation, but its often at the tradeoff of another operation. Then it comes down to ease of implementation, where I'd say skiplists have a harder time explaining vs. hashing.
Or leveldb's: https://github.com/google/leveldb/blob/master/db/skiplist.h
Not an implementation, but a very fun explanation, that you could definitely implement if desired.