Editing Skip list (section)

==Usages==
List of applications and frameworks that use skip lists:
*[[Apache Portable Runtime]] implements skip lists.<ref>
[https://apr.apache.org/docs/apr/1.6/group__apr__skiplist.html Apache Portable Runtime APR 1.6 documentation]
</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}}
* 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]
</ref>
*[[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>
* [[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>
* [[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>
* [[Java_(programming_language)|Java]] uses skip lists for its [https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ConcurrentSkipListSet.html ConcurrentSkipListSet] and [https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/ConcurrentSkipListMap.html ConcurrentSkipListMap]. 

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>