5 ms·
Is it me, or does the post not explain what the benefits are of a skiplist? Ok, maybe it's just "a here's how to implement" post, but seems strange.
by mbfg 4y ago
Is it me, or does the post not explain what the benefits are of a skiplist? Ok, maybe it's just "a here's how to implement" post, but seems strange.
- killingtime74 4y agoYou’re right it didn’t. I believe the main benefit vs binary search in arrays is that it’s linked list like nature makes insertion and removal Faster
- thesz 4y agoPlease consider COLA: http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/lec23.pdf http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/le... A hierarchy of sorted arrays, with merging when needed. Single access time is O(logN), scan is theoretically the fastest possible, inserts and deletes are also O(logN). Almost no pointer chasing.
- bodhiandphysics 4y agoSkip lists in practice are faster than balanced binary trees in insertion, since rebalancing is slow, while insert and delete in a sl are very fast (if you have a fast source of random or pseudorandom numbers). Skip list insertion is also very easily to parallelize. Insert on a bbt requires locking basically the whole tree.
- thesz 4y agoIf you can turn your keys into byte/bit sequences, and most of the time you can, you can use crit bit trees or binary Patricia trees. These are fast structures and support ordered traversal. They also do not rebalance and do not require locking the whole tree. Skip lists are built upon double linked lists, many of them. Parallelizing operations on double linked lists is not easy, it is quite easy to introduce potential deadlock.
- Tyr42 4y agoLooks like singlely linked lists in the linked article.
- thesz 4y agoDouble linked lists would help navigate quicker. But let's discuss why even skip list on even single linked lists is not that easy. The problem with double-linked lists modified in parallel is that one should lock at least two places where changes are performed. When you lock two things, you need an order between them on which to lock first. Otherwise, it is possible to introduce deadlocks - first actor needs A and B and locks A, second actor needs A and B and locks B. Crucial part here is the need to lock more than one object. If I understand skip lists correctly, it is possible to insert element into several lists at once. Thus, the need to work on more than one element. Thus, the possibility of deadlock that needs to be accounted for.
- dragonwriter 4y ago> Skip lists are built upon double linked lists, I've always seen them with singly-linked lists; double doesn't give an average or worst-case order improvement to anything, but it does make some ops faster within the same complexity class.
- thesz 4y agoOkay, skip lists are built upon singly-linked lists, but there are still need to lock more than one object to modify. The need to lock multiply objects at once is the potential source of deadlocks.
- AdamProut 4y agoI talked a bit about some of the advantages in this pretty old blog post: https://www.singlestore.com/blog/what-is-skiplist-why-skiplist-index-for-memsql/ https://www.singlestore.com/blog/what-is-skiplist-why-skipli... Simplicity is really the biggest advantage. Being simple, its much easier to implement a skiplist lock free vs other data structures. This helps it perform really well under highly concurrent point read and write workloads. Its not as good at scans, but if you really care about scan performance you should be using a columnstore layout (and not a tree).
- mbfg 4y agois the max tower height really just randomly determined, or is it fixed, or sized based on the total # of entries?
- kccqzy 4y agoIf we are going as far as using a source of randomness in our data structures, I think treaps are conceptually just as simple if not simpler, and I think is also easier to implement than skip lists.