什么是跳表？

提示

题眼： olngn 复杂度

Redis 跳表（Skip List）是一种有序的数据结构，在 Redis 中被用于实现有序集合（Sorted Set）。

跳表的核心是构建多层链表，最底层链表包含了有序集合中的所有元素，并且这些元素按照其对应的分值（score）从小到大依次排列，就如同普通的有序链表一样。然后在此基础上，每隔几个节点就会提取出一些节点构建上一层链表，依次类推构建出多层链表。

上层链表相当于下层链表的一种 “索引”，比如在查找元素时，先从最上层链表开始查找，由于上层链表节点相对稀疏，可以快速跳过许多节点定位到目标元素所在的大致区间，然后再逐层下降到下一层链表继续查找，直至找到目标元素或者确定目标元素不存在为止。通过这种方式，能够在有序链表的基础上显著提高查找效率，其时间复杂度可以达到平均 O (log n)，接近平衡树的查找效率，但实现起来相对更简单直观。

重要

参考答案：

跳表是一种有序的数据结构，它会使用多层索引来加快数据的查询和写入。它的底层时一个有序的链表，然后在这个链表之上会每隔几个节点就提取一个元素，再组织一个链表，这个链表的的元素会指向底层的链表，这样子重复几次，就搭建了一个金字塔形状的结构，每一层链表都是下一层元素的索引，直到底层元素。这样的好处是底层元素是有序排列的，然后查询和插入的效率理论上都是ologn，而且相对树而言，它结构更简单，需要的内存开销也非常小。