面试官：Redis 的跳表你了解多少？。。
引言：你知道 Redis 的 Zset 为什么要用跳表，而不用红黑树或者 B+ 树呢？这是一个经常会被问到的问题，和数据库为什么要计成 B+ 树，而不是红黑树和平衡树有异曲同工之妙，本文将用带大家展示跳表在 Redis 中的运用。
题目
面试官：Redis 的跳表你了解多少？。。
推荐解析
Zset 的两种底层实现
首先我们需要知道跳表并不是 Zset 的唯一实现，它是可选项，当满足条件时候，就会使用跳表进行效率的提升。
1）Zset 键值对数量少于 128 个
2）每个元素的长度小于 64 字节
如果同时满足上面的两个条件，此时就会采用 ZipList，如果不满足就会采用 SkipList。
普通链表 VS 跳表
1）结构
1.1）有序链表：由一个个节点组成，每个节点包含数据和指向下一个节点的指针。
1.2）跳表：由多层级组成，每一层都是一个有序链表，每一层的节点指向下一层的节点。
2）时间复杂度
2.1）有序链表：插入、删除和查找的平均时间复杂度为O(n)，其中n是链表的长度。
2.2）跳表：插入、删除和查找的平均时间复杂度为O(log n)，其中n是元素的个数。
3）空间复杂度
3.1）有序链表：空间复杂度为O(n)，其中n是链表的长度。
3.2）跳表：空间复杂度为O(n log n)，其中n是元素的个数。
4）插入和删除操作
4.1）有序链表：插入和删除操作需要遍历链表找到插入或删除位置，时间复杂度较高。
4.2）跳表：通过建立多层级索引，插入和删除操作只需更新索引节点，时间复杂度较低。
5）查找操作
5.1）有序链表：查找操作需要遍历整个链表，时间复杂度较高。
5.2）跳表：通过多层级索引，可以快速跳跃到目标位置，查找操作时间复杂度较低。
理想清理，每一层的索引是下一层元素个数的二分之一。
一级索引：16 二级索引：8 三级索引：4 四级索引：2
递推公式可得：H = log2^n-1
理论上 Redis 的一个类型可以放大约 40 亿个实例，2^32-1个。因此索引高度不能超过 32。
每次创建一个新跳跃表节点的时候，程序都会根据幂次定律（zslRandomLevel,越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。 节点层高确定之后便不会在修改。
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
根据概率论，计算期望，当 p =0.25，期望层高为 1/(1-0.25)=1.33。
红黑树 VS 跳表
1）结构：红黑树是一种二叉搜索树，而跳表是一种多层级的有序链表。
2）平衡性：红黑树通过颜色和规则来保持平衡，而跳表通过多层级索引来提高查询效率。
3）动态性：红黑树和跳表都支持高效的动态操作，包括插入、删除和查找。
4）空间复杂度：红黑树和跳表的空间复杂度都为O(n)，但是跳表的额外索引层级会增加一些额外的空间开销。
主要原因：跳表实现比较简单，并且对于区间查找的效率比较高，红黑树的高度不好控制。
B+ 树 VS 跳表
B+树
1）可以是多叉树（区别二叉树），每个节点可包含多个子节点，减少树的高度，查询效率较高。
2）叶子节点存放真正的 Value，非叶子节点存放多个 Key。
3）平衡性强，高度差控制的不大。
4）因为叶子节点是有一条链表相连的，因此范围查询的效率很高。
主要原因：因为 B+ 树是给数据库用的，数据库存放的数据量比较大，而缓存不需要存储大量数据，跳表不需要节点分裂和合并。跳表会更节省内存，更容易实现和进行 Debug。
跳表插入过程
1）首先定义了一个函数 zslRandomLevel()，用于生成随机的插入元素层高，该函数会根据概率 ZSKIPLIST_P 来确定插入元素的层高，同时限制最大层高为 ZSKIPLIST_MAXLEVEL 。
2）在 zslInsert() 函数中，首先声明了需要更新的节点数组 update[] 和 rank[] ，以及变量 i 和 level 。然后从跳表的头节点开始向下遍历，找到插入元素的位置，并记录每层的跨越节点数量 rank[] 。
3）在获取到插入元素的位置后，判断插入元素的随机层高是否大于当前跳表的层高，如果是则需要补全需要更新的节点，并更新跳表的层高。
4）接着创建新节点 x，并根据随机层高分层插入节点，同时更新同层前一节点的步长信息。最后更新新增节点未涉及层节点的步长信息，以及更新跳表的相关信息。
5）最后将插入节点的前后指针指向正确的节点，并增加跳表的长度。最终返回插入的节点 x 。整个过程保证了插入操作的正确性和效率。
int zslRandomLevel(void) {
int level = 1;
// (random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF) 概率为1/4
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
// update存放需要更新的节点
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
level = zslRandomLevel();
if (level > zsl->level) {
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
x = zslCreateNode(level,score,ele);
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
/* update span covered by update[i] as x is inserted here */
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
/* increment span for untouched levels */
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
其他补充
鱼聪明 AI 的回答：
鱼聪明 AI 地址：https://www.yucongming.com/
压缩列表：当有序集合元素数量较少时，Redis会使用压缩列表进行存储。压缩列表是一种紧凑的线性结构，可以节省内存空间。每个元素在压缩列表中占用连续的内存空间，元素之间没有额外的指针等开销。 跳表：当有序集合元素数量较多时，Redis会使用跳表进行存储。跳表是一种有序的数据结构，可以快速地进行查找、插入和删除操作。跳表通过在每个级别添加索引节点来加速查找元素的过程，使得查找的时间复杂度可以达到O(log n)。
实战场景：假设我们需要存储一个社交平台的用户关注列表，其中每个用户关注的人数不定，但是需要按照关注人数的多少进行排序。这时可以使用有序集合来存储用户ID和对应的关注人数，通过有序集合的排序功能可以快速地获取关注人数最多的用户。
跳表的优点：
查询效率高：跳表通过添加索引节点来加速查找元素的过程，使得查询的时间复杂度可以达到O(log n)，效率比较高。 支持范围查找：由于跳表是有序的数据结构，所以可以支持范围查找，例如查找某个范围内的元素。 空间利用率高：跳表通过添加索引节点来加速查找，相比于普通链表来说，空间利用率更高，内存占用更少。
总的来说，跳表在有序集合这种需要快速查找、有序存储的场景下具有明显的优势。
CSDN 某同学的回答
跳表（skiplist）是一种有序的数据结构，它可以通过维护指向每个节点中其他节点的多个指针来快速访问节点。简单来说，跳表是通过向双向链接列添加多个索引而形成的。
与双向链接列表相比，它支持快速搜索、更新和删除，因此适用于需求灵活的场景。
对于双向链表，即使存储在链接列表中的数据是有序的，如果我们想在其中找到某个数据，它也只能从头到尾遍历链接列表，反之亦然。这样搜索效率将非常低，时间复杂度将非常高，达到O（n）。 跳表在搜索某个数据时，首先在索引中找到一个较大的范围，然后再放到原始链接列表中进行精确搜索。因为在添加一层索引后，搜索节点的次数减少了，因此搜索效率大大提高，是典型的空间换时间。
当链表长度相对较大时，索引构建效率将显著提高。第一级链表不是单向链表，而是有序的双向链表。为了以相反的顺序获得范围中的元素。
书籍推荐
《Redis 设计与实现》、《Redis 入门指南》
文章推荐
https://blog.csdn.net/weixin_46935110/article/details/127816987
https://juejin.cn/post/6844903446475177998?searchId=20240314190732B2DD4313232A509DC159
欢迎交流
在阅读完本文后，最主要的你应该了解了 Zset 底层的两种实现，为什么不用红黑树、B+树、普通链表？跳表的插入过程是怎么样的？掌握了这些问题后，你基本能回答出面试官对于 Redis 原理的一些提问了，在文末还有三个问题去检验学习的成果，欢迎大家在评论区进行友好交流！
1）Redis 跳表的插入和删除操作的时间复杂度是多少，是否会随着跳表的大小增加而变化？
2）Redis 跳表的实现原理是什么，它是如何保证查询效率的？
3）Redis 跳表在并发环境下会有哪些可能的性能问题，如何解决这些问题？
点燃求职热情！每周持续更新，海量面试题等你挑战！赶紧关注面试鸭公众号，轻松备战春招和暑期实习！
往期推荐