3 ms·
Skiplists are my favorite data structure. There are a few use cases that they can't satisfy, but for the typical memory-bound key-value store application, it's
by bob1029 5y ago
Skiplists are my favorite data structure. There are a few use cases that they can't satisfy, but for the typical memory-bound key-value store application, it's a very simple & effective approach.
If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet.
- valbaca 5y agoI'm sure online resources abound...but do you have a favorite descriptor or implementation of them? Or a particular use-case?
- bob1029 5y agoI've used indexed skiplist implementations in DIY database projects. The idea was to first build a super fast K/V store (i.e. to memory+disk), and then build skiplists on top of that for tying together collections of indexed data. The problem with skiplists is that they kinda suck when used directly with mutable block storage. There is no way to do incremental updates like with a splay tree where you can write just the diff (a modified sub-tree and a new root node) to the end of a contiguous log file.
- codr7 5y agoLinks to efficient implementations would be much appreciated. 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.
- bob1029 5y agoYou can do probabilistic inserts which should ensure the # of levels scales appropriately with the quantity of data. The probability factor can be a simple constant or some linear function of the quantity and/or index #.
- tsumnia 5y ago> 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".
- lqr 5y agoGeometrically-growing arrays (std::vector) and hash tables also have amortized O(1) insertion complexity. They are some of the most widely-used data structures of all. I agree that amortized guarantees can be a problem in certain applications, but it seems that programmers are happy to accept them most of the time.
- tsumnia 5y agoTrue, I think it's more that skiplists are both amortized and (taught to) expand randomly unless you dig deeper into optimizing the structure. I think with regard to hash tables, the annoyance of hashing is overlooked due to the simplicity of the algorithm. 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.
- uyt 5y agoYou can check out redis's implementation: https://github.com/redis/redis/blob/unstable/src/t_zset.c https://github.com/redis/redis/blob/unstable/src/t_zset.c Or leveldb's: https://github.com/google/leveldb/blob/master/db/skiplist.h https://github.com/google/leveldb/blob/master/db/skiplist.h
- milofeynman 5y agohttps://blog.discord.com/using-rust-to-scale-elixir-for-11-million-concurrent-users-c6f19fc029d3 https://blog.discord.com/using-rust-to-scale-elixir-for-11-m... Not an implementation, but a very fun explanation, that you could definitely implement if desired.
- MatteoFrigo 5y agoIf you are a fan of skip lists, you may want to look into treaps as well. "Treap" is a portmanteau of "tree" and "heap": it is a binary search tree with respect to the search key, and it is a heap in another random or quasi-random quantity such as a hash of the key. Treaps have essentially all the properties of skip lists, and they are even simpler to implement. 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.
- mamcx 5y ago> If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet. 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" So this flip the rows into columns but for a smallish batch. Probably making locks expensive but never have implemented this stuff.
- jasonwatkinspdx 5y agoI don't know about splay trees specifically, but the combination of an in memory index structor and append only log persistence has been a common theme in recent database research. Microsoft's bw-tree, a derivative of which powers CosmosDB is one example (though it uses a lock free hash table instead of a splay tree or similar).
- bob1029 5y agoThe reason for the splay tree is because of their dynamic programming properties. When combined with an append-only log, you are naturally pushing the most frequently utilized information to the front, and letting older items fall to the back of the log. 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.
- jasonwatkinspdx 5y agoI can see how that'd be very effective for a cache, but I'm not at all seeing how it'd work for a database. You'd need to touch all live data to copy it forward and keep track of the low water mark before you truncate the prefix of the log. That'd have horrific write amplification.