MIT's Introduction to Algorithms, Lecture 12: Skip Lists

You're viewing a comment by José Luis Campanello and its responses.

José Luis Campanello Permalink
July 16, 2009, 21:21

Oh, i've read that paper long time ago (it's from early 90s if i'm not wrong). Stunning data structure.

I had not seen the video, so perhaps what follows is on it:

It turns out that not only skip lists are simple to implement, they can can also be "easily" changed to support multiple readers/writers. The structure (with n sized next pointer buckets) and the statistical distribution of bucket size allows for "localized" pointer management, resulting in more granular changes, making many inserts local. Compare this with AVL trees, where local insertions can alter large portions of the tree.

I've read (some time ago) that many high performance databases (Oracle, for instance) have changed to use this data structure for many operations because of it's better multi-threaded properties.

If my memory is not wrong, you can search ACM digital library and many papers on skip lists will pop out in the results, including multiple writers analisys.

Cool blog, BTW.

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.