Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Skip Lists Done Right

ticki.github.io

Post reply on HN
Print view View original

81–87 of 87 posts

Re: Skip Lists Done Right

#81

Post by kazinator »

OskarS wrote: post #24
airesQ wrote: post #18

Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. Recently I got rid of huge bottleneck on an oldish piece of software by moving from a vanilla linked list to a skip list. And I did do many things suggested in the article (e.g. having a vector of fixed length for the pointers, and thus a fixed tallness). Funnily enough, for my case, I managed to do without a RNG just fine. I just…

> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is t…

Another consideration regarding memory: a binary tree with no parent pointers has two pointers per node. (Traversal then needs temp space due to to recursion or iteration with explicit stack.)

However, a binary tree can be traversed in O(n) in both directions.

A skip list with a singly-linked level zero cannot be traversed in reverse.

If we make it doubly linked to meet the requirement for reverse traversal then ... it has two pointers per node and then some. There goes your storage advantage.

Re: Skip Lists Done Right

#82

Post by sobani »

kazinator wrote: post #81
OskarS wrote: post #24

Earlier quoted context omitted.

> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is t…

Another consideration regarding memory: a binary tree with no parent pointers has two pointers per node. (Traversal then needs temp space due to to recursion or iteration with explicit stack.) However, a binary tree can be traversed in O(n) in both directions . A skip list with a singly-linked level zero cannot be traversed in reverse. If we make it doubly linked to meet the requirement for reverse traversal then ...…

Actually, you can. As per the article, you can view the skiplist as a tree when turned 1/8th.

So you can start at the head, put it on the stack, move to the next node referenced at the hightest level, put it on the stack, etc. just like you can start from the top of the tree, put it on the stack, move right, put it on the stack, etc.

The advantage of the skiplist over the tree is that you can traverse forward in O(1) space. But both are equally bad in reverse

Re: Skip Lists Done Right

#83

Post by cronjobber »

qwertyuiop924 wrote: post #77
andars wrote: post #64

Earlier quoted context omitted.

> ... just, you know ... you know ... Yes, I know. Do you? You made the suggestion that skip lists are inferior to ordered lists, not me. (good for "increasing access times on ordered lists") I'm still perplexed as to your rationale for that statement.

No, I didn't, AFAIK. I'm baffled as to where you drew that from...

Maybe because you wrote "increasing access times", which could be read as "skip lists are slower." Not what you meant, probably.

Re: Skip Lists Done Right

#84

Post by andars »

cronjobber wrote: post #83
qwertyuiop924 wrote: post #77

Earlier quoted context omitted.

No, I didn't, AFAIK. I'm baffled as to where you drew that from...

Maybe because you wrote "increasing access times", which could be read as "skip lists are slower." Not what you meant, probably.

This was my understanding of that comment. How else could that be read? I am not able to think of another interpretation of that statement or a context when increased access times would be desired.

Re: Skip Lists Done Right

#85

Post by qwertyuiop924 »

andars wrote: post #84
cronjobber wrote: post #83

Earlier quoted context omitted.

Maybe because you wrote "increasing access times", which could be read as "skip lists are slower." Not what you meant, probably.

This was my understanding of that comment. How else could that be read? I am not able to think of another interpretation of that statement or a context when increased access times would be desired.

The intended interpretation is that skip lists make access to specific items in ordered lists faster.

I am actually a native speaker, so I have no excuse here. I just suck at writing, I guess...

Re: Skip Lists Done Right

#86

Post by brongondwana »

ComputerGuru wrote: post #7
brongondwana wrote: post #6

Looks like I already do pretty much all those things in twoskip: https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip... (except for the level choice. Which is a bit meh to me, because a write will probably trigger 3 fsyncs, so the cost of level choice is very low) That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk.

>That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk. What will you use instead (and why)?

Sorry I didn't get back to this.

It's a virtual linear log file which gets split occasionally by appending a sorted list of pointers to the end and "closing" that log file, along with occasional tasks repacking the log files together.

Individual records (either key/value or key/tombstone) have a pointer showing how far back they cast a "shadow" so you know how long you need to keep tombstones for.

Since only the active log file can ever have changes made, you can repack any two adjacent files together into a single compacted log file at any time, removing any duplicates or tombstones that don't cast a shadow outside the range being compacted.

Re: Skip Lists Done Right

#87

Post by brongondwana »

rawnlq wrote: post #17
ComputerGuru wrote: post #7

Earlier quoted context omitted.

>That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk. What will you use instead (and why)?

B-trees, LSM trees, or any data structure that's actually designed to be cache friendly. I think his claim that his optimizations can beat a b-tree is bullshit otherwise he would've shown benchmarks.

I haven't written it yet. I suspect I can't beat b-tree in entirely random read workloads.
Post reply on HN