记得点赞 + 关注呦。

前言

Redis 有五种根本数据类型，可是大家晓得这五种数据类型的底层是咋实现吗？接下就带大家理解一下 String、List、Hash、Set、Sorted Set 底层是如何实现的，在这之前，先来看下上面的根本数据结构，别离有简略动静字符串 (SDS)、链表、字典、跳跃表、整数汇合以及压缩列表，它们是 Redis 数据结构的根本组成部分。

五种数据结构底层实现

<font size=4 color=green>1. String</font>

• 如果一个字符串对象保留的是整数值，并且这个整数值能够用 long 类型来示意，那么字符串对象会将整数值保留在字符串对象构造的 ptr 属性外面（将 void* 转换成 long），并将字符串对象的编码设置为 int。
• 如果字符串对象保留的是一个字符串值，并且这个字符串值的长度大于 39 字节，那么字符串对象将应用一个简略动静字符串（SDS）来保留这个字符串值，并将对象的编码设置为 raw。
• 如果字符串对象保留的是一个字符串值，并且这个字符串值的长度小于等于 39 字节，那么字符串对象将应用 embstr 编码的形式来保留这个字符串值。

<font size=4 color=green>2. List</font>

• 列表对象的编码能够是 ziplist 或者 linkedlist。
• 列表对象保留的所有字符串元素的长度都小于 64 字节并且保留的元素数量小于 512 个，应用 ziplist 编码；否则应用 linkedlist；

<font size=4 color=green>3. Hash</font>

• 哈希对象的编码能够是 ziplist 或者 hashtable。
• 哈希对象保留的所有键值对的键和值的字符串长度都小于 64 字节并且保留的键值对数量小于 512 个，应用 ziplist 编码；否则应用 hashtable；

<font size=4 color=green>4. Set</font>

• 汇合对象的编码能够是 intset 或者 hashtable。
• 汇合对象保留的所有元素都是整数值并且保留的元素数量不超过 512 个，应用 intset 编码；否则应用 hashtable；

<font size=4 color=green>5. Sorted Set</font>

• 有序汇合的编码能够是 ziplist 或者 skiplist
• 有序汇合保留的元素数量小于 128 个并且保留的所有元素成员的长度都小于 64 字节。应用 ziplist 编码；否则应用 skiplist；

接下来别离说说这些底层数据结构。

一、简略动静字符串（SDS）

Redis 本人构建了一种名为简略动静字符串（simple dynamic string，SDS）的形象类型，并将 SDS 用作 Redis 的默认字符串示意。如：

 set msg "hello world"  

key 和 value 底层都是用 SDS 来实现的。
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’。

SDS 与 C 语言字符串比拟相近，但领有更过的劣势：

1. SDS 获取字符串长度工夫复杂度 O(1)：因为 SDS 通过 len 字段来存储长度，应用时间接读取就能够；C 语言要想获取字符串长度须要遍历整个字符串，工夫复杂度 O(N)。2. SDS 能杜绝缓冲区的溢出：因为当 SDS API 要对 SDS 进行批改时，会先查看 SDS 的空间是否足够，如果不够的话 SDS 会主动扩容，So，不会造成缓冲区溢出。而 C 语言则不剧本这个性能。3. SDS 能缩小批改字符串时带来的内存重调配次数：- 空间预调配：当 SDS 扩容时不只是会减少须要的空间大小，还会额定的调配一些未应用的空间。调配的规定是：如果调配后 SDS 的长度小于 1MB，那么会调配等于调配后 SDS 的大小的未应用空间，简略说就是，SDS 动态分配后是 16KB，那么就会多调配 16KB 的未应用空间；如果 小于 1MB，那么久调配 1MB 的未应用空间。- 惰性空间开释：惰性空间开释用于优化 SDS 的字符串缩短操作：当 SDS 的 API 须要缩短 SDS 保留的字符串时，并不会立刻内存重调配来回收多进去的字节，而是用 free 来记录未应用空间。

二、链表

  链表提供了高效的节点重排能力，以及程序性的节点拜访形式，并且能够通过增删节点来灵便地调整链表的长度。链表在 Redis 中的利用十分宽泛，比方 List 的底层实现之一链表，当一个 List 蕴含了数量比拟多的元素，又或者列表中蕴含的元素都是比拟长的字符串时，Redis 就会应用链表作为 List 的底层实现。除了用作 List 的底层实现之外，公布与订阅、慢查问、监视器等动能也用到了链表，Redis 服务器自身还应用链表来保留多个客户端的状态信息，以及应用链表来构建客户端输入缓冲区。
  每个链表节点应用一个 adlist.h/listNode 构造来示意：

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

多个 listNode 能够通过 prev 和 next 指针组成双端链表，如下图所示。

尽管仅仅应用多个 listNode 构造就能够组成链表，但应用 adlist.h/list 来持有链表的话，操作起来会更不便：

typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所蕴含的节点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值开释函数
    void (*free)(void *ptr);

    // 节点值比照函数
    int (*match)(void *ptr, void *key);

} list;

list 构造为链表提供了表头指针 head、表尾指针 tail，以及链表长度计数器 len，而 dup、free 和 match 成员则是用于实现多态链表所需的类型特定函数：

• dup 函数用于复制链表节点所保留的值；
• free 函数用于开释链表节点所保留的值；
• match 函数则用于比照链表节点所保留的值和另一个输出值是否相等。
  下图是由一个 list 构造和三个 listNode 构造组成的链表：
  
  Redis 的链表实现的个性能够总结如下：
• 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1)。
• 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的拜访以 NULL 为起点。
• 带表头指针和表尾指针：通过 list 构造的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1)。
• 带链表长度计数器：程序应用 list 构造的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O(1)。

• 多态：链表节点应用 void* 指针来保留节点值，并且能够通过 list 构造的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表能够用于保留各种不同类型的值。

  三、字典

  字典，又称符号表（symbol table）、关联数组（associative array）或者映射（map），是一种用于保留键值对（key-value pair）的形象数据结构。其中 Key 是惟一的。相似 Java 的 Map。
  字典在 Redis 中次要被利用与：

• Redis 数据库底层就是用字典实现的，对数据库的增、删、改、查操作都是构建在对字典的操作之上，比方：

  > set msg "hello world"
  OK

  这个就是创立一个 key 为 “msg”，value 为 “hello world” 的键值对，保留在代表数据库的字典中。

• 字典还是哈希键的底层实现之一：当一个哈希键蕴含的键值对比拟多，又或者键值对中的元素都是比拟长的字符串时，Redis 就会应用字典作为哈希键的底层实现。

Redis 的字典应用哈希表作为底层实现，一个哈希表外面能够有多个哈希表节点，而每个哈希表节点就保留了字典中的一个键值对。
接下来的三个大节将别离介绍 Redis 的哈希表、哈希表节点、以及字典的实现。

哈希表

Redis 字典所应用的哈希表由 dict.h/dictht 构造定义：

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

table 属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry 构造的指针，每个 dictEntry 构造保留着一个键值对。

size 属性记录了哈希表的大小，也即是 table 数组的大小，而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

sizemask 属性的值总是等于 size – 1，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引下面。

下图 展现了一个大小为 4 的空哈希表（没有蕴含任何键值对）。

哈希节点

哈希表节点应用 dictEntry 构造示意，每个 dictEntry 构造都保留着一个键值对：

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，造成链表
    struct dictEntry *next;

} dictEntry;

key 属性保留着键值对中的键，而 v 属性则保留着键值对中的值，其中键值对的值能够是一个指针，或者是一个 uint64_t 整数，又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针，这个指针能够将多个哈希值雷同的键值对连贯在一次，以此来解决键抵触（collision）的问题。

举个例子，下图就展现了如何通过 next 指针，将两个索引值雷同的键 k1 和 k0 连贯在一起。

字典

Redis 中的字典由 dict.h/dict 构造示意：

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 公有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type 属性和 privdata 属性是针对不同类型的键值对，为创立多态字典而设置的：

• type 属性是一个指向 dictType 构造的指针，每个 dictType 构造保留了一簇用于操作特定类型键值对的函数，Redis 会为用处不同的字典设置不同的类型特定函数。
• 而 privdata 属性则保留了须要传给那些类型特定函数的可选参数。

ht 属性是一个蕴含两个项的数组，数组中的每个项都是一个 dictht 哈希表，个别状况下，字典只应用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时应用。

除了 ht[1] 之外，另一个和 rehash 无关的属性就是 rehashidx：它记录了 rehash 目前的进度，如果目前没有在进行 rehash，那么它的值为 -1。

下图 展现了一个一般状态下（没有进行 rehash）的字典：

哈希算法

当将一个新的键值对插入到字典中，须要计算索引值，Redis 计算索引值的办法是：

# 应用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 应用哈希表的 sizemask 属性和哈希值，计算出索引值
# 依据状况不同，ht[x] 能够是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

相似 Java 的 HashMap，计算 key 的 hash 值，而后 hash & (len – 1), 而 Redis 的 sizemask 就是 size – 1。

哈希抵触怎么办

当呈现 Hash 抵触时，Redis 应用的是 链地址法 来解决抵触，链地址法就是将抵触的节点形成一个链表放在该索引地位上，Redis 采纳的是头插法。解决 hash 抵触的还有三种办法，别离是：凋谢定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）、再哈希法以及建设一个公共溢出区，当前会独自介绍一些解决 hash 抵触的四种办法。

rehash

随着一直的操作，hash 表中的键值对可能会增多或缩小，为了让哈希表的负载因子放弃在一个范畴内，须要对 hash 表进行扩容或膨胀，膨胀和扩容的过程就叫 rehash。rehash 过程如下：

1. 为字典的 ht[1] 哈希表调配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 以后蕴含的键值对数量（也即是 ht[0].used 属性的值）(ht 是字典中的 hash 表，上文有介绍)：

   • 如果执行的是扩大操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n（2 的 n 次方幂）；
   • 如果执行的是膨胀操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n。
2. 将保留在 ht[0] 中的所有键值对 rehash 到 ht[1] 下面：rehash 指的是从新计算键的哈希值和索引值，而后将键值对搁置到 ht[1] 哈希表的指定地位上。
3. 当 ht[0] 蕴含的所有键值对都迁徙到了 ht[1] 之后（ht[0] 变为空表），开释 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做筹备

当以下条件中的任意一个被满足时，程序会主动开始对哈希表执行扩大操作：

服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1；
服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5；
其中哈希表的负载因子能够通过公式：

# 负载因子 = 哈希表已保留节点数量 / 哈希表大小  
load_factor = ht[0].used / ht[0].size

计算得出。

比如说，对于一个大小为 4，蕴含 4 个键值对的哈希表来说，这个哈希表的负载因子为：

load_factor = 4 / 4 = 1
又比如说，对于一个大小为 512，蕴含 256 个键值对的哈希表来说，这个哈希表的负载因子为：

load_factor = 256 / 512 = 0.5
依据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行，服务器执行扩大操作所需的负载因子并不相同，这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中，Redis 须要创立以后服务器过程的子过程，而大多数操作系统都采纳写时复制（copy-on-write）技术来优化子过程的应用效率，所以在子过程存在期间，服务器会进步执行扩大操作所需的负载因子，从而尽可能地防止在子过程存在期间进行哈希表扩大操作，这能够防止不必要的内存写入操作，最大限度地节约内存。

另一方面，当哈希表的负载因子小于 0.1 时，程序主动开始对哈希表执行膨胀操作。

渐进式 rehash

rehash 时会将 ht[0] 所有的键值对迁徙到 ht[1] 中，但这个动作不是一次性的，而是分屡次、渐进式地实现。这样的所得起因时：当数据量大的时候一次性迁徙会造成服务器在一段时间内定制服务。为了防止产生这样的事就呈现了 渐进式 rehash。
以下是哈希表渐进式 rehash 的具体步骤：
1) 为 ht[1] 调配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
2) 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为 0，示意 rehash 工作正式开始。
3) 在 rehash 进行期间，每次对字典执行增加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作实现之后，程序将 rehashidx 属性的值增一。
4) 随着字典操作的一直执行，最终在某个工夫点上，ht[0] 的所有键值对都会被 rehash 至 ht[1]，这时程序将 rehashidx 属性的值设为 -1，示意 rehash 操作已实现。

渐进式 rehash 的益处在于它采取分而治之的形式，将 rehash 键值对所需的计算工作均滩到对字典的每个增加、删除、查找和更新操作上，从而防止了集中式 rehash 而带来的宏大计算量。在 rehash 期间，字典的删改查操作都是同时作用在 ht[0] 以及 ht[1] 上的。如查找一个键，会当初 ht[0] 查找，找不到就去 ht[1] 查找，留神的是减少操作，新增的键值对只会保留到 ht[1] 上，不会保留到 ht[0] 上，这一措施保障了 ht[0] 的键值只减不增，随着 rehash 操作 ht[0] 最终会变成空表。

Redis 的字典实现的个性能够总结如下：

• 字典被宽泛用于实现 Redis 的各种性能，其中包含数据库和哈希键。
• Redis 中的字典应用哈希表作为底层实现，每个字典带有两个哈希表，一个用于平时应用，另一个仅在进行 rehash 时应用。
• 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 应用 MurmurHash2 算法来计算键的哈希值。
• 哈希表应用链地址法来解决键抵触，被调配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对哈希表进行扩大或者膨胀操作时，程序须要将现有哈希表蕴含的所有键值对 rehash 到新哈希表外面，并且这个 rehash 过程并不是一次性地实现的，而是渐进式地实现的。

四、跳跃表

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

  在大部分状况下，跳跃表的效率能够和均衡树相媲美，并且因为跳跃表的实现比均衡树要来得更为简略，所以有不少程序都应用跳跃表来代替均衡树。

  Redis 应用跳跃表作为有序汇合键的底层实现之一：如果一个有序汇合蕴含的元素数量比拟多，又或者有序汇合中元素的成员（member）是比拟长的字符串时，Redis 就会应用跳跃表来作为有序汇合键的底层实现。

  Redis 只在两个中央用到了跳跃表，一个是实现有序汇合键，另一个是在集群节点中用作外部数据结构，除此之外，跳跃表在 Redis 外面没有其余用处。

Redis 的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个构造定义，其中 zskiplistNode 构造用于示意跳跃表节点，而 zskiplist 构造则用于保留跳跃表节点的相干信息，比方节点的数量，以及指向表头节点和表尾节点的指针，等等。

上图展现了一个跳跃示意例，位于图片最右边的是 zskiplist 构造，该构造蕴含以下属性：

• header：指向跳跃表的表头节点。
• tail：指向跳跃表的表尾节点。
• level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
• length：记录跳跃表的长度，也即是，跳跃表目前蕴含节点的数量（表头节点不计算在内）。

位于 zskiplist 构造右方的是四个 zskiplistNode 构造，该构造蕴含以下属性：

• 层（level）：节点中用 L1、L2、L3 等字样标记节点的各个层，L1 代表第一层，L2 代表第二层，以此类推。每个层都带有两个属性：后退指针和跨度。后退指针用于拜访位于表尾方向的其余节点，而跨度则记录了后退指针所指向节点和以后节点的间隔。在下面的图片中，连线上带有数字的箭头就代表后退指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，拜访会沿着层的后退指针进行。
• 后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于以后节点的前一个节点。后退指针在程序从表尾向表头遍历时应用。
• 分值（score）：各个节点中的 1.0、2.0 和 3.0 是节点所保留的分值。在跳跃表中，节点按各自所保留的分值从小到大排列。
• 成员对象（obj）：各个节点中的 o1、o2 和 o3 是节点所保留的成员对象。

留神表头节点和其余节点的结构是一样的：表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性都不会被用到，所以图中省略了这些局部，只显示了表头节点的各个层。

本节接下来的内容将对 zskiplistNode 和 zskiplist 两个构造进行更具体的介绍。

1. 跳跃表节点

跳跃表节点的实现由 redis.h/zskiplistNode 构造定义：

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 后退指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];} zskiplistNode;

<font size=5 color=green> 层 </font>
跳跃表节点的 level 数组能够蕴含多个元素，每个元素都蕴含一个指向其余节点的指针，程序能够通过这些层来放慢拜访其余节点的速度，一般来说，层的数量越多，拜访其余节点的速度就越快。

每次创立一个新跳跃表节点的时候，程序都依据幂次定律（power law，越大的数呈现的概率越小）随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的“高度”。

下图别离展现了三个高度为 1 层、3 层和 5 层的节点，因为 C 语言的数组索引总是从 0 开始的，所以节点的第一层是 level[0]，而第二层是 level[1]，以此类推。

<font size=5 color=green> 跨度 </font>
层的跨度（level[i].span 属性）用于记录两个节点之间的间隔：

两个节点之间的跨度越大，它们相距得就越远。
指向 NULL 的所有后退指针的跨度都为 0，因为它们没有连向任何节点。
初看上去，很容易认为跨度和遍历操作无关，但实际上并不是这样 —— 遍历操作只应用后退指针就能够实现了，跨度实际上是用来计算排位（rank）的：在查找某个节点的过程中，将沿途拜访过的所有层的跨度累计起来，失去的后果就是指标节点在跳跃表中的排位。

举个例子，下图用虚线标记了在跳跃表中查找分值为 3.0、成员对象为 o3 的节点时，沿途经验的层：查找的过程只通过了一个层，并且层的跨度为 3，所以指标节点在跳跃表中的排位为 3。

<font size=5 color=green> 后退指针 </font>
节点的后退指针（backward 属性）用于从表尾向表头方向拜访节点：跟能够一次跳过多个节点的后退指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

下图用虚线展现了如果从表尾向表头遍历跳跃表中的所有节点：程序首先通过跳跃表的 tail 指针拜访表尾节点，而后通过后退指针拜访倒数第二个节点，之后再沿着后退指针拜访倒数第三个节点，再之后遇到指向 NULL 的后退指针，于是拜访完结。

<font size=5 color=green> 分值和成员 </font>

节点的分值（score 属性）是一个 double 类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。

节点的成员对象（obj 属性）是一个指针，它指向一个字符串对象，而字符串对象则保留着一个 SDS 值。

在同一个跳跃表中，各个节点保留的成员对象必须是惟一的，然而多个节点保留的分值却能够是雷同的：分值雷同的节点将依照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在后面（凑近表头的方向），而成员对象较大的节点则会排在前面（凑近表尾的方向）。

举个例子，在下图所示的跳跃表中，三个跳跃表节点都保留了雷同的分值 10086.0，但保留成员对象 o1 的节点却排在保留成员对象 o2 和 o3 的节点之前，而保留成员对象 o2 的节点又排在保留成员对象 o3 的节点之前，由此可见，o1、o2、o3 三个成员对象在字典中的排序为 o1 <= o2 <= o3。

2. 跳跃表
   尽管仅靠多个跳跃表节点就能够组成一个跳跃表，如下图所示。
   
   但通过应用一个 zskiplist 构造来持有这些节点，程序能够更不便地对整个跳跃表进行解决，比方快速访问跳跃表的表头节点和表尾节点，又或者疾速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息，如下图所示。
   
   zskiplist 构造的定义如下：

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

header 和 tail 指针别离指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为 O(1)。

通过应用 length 属性来记录节点的数量，程序能够在 O(1) 复杂度内返回跳跃表的长度。

level 属性则用于在 O(1) 复杂度内获取跳跃表中层高最大的那个节点的层数量，留神表头节点的层高并不计算在内。

对于跳跃表的总结：

• 跳跃表是有序汇合的底层实现之一，除此之外它在 Redis 中没有其余利用。
• Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个构造组成，其中 zskiplist 用于保留跳跃表信息（比方表头节点、表尾节点、长度），而 zskiplistNode 则用于示意跳跃表节点。
• 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
• 在同一个跳跃表中，多个节点能够蕴含雷同的分值，但每个节点的成员对象必须是惟一的。
• 跳跃表中的节点依照分值大小进行排序，当分值雷同时，节点依照成员对象的大小进行排序。

五、整数汇合

整数汇合（intset）是汇合键的底层实现之一：当一个汇合只蕴含整数值元素，并且这个汇合的元素数量不多时，Redis 就会应用整数汇合作为汇合键的底层实现。

举个例子，如果咱们创立一个只蕴含五个元素的汇合键，并且汇合中的所有元素都是整数值，那么这个汇合键的底层实现就会是整数汇合：

redis> SADD numbers 1 3 5 7 9
(integer) 5

redis> OBJECT ENCODING numbers
"intset"

整数汇合（intset）是 Redis 用于保留整数值的汇合形象数据结构，它能够保留类型为 int16_t、int32_t 或者 int64_t 的整数值，并且保障汇合中不会呈现反复元素。

每个 intset.h/intset 构造示意一个整数汇合：

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 汇合蕴含的元素数量
    uint32_t length;

    // 保留元素的数组
    int8_t contents[];} intset;

contents 数组是整数汇合的底层实现：整数汇合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不蕴含任何反复项。

length 属性记录了整数汇合蕴含的元素数量，也即是 contents 数组的长度。

尽管 intset 构造将 contents 属性申明为 int8_t 类型的数组，但实际上 contents 数组并不保留任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值：如果 encoding 属性的值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组里的每个项都是一个 int16_t 类型的整数值（最小值为 -32,768，最大值为 32,767）。
下图是一个蕴含五个 int16_t 类型整数值的整数汇合。

每当咱们要将一个新元素增加到整数汇合外面，并且新元素的类型比整数汇合现有所有元素的类型都要长时，整数汇合须要先进行降级（upgrade），而后能力将新元素增加到整数汇合外面。

降级整数汇合并增加新元素共分为三步进行：

• 依据新元素的类型，扩大整数汇合底层数组的空间大小，并为新元素调配空间。
• 将底层数组现有的所有元素都转换成与新元素雷同的类型，并将类型转换后的元素搁置到正确的位上，而且在搁置元素的过程中，须要持续维持底层数组的有序性质不变。
• 将新元素增加到底层数组外面。

整数汇合不反对降级操作，一旦对数组进行了降级，编码就会始终放弃降级后的状态。

对于整数汇合的总结：

• 整数汇合是汇合键的底层实现之一。
• 整数汇合的底层实现为数组，这个数组以有序、无反复的形式保留汇合元素，在有须要时，程序会依据新增加元素的类型，扭转这个数组的类型。
• 降级操作为整数汇合带来了操作上的灵活性，并且尽可能地节约了内存。
• 整数汇合只反对降级操作，不反对降级操作。

六、压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

当一个列表键只蕴含大量列表项，并且每个列表项要么就是小整数值，要么就是长度比拟短的字符串，那么 Redis 就会应用压缩列表来做列表键的底层实现。

比如说，执行以下命令将创立一个压缩列表实现的列表键：

redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6

redis> OBJECT ENCODING lst
"ziplist"

因为列表键外面蕴含的都是 1、3、5、10086 这样的小整数值，以及 “hello”、“world” 这样的短字符串。

另外，当一个哈希键只蕴含大量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比拟短的字符串，那么 Redis 就会应用压缩列表来做哈希键的底层实现。

举个例子，执行以下命令将创立一个压缩列表实现的哈希键：

redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK

redis> OBJECT ENCODING profile
"ziplist"

因为哈希键外面蕴含的所有键和值都是小整数值或者短字符串。
<font size=3 color=green> 压缩列表的形成:</font>
压缩列表是 Redis 为了节约内存而开发的，由一系列非凡编码的间断内存块组成的程序型（sequential）数据结构。

一个压缩列表能够蕴含任意多个节点（entry），每个节点能够保留一个字节数组或者一个整数值。

下图展现了压缩列表的各个组成部分。

下表则记录了各个组成部分的类型、长度、以及用处。表 7-1 则记录了各个组成部分的类型、长度、以及用处。

<font size=3 color=green> 压缩列表节点的形成:</font>
每个压缩列表节点都由 previous_entry_length、encoding、content 三个局部组成，如下图所示。

• 节点的 previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度。
• 节点的 encoding 属性记录了节点的 content 属性所保留数据的类型以及长度：
• 节点的 content 属性负责保留节点的值，节点值能够是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。
  对于压缩列表的总结：
• 压缩列表是一种为节约内存而开发的程序型数据结构。
• 压缩列表被用作列表键和哈希键的底层实现之一。
• 压缩列表能够蕴含多个节点，每个节点能够保留一个字节数组或者整数值。
• 增加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作呈现的几率并不高。

• 最初

如果感觉还不错请点赞关注转发，不胜感激。

更多精彩内容 微信搜素：蘑菇睡不着