后端通用面试教程数据结构与算法面试题Redis数据结构（二）

1. 前言

上一章节介绍了 SDS 数据结构，即 Redis 最基础的 Key-Value 存储实现，本章节继续介绍 Redis 底层的高级数据结构。

Redis 的五种基本结构中还有一个叫做 zset 的数据结构，zset 保证了每个值的唯一性，这方面性质同传统的 set 集合，也可以对每个值赋予 score，按照 score 进行排序。这种高级性质依赖于底层的跳跃表数据结构实现。

2. SkipList

2.1 SkipList 数据结构

面试官提问： Redis zset 数据结构的底层实现是什么？为什么要使用跳跃表？

题目解析：

在介绍跳跃表（SkipList，简称跳表）之前，我们可以以单链表数据结构作为对比。

在单链表中，我们查询一个元素的时间复杂度是 O (N)，其中 N 是链表的长度，因为需要诶个遍历节点，单链表不支持数组的随机插入和删除，也不支持数组的自动排序，显然不适合作为 zset 的实现方式。

跳跃表的基础定义可参考维基百科定义

参考定义，我们给出 C 语言的结构体定义：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

候选人需要描述跳表的数据结构，可以通过画图或者其他方式给出定义。

​

从结构体可以看出，节点有不同的定义：

• sds：存储的字符串对象；
• score：分数，跳表中所有节点按照 score 由大到小排列；
• backward：指向后退节点的指针；
• forward：指向下一个节点的指针；
• level：数组，数组中的每一个元素包括了指向其他节点的指针，level 的长度在 1 到 32（2^5）之间。

其中跳表的主要组成结构有：

• 表头：表示跳表的入口；
• 表尾：表示跳表的尾部，数值全部都是 NULL；
• 节点：保存具体数值，并且具有层结构；
• 层：就是上述 level 定义中的单个元素，保存前一个节点的指针，以及该层下个节点向前跨越的数值（span）。

跳表的查询过程本质上是自上而下的二分查找，插入和查询过程都相对复杂，这里不做赘述。

在阐述基本定义之后，我们需要关注跳跃表的核心特点：

• 本质是随机化数据结构，可以在对数（logN）时间内完成对数据的查找、插入、删除操作；
• 跳跃表在 Redis 的唯一应用，就是作为有序集合支撑底层数据结构。

2.2 跳跃表 vs 二叉树

面试官提问： 二叉查找树也能实现对数时间的查找插入特性，为什么还要使用跳跃表？

题目解析：

面试官经常会拿跳表和其他数据结构进行对比，依次同时考察候选人数据结构的基础能力。

虽然二叉查找树（Binary Search Tree）也满足插入、查找、删除时间复杂度为 O (logN)，但是在极端情况下，如果插入的数据满足完全有序（例如 1，2，3，4 …），则每次插入二手树都是右节点，这时二叉查找树会退化为线性链表，查询时间复杂度退化为 O（N）。相对于二叉查找树，跳跃表的表现更稳定。

2.3 跳跃表 vs 红黑树

面试官提问： 红黑树也能实现对数时间的查找插入特性，为什么还要使用跳跃表？

题目解析：

红黑树（Red Black Tree）是二叉查找树的一种变形，查找、插入、删除的时间复杂度也是 O (logN)，为什么 Redis 不使用红黑树作为 zset 的数据结构实现？

关于这一点，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.

总结下来就是两点原因：

（1）相对于 B 树 / 红黑树，跳跃表修改节点对内存的变量影响小；

（2）性能接近红黑树，但是跳表编码实现更简单，方便调试，简单来说就是编码完整的红黑树实现麻烦且不直观。

3. 小结

本章节介绍了跳跃表的基本数据结构定义、插入查找的时间复杂度，以及和其他数据结构的对比。跳表是常见的 Redis 底层数据结构，希望大家能够深入理解并掌握。