alt Hacker NewsSkiplists are designed for fast intersection, not for single value lookup (assuming a sane design that's not based on linked lists, that's just an educational device that's never used in practice).
They are extremely good at intersections, as you can use the skip pointers in clever ways to skip ahead and eliminate whole swathes of values. You can kinda do that with b-trees[1] as well, but skip lists can beat them out in many cases.
It's highly dependent on the shape of the data though. For random numbers, it's probably an even match, but for postings lists and the like (where skiplists are often used), they perform extremely well as these often have runs of semiconsecutive values being intersected.
[1] I'll argue that if you squint a bit, a skiplist arguably is a sort of degenerate b-tree.
Replies
I don't understand how they differ in this regard from range trees, which they essentially are, just their method of construction is different.
Things like BSP trees are very good at intersections indeed, and have been used for things since time immemorial, but I think the skiplist/tree tradeoff is not that different in this domain.
Treaps can handle parallel set operations very efficiently:
Actually, prolly trees are probably best for intersections. You can use bloom filters as a first pass
B(+)Trees do actually admit a fast intersection (they offer a way more powerful projected-to-shared-keyspace mutual index join, technically it's even able to do antijoin but that'll actually modify iteration more than a very genericalized inner join; basically whenever you look at a key in any one of the involved indices you project it to a shared keyspace before doing the comparison-based-search things):
You get cache locality from the upper layers, and for navigation basically `let mut head = keyspace.min(); 'outer: while(!cursors[0].finished()){ for(&mut cursor in cursors.iter_mut()) { let new_head = cursor.seek_to_target_or_next_after_if_none_match(head); if (head != new_head) {continue 'outer; }} /* passed all without seeking past target on any one */ output_fun(head, cursors.iter().map(|x| x.val())); }`. If you want you can do the inner loop's seeks concurrently, which helps if those are IO latency bound and you can afford to waste absolute IOPS on eagerly doing that. You'll want to locally compute the max() of those returned and assign that to `head`. Imagine the cursors are lambda-parametrized to feel like they operate on the projected shared keyspace.
If the keys are a bitstring prefix suited to a binary prefix trie you can actually intersect that way, it's beyond worst case optimal when multiple key columns are involved. Sadly any simple implementation strategies of those algorithms have prohibitive external-memory-machine coefficients for their nominally poly-logarithmic IOPS, due to involvement of combinatorial explosion / curse of dimensionality in search tree/trie structures. They do work though. C.f. "Tetris-LoadBalanced"/"Tetris-Reordered".
The latter even tames one index containing "all" even numbers and the other "all" odd numbers, well, matters more if you involve 3+ columns :D