Skip Lists Done Right
ticki.github.io
Skip Lists Done Right
1–10 of 87 posts
Re: Skip Lists Done Right
#2Excellent article, I really love algorithm and datastructure.
if anyone else is interested like me, I recommend this book
https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...
Re: Skip Lists Done Right
#3Excellent article, I really love algorithm and datastructure. if anyone else is interested like me, I recommend this book https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...
It is also very handy if you need to flatten a small (< 2 kg) household pet.
Re: Skip Lists Done Right
#4Re: Skip Lists Done Right
#5> I can't seem to find my favorite trick: deterministic (ie. without rng) skipping by linking on traversal instead of insert/delete.
Says one comment. Can anyone explain that?
Re: Skip Lists Done Right
#6Looks 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.
Re: Skip Lists Done Right
#7Looks 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)?
Re: Skip Lists Done Right
#8[deleted]
Re: Skip Lists Done Right
#9Excellent article, I really love algorithm and datastructure. if anyone else is interested like me, I recommend this book https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...
It is also very handy if you need to flatten a small (< 2 kg) household pet.
> It is also very handy if you need to flatten a small (or your ego :)