手写一个跳表，跪了。。。

尼恩说在前面

在40岁老架构师尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团、蚂蚁、得物的面试资格，遇到很多很重要的相关面试题：

手写一个跳表？

redis为什么用跳表不用B+树吗？

最近有小伙伴在蚂蚁、面试字节，都问到了相关的面试题，可以说是逢面必问。

小伙伴没有系统的去梳理和总结，所以支支吾吾的说了几句，面试官不满意，面试挂了。

所以，尼恩给大家做一下系统化、体系化的梳理，使得大家内力猛增，可以充分展示一下大家雄厚的 “技术肌肉”，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提”。

当然，这道面试题，以及参考答案，也会收入咱们的《尼恩Java面试宝典PDF》V175版本，供后面的小伙伴参考，提升大家的 3高架构、设计、开发水平。

《尼恩架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请到文末公号【技术自由圈】获取

本文作者：

第一作者 Moen （负责写初稿）
第二作者尼恩（40岁老架构师，负责提升此文的技术高度，让大家有一种俯视技术的感觉）

本文目录

- 尼恩说在前面

- 什么是跳表

对有序链表查询优化过程
跳表的特点
随机层数在性能上的优化

- Redis中ZSet是怎么实现的

Redis中ZSet底层数据结构
zpilist和skiplist之间何时进行转换
Redis对跳表的实现及改进与优化

- 跳表与平衡树、哈希表的比较

- Redis为什么使用跳表而不用平衡树

- 跳表与B+树的比较

- 基于Java实现跳表

- 总结

- 说在最后：有问题找老架构取经

什么是跳跃表（skiplist）?

Redis 是一个开源（BSD许可）的，内存中的数据结构存储系统，它可以用作数据库、缓存和消息中间件。

Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

跳跃表（skiplist）是一种随机化的数据，由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。

跳表是一种带多级索引的链表，本质上也是一种查找结构，用于解决算法中的查找问题，即根据给定的key，快速查找它所在的位置（value）。跳跃表(skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均0 (1ogN)、最坏O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

从直观理解的维度来绘制，一个3层索引结构的skiplist ， demo 示意图如下：

在这里插入图片描述

此图来自于尼恩和小伙伴们的本系列文章的第一篇：

字节面试： Mysql为什么用B+树，不用跳表？

换一种方式，从编码实现的维度来绘制，一个3层索引结构的skiplist 的 demo 示意图如下：
在这里插入图片描述

对有序链表的查询优化过程

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。

这样查找效率就会很低，时间复杂度会很高，是 O(n)。

在这里插入图片描述

step1：建立一级索引

对链表中每两个节点建立第一级索引 , 大致的方法如下：

假如为每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：
在这里插入图片描述

这样所有新增加的指针连成了一个新的链表（上图中第一级索引指向的链表），

但第一级索引包含的节点个数只有原来的一半（上图中是5, 9, 16）。

请注意：实际应用中的skiplist每个节点应该包含key和value两部分。

这里为了方便描述，并没有具体区分key和value，但实际上列表中是按照key进行排序的，查找过程也是根据key进行比较。

现在当我们想查找数据的时候，查找的过程如下：

可以先第一级索引层遍历进行查找。
当碰到比待查数据大的节点时，再回到原来的链表中进行查找。

比如，我们想查找14，查找的路径是沿着下图中标红的指针所指向的方向进行的：
在这里插入图片描述

14首先和5比较，再和9比较，比它们都大，继续向后比较。
但14和16比较的时候，比16要小，因此回到下面的链表（原链表），与13比较。
14比13要大，沿下面的指针继续向后和16比较。14比16小，说明待查数据14在原链表中不存在，而且它的插入位置应该在13和16之间。

在这个查找过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了。

通过第一层索引，我们发现：需要比较的节点数大概只有原来的一半。

step2：建立二级索引

利用同样的方式，我们可以在第一层新产生的链表上，继续为每相邻的两个节点增加一个指针，从而产生第二层链表，这一层链表是第二层索引。

第二层索引如下图：
在这里插入图片描述

在这个新的第二层索引结构上，如果我们还是查找14，

那么沿着最上层链表首先要比较的是9，发现14比9大，接下来我们就知道只需要到9的后面去继续查找，从而一下子跳过了9前面的所有节点。

从上述过程我们看出，加了一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。

跳表的特点

跳表是一种动态数据结构，支持快速地插入、删除、查找操作，时间复杂度都是 O(logn)。

跳表的空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

跳表即表示跳跃表，指的就是除了最下面第1层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候，可由高层链表到底层链表逐层降低，在这个过程中，跳过了一些节点，从而也就加快了查找速度。

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。即上面每一层链表的节点个数，是下面一层的节点个数的一半。

随机层数在插入性能上的优化

新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。

如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。

比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。

为了表达清楚，下面通过多个图的方式，一步一步展示了插入操作如何通过随机层数，决定一个节点要插入跳表的哪几层的问题：

在这里插入图片描述

上图，插入9的时候，随机层数为2，就需要插入2层：

在原始链表层，插入 9。
和第一个索引层，插入 9。

上图，插入5的时候，随机层数为4，就需要插入4层：

在原始链表层，插入 5。
和第一个索引层，插入 5。
和第二个索引层，插入 5。
和第三个索引层，插入 5。

上图，插入1的时候，随机层数为1，就需要插入1层：

在原始链表层，插入 1。

在这里插入图片描述

上图，插入21的时候，随机层数为3，就需要插入3层：

在原始链表层，插入 21。
和第一个索引层，插入 21。
和第二个索引层，插入 21。

上图，插入6的时候，随机层数为1，就需要插入1层：

在原始链表层，插入 1。

上图，插入16的时候，随机层数为1，就需要插入1层：

在原始链表层，插入 1。

从上面skiplist的创建和插入过程可以看出，每一个节点的层数（level）是随机出来的，而且新插入一个节点不会影响其它节点的层数。

skiplist 在插入的效率比较高，插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。

与之相比，B+树在插入的时候要维护树的平衡，插入过程中会发生 page 的分裂，插入的性能就会差很多，具体请见：

字节面试： Mysql为什么用B+树，不用跳表？

插入的性能很高，这是skiplist的一个很重要的特性，这让它在插入性能上明显优于平衡树的方案。

skiplist执行插入，需要计算随机数，是一个很关键的过程，它对skiplist的统计特性有着很重要的影响。

这并不是一个普通的服从均匀分布的随机数，它的计算过程如下：

首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
节点最大的层数不允许超过一个最大值，记为MaxLevel。

跳表查找元素的过程

刚刚创建的这个skiplist总共包含4层链表，现在假设我们在它里面依然查找14，下图给出了查找路径：
在这里插入图片描述

Redis中ZSet是怎么实现的

Redis中 ZSet（Sorted Set）是Redis中的一种特殊数据结构，它内部维护一个有序的dict，这个字典dict包括两个属性：成员（member）、分数（score，double类型）。

这个ZSet 结构价值很大：

可以帮助我们实现排行榜、
朋友圈点赞等记分类型的排行数据，
以及实现延迟队列、限流。

Redis中ZSet实现包括多种结构，有ziplist（压缩列表）、skiplist（跳表）、listpack（紧凑列表，在Redis5.0中新增）。

listpack是为了替代ziplist，在Redis7.0中已经彻底弃用ziplist。

Redis中Zset底层数据结构

前面提到过，Redis中的ZSet是在dict、ziplist（listpack）、skiplist基础上构建起来的：

当数据较少时，sorted set是由一个ziplist来实现的。
当数据多的时候，sorted set是由一个叫zset的数据结构来实现的，这个zset包含一个dict + 一个skiplist。

当数据多的时候，zset包含一个dict + 一个skiplist：

dict用来查询数据到分数(score)的对应关系，
而skiplist用来根据分数查询数据（可能是范围查找）。

ziplist就是由很多数据项组成的一大块连续内存。由于sorted set的每一项元素都由数据和score组成，因此，当使用zadd命令插入一个(数据, score)对的时候，底层在相应的ziplist上就插入两个数据项：数据在前，score在后。

ziplist的主要优点是节省内存，但它上面的查找操作只能按顺序查找（可以正序也可以倒序）。因此，sorted set的各个查询操作，就是在ziplist上从前向后（或从后向前）一步步查找，每一步前进两个数据项，跨域一个(数据, score)对。

ZSet中的字典和跳表布局

其中skiplist用来实现有序集合，其中每个元素按照其分值大小在跳表中进行排序，跳表的插入、删除和查找操作时间复杂度都是O(1)，能够保证较好的性能。

dict用来实现元素到分值的映射，其中元素作为键，分值作为值。哈希表的插入、删除和查找操作的时间复杂度都是O(1)，具备非常高的性能。

redis的zpilist和skiplist之间何时进行转换

随着数据的插入，Redis底层会将ziplist转换成skiplist，那么到底插入多少数据才会转换，下面进行分析。

本文主要涉及两个Redis配置（在redis.conf中的ADVANCED CONFIG部分）

Similarly to hashes and lists, sorted sets are also specially encoded in
order to save a lot of space. This encoding is only used when the length and
elements of a sorted set are below the following limits:

Redis7.0之前的配置

zset-max-ziplist-entries 128 // ziplist中元素个数
zset-max-ziplist-value 64 // ziplist中元素大小

Redis7.0之后的配置

zset-max-listpack-entries 128 // listpack中元素个数
zset-max-listpack-value 64 // listpack中元素大小

在Redis中，以上两个配置说明，只有当长度和排序集的元素个数，同时满足以下两个条件时会使用ziplist（listpack）作为其内部表示，具体条件如下：

元素数量少：集合中的元素数量必须小于配置的阈值：zset-max-ziplist-entries（zset-max-listpack-entries）
插入数据长度：当ZSet中插入的任意一个数据的长度超过64的时候。

总结：当元素数量少于128，每个元素的长度都小于64字节的时候，Redis使用ziplist（listpack），否则使用是skiplist。

/* Convert the sorted set object into a listpack if it is not already a listpack
 * and if the number of elements and the maximum element size and total elements size
 * are within the expected ranges. */
void zsetConvertToListpackIfNeeded(robj *zobj, size_t maxelelen, size_t totelelen) {
    if (zobj->encoding == OBJ_ENCODING_LISTPACK) return;
    zset *zset = zobj->ptr;

    if (zset->zsl->length <= server.zset_max_listpack_entries &&
        maxelelen <= server.zset_max_listpack_value &&
        lpSafeToAdd(NULL, totelelen))
    {
        zsetConvert(zobj,OBJ_ENCODING_LISTPACK);
    }
}

Redis对跳表的实现及改进与优化

Redis 的跳跃表是由 redis.h/zskiplistNode和 redis.h/zskiplist 两个结构定义，其中 zskiplistNode 用于表示跳跃节点，而 zskiplist 结构则用于保存跳跃表节点的相关信息，比如节点的数量以及指向表头节点和表尾节点的指针等等。

在这里插入图片描述

上图最左边的是 zskiplist 结构，该结构包含以下属性：

header：指向跳跃表的表头节点

tail：指向跳跃表的表尾节点

level：记录目前跳跃表内，层数最大的那个节点层数（表头节点的层数不计算在内）

length：记录跳跃表的长度，也就是跳跃表目前包含节点的数量（表头节点不计算在内）

位于 zskiplist 结构右侧是四个 zskiplistNode 结构，该结构包含以下属性：

层（level）：节点中用 L1、L2、L3 等字样标记节点的各个层，L1 代表第一层，L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其它节点，而跨度则记录了前进指针所指向节点和当前节点的距离。

后退（backward）指针：节点中用 BW 字样标识节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。

分值（score）：各个节点中的 1.0、2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。

总结起来，Redis中的skiplist跟前面介绍的经典的skiplist相比，有如下不同：

分数(score)允许重复，即skiplist的key允许重复。这在最开始介绍的经典skiplist中是不允许的。
在比较时，不仅比较分数（相当于skiplist的key），还比较数据本身。在Redis的skiplist实现中，数据本身的内容唯一标识这份数据，而不是由key来唯一标识。另外，当多个元素分数相同的时候，还需要根据数据内容来进字典排序。
第1层链表不是一个单向链表，而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。
在skiplist中可以很方便地计算出每个元素的排名(rank)。

跳表与平衡树、哈希表的比较

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
从算法实现难度上来比较，skiplist比平衡树要简单得多。

Redis为什么使用跳表而不使用平衡树

关于这个问题，Redis作者是这么说的：

There are a few reasons:
1、They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2、A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3、They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch(already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

主要是从内存占用、对范围查找的支持、实现难易程度这三方面总结的原因，简单翻译如下：

它们不是非常内存密集型的。基本上由你决定。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存。

Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。

它们更易于实现、调试等。例如，由于跳表的简单性，我收到了一个补丁（已经在Redis master中），其中扩展了跳表，在 O(log(N) 中实现了 ZRANK。它只需要对代码进行少量修改。

关于上述观点，做几点补充如下：

从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。

在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。

从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。

跳表与B+树的比较

相同点：skiplist和B+树的最下面一层，都包含了所有数据，且都是有序的，适合用于范围查询。
不同点：
- B+树本质上是一种多叉平衡二叉树。当数据库表不断插入新的数据时，为了维持B+树的平衡，B+树会不断分裂调整数据页，来保证B+树的子树们的高度层级尽量一致（一般最多差一个层级）。适合读多写少的场景。（存储引擎RocksDB内部使用了跳表，对比使用B+树的innodb，虽然写性能更好，但读性能属实差了些。）
- skiplist在新增/删除数据时，依靠随机函数，即可确定是否需要向上添加索引，达到一个二分的效果，无需平衡数据结构，少了旋转平衡的开销。
- skiplist占用更少的内存，且更容易实现、调试。
B+树是多叉平衡搜索树，只需要3层左右就能存放2kw左右的数据，同样情况下跳表则需要24层左右，假设层高对应磁盘IO，那么B+树的读性能会比跳表要好，因此mysql选了B+树做索引。
redis的读写全在内存里进行操作，不涉及磁盘IO，同时跳表实现简单，相比B+树、AVL树、少了旋转树结构的开销，因此redis使用跳表来实现ZSET，而不是树结构。

总之：

B+树是 “磁盘友好” 型的数据机构，适合于 DB。
跳表是 “内存友好” 型的数据结构，适合于 Cache。

字节的真题：手写一个跳表

第一步：定义好跳表的节点

每一个节点，都带着一个指针数组，

一个最大16层的跳表，每一个node结构包含一个规模为16大小的指针数组

在这里插入图片描述

第二步：定义好生产随机层数的方法



  // 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
  // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
  // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
  //        50%的概率返回 1
  //        25%的概率返回 2
  //      12.5%的概率返回 3 ...
  private int randomLevel() {
    int level = 1;

    while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
      level += 1;
    return level;
  }