likes
comments
collection
share

Redis两层数据结构简介

作者站长头像
站长
· 阅读数 20

Redis两层数据结构简介

Redis两层数据结构简介

Redis两层数据结构简介

Redis 的性能高的原因之一是它每种数据结构都是经过专门设计的，并都有一种或多种数据结构来支持，依赖这些灵活的数据结构，来提升读取和写入的性能。如果要了解 Redis 的数据结构，可以从两个不同的层面来讨论它：

  • 第一个层面，是从使用者的角度，这一层面也是 Redis 暴露给外部的调用接口，比如：String, List, Hash, Set, Sorted Set
  • 第二个层面，是从内部实现的角度，属于更底层的实现，比如：dict, SDS, linkedlist, ziplist, quicklist, skiplist, intset

本文的重点在于讨论第二个层面：

  • Redis 数据结构的内部实现
  • 这两个层面的数据结构之间的关系：Redis 如何通过组合第二个层面的各种基础数据结构来实现第一个层面的更高层的数据结构

Redis 设计原则

存储效率。Redis 是专用于存储数据的，它对计算机资源的主要消耗就在于内存，因此节省内存是它非常非常重要的一个方面。这意味着 Redis 一定是非常精细地考虑了压缩数据、减少内存碎片等问题。

快速响应时间。与快速响应时间相对的，是高吞吐量。Redis 是用于提供在线访问的，对于单个请求的响应时间要求很高，因此，快速响应时间是比高吞吐量更重要的目标。

单线程。Redis 的性能瓶颈不在于 CPU 资源，而在于内存访问和网络 IO。而采用单线程的设计带来的好处是，极大简化了数据结构和算法的实现。相反，Redis 通过异步 IO 和 pipelining 等机制来实现高速的并发访问。显然，单线程的设计，对于单个请求的快速响应时间也提出了更高的要求。

RedisObject：两层数据结构的桥梁

什么是 RedisObject?

  • 从 Redis 的使用者的角度来看，一个 Redis 节点包含多个 Database（非 Cluster 模式下默认是 16 个，Cluster 模式下只能是 1 个），而一个 Database 维护了从 Key Space 到 Object Space 的映射关系，这个映射关系的 Key 是 String 类型，而 Value 可以是多种数据类型，比如：String, List, Hash, Set, Sorted Set等。
  • 而从 Redis 内部实现的角度来看，Database 内的这个映射关系是用一个 dict 来维护的。Dict 的 Key 固定用一种数据结构来表达就够了，这就是动态字符串 SDS；而 Value 则比较复杂，为了在同一个 dict 内能够存储不同类型的 Value，这就需要一个通用的数据结构，这个通用的数据结构就是 robj，全名是 RedisObject

举个例子：

  • 如果 Value 是 List 类型，那么它的内部存储结构是一个quicklist或者是一个ziplist
  • 如果 Value 是 String 类型，那么它的内部存储结构一般情况下是一个 SDS。但如果 String 类型的 Value 的值是一个数字，那么 Redis 内部还会把它转成 Long 型来存储，从而减小内存使用。

Redis的数据结构定义：（基于 Redis 3.2 版本）

Redis两层数据结构简介

一个 robj 包含如下5个字段：

  • type: 对象的数据类型。占 4 个 bit。可能的取值有 5 种：OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_Hash，分别对应 Redis 对外暴露的5种数据结构
  • encoding: 对象的内部表示方式（也可以称为编码）。占 4 个 bit。可能的取值有 10 种，即前面代码中的 10 个OBJ_ENCODING_XXX常量。
  • lru: 做 LRU 替换算法用，占 24 个 bit。
  • refcount: 引用计数。它允许 robj 对象在某些情况下被共享。
  • ptr: 数据指针。指向真正的数据。比如，一个代表 String 的 robj，它的 ptr 可能指向一个 SDS 结构；一个代表 List 的 robj，它的 ptr 可能指向一个 quicklist。

refcount 字段的说明：

C 语言本身不像 Java 有内存自动回收机制。但是，在开始的时候曾说到 Redis 的对象系统采用计数技术实现了内存回收机制。Redis 也通过这一机制通过跟进对象的引用计数信息，在适当的时候进行内存回收。而计数信息在 RedisObject 结构中由 refcount 属性记录。

  • 当新建一个对象时，refcount 的值被初始化为 1.
  • 当对象被一个新程序引用时，refcount + 1.
  • 当对象不再被一个程序引用时，refcount - 1.

encoding 字段的说明：

这里特别需要仔细察看的是 encoding 字段。对于同一个 type，还可能对应不同的 encoding，这说明同样的一个数据类型，可能存在不同的内部表示方式。而不同的内部表示，在内存占用和查找性能上会有所不同。

当 type = OBJ_STRING的时候，表示这个 robj 存储的是一个 String，这时 encoding 可以是下面 3 种中的一种：

  • OBJ_ENCODING_RAW: String 采用原生的表示方式，即用 SDS 来表示。
  • OBJ_ENCODING_INT: String 采用数字的表示方式，实际上是一个 Long 型。
  • OBJ_ENCODING_EMBSTR: String 采用一种特殊的嵌入式的 SDS 来表示。

当 type = OBJ_Hash的时候，表示这个 robj 存储的是一个 Hash，这时 encoding 可以是下面 2 种中的一种：

  • OBJ_ENCODING_HT: Hash 采用一个dict来表示
  • OBJ_ENCODING_ZIPLIST: Hash 采用一个ziplist来表示

10 种 encoding 的取值说明：

Redis两层数据结构简介

robj的作用：

RedisObject 就是 Redis 对外暴露的第一层面的数据结构：String, List, Hash, Set, Sorted Set，而每一种数据结构的底层实现所对应的是哪些第二层面的数据结构（dict, SDS, ziplist, quicklist, skiplist等），则通过不同的encoding来区分。可以说，robj是联结两个层面的数据结构的桥梁。

Redis的第一层数据结构

1、String： String 是最简单的数据类型，一般用于复杂的计数功能的缓存：微博数，粉丝数等。

底层实现方式：动态字符串 SDS 或者 Long

2、Hash： Hash 适合用于存储对象，因为一个对象的各个属性，正好对应一个 Hash 结构的各个 Field，可以方便地操作对象中的某个字段。

底层实现方式：压缩列表 ziplist 或者字典 dict

3、List： List 的实现为一个双向链表，经常被用作队列使用，支持在链表两端进行 push 和 pop 操作，时间复杂度为O(1)；同时也支持在链表中的任意位置的存取操作，但是需要对 List 进行遍历，时间复杂度为 O(n)。

List 的应用场景非常多，比如微博的关注列表，粉丝列表，消息列表等功能都可以用 Redis 的 List 结构来实现。可以利用 lrange 命令，做基于 Redis 的分页功能。

Redis 3.2 之前的底层实现方式：压缩列表 ziplist 或者 双向循环链表 linkedlist

Redis 3.2 及之后的底层实现方式：quicklist

4、Set： Set 是一个存放不重复值的无序集合，可做全局去重的功能，提供了判断某个元素是否在 Set 集合内的功能，这个也是 List 所不能提供的。基于 Set 可以实现交集、并集、差集的操作，计算共同喜好，全部的喜好，自己独有的喜好等功能。

底层实现方式：有序整数集合 intset 或者字典 dict

5、Sorted Set： Sorted set 相比 Set 多了一个权重参数 Score，集合中的元素能够按 Score 进行排列。可以做排行榜应用，取 TOP N 操作。另外，Sorted Set 可以用来做延时任务。最后一个应用就是可以做范围查找。

底层实现方式：压缩列表 ziplist 或者 skipset

Redis两层数据结构简介

Redis的第二层数据结构

1、SDS（简单动态字符串）

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示；

　　在 Redis 里面， C 字符串只会作为字符串字面量（string literal）， 用在一些无须对字符串值进行修改的地方， 比如打印日志；

　　当 Redis 需要的不仅仅是一个字符串字面量， 而是一个可以被修改的字符串值时， Redis 就会使用 SDS 来表示字符串值： 比如在 Redis 的数据库里面， 包含字符串值的键值对在底层都是由 SDS 实现的。

C 语言字符串有以下几个问题：

  • 计算字符串的长度时间复杂度为 O(n)；
  • 每一次删除和增加字符串的长度，都需要重新分配空间；
  • 缓存区异常；
  • 类似 ASCII 码，字符串中不能出现空白符。否则认为是字符串的结尾；

Redis 改进：

  • Redis 的结构中存储了字符串的长度，所以获取字符串的长度的时间复杂的为 O(1)
  • 由于 Redis 分配的空间不是按照需要的分配，一般会有多余的空间（空间预分配）。所以字符串长度增加时，剩余的空间足够，就可以避免重新分配空间。减少字符的长度时也不是直接删除多余的内容。而是设置已使用空间的长度，隐藏删除内容（惰性释放）。
  • Redis 会先检查总的空间大小，满足才会分配，避免缓存区溢出；
  • 不存在空白符的干扰

在SDS.h/SDShdr下定义了SDS的结构　

struct SDShdr {
  // 记录 buf 数组中已使用字节的数量
  // 等于 SDS 所保存字符串的长度
  int len;
​
  // 记录 buf 数组中未使用字节的数量
  int free;
​
  // 字节数组，用于保存字符串
  char buf[];
​
};

属性说明

  • free 属性的值为 0 ， 表示这个 SDS 没有分配任何未使用空间。
  • len 属性的值为 5 ， 表示这个 SDS 保存了一个五字节长的字符串。
  • buf 属性是一个 char 类型的数组， 数组的前五个字节分别保存了 'R' 、 'e' 、 'd' 、 'i' 、 's' 五个字符， 而最后一个字节则保存了空字符 '\0';

Redis两层数据结构简介

额外分配空间数量的公式：

1.如果 SDS 修改之后，SDS 的长度( len 属性的值)小于 1MB，那么就会分配和len属性同样大的未使用空间，也就是 free 属性会和 len 属性相同，相当于将原数组长度 double。

2.如果 SDS 修改之后，SDS 的长度( len 属性的值)大于或等于 1MB，那么就会分配固定的 1MB 未使用空间。

3.而 free 属性就决定了是不是需要进行额外的内存重分配操作，假如 free 为 7，而你需要拼接的字符串长度只有 5，那就不需要进行内存重分配操作，直接存储就可以。

实际在数据存储过程中，字符串对象根据保存值的类型、长度不同，可以分为三种存储结构：

  • Int：如果存储的是整数值（可以用 Long 表示），则底层通过如下结构进行存储，其中 type 代表当前对象为 String 对象，encoding 表示当前对象的编码格式，ptr 的属性保存是真实的值；

    Redis两层数据结构简介

  • raw：如果存储的是字符串且字符串长度超过 39 字节，则底层通过如下结构进行存储，其中 type 代表当前对象为 String 对象，encoding 表示当前对象的编码格式，ptr 为指针指向一个 SDS（shshdr：简单动态字符串对象）来保存具体的值；

Redis两层数据结构简介　Redis两层数据结构简介

  • embstr: 如果存储的是字符串且字符串长度未超过 39 字节，则底层通过 embstr 结构进行存储（需要一块连续的内存空间）

    Redis两层数据结构简介

编码转换

Redis两层数据结构简介

最后，对 C 字符串和 SDS 之间的区别做一个总结：

C 字符串SDS
获取字符串长度复杂度为 O(N)获取字符串长度复杂度为 O(1)
修改字符串时需要执行 N 次内存重分配修改字符串时最多需要执行 N 次内存重分配
不能保存二进制数据可以保存二进制数据
可以使用 C 字符串函数库的所有函数可以使用 C 字符串函数库的一部分函数

2、List（双向链表）

Redis 的 List 对象的底层实现之一就是链表。C 语言本身没有链表这个数据结构的，所以 Redis 自己设计了一个链表数据结构。

链表节点结构设计

先来看看「链表节点」结构的样子：

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

有前置节点和后置节点，可以看的出，这个是一个双向链表。

Redis两层数据结构简介

链表结构设计

不过，Redis 在 listNode 结构体基础上又封装了 list 这个数据结构，这样操作起来会更方便，链表结构如下：

typedef struct list {
    //链表头节点
    listNode *head;
    //链表尾节点
    listNode *tail;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void (*free)(void *ptr);
    //节点值比较函数
    int (*match)(void *ptr, void *key);
    //链表节点数量
    unsigned long len;
} list;

list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数。

举个例子，下面是由 list 结构和 3 个 listNode 结构组成的链表。

Redis两层数据结构简介

链表的优势与缺陷

Redis 的链表实现优点如下：

  • listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；
  • list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1) ；
  • list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需 O(1) ；
  • listNode 链表节使用 void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

链表的缺陷也是有的：

  • 链表每个节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU 缓存来加速访问。
  • 还有一点，保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。

因此，Redis 3.0 的 List 对象在数据量比较少的情况下，会采用「压缩列表」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。

不过，压缩列表存在性能问题（具体什么问题，下面会说），所以 Redis 在 3.2 版本设计了新的数据结构 quicklist，并将 List 对象的底层数据结构改由 quicklist 实现。

然后在 Redis 5.0 设计了新的数据结构 listpack，沿用了压缩列表紧凑型的内存布局，最终在最新的 Redis 版本，将 Hash 对象和 Zset 对象的底层数据结构实现之一的压缩列表，替换成由 listpack 实现。

3、ziplist（压缩链表）

压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。

Redis两层数据结构简介

压缩列表在表头有三个字段：

  • zlbytes ，长度4个字节，记录整个压缩列表占用内存字节数；
  • zltail ，长度4个字节，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
  • zllen ，长度2个字节，记录压缩列表包含的节点数量；当这个属性的值小于 65535 时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 65535 时，节点的真实数量需要遍历整个压缩列表才能计算得出
  • zlend ，长度1个字节，标记压缩列表的结束点，固定值 0xFF（十进制 255 ）。

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。

另外，压缩列表节点（entry）的构成如下：

Redis两层数据结构简介

压缩列表节点包含三部分内容：

  • prevlen ，记录了「前一个节点」的长度；
  • encoding ，记录了当前节点实际数据的类型以及长度；
  • data ，记录了当前节点的实际数据；

当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及数据的大小，会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。

分别说下，prevlen 和 encoding 是如何根据数据的大小和类型来进行不同的空间大小分配。

压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」，而且 prevlen 属性的空间大小跟前一个节点长度值有关，比如：

  • 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
  • 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

encoding 属性的空间大小跟数据是字符串还是整数，以及字符串的长度有关：

  • 如果当前节点的数据是整数，则 encoding 会使用 1 字节的空间进行编码。
  • 如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节/2字节/5字节的空间进行编码。

连锁更新

压缩列表除了查找复杂度高的问题，还有一个问题。

压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

前面提到，压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配：

  • 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
  • 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，如下图：

Redis两层数据结构简介

因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。

这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为 e1 的前置节点，如下图：

Redis两层数据结构简介

因为 e1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作，并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

多米诺牌的效应就此开始。

Redis两层数据结构简介

e1 原本的长度在 250～253 之间，因为刚才的扩展空间，此时 e1 的长度就大于等于 254 了，因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。

正如扩展 e1 引发了对 e2 扩展一样，扩展 e2 也会引发对 e3 的扩展，而扩展 e3 又会引发对 e4 的扩展…. 一直持续到结尾。

这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」，就像多米诺牌的效应一样，第一张牌倒下了，推动了第二张牌倒下；第二张牌倒下，又推动了第三张牌倒下….，

压缩列表的缺陷

空间扩展操作也就是重新分配内存，因此连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能。

所以说，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，最糟糕的是会有「连锁更新」的问题。

因此，压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新，也是能接受的。

虽说如此，Redis 针对压缩列表在设计上的不足，在后来的版本中，新增设计了两种数据结构：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。这两种数据结构的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的「连锁更新」的问题。

4、skiplist（跳表）

Redis 只有在 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。

Zset 对象是唯一一个同时使用了两个数据结构来实现的 Redis 对象，这两个数据结构一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

Zset 对象能支持范围查询（如 ZRANGEBYSCORE 操作），这是因为它的数据结构设计采用了跳表，而又能以常数复杂度获取元素权重（如 ZSCORE 操作），这是因为它同时采用了哈希表进行索引。

接下来，详细的说下跳表。

跳表结构设计

链表在查找元素的时候，因为需要逐一查找，所以查询效率非常低，时间复杂度是 O(N)，于是就出现了跳表。跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。

那跳表长什么样呢？我这里举个例子，下图展示了一个层级为 3 的跳表。

Redis两层数据结构简介

图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

  • L0 层级共有 5 个节点，分别是节点1、2、3、4、5；
  • L1 层级共有 3 个节点，分别是节点 2、3、5；
  • L2 层级只有 1 个节点，也就是节点 3 。

如果我们要在链表中查找节点 4 这个元素，只能从头开始遍历链表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再往前遍历找到节点 4。

可以看到，这个查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度就是 O(logN)。

那跳表节点是怎么实现多层级的呢？这就需要看「跳表节点」的数据结构了，如下：

typedef struct zskiplistNode {
    //Zset 对象的元素值
    SDS ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
​
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

Zset 对象要同时保存元素和元素的权重，对应到跳表节点结构里就是 SDS 类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针，指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的 zskiplistLevel 结构体类型的 level 数组。

level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」，跨度时用来记录两个节点之间的距离。

比如，下面这张图，展示了各个节点的跨度。

Redis两层数据结构简介

第一眼看到跨度的时候，以为是遍历操作有关，实际上并没有任何关系，遍历操作只需要用前向指针就可以完成了。

跨度实际上是为了计算这个节点在跳表中的排位。具体怎么做的呢？因为跳表中的节点都是按序排列的，那么计算某个节点排位的时候，从头节点点到该结点的查询路径上，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位。

举个例子，查找图中节点 3 在跳表中的排位，从头节点开始查找节点 3，查找的过程只经过了一个层（L3），并且层的跨度是 3，所以节点 3 在跳表中的排位是 3。

另外，图中的头节点其实也是 zskiplistNode 跳表节点，只不过头节点的后向指针、权重、元素值都会被用到，所以图中省略了这部分。

问题来了，由谁定义哪个跳表节点是头节点呢？这就介绍「跳表」结构体了，如下所示：

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

跳表结构里包含了：

  • 跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
  • 跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量；
  • 跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量；

跳表节点查询过程

查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，共有两个判断条件：

  • 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
  • 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。

如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

举个例子，下图有个 3 层级的跳表。

Redis两层数据结构简介

如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的：

  • 先从头节点的最高层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；
  • 但是该层上的下一个节点是空节点，于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[1];
  • 「元素：abc，权重：3」节点的 leve[1] 的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据「大于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]；
  • 「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束。

跳表节点层数设置

跳表的相邻两层的节点数量的比例会影响跳表的查询性能。

举个例子，下图的跳表，第二层的节点数量只有 1 个，而第一层的节点数量有 6 个。

Redis两层数据结构简介

这时，如果想要查询节点 6，那基本就跟链表的查询复杂度一样，就需要在第一层的节点中依次顺序查找，复杂度就是 O(N) 了。所以，为了降低查询复杂度，我们就需要维持相邻层结点数间的关系。

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN) 。

下图的跳表就是，相邻两层的节点数量的比例是 2 : 1。

Redis两层数据结构简介

那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢？

如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。

Redis 则采用一种巧妙的方法是，跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

具体的做法是，跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 32。

Redis两层数据结构简介

参考资料：

  • 《Redis 设计与实现》
  • 《Redis 源码剖析与实战》

总结：

常言道：知其然，知其所有然。我们知道 Redis 是一种非常“快”的非关系型数据库，那么它为什么快？怎样的数据结构设计才能够支持它在内存中的高速访问？

看完这篇文章，相信你对 Redis 以及它的的五种数据结构产生了更深的认识。

推荐阅读

浅谈电子标书加解密那些事V1

一次数据同步的模型分享

数据库备份

重构-把代码写的更漂亮

浅析大数据OLAP引擎-Presto

招贤纳士

政采云技术团队（Zero），一个富有激情、创造力和执行力的团队，Base 在风景如画的杭州。团队现有 500 多名研发小伙伴，既有来自阿里、华为、网易的“老”兵，也有来自浙大、中科大、杭电等校的新人。团队在日常业务开发之外，还分别在云原生、区块链、人工智能、低代码平台、中间件、大数据、物料体系、工程平台、性能体验、可视化等领域进行技术探索和实践，推动并落地了一系列的内部技术产品，持续探索技术的新边界。此外，团队还纷纷投身社区建设，目前已经是 google flutter、scikit-learn、Apache Dubbo、Apache Rocketmq、Apache Pulsar、CNCF Dapr、Apache DolphinScheduler、alibaba Seata 等众多优秀开源社区的贡献者。如果你想改变一直被事折腾，希望开始折腾事；如果你想改变一直被告诫需要多些想法，却无从破局；如果你想改变你有能力去做成那个结果，却不需要你；如果你想改变你想做成的事需要一个团队去支撑，但没你带人的位置；如果你想改变本来悟性不错，但总是有那一层窗户纸的模糊……如果你相信相信的力量，相信平凡人能成就非凡事，相信能遇到更好的自己。如果你希望参与到随着业务腾飞的过程，亲手推动一个有着深入的业务理解、完善的技术体系、技术创造价值、影响力外溢的技术团队的成长过程，我觉得我们该聊聊。任何时间，等着你写点什么，发给 zcy-tc@cai-inc.com

微信公众号

文章同步发布，政采云技术团队公众号，欢迎关注

Redis两层数据结构简介