Jump to content

Skip list: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Improve existing references (no substantive change)
m Indexable skiplist: Fix link to A Skip List Cookbook
 
(93 intermediate revisions by 58 users not shown)
Line 1: Line 1:
{{Short description|Probabilistic data structure}}
{{Infobox data structure
{{Infobox data structure
|name=Skip List
| name = Skip list
|type=List
| type = List
|invented_by=[[William Pugh|W. Pugh]]
| invented_by = [[William Pugh (computer scientist)|W. Pugh]]
|invented_year=1989
| invented_year = 1989
| space_avg = <math>O(n)</math>
|
| space_worst = <math>O(n\log n)</math><ref name="cs.uwaterloo">{{cite thesis |title=Skip Lists and Probabilistic Analysis of Algorithms |first=Thomas |last=Papadakis |type=Ph.D. |year=1993 |publisher=University of Waterloo |url=http://www.cs.uwaterloo.ca/research/tr/1993/28/root2side.pdf}}</ref>
|space_avg=O(n)
| search_avg = <math>O(\log n)</math>
|space_worst=O(n log n)<ref name="cs.uwaterloo">{{cite thesis |title=Skip Lists and Probabilistic Analysis of Algorithms |first=Thomas |last=Papadakis |type=Ph.D. |year=1993 |publisher=University of Waterloo |url=http://www.cs.uwaterloo.ca/research/tr/1993/28/root2side.pdf}}</ref>
| search_worst = <math>O(n)</math><ref name="cs.uwaterloo" />
|search_avg=O(log n)
| insert_avg = <math>O(\log n)</math>
|search_worst=O(n)<ref name="cs.uwaterloo" />
| insert_worst = <math>O(n)</math>
|insert_avg=O(log n)
| delete_avg = <math>O(\log n)</math>
|insert_worst=O(n)
| delete_worst = <math>O(n)</math>
|delete_avg=O(log n)
|delete_worst=O(n)
}}
}}
{{Probabilistic}}
{{Probabilistic}}
In [[computer science]], a '''skip list''' is a [[data structure]] that allows fast search within an [[ordered sequence]] of elements. Fast search is made possible by maintaining a [[linked list|linked]] hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one. Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally we are searching in the full sequence. The elements that are skipped over may be chosen probabilistically <ref name="pugh">{{Cite journal | doi = 10.1145/78973.78977| title = Skip lists: A probabilistic alternative to balanced trees| journal = [[Communications of the ACM]]| volume = 33| issue = 6| pages = 668| year = 1990| last1 = Pugh | first1 = W. | authorlink1 = William Pugh| url = ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf}}</ref> or deterministically,<ref>{{cite conference |url=http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf |title=Deterministic skip lists |last1=Munro |first1=J. Ian |authorlink1=Ian Munro (computer scientist) |last2=Papadakis |first2=Thomas |last3=Sedgewick |first3=Robert |authorlink3=Robert Sedgewick (computer scientist) |date=1992 |publisher=Society for Industrial and Applied Mathematics, Philadelphia, PA, USA |book-title=Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92) |pages=367–375 |location=Orlando, Florida, USA |doi=10.1145/139404.139478}}</ref> with the former being more common.
In [[computer science]], a '''skip list''' (or '''skiplist''') is a [[Randomized algorithm|probabilistic]] [[data structure]] that allows <math>O(\log n)</math> [[Average-case complexity|average complexity]] for search as well as <math>O(\log n)</math> average complexity for insertion within an [[ordered sequence]] of <math>n</math> elements. Thus it can get the best features of a sorted [[Array data structure|array]] (for searching) while maintaining a [[linked list]]-like structure that allows insertion, which is not possible with a static array. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one (see the picture below on the right). Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally searching in the full sequence. The elements that are skipped over may be chosen probabilistically<ref name="pugh">{{Cite journal | doi = 10.1145/78973.78977| title = Skip lists: A probabilistic alternative to balanced trees| journal = [[Communications of the ACM]]| volume = 33| issue = 6| pages = 668–676| year = 1990| last1 = Pugh | first1 = W. | s2cid = 207691558| author-link1 = William Pugh (computer scientist) | url = ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf}}</ref> or deterministically,<ref>{{cite conference |url=https://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf |title=Deterministic skip lists |last1=Munro |first1=J. Ian |author-link1=Ian Munro (computer scientist) |last2=Papadakis |first2=Thomas |last3=Sedgewick |first3=Robert |author-link3=Robert Sedgewick (computer scientist) |date=1992 |publisher=Society for Industrial and Applied Mathematics, Philadelphia, PA, USA |book-title=Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92) |pages=367–375 |location=Orlando, Florida, USA |s2cid=7477119}}</ref> with the former being more common.


== Description ==
== Description ==
[[File:Skip list.svg|thumb|400px|A schematic picture of the skip list data structure. Each box with an arrow represents a pointer and a row is a [[linked list]] giving a sparse subsequence; the numbered boxes at the bottom represent the ordered data sequence. Searching proceeds downwards from the sparsest subsequence at the top until consecutive elements bracketing the search element are found.]]
[[File:Skip list.svg|thumb|400px|A schematic picture of the skip list data structure. Each box with an arrow represents a pointer and a row is a [[linked list]] giving a sparse subsequence; the numbered boxes (in yellow) at the bottom represent the ordered data sequence. Searching proceeds downwards from the sparsest subsequence at the top until consecutive elements bracketing the search element are found.]]


A skip list is built in layers. The bottom layer is an ordinary ordered [[linked list]]. Each higher layer acts as an "express lane" for the lists below, where an element in layer ''i'' appears in layer ''i''+1 with some fixed probability ''p'' (two commonly used values for ''p'' are 1/2 or 1/4). On average, each element appears in 1/(1-''p'') lists, and the tallest element (usually a special head element at the front of the skip list) in all the lists. The skip list contains <math>\log_{1/p} n\,</math> lists.
A skip list is built in layers. The bottom layer <math>1</math> is an ordinary ordered [[linked list]]. Each higher layer acts as an "express lane" for the lists below, where an element in layer <math>i</math> appears in layer <math>i+1</math> with some fixed probability <math>p</math> (two commonly used values for <math>p</math> are <math>1/2</math> or <math>1/4</math>). On average, each element appears in <math>1/(1-p)</math> lists, and the tallest element (usually a special head element at the front of the skip list) appears in all the lists. The skip list contains <math>\log_{1/p}n\,</math> (i.e. logarithm base <math>1/p</math> of <math>n</math>) lists.


A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most 1/''p'', which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total ''expected'' cost of a search is <math>(\log_{1/p} n)/p,\,</math> which is <math>\mathcal{O}(\log n)\,</math> when ''p'' is a constant. By choosing different values of ''p'', it is possible to trade search costs against storage costs.
A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most <math>1/p</math>, which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total ''expected'' cost of a search is <math>\tfrac{1}{p}\log_{1/p}n</math> which is <math>O(\log n)\,</math>, when <math>p</math> is a constant. By choosing different values of <math>p</math>, it is possible to trade search costs against storage costs.


=== Implementation details ===
=== Implementation details ===
[[File:Skip list add element-en.gif|thumb|Skip list add element-en|400px|Inserting elements to skip list]]
[[File:Skip list add element-en.gif|thumb|400px|Inserting elements into a skip list]]
The elements used for a skip list can contain more than one pointer since they can participate in more than one list.
The elements used for a skip list can contain more than one pointer since they can participate in more than one list.


Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list.
Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list.


<math>\mathcal{O}(n)</math> operations, which force us to visit every node in ascending order (such as printing the entire list), provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to <math>\mathcal{O}(\log n)</math> search time. (Choose the level of the i'th finite node to be 1 plus the number of times we can repeatedly divide i by 2 before it becomes odd. Also, i=0 for the negative infinity header as we have the usual special case of choosing the highest possible level for negative and/or positive infinite nodes.) However this also allows someone to know where all of the higher-than-level 1 nodes are and delete them.
<math>O(n)</math> operations, which force us to visit every node in ascending order (such as printing the entire list), provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to <math>O(\log n)</math> search time. (Choose the level of the i'th finite node to be 1 plus the number of times it is possible to repeatedly divide i by 2 before it becomes odd. Also, i=0 for the negative infinity header as there is the usual special case of choosing the highest possible level for negative and/or positive infinite nodes.) However this also allows someone to know where all of the higher-than-level 1 nodes are and delete them.


Alternatively, we could make the level structure quasi-random in the following way:
Alternatively, the level structure could be made quasi-random in the following way:


make all nodes level 1
make all nodes level 1
j ← 1
j ← 1
'''while''' the number of nodes at level j > 1 '''do'''
'''while''' the number of nodes at level j > 1 '''do'''
'''for''' each i'th node at level j '''do'''
'''for''' each i'th node at level j '''do'''
'''if''' i is odd
'''if''' i is odd '''and''' i is not the last node at level j
'''if''' i is not the last node at level j
randomly choose whether to promote it to level j+1
'''else if''' i is even '''and''' node i-1 was not promoted
randomly choose whether to promote it to level j+1
promote it to level j+1
'''else'''
do not promote
'''end if'''
'''end if'''
'''repeat'''
j ← j + 1
'''else if''' i is even and node i-1 was not promoted
promote it to level j+1
'''end if'''
'''repeat'''
j ← j + 1
'''repeat'''
'''repeat'''


Like the derandomized version, quasi-randomization is only done when there is some other reason to be running an <math>\mathcal{O}(n)</math> operation (which visits every node).
Like the derandomized version, quasi-randomization is only done when there is some other reason to be running an <math>O(n)</math> operation (which visits every node).


The advantage of this quasi-randomness is that it doesn't give away nearly as much level-structure related information to an [[Adversary (online algorithm)|adversarial user]] as the de-randomized one. This is desirable because an adversarial user who is able to tell which nodes are not at the lowest level can pessimize performance by simply deleting higher-level nodes. (Bethea and Reiter however argue that nonetheless an adversary can use probabilistic and timing methods to force performance degradation.<ref>{{cite conference |first1=Darrell |last1=Bethea |first2=Michael K. |last2=Reiter |title=Data Structures with Unpredictable Timing |url=https://www.cs.unc.edu/~djb/papers/2009-ESORICS.pdf#page=5 |at=pp. 456–471, §4 "Skip Lists" |doi=10.1007/978-3-642-04444-1_28 |conference=ESORICS 2009, 14th European Symposium on Research in Computer Security |location=Saint-Malo, France |date=September 21–23, 2009 |isbn=3-642-04443-3}}</ref>) The search performance is still guaranteed to be logarithmic.
The advantage of this quasi-randomness is that it doesn't give away nearly as much level-structure related information to an [[Adversary (online algorithm)|adversarial user]] as the de-randomized one. This is desirable because an adversarial user who is able to tell which nodes are not at the lowest level can pessimize performance by simply deleting higher-level nodes. (Bethea and Reiter however argue that nonetheless an adversary can use probabilistic and timing methods to force performance degradation.<ref>{{cite conference |first1=Darrell |last1=Bethea |first2=Michael K. |last2=Reiter |title=Data Structures with Unpredictable Timing |url=https://www.cs.unc.edu/~djb/papers/2009-ESORICS.pdf#page=5 |at=pp. 456–471, §4 "Skip Lists" |doi=10.1007/978-3-642-04444-1_28 |conference=ESORICS 2009, 14th European Symposium on Research in Computer Security |location=Saint-Malo, France |date=September 21–23, 2009 |isbn=978-3-642-04443-4}}</ref>) The search performance is still guaranteed to be logarithmic.


It would be tempting to make the following "optimization": In the part which says "Next, for each ''i''th...", forget about doing a coin-flip for each even-odd pair. Just flip a coin once to decide whether to promote only the even ones or only the odd ones. Instead of <math>\mathcal{O}(n \log n)</math> coin flips, there would only be <math>\mathcal{O}(\log n)</math> of them. Unfortunately, this gives the adversarial user a 50/50 chance of being correct upon guessing that all of the even numbered nodes (among the ones at level 1 or higher) are higher than level one. This is despite the property that he has a very low probability of guessing that a particular node is at level ''N'' for some integer ''N''.
It would be tempting to make the following "optimization": In the part which says "Next, for each ''i''th...", forget about doing a coin-flip for each even-odd pair. Just flip a coin once to decide whether to promote only the even ones or only the odd ones. Instead of <math>O(n \log n)</math> coin flips, there would only be <math>O(\log n)</math> of them. Unfortunately, this gives the adversarial user a 50/50 chance of being correct upon guessing that all of the even numbered nodes (among the ones at level 1 or higher) are higher than level one. This is despite the property that there is a very low probability of guessing that a particular node is at level ''N'' for some integer ''N''.


A skip list does not provide the same absolute worst-case performance guarantees as more traditional [[balanced tree]] data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure. However, they work well in practice, and the randomized balancing scheme has been argued to be easier to implement than the deterministic balancing schemes used in balanced binary search trees. Skip lists are also useful in [[parallel computing]], where insertions can be done in different parts of the skip list in parallel without any global rebalancing of the data structure. Such parallelism can be especially advantageous for resource discovery in an ad-hoc [[wireless network]] because a randomized skip list can be made robust to the loss of any single node.<ref>{{cite thesis |type=Ph.D. thesis | last=Shah | first=Gauri | title=Distributed Data Structures for Peer-to-Peer Systems | year=2003 | url=http://www.cs.yale.edu/homes/shah/pubs/thesis.pdf |publisher=Yale University}}</ref>
A skip list does not provide the same absolute worst-case performance guarantees as more traditional [[balanced tree]] data structures, because it is always possible (though with very low probability<ref>{{cite journal |last1=Sen |first1=Sandeep |title=Some observations on skip lists |journal=Information Processing Letters |date=1991 |volume=39 |issue=4 |pages=173–176 |doi=10.1016/0020-0190(91)90175-H }}</ref>) that the coin-flips used to build the skip list will produce a badly balanced structure. However, they work well in practice, and the randomized balancing scheme has been argued to be easier to implement than the deterministic balancing schemes used in balanced binary search trees. Skip lists are also useful in [[parallel computing]], where insertions can be done in different parts of the skip list in parallel without any global rebalancing of the data structure. Such parallelism can be especially advantageous for resource discovery in an ad-hoc [[wireless network]] because a randomized skip list can be made robust to the loss of any single node.<ref>{{cite thesis |type=Ph.D. thesis | last=Shah | first=Gauri | title=Distributed Data Structures for Peer-to-Peer Systems | year=2003 | url=http://www.cs.yale.edu/homes/shah/pubs/thesis.pdf |publisher=Yale University}}</ref>


=== Indexable skiplist ===
=== Indexable skiplist ===
As described above, a skip list is capable of fast <math>O(\log n)</math> insertion and removal of values from a sorted sequence, but it has only slow <math>O(n)</math> lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of [[random access]] indexed lookups can be improved to <math>O(\log n)</math>.

As described above, a skiplist is capable of fast <math>\mathcal{O}(\log n)</math> insertion and removal of values from a sorted sequence, but it has only slow <math>\mathcal{O}(n)</math> lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of [[random access]] indexed lookups can be improved to <math>\mathcal{O}(\log n)</math>.


For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.
For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.
Line 75: Line 70:
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Bottom level
o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Bottom level
''' '''
Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL
Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL
Node Node Node Node Node Node Node Node Node Node
Node Node Node Node Node Node Node Node Node Node


Notice that the width of a higher level link is the sum of the component links below it (i.e. the width 10 link spans the links of widths 3, 2 and 5 immediately below it). Consequently, the sum of all widths is the same on every level (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5).
Notice that the width of a higher level link is the sum of the component links below it (i.e. the width 10 link spans the links of widths 3, 2 and 5 immediately below it). Consequently, the sum of all widths is the same on every level (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).


To index the skip list and find the i'th value, traverse the skip list while counting down the widths of each traversed link. Descend a level whenever the upcoming width would be too large.
To index the skip list and find the i'th value, traverse the skip list while counting down the widths of each traversed link. Descend a level whenever the upcoming width would be too large.
Line 85: Line 79:
For example, to find the node in the fifth position (Node 5), traverse a link of width 1 at the top level. Now four more steps are needed but the next width on this level is ten which is too large, so drop one level. Traverse one link of width 3. Since another step of width 2 would be too far, drop down to the bottom level. Now traverse the final link of width 1 to reach the target running total of 5 (1+3+1).
For example, to find the node in the fifth position (Node 5), traverse a link of width 1 at the top level. Now four more steps are needed but the next width on this level is ten which is too large, so drop one level. Traverse one link of width 3. Since another step of width 2 would be too far, drop down to the bottom level. Now traverse the final link of width 1 to reach the target running total of 5 (1+3+1).
'''function''' lookupByPositionIndex(i)
'''function''' lookupByPositionIndex(i)
node ← head
node ← head
i ← i + 1 ''# don't count the head as a step''
i ← i + 1 ''# don't count the head as a step''
'''for''' level '''from''' top '''to''' bottom '''do'''
'''for''' level '''from''' top '''to''' bottom '''do'''
'''while''' i ≥ node.width[level] '''do''' ''# if next step is not too far''
'''while''' i ≥ node.width[level] '''do''' ''# if next step is not too far''
i ← i - node.width[level] ''# subtract the current width''
i ← i - node.width[level] ''# subtract the current width''
node ← node.next[level] ''# traverse forward at the current level''
node ← node.next[level] ''# traverse forward at the current level''
'''repeat'''
'''repeat'''
'''repeat'''
'''repeat'''
'''return''' node.value
'''return''' node.value
'''end function'''
'''end function'''


This method of implementing indexing is detailed in [http://cg.scs.carleton.ca/~morin/teaching/5408/refs/p90b.pdf Section 3.4 Linear List Operations in "A skip list cookbook" by William Pugh].
This method of implementing indexing is detailed in ''"A skip list cookbook"'' by William Pugh<ref>
William Pugh.
''"A skip list cookbook"''.
1990.
[https://drum.lib.umd.edu/items/56c44671-3973-46b6-9e52-f71dc95af178 Section 3.4 Linear List Operations ].
</ref>


==History==
==History==
Skip lists were first described in 1989 by [[William Pugh (computer scientist)|William Pugh]].<ref>{{cite tech report |first=William |last=Pugh |author-link=William Pugh (computer scientist) |date=April 1989 |title=Concurrent Maintenance of Skip Lists |number=CS-TR-2222 |institution=Dept. of Computer Science, U. Maryland |url=http://drum.lib.umd.edu/handle/1903/542 |format=PS, PDF}}</ref>

Skip lists were first described in 1989 by [[William Pugh]].<ref>{{cite techreport |first=William |last=Pugh |authorlink=William Pugh |date=April 1989 |title=Concurrent Maintenance of Skip Lists |number=CS-TR-2222 |institution=Dept. of Computer Science, U. Maryland |url=http://drum.lib.umd.edu/handle/1903/542 |format=PS, PDF}}</ref>


To quote the author:
To quote the author:


{{blockquote
:''Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.''
|text=''Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.''
|author=William Pugh
|source=''Concurrent Maintenance of Skip Lists'' (1989)
}}


==Usages==
==Usages==
List of applications and frameworks that use skip lists:
List of applications and frameworks that use skip lists:
*[[Apache Portable Runtime]] implements skip lists.<ref>
*[[MemSQL]] uses skip lists as its prime indexing structure for its database technology.
[https://apr.apache.org/docs/apr/1.6/group__apr__skiplist.html Apache Portable Runtime APR 1.6 documentation]
*[[Cyrus IMAP server]] offers a "skiplist" backend DB implementation ([http://git.cyrusimap.org/cyrus-imapd/tree/lib/cyrusdb_skiplist.c source file])
</ref>
*[[MemSQL]] uses lock-free skip lists as its prime indexing structure for its database technology.
*[[MuQSS]], for the [[Linux kernel]], is a [[Scheduling (computing)#SHORT-TERM|cpu scheduler]] built on skip lists.<ref>
LWN's
[https://lwn.net/Articles/720227 article]
</ref><ref>{{Cite web|url=https://lkml.org/lkml/2016/10/29/4|title=LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120|website=lkml.org|access-date=2017-05-11}}</ref>
*[[Cyrus IMAP server]] offers a "skiplist" backend DB implementation<ref>
Cyrus IMAP server.
[https://github.com/cyrusimap/cyrus-imapd/blob/master/lib/cyrusdb_skiplist.c skiplist source file]
</ref>
*[[Lucene]] uses skip lists to search delta-encoded posting lists in logarithmic time.{{Citation needed|date=June 2014}}
*[[Lucene]] uses skip lists to search delta-encoded posting lists in logarithmic time.{{Citation needed|date=June 2014}}
*[http://qt-project.org/doc/qt-4.8/qmap.html#details QMap] (up to Qt 4) template class of [[Qt (framework)|Qt]] that provides a dictionary.
* The "QMap" key/value dictionary (up to Qt 4) template class of [[Qt (framework)|Qt]] is implemented with skip lists.<ref>
[http://qt-project.org/doc/qt-4.8/qmap.html#details QMap]
*[[Redis]], an ANSI-C open-source persistent key/value store for Posix systems, uses skip lists in its implementation of ordered sets.<ref>{{cite web | title=Redis ordered set implementation | url=https://github.com/antirez/redis/blob/unstable/src/t_zset.c}}</ref>
</ref>
*[https://github.com/shuttler/nessDB nessDB], a very fast key-value embedded Database Storage Engine (Using log-structured-merge (LSM) trees), uses skip lists for its memtable.
*[[Redis]], an ANSI-C open-source persistent key/value store for Posix systems, uses skip lists in its implementation of ordered sets.<ref>{{cite web | title=Redis ordered set implementation | website=[[GitHub]]| url=https://github.com/antirez/redis/blob/unstable/src/t_zset.c}}</ref>
*[http://www.dekorte.com/projects/opensource/skipdb/ skipdb] is an open-source database format using ordered key/value pairs.
* [[Discord]] uses skip lists to handle storing and updating the list of members in a [[Discord#Servers|server]].<ref>{{cite web |last1=Nowack |first1=Matt |title=Using Rust to Scale Elixir for 11 Million Concurrent Users |url=https://discord.com/blog/using-rust-to-scale-elixir-for-11-million-concurrent-users |website=Discord Blog |access-date=23 July 2023}}</ref>
*[http://download.oracle.com/javase/6/docs/enwiki/api/java/util/concurrent/ConcurrentSkipListSet.html ConcurrentSkipListSet] and [http://download.oracle.com/javase/6/docs/enwiki/api/java/util/concurrent/ConcurrentSkipListMap.html ConcurrentSkipListMap] in the Java 1.6 API.
* [[RocksDB]] uses skip lists for its default Memtable implementation.<ref>{{Cite web |title=MemTable |url=https://github.com/facebook/rocksdb/wiki/MemTable |access-date=2023-12-12 |website=GitHub |language=en}}</ref>
*[https://github.com/flightaware/speedtables Speed Tables] are a fast key-value datastore for Tcl that use skiplists for indexes and lockless shared memory.

*[https://github.com/google/leveldb leveldb], a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values
Skip lists are also used in distributed applications (where the nodes represent physical computers, and pointers represent network connections) and for implementing highly scalable concurrent [[priority queue]]s with less lock contention,<ref>{{Cite book | doi = 10.1109/IPDPS.2000.845994| chapter = Skiplist-based concurrent priority queues| title = Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000| pages = 263| year = 2000| last1 = Shavit | first1 = N.| last2 = Lotan | first2 = I.| isbn = 978-0-7695-0574-9| chapter-url = http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/Priority_Queues.pdf| citeseerx = 10.1.1.116.3489| s2cid = 8664407}}</ref> or even [[non-blocking algorithm | without locking]],<ref>{{Cite book | last1 = Sundell | first1 = H. | last2 = Tsigas | first2 = P. | doi = 10.1109/IPDPS.2003.1213189 | chapter = Fast and lock-free concurrent priority queues for multi-thread systems | title = Proceedings International Parallel and Distributed Processing Symposium | pages = 11 | year = 2003 | isbn = 978-0-7695-1926-5 | citeseerx = 10.1.1.113.4552 | s2cid = 20995116 }}</ref><ref>{{Cite conference | last1 = Fomitchev | first1 = Mikhail| last2 = Ruppert | first2 = Eric| doi = 10.1145/1011767.1011776 | title = Lock-free linked lists and skip lists | conference = Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC)| pages = 50–59| year = 2004 | isbn = 1581138024 | url = http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf}}</ref><ref>{{Cite book | last1 = Bajpai | first1 = R. | last2 = Dhara | first2 = K. K. | last3 = Krishnaswamy | first3 = V. | doi = 10.1109/ISPA.2008.90 | chapter = QPID: A Distributed Priority Queue with Item Locality | title = 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications | pages = 215 | year = 2008 | isbn = 978-0-7695-3471-8 | s2cid = 15677922 }}</ref> as well as [[lock-free]] concurrent dictionaries.<ref>{{Cite book | last1 = Sundell | first1 = H. K. | last2 = Tsigas | first2 = P. | doi = 10.1145/967900.968188 | chapter = Scalable and lock-free concurrent dictionaries | title = Proceedings of the 2004 ACM symposium on Applied computing - SAC '04 | pages = 1438 | year = 2004 | isbn = 978-1581138122 | s2cid = 10393486 | chapter-url = http://www.cse.chalmers.se/~tsigas/papers/Lock-Free_Dictionary.pdf}}</ref> There are also several US patents for using skip lists to implement (lockless) priority queues and concurrent dictionaries.<ref>{{cite patent | country=US | number=7937378 | status=patent}}</ref>
[http://code.activestate.com/recipes/576930/ Skip lists are used for efficient statistical computations] of [[Moving average#Moving median|running medians]] (also known as moving medians).
Skip lists are also used in distributed applications (where the nodes represent physical computers, and pointers represent network connections) and for implementing highly scalable concurrent [[priority queue]]s with less lock contention,<ref>{{Cite book | doi = 10.1109/IPDPS.2000.845994| chapter = Skiplist-based concurrent priority queues| title = Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000| pages = 263| year = 2000| last1 = Shavit | first1 = N.| last2 = Lotan | first2 = I.| isbn = 0-7695-0574-0| url = http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/Priority_Queues.pdf}}</ref> or even without locking,<ref>{{Cite book | last1 = Sundell | first1 = H. | last2 = Tsigas | first2 = P. | doi = 10.1109/IPDPS.2003.1213189 | chapter = Fast and lock-free concurrent priority queues for multi-thread systems | title = Proceedings International Parallel and Distributed Processing Symposium | pages = 11 | year = 2003 | isbn = 0-7695-1926-1 | pmid = | pmc = }}</ref><ref>{{Cite conference | last1 = Fomitchev | first1 = Mikhail| last2 = Ruppert | first2 = Eric| doi = 10.1145/1011767.1011776 | title = Lock-free linked lists and skip lists | conference = Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC)| pages = 50–59| year = 2004 | isbn = 1581138024 | url = http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf| pmid = | pmc = }}</ref><ref>{{Cite book | last1 = Bajpai | first1 = R. | last2 = Dhara | first2 = K. K. | last3 = Krishnaswamy | first3 = V. | doi = 10.1109/ISPA.2008.90 | chapter = QPID: A Distributed Priority Queue with Item Locality | title = 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications | pages = 215 | year = 2008 | isbn = 978-0-7695-3471-8 | pmid = | pmc = }}</ref> as well as lockless concurrent dictionaries.<ref>{{Cite book | last1 = Sundell | first1 = H. K. | last2 = Tsigas | first2 = P. | doi = 10.1145/967900.968188 | chapter = Scalable and lock-free concurrent dictionaries | title = Proceedings of the 2004 ACM symposium on Applied computing - SAC '04 | pages = 1438 | year = 2004 | isbn = 1581138121 | url = http://www.cse.chalmers.se/~tsigas/papers/Lock-Free_Dictionary.pdf| pmid = | pmc = }}</ref> There are also several US patents for using skip lists to implement (lockless) priority queues and concurrent dictionaries.<ref>{{cite patent | country=US | number=7937378 | status=patent}}</ref>


==See also==
==See also==
*[[Bloom filter]]
* [[Bloom filter]]
*[[Skip graph]]
* [[Skip graph]]


==References==
==References==
{{Reflist}}
<references/>


==External links==
== External links ==
{{Commons category}}
{{Commonscat}}

*[https://xlinux.nist.gov/dads/HTML/skiplist.html "Skip list" entry] in the [[Dictionary of Algorithms and Data Structures]]
* [https://xlinux.nist.gov/dads/HTML/skiplist.html "Skip list" entry] in the [[Dictionary of Algorithms and Data Structures]]
*[http://msdn.microsoft.com/en-us/library/ms379573(VS.80).aspx#datastructures20_4_topic4 Skip Lists: A Linked List with Self-Balancing BST-Like Properties] on [[MSDN]] in C# 2.0
*[http://videolectures.net/mit6046jf05_demaine_lec12/ Skip Lists lecture (MIT OpenCourseWare: Introduction to Algorithms) ]
* [http://videolectures.net/mit6046jf05_demaine_lec12/ Skip Lists lecture (MIT OpenCourseWare: Introduction to Algorithms) ]
*[http://opendatastructures.org/versions/edition-0.1e/ods-java/4_Skiplists.html Open Data Structures - Chapter 4 - Skiplists]
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/4_Skiplists.html Open Data Structures - Chapter 4 - Skiplists], [[Pat Morin]]
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.514 Skip trees, an alternative data structure to skip lists in a concurrent approach]
* [http://www0.cs.ucl.ac.uk/staff/a.gonzalezbeltran/pubs/icc2007.pdf Skip tree graphs, a distributed version of skip trees]
* [http://www0.cs.ucl.ac.uk/staff/a.gonzalezbeltran/pubs/icc2007.pdf Skip tree graphs, a distributed version of skip trees]
* [http://www0.cs.ucl.ac.uk/staff/a.gonzalezbeltran/pubs/AGB-comcom08.pdf More on skip tree graphs, a distributed version of skip trees]
* [http://www0.cs.ucl.ac.uk/staff/a.gonzalezbeltran/pubs/AGB-comcom08.pdf More on skip tree graphs, a distributed version of skip trees]

===Demo applets===
*[http://people.ksp.sk/~kuko/bak/index.html Skip List Applet] by Kubo Kovac
*Thomas Wenger's demo applet on skiplists

===Implementations===
*[https://metacpan.org/module/Algorithm::SkipList Algorithm::SkipList, implementation in Perl on CPAN]
*[http://code.activestate.com/recipes/576930/ Raymond Hettinger's implementation in Python]
*[http://java.sun.com/javase/6/docs/enwiki/api/java/util/concurrent/ConcurrentSkipListSet.html ConcurrentSkipListSet documentation for Java 6] (and [http://www.docjar.com/html/enwiki/api/java/util/concurrent/ConcurrentSkipListSet.java.html sourcecode])


{{Data structures}}
{{Data structures}}


[[Category:Computer-related introductions in 1989]]
{{DEFAULTSORT:Skip List}}
[[Category:1989 introductions]]
[[Category:Linked lists]]
[[Category:Linked lists]]
[[Category:Probabilistic data structures]]
[[Category:Probabilistic data structures]]

Latest revision as of 00:33, 25 June 2024

Skip list
TypeList
Invented1989
Invented byW. Pugh
Time complexity in big O notation
Operation Average Worst case
Search [1]
Insert
Delete
Space complexity
Space [1]

In computer science, a skip list (or skiplist) is a probabilistic data structure that allows average complexity for search as well as average complexity for insertion within an ordered sequence of elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one (see the picture below on the right). Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally searching in the full sequence. The elements that are skipped over may be chosen probabilistically[2] or deterministically,[3] with the former being more common.

Description

[edit]
A schematic picture of the skip list data structure. Each box with an arrow represents a pointer and a row is a linked list giving a sparse subsequence; the numbered boxes (in yellow) at the bottom represent the ordered data sequence. Searching proceeds downwards from the sparsest subsequence at the top until consecutive elements bracketing the search element are found.

A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer appears in layer with some fixed probability (two commonly used values for are or ). On average, each element appears in lists, and the tallest element (usually a special head element at the front of the skip list) appears in all the lists. The skip list contains (i.e. logarithm base of ) lists.

A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most , which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total expected cost of a search is which is , when is a constant. By choosing different values of , it is possible to trade search costs against storage costs.

Implementation details

[edit]
Inserting elements into a skip list

The elements used for a skip list can contain more than one pointer since they can participate in more than one list.

Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list.

operations, which force us to visit every node in ascending order (such as printing the entire list), provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to search time. (Choose the level of the i'th finite node to be 1 plus the number of times it is possible to repeatedly divide i by 2 before it becomes odd. Also, i=0 for the negative infinity header as there is the usual special case of choosing the highest possible level for negative and/or positive infinite nodes.) However this also allows someone to know where all of the higher-than-level 1 nodes are and delete them.

Alternatively, the level structure could be made quasi-random in the following way:

make all nodes level 1
j ← 1
while the number of nodes at level j > 1 do
    for each i'th node at level j do
        if i is odd and i is not the last node at level j
            randomly choose whether to promote it to level j+1
        else if i is even and node i-1 was not promoted
            promote it to level j+1
        end if
    repeat
    j ← j + 1
repeat

Like the derandomized version, quasi-randomization is only done when there is some other reason to be running an operation (which visits every node).

The advantage of this quasi-randomness is that it doesn't give away nearly as much level-structure related information to an adversarial user as the de-randomized one. This is desirable because an adversarial user who is able to tell which nodes are not at the lowest level can pessimize performance by simply deleting higher-level nodes. (Bethea and Reiter however argue that nonetheless an adversary can use probabilistic and timing methods to force performance degradation.[4]) The search performance is still guaranteed to be logarithmic.

It would be tempting to make the following "optimization": In the part which says "Next, for each ith...", forget about doing a coin-flip for each even-odd pair. Just flip a coin once to decide whether to promote only the even ones or only the odd ones. Instead of coin flips, there would only be of them. Unfortunately, this gives the adversarial user a 50/50 chance of being correct upon guessing that all of the even numbered nodes (among the ones at level 1 or higher) are higher than level one. This is despite the property that there is a very low probability of guessing that a particular node is at level N for some integer N.

A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability[5]) that the coin-flips used to build the skip list will produce a badly balanced structure. However, they work well in practice, and the randomized balancing scheme has been argued to be easier to implement than the deterministic balancing schemes used in balanced binary search trees. Skip lists are also useful in parallel computing, where insertions can be done in different parts of the skip list in parallel without any global rebalancing of the data structure. Such parallelism can be especially advantageous for resource discovery in an ad-hoc wireless network because a randomized skip list can be made robust to the loss of any single node.[6]

Indexable skiplist

[edit]

As described above, a skip list is capable of fast insertion and removal of values from a sorted sequence, but it has only slow lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of random access indexed lookups can be improved to .

For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.

For example, here are the widths of the links in the example at the top of the page:

   1                               10
 o---> o---------------------------------------------------------> o    Top level
   1           3              2                    5
 o---> o---------------> o---------> o---------------------------> o    Level 3
   1        2        1        2              3              2
 o---> o---------> o---> o---------> o---------------> o---------> o    Level 2
   1     1     1     1     1     1     1     1     1     1     1 
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level
Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

Notice that the width of a higher level link is the sum of the component links below it (i.e. the width 10 link spans the links of widths 3, 2 and 5 immediately below it). Consequently, the sum of all widths is the same on every level (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).

To index the skip list and find the i'th value, traverse the skip list while counting down the widths of each traversed link. Descend a level whenever the upcoming width would be too large.

For example, to find the node in the fifth position (Node 5), traverse a link of width 1 at the top level. Now four more steps are needed but the next width on this level is ten which is too large, so drop one level. Traverse one link of width 3. Since another step of width 2 would be too far, drop down to the bottom level. Now traverse the final link of width 1 to reach the target running total of 5 (1+3+1).

function lookupByPositionIndex(i)
    node ← head
    i ← i + 1                           # don't count the head as a step
    for level from top to bottom do
        while i ≥ node.width[level] do # if next step is not too far
            i ← i - node.width[level]  # subtract the current width
            node ← node.next[level]    # traverse forward at the current level
        repeat
    repeat
    return node.value
end function

This method of implementing indexing is detailed in "A skip list cookbook" by William Pugh[7]

History

[edit]

Skip lists were first described in 1989 by William Pugh.[8]

To quote the author:

Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

— William Pugh, Concurrent Maintenance of Skip Lists (1989)

Usages

[edit]

List of applications and frameworks that use skip lists:

  • Apache Portable Runtime implements skip lists.[9]
  • MemSQL uses lock-free skip lists as its prime indexing structure for its database technology.
  • MuQSS, for the Linux kernel, is a cpu scheduler built on skip lists.[10][11]
  • Cyrus IMAP server offers a "skiplist" backend DB implementation[12]
  • Lucene uses skip lists to search delta-encoded posting lists in logarithmic time.[citation needed]
  • The "QMap" key/value dictionary (up to Qt 4) template class of Qt is implemented with skip lists.[13]
  • Redis, an ANSI-C open-source persistent key/value store for Posix systems, uses skip lists in its implementation of ordered sets.[14]
  • Discord uses skip lists to handle storing and updating the list of members in a server.[15]
  • RocksDB uses skip lists for its default Memtable implementation.[16]

Skip lists are also used in distributed applications (where the nodes represent physical computers, and pointers represent network connections) and for implementing highly scalable concurrent priority queues with less lock contention,[17] or even without locking,[18][19][20] as well as lock-free concurrent dictionaries.[21] There are also several US patents for using skip lists to implement (lockless) priority queues and concurrent dictionaries.[22]

See also

[edit]

References

[edit]
  1. ^ a b Papadakis, Thomas (1993). Skip Lists and Probabilistic Analysis of Algorithms (PDF) (Ph.D.). University of Waterloo.
  2. ^ Pugh, W. (1990). "Skip lists: A probabilistic alternative to balanced trees" (PDF). Communications of the ACM. 33 (6): 668–676. doi:10.1145/78973.78977. S2CID 207691558.
  3. ^ Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert (1992). "Deterministic skip lists" (PDF). Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. pp. 367–375. S2CID 7477119.
  4. ^ Bethea, Darrell; Reiter, Michael K. (September 21–23, 2009). Data Structures with Unpredictable Timing (PDF). ESORICS 2009, 14th European Symposium on Research in Computer Security. Saint-Malo, France. pp. 456–471, §4 "Skip Lists". doi:10.1007/978-3-642-04444-1_28. ISBN 978-3-642-04443-4.
  5. ^ Sen, Sandeep (1991). "Some observations on skip lists". Information Processing Letters. 39 (4): 173–176. doi:10.1016/0020-0190(91)90175-H.
  6. ^ Shah, Gauri (2003). Distributed Data Structures for Peer-to-Peer Systems (PDF) (Ph.D. thesis). Yale University.
  7. ^ William Pugh. "A skip list cookbook". 1990. Section 3.4 Linear List Operations .
  8. ^ Pugh, William (April 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.
  9. ^ Apache Portable Runtime APR 1.6 documentation
  10. ^ LWN's article
  11. ^ "LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120". lkml.org. Retrieved 2017-05-11.
  12. ^ Cyrus IMAP server. skiplist source file
  13. ^ QMap
  14. ^ "Redis ordered set implementation". GitHub.
  15. ^ Nowack, Matt. "Using Rust to Scale Elixir for 11 Million Concurrent Users". Discord Blog. Retrieved 23 July 2023.
  16. ^ "MemTable". GitHub. Retrieved 2023-12-12.
  17. ^ Shavit, N.; Lotan, I. (2000). "Skiplist-based concurrent priority queues" (PDF). Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000. p. 263. CiteSeerX 10.1.1.116.3489. doi:10.1109/IPDPS.2000.845994. ISBN 978-0-7695-0574-9. S2CID 8664407.
  18. ^ Sundell, H.; Tsigas, P. (2003). "Fast and lock-free concurrent priority queues for multi-thread systems". Proceedings International Parallel and Distributed Processing Symposium. p. 11. CiteSeerX 10.1.1.113.4552. doi:10.1109/IPDPS.2003.1213189. ISBN 978-0-7695-1926-5. S2CID 20995116.
  19. ^ Fomitchev, Mikhail; Ruppert, Eric (2004). Lock-free linked lists and skip lists (PDF). Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 50–59. doi:10.1145/1011767.1011776. ISBN 1581138024.
  20. ^ Bajpai, R.; Dhara, K. K.; Krishnaswamy, V. (2008). "QPID: A Distributed Priority Queue with Item Locality". 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications. p. 215. doi:10.1109/ISPA.2008.90. ISBN 978-0-7695-3471-8. S2CID 15677922.
  21. ^ Sundell, H. K.; Tsigas, P. (2004). "Scalable and lock-free concurrent dictionaries" (PDF). Proceedings of the 2004 ACM symposium on Applied computing - SAC '04. p. 1438. doi:10.1145/967900.968188. ISBN 978-1581138122. S2CID 10393486.
  22. ^ US patent 7937378 
[edit]