SkipList 原理

深碍√TFBOYSˉ_ 2022-06-11 23:51 189阅读 0赞

**跳表是允许在[有序序列][Link 1]元素内快速搜索的[数据结构][Link 2]。**

通过维护子序列的[链接][Link 3]层次结构可以快速搜索，每个连续的子序列跳过比前一个更少的元素。搜索开始于最小的子序列，直到找到两个连续的元素，一个更小，一个大于或等于所搜索的元素。通过链接层次结构，这两个元素链接到下一个最短子序列的元素，其中搜索继续，直到最后我们以完整的顺序搜索。可以概率地或确定性地选择跳过的元素

完整的跳表的图示

![470px-Skip_list.svg.png][]

跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

下面来研究一下跳表的核心思想：

先从链表开始，如果是一个简单的链表，那么我们知道在链表中查找一个元素I的话，需要将整个链表遍历一次。

![skiplist_linklist.png][]

如果是说链表是排序的，并且节点中还存储了指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。

![skiplist_linklist_two_ahead.png][]

这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。

## 使用跳过列表的应用程序和框架列表：  [MemSQL][]使用跳过列表作为其数据库技术的主要索引结构。  [Cyrus IMAP服务器][Cyrus IMAP]提供了一个“skiplist”后端DB实现  [Lucene][]使用跳过列表以对数时间搜索增量式编码的发布列表。  [QMAP][]（最多Qt的4）模板类的[Qt的][Qt]，提供了一个字典。  [Redis][]是用于Posix系统的ANSI-C开源持久密钥/值存储，它在执行有序集时使用跳过列表。  [nessDB][]是一个非常快速的键值嵌入式数据库存储引擎（使用日志结构合并（LSM）树），它的memtable使用了跳过列表。  [skipdb][]是使用有序键/值对的开源数据库格式。  Java 1.6 API中的[ConcurrentSkipListSet][]和[ConcurrentSkipListMap][]。  [速度表][Link 4]是Tcl的一个快速键值数据存储区，它使用滑雪板进行索引和无锁共享内存。  [leveldb][]是一种用于在Google中编写的快速键值存储库，它提供从字符串键到字符串值的有序映射  Con Kolivas的MuQSS [\[8\]][8] Linux内核计划程序使用跳过列表  [SkiMap][]使用跳过列表作为基础数据结构，为机器人映射系统构建更复杂的3D稀疏网格。      ##

[Link 1]: https://en.wikipedia.org/wiki/Ordered_sequence
[Link 2]: https://en.wikipedia.org/wiki/Data_structure
[Link 3]: https://en.wikipedia.org/wiki/Linked_list
[470px-Skip_list.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/8/86/Skip_list.svg/470px-Skip_list.svg.png
[skiplist_linklist.png]: /images/20220612/4f5b63b920b847b08113da3bed827189.png
[skiplist_linklist_two_ahead.png]: /images/20220612/306c5545e95f4c3a9eff0d1745803f4f.png
[MemSQL]: https://en.wikipedia.org/wiki/MemSQL
[Cyrus IMAP]: https://en.wikipedia.org/wiki/Cyrus_IMAP_server
[Lucene]: https://en.wikipedia.org/wiki/Lucene
[QMAP]: http://qt-project.org/doc/qt-4.8/qmap.html#details
[Qt]: https://en.wikipedia.org/wiki/Qt_%28framework%29
[Redis]: https://en.wikipedia.org/wiki/Redis
[nessDB]: https://github.com/shuttler/nessDB
[skipdb]: http://www.dekorte.com/projects/opensource/skipdb/
[ConcurrentSkipListSet]: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListSet.html
[ConcurrentSkipListMap]: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html
[Link 4]: https://github.com/flightaware/speedtables
[leveldb]: https://github.com/google/leveldb
[8]: https://en.wikipedia.org/wiki/Skip_list#cite_note-8
[SkiMap]: https://github.com/m4nh/skimap_ros