Here are some of the differences
References
| Skiplist | Binary tree |
|---|---|
| Concurrency - Skip lists are more amenable to concurrent access/modification. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked. pressure. | The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. |
| Performance in concurrent applications - Locking skip lists are insanely fast. They scale incredibly well with the number of concurrent accesses. This is what makes skip lists special, other lock based data structures tend to croak under | Locking red-black trees croak under concurrent access. Their performance degrades linearly with each new concurrent user. Of the two known locking red-black tree implementations, one essentially has a global lock during tree rebalancing. The other uses fancy (and complicated) lock escalation but still doesn't significantly out perform the global lock version. |
| Easier to implement as it is just a list | Little complicated |
| Randomization effects - As insertions are based on flip of coin, it may result in badly balanced skiplist. Also, its not easy to write unit tests on them. | Tend to give fast results in any case as they are balanced. |
| Space usage - skip lists take more space than a balanced tree. I think a skip list takes 4 pointers per node on an average, which is twice as much as a tree. | Takes lesser space |
| locality of reference - skip lists are not cache friendly because they don't optimize locality of reference i.e. related elements tend to stay far apart and not on the same page. | This doesn't hold. |
| Available implementation - lack of available implementations. | There are far more optimized tree implementations than skip lists. |
References
0 comments:
Post a Comment