Re:MIT’s Introduction to Algorithms, Lecture 12: Skip Lists ...
by aston on Friday October 17, 2008 @06:31AM
(#335470)
Skiplists are for most CS students their first and maybe only introduction to a data structure where the theoretical math comes out beautifully (impossibly?) small, and gets beaten by some variation of the binary tree if you actually try it in real life. There are a ton more, many of which I learned about from that same lecturer. Fun to talk about and toy with, but you'll never need Y-fast Tries in your day-to-day.
While skiplists are indeed simple to implement and do have log(n) average time for most operations, they're an example of theory and practice being the same in theory but not in practice.
The real-world performance of skiplists is worse than that of B-trees, especially when you have costly comparisons. They also don't maintain as much locality and will thrash the cache more.