关于redis:Redis拼多多面试官问我zset底层是如何实现的我反手就把跳表的数据结构画了出来

引言

Redis 因为其齐全基于内存、性能杰出，加上具备丰盛的数据类型，在电商环境中深受后端开发的青睐。其中有序汇合 zset 就是根本数据类型之一，并且每个 member 都带有 score（可用于排序），因而很适宜在打赏日榜、近一周收益这类场景中使用。

数据结构初探

有序汇合对象的编码能够是 ziplist 或者 skiplist。同时满足以下条件时应用 ziplist 编码：

• 元素数量小于 128 个
• 所有 member 的长度都小于 64 字节

以上两个条件的上限值可通过 zset-max-ziplist-entries 和 zset-max-ziplist-value 来批改。

ziplist 编码的有序汇合应用紧挨在一起的压缩列表节点来保留，第一个节点保留 member，第二个保留 score。ziplist 内的汇合元素按 score 从小到大排序，score 较小的排在表头地位。

skiplist 编码的有序汇合底层是一个命名为 zset 的构造体，而一个 zset 构造同时蕴含一个字典和一个跳跃表。跳跃表按 score 从小到大保留所有汇合元素。而字典则保留着从 member 到 score 的映射，这样就能够用 O(1)的复杂度来查找 member 对应的 score 值。尽管同时应用两种构造，但它们会通过指针来共享雷同元素的 member 和 score，因而不会节约额定的内存。

深刻跳表 skiplist

在介绍跳表前，咱们先来回顾一下根本链表，并思考为何一步一步演化成跳表的数据结构。

在这样一个链表中，如果咱们要查找某个数据，那么须要从头开始一一进行比拟，直到找到蕴含数据的那个节点，或者找到第一个比给定数据大的节点为止（没找到）。也就是说，工夫复杂度为 O(n)。同样，当咱们要插入新数据的时候，也要经验同样的查找过程，从而确定插入地位。

如果咱们每隔一个节点减少一个指针，让指针指向下下个节点，如下图：

当初当咱们想查找数据的时候，能够先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比方，咱们想查找 23，查找的门路是沿着下图中标红的指针所指向的方向进行的：

• 23 首先和 7 比拟，再和 19 比拟，比它们都大，持续向后比拟。
• 但 23 和 26 比拟的时候，比 26 要小，因而回到上面的链表（原链表），与 22 比拟。
• 23 比 22 要大，沿上面的指针持续向后和 26 比拟。23 比 26 小，阐明待查数据 23 在原链表中不存在，而且它的插入地位应该在 22 和 26 之间。

在这个查找过程中，因为新减少的指针，工夫复杂度不再是 O(N)了，也即咱们不再须要与链表中每个节点一一进行比拟了。须要比拟的节点数大略只有原来的一半。

利用同样的形式，咱们能够在下层新产生的链表上，持续扩大指针，从而产生第三层链表。如下图：

在这个新的三层链表构造上，如果咱们还是查找 23，那么沿着最上层链表首先要比拟的是 19，发现 23 比 19 大，接下来咱们就晓得只须要到 19 的前面去持续查找，从而一下子跳过了 19 后面的所有节点。能够设想，当链表足够长的时候，这种多层链表的查找形式能让咱们跳过很多上层节点，大大放慢查找的速度。

skiplist 正是受这种多层链表的想法的启发而设计进去的。实际上，依照下面生成链表的形式，下面每一层链表的节点个数，是上面一层的节点个数的一半，这样查找过程就十分相似于一个二分查找，使得查找的工夫复杂度能够升高到 O(log n)。然而，这种办法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱高低相邻两层链表上节点个数严格的 2:1 的对应关系。如果要维持这种对应关系，就必须把新插入的节点前面的所有节点（也包含新插入的节点）从新进行调整，这会让工夫复杂度从新堕落成 O(n)。删除数据也有同样的问题。

skiplist 为了防止这一问题，它不要求高低相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。附源码：

#define ZSKIPLIST_MAXLEVEL 32 
#define ZSKIPLIST_P 0.25 

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

执行插入操作时计算随机数的过程，是一个很要害的过程，它对 skiplist 的统计个性有着很重要的影响。这并不是一个一般的遵从均匀分布的随机数，而是遵从肯定规定的：

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

比方，一个节点随机出的层数是 3，那么就把它链入到第 1 层到第 3 层这三层链表中。为了表白分明，下图展现了如何通过一步步的插入操作从而造成一个 skiplist 的过程：

从下面 skiplist 的创立和插入过程能够看出，每一个节点的层数（level）是随机进去的，而且新插入一个节点不会影响其它节点的层数。因而，插入操作只须要批改插入节点前后的指针，而不须要对很多节点都进行调整。这就升高了插入操作的复杂度。实际上，这是 skiplist 的一个很重要的个性，这让它在插入性能上显著优于均衡树的计划。这在前面咱们还会提到。

skiplist，指的就是除了最上面第 1 层链表之外，它会产生若干层稠密的链表，这些链表外面的指针成心跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得咱们在查找数据的时候可能先在高层的链表中进行查找，而后逐层升高，最终降到第 1 层链表来准确地确定数据地位。在这个过程中，咱们跳过了一些节点，从而也就放慢了查找速度。

刚刚创立的这个 skiplist 总共蕴含 4 层链表，当初假如咱们在它外面仍然查找 23，下图给出了查找门路：

须要留神的是，后面演示的各个节点的插入过程，实际上在插入之前也要先经验一个相似的查找过程，在确定插入地位后，再实现插入操作。

理论利用中的 skiplist 每个节点应该蕴含 member 和 score 两局部。后面的形容中咱们没有具体辨别 member 和 score，但实际上列表中是依照 score 进行排序的，查找过程也是依据 score 在比拟。

为什么采纳跳表，而不应用哈希表或均衡树实现呢

1. skiplist 和各种均衡树（如 AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因而，在哈希表上只能做单个 key 的查找，不合适做范畴查找。所谓范畴查找，指的是查找那些大小在指定的两个值之间的所有节点。
2. 在做范畴查找的时候，均衡树比 skiplist 操作要简单。在均衡树上，咱们找到指定范畴的小值之后，还须要以中序遍历的程序持续寻找其它不超过大值的节点。如果不对均衡树进行肯定的革新，这里的中序遍历并不容易实现。而在 skiplist 上进行范畴查找就非常简单，只须要在找到小值之后，对第 1 层链表进行若干步的遍历就能够实现。
3. 均衡树的插入和删除操作可能引发子树的调整，逻辑简单，而 skiplist 的插入和删除只须要批改相邻节点的指针，操作简略又疾速。
4. 从内存占用上来说，skiplist 比均衡树更灵便一些。一般来说，均衡树每个节点蕴含 2 个指针（别离指向左右子树），而 skiplist 每个节点蕴含的指针数目均匀为 1 /(1-p)，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取 p =1/4，那么均匀每个节点蕴含 1.33 个指针，比均衡树更有劣势。