Byzantine Reality

Searching for Byzantine failures in the world around us

Skip Lists

One of the billion books I’ve been reading lately is Pragmatic Thinking and Learning. And it’s been really good so far. But as I’m not done reading it yet, I’m not ready to really review it. But one of the exercises in the book led me down the path of today’s exercise. The book tells you to go look at Oblique Strategies and keep in mind whatever advice it gives you. It’s more of a problem solving strategy for when you get in a rut, and I got something to the effect of this:

Try to focus on something unimportant.

With that in mind, I looked at the traffic for my blog. Since an odd amount of traffic has been coming from reddit, I figured I’d see if there were any interesting programming articles on it. The only one I ended up finding on the main page was an article on skip lists. The more interesting part of it is actually the video at the bottom of the page, which links to the MIT lecture on the topic. Check it out if you’ve got half an hour and want to refresh your programming knowledge.

The basic motivation for skip lists is that many types of trees are too difficult to implement properly in a short amount of time, so why not use a linked list with some optimizations? Skip lists give you fast search, insert, and delete times (just as fast as treaps and b-trees) but are far less complicated. The downside is that skip lists take more storage (twice as much), but are way less complicated.

Although it’s something you probably won’t have to implement for your job or the like, it’s a really cool concept and I’m surprised I never came across it until now. Check it out, or at least the Wikipedia summary of it.