乐趣区

关于java:Redis跳跃表是如何添加元素的

jiezi

明天分享的这道题来自于蔚来的实在面试题。

Java 面试不可能不问 Redis，问到 Redis 不可能不问 Redis 的罕用数据类型，问到 Redis 的罕用数据类型，不可能不问跳跃表，当问到跳跃表常常会被问到跳跃表的查问和增加流程，所以接下来咱们一起来看这道题的答案吧。

Redis 有序汇合 ZSet 是由 ziplist (压缩列表) 或 skiplist (跳跃表) 组成的。

  1. 压缩列表 ziplist 实质上就是一个字节数组，是 Redis 为了节约内存而设计的一种线性数据结构，能够蕴含多个元素，每个元素能够是一个字节数组或一个整数。

  2. 跳跃表 skiplist 是一种有序数据结构，它通过在每个节点中维持多个指向其余节点的指针，从而达到快速访问节点的目标。跳跃表反对均匀 O(logN)、最坏 O(N) 复杂度的节点查找，还能够通过程序性操作来批量解决节点。

    跳跃表介绍

    跳跃表 Skip List，也称之为跳表，是一种数据结构，用于在有序元素的汇合中进行高效的查找操作。它通过增加多层链表的形式，提供了一种以空间换工夫的形式来减速查找。

跳跃表由一个带有多层节点的链表组成，每一层都是原始链表的一个子集。最底层是一个残缺的有序链表，蕴含所有元素。每个更高层级都是下层级的子集，通过增加额定的指针来跳过一些元素。这些额定的指针称为“跳跃指针”，它们容许快速访问更远的节点，从而缩小了查找所需的比拟次数。

跳跃表的均匀查找时间复杂度为 O(log n)，其中 n 是元素的数量。这使得它比一般的有序链表具备更快的查找性能，并且与均衡二叉搜寻树（如红黑树）相比，实现起来更为简略。

简略的跳跃表如下图所示：

跳跃表增加流程

前置常识：节点随机层数

在开始讲跳跃表的增加流程之前，必须先搞懂一个概念：节点的随机层数。
所谓的随机层数指的是每次增加节点之前，会学生成以后节点的随机层数，依据生成的随机层数来决定将以后节点存在几层链表中。

为什么要这样设计呢？

这样设计的目标是为了保障 Redis 的执行效率。

为什么要生成随机层数，而不是制订一个固定的规定，比方下层节点是上层逾越两个节点的链表组成，如下图所示：

如果制订了规定，那么就须要在增加或删除时，为了满足其规定，做额定的解决，比方增加了一个新节点，如下图所示：

这样就不满足制订的下层节点逾越上层两个节点的规定了，就须要额定的调整下层中的所有节点，这样程序的效率就升高了，所以应用随机层数，不强制制订规定，这样就不须要进行额定的操作，从而也就不会占用服务执行的工夫了。

增加流程

Redis 中跳跃表的增加流程如下图所示：

  1. 第一个元素增加到最底层的有序链表中（最底层存储了所有元素数据）。
  2. 第二个元素生成的随机层数是 2，所以再减少 1 层，并将此元素存储在第 1 层和最低层。
  3. 第三个元素生成的随机层数是 4，所以再减少 2 层，整个跳跃表变成了 4 层，将此元素保留到所有层中。
  4. 第四个元素生成的随机层数是 1，所以把它按程序保留到最初一层中即可。

其余新增节点以此类推。

随机层数源码剖析

随机层数的源码在 t_zset.c/zslRandomLevel(void) 中，如下所示：

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

从源码可知，随机层数有 50% 的概率被调配到 Level 1，25% 的概率被调配到 Level 2，12.5% 的概率被调配到 Level 3，以此类推。

Redis 跳跃表默认容许最大的层数是 32，此值在 ZSKIPLIST_MAXLEVEL 源码中被定义。

小结

跳跃表是由多个有序的链表组成的，最底层存储了所有元素的数据，这样存储让它的查问效率更高，查问复杂度从 O(n) 变为了 O(log n)。跳跃表的增加流程是依据节点生成的随机层数，将它插入到最底层节点和下层的 N-1 层节点中，形容增加流程的要害就是了解随机层数以及其背地的原理。

参考 & 鸣谢

https://segmentfault.com/a/1190000022028505

本文已收录到我的面试小站 www.javacn.site，其中蕴含的内容有：Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、音讯队列等模块。

退出移动版