源自小林coding，《Redis设计与实现》，部分图片出自个人进一步整理学习

Redis数据结构

Redis底层数据结构设计与要点一览

回顾时直接看 Redis底层数据结构设计与要点一览，详细内容继续阅读后续。

Redis数据结构

【正文开始】我是分割线

Redis的键值对中的 key是字符串对象，value可以是字符串对象，也可以是集合数据类型的对象，比如List对象、Hash对象、Set对象、Zset对象。

Redis使用了一个 哈希表保存所有键值对，哈希表的最大好处是让我们可以用O(1)的时间复杂度来快速查找到键值对。哈希表其实就是一个数组，数组中的元素叫做 哈希桶。

哈希桶存放的是指向键值对数据的指针（dictEntry*），通过指针找到键值对数据，然后因为键值对的值可以保存字符串对象和集合数据类型，所以键值对的数据结构中并不是保存值本身，而是保存了void* key 和 void* value指针，分别指向了实际的键对象和值对象，这样即使值是集合数据，也可以通过void* value指针找到。

dict结构，结构体例存放了2个哈希表，正常情况下都是用 哈希表1，哈希表2只有在rehash的时候才用；
dictht结构，表示哈希表的结构，结构里存放了哈希表数组，数组中的每个元素都是指向一个哈希表节点结构(dictEntry)的指针；

注意： void* key和void* value指针指向的是**Redis对象**，Redis中的每个对象都由redisObject结构表示：

type，标识该对象是什么类型（String、List、Hash、Set、Zset）的对象

encoding，标识该对象使用了哪种底层的数据结构

ptr，指向底层数据结构的指针

Redis键值对数据库的全景图（Redis对象和数据结构的关系(Redis 3.0)）

SDS，Simple Dynamic String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


struct __attribute__ ((__packed__)) sdshdr {
    uint16_t len;
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};

SDS设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。

在变成上，Redis 使用专门的编译优化来节省内存空间，即在 struct声明了__attribute__((packed))，作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。

链表

【链表节点】结构

1
2
3
4
5
6
7
8


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

链表结构设计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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链表实现的优点：

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

Redis链表的缺陷：

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

故 Redis3.0的List对象在数据量比较少的情况下，会采用【压缩列表】作为底层数据结构的实现，优势是节省内存空间，并且是内存紧凑型的数据结构。

但压缩列表存在性能问题，所以Redis在3.2版本设计了新的数据结构quicklist，并将List对象的底层数据结构改由quicklist实现。然后在Redis 5.0 设计了新的数据结构lsitpack，沿用了压缩列表紧凑型的内存布局，最终在最新的Redis版本，将Hash对象和Zset对象的底层数据结构实现之一的压缩列表，替换成由listpack实现。

压缩列表

压缩列表的最大特点：被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用CPU缓存，而且会针对不同长度的数据，进行相应编码，这种方式可以有效节省内存开销。

压缩列表结构的设计

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

zlbytes，记录整个压缩列表占用对内存字节数；
zltail，记录压缩列表【尾部】节点距离起始地址有多少字节，也就是列表尾的偏移量；
zllen，记录压缩列表包含的节点数量；
zlend，标记压缩列表的结束点，固定值 0xFF(十进制255)。

压缩列表中，查找第一个元素和最后一个元素的时间复杂度是O(1)，但是查找其他元素的复杂度是O(N)，因此压缩列表不适合保存过多的元素。

压缩列表节点(entry)的构成

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

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

prevlen属性的空间大小跟前一个节点长度值有关：

若前一个节点的长度小于254字节（254 = 256($2^8$) - 2）,那么prevlen属性需要用 1字节的空间来保存这个长度值；

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

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

若当前节点的数据是整数，则encoding会使用 1字节的空间进行编码；

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

连锁更新

除了查找复杂度高的问题，还存在连锁更新的问题。

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

前面提到，压缩列表节点的 prevlen 属性会根据前⼀个节点的⻓度进⾏不同的空间⼤⼩分配：

如果前⼀个节点的⻓度⼩于 254 字节，那么 prevlen 属性需要⽤ 1 字节的空间来保存这个⻓度值；
如果前⼀个节点的⻓度⼤于等于 254 字节，那么 prevlen 属性需要⽤ 5 字节的空间来保存这个⻓度值；

举例：

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

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

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

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

多米诺骨牌效应开始了……

这种在特殊情况下产生的连续多次空间扩展操作叫做【连锁更新】。就像多米诺骨牌效应。

压缩列表的缺陷

连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这会直接影响到压缩列表的访问性能。因此，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加了，或者元素变大了，会导致内存重新分配，最糟糕的是会有【连锁更新】问题。

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

quicklist（Redis 3.2引入）和listpack（Redis 5.0引入）。这两种数据结构的目标就是 尽可能地保持压缩列表节省内存地优势，同时解决压缩列表的【连锁更新】问题。

哈希表

Redis 3.0中Hash对象的底层实现之一是压缩列表（Redis 最新版代码已经将压缩列表替换成listpack），Hash对象的另一个底层实现是哈希表。

哈希表的优点：能以O(1)复杂度快速查询数据。

风险：在哈希表大小固定的情况下，随着数据不断增多，发生哈希冲突的可能性也会越高。**Redis采用了【链式哈希】来解决哈希冲突，**在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接以便这些数据在表中仍然可以被查询到。

哈希表的结构设计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    unsigned long sizemask;
    // 该哈希表已有的节点数量
    unsigned long used;
} dictht;

哈希表节点的结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


typedef struct dictEntry {
    // 键值对中的键
    void *key;
    // 键值对中的值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个哈希表节点，形成链表(解决哈希冲突)
    struct dicEntry *next;	
} dictEntry;

union结构，当键值对中的【值】是整数或浮点数时，可以将值的数据内嵌到dictEntry结构里，无需再用一个指针指向实际的值，从而 节省了内存空间。

哈希冲突

哈希表实际上是一个数组，数组里每一个元素就是一个哈希桶。

（哈希值 % 哈希表大小）的结果值就是该key-value对应的数组元素位置，也就是第几个哈希桶。

哈希冲突：当有两个以上数量的key被分配到哈希表中同一个哈希桶上时，此时称这些key发生了冲突。

如下图中的key1和key9对应到相同的哈希桶中，就发生了哈希冲突。

链式哈希的实现：被分配到同一个哈希桶上的多个节点用单项链表链接起来。

局限性：随着链表长度的增加，在查询这一位置上的数据的耗时线性增加，查询复杂度是O(n)。

解决这一问题的方法是 进行rehash，也就是对哈希表大小进行扩展。

rehash

在实际使用哈希表时，Redis定义了一个dict结构体，这个结构体定义了两个哈希表(ht[2])。

1
2
3
4
5
6


typedef struct dict {
    ...
    // 两个Hash表，交替使用，用于rehash操作
    dictht ht[2];
    ...
} dict;

rehash的三个过程：

分配空间。给【哈希表2】分配空间，一般时【哈希表1】的2倍；
数据迁移。将【哈希表1】的数据迁移到【哈希表2】中；
释放空间，重置表名。迁移完成后，【哈希表1】的空间会被释放，并把【哈希表2】设置为【哈希表1】，然后在【哈希表2】新创建一个空白哈希表，为下次rehash做准备。

第二步的问题：如果【哈希表1】的数据量非常大，那么迁移至【哈希表2】的时候，因为会涉及大量的数据拷贝，此时可能会对Redis造成阻塞，无法服务其他请求。

渐进式rehash

为了避免rehash在数据迁移过程中，因拷贝数据的耗时影响Redis性能的情况，所以Redis采用了渐进式rehash，即数据迁移的工作分多次迁移，而不是一次性迁移完成。

渐进式rehash步骤如下：

给【哈希表2】分配空间；
在rehash进行期间，每次哈希表元素进行新增、删除、查找或更新操作时，Redis除了会执行对应的操作之外，还会顺序将【哈希表1】中索引位置上的所有key-value迁移到【哈希表2】上；
随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把【哈希表1】所哟的key-value迁移到【哈希表2】，从而完成rehash操作。

在进行渐进式rehash过程中，会有两个哈希表，所以在渐进式rehash进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。

rehash触发条件

负载因子：负载因子 = 哈希表已保存节点数量 / 哈希表大小

触发rehash操作的条件：

当负载因子>=1，并且Redis没有在执行bgsave命令或bgrewriteaof命令，即没有执行RDB快照或没有进行AOF重写时就会进行rehash；
当负载因子>=5，说明哈希冲突非常严重了，不管有没有在执行RDB快照或AOF重写，都会强制进行rehash操作。

整数集合

本质是一块连续内存空间，结构定义如下：

1
2
3
4
5
6
7
8


typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

虽然contents被声明为int8_t类型的数组，但实际上 contents数组并不保存任何int8_t类型的元素，contents数组的真正类型取决于intset结构体里的encoding属性的值。

若 encoding属性值为 INTSET_ENC_INT16（INTSET_ENC_INT32 或 INTSET_ENC_INT64），那么contents就是int16_t（int32_t 或 int64_t）类型的数组，数组中每个元素类型都是int16_t（int32_t 或 int64_t）

不同类型的content数组，其大小也不同。

整数集合的升级操作

如果新元素的类型（int32_t）⽐整数集合现有所有元素的类型（int16_t）都要⻓时，整数集合需要先进⾏升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间⼤⼩，然后才能将新元素加⼊到整数集合⾥，当然升级的过程中，也要维持整数集合的有序性。

整数集合的升级过程在原本的数组上扩展空间，而不会重新分配一个新类型的数组。

升级操作的几个要点：

在原本数组上扩展空间；
原有元素类型转换为升级后的元素类型；
重新放置原来的元素位置，并保持有序性。

举例，假设有一个整数集合里有3个类型为int16_t的元素：

现在往整数集合中加入一个新元素65535，这个新元素需要用int32_t类型来保存，所以整数集合需要进行升级操作，首先需要为contents数组扩容，在原本空间大小之上再扩容80位（4 x 32 - 3 x 16 = 80），这样就能保存下4个类型位int32_t的元素。

整个转换过程如下：

整数集合升级的好处：节省内存资源。

不支持降级操作

跳表

练习内容：CPP-Practice/MyskipList

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

Zset对象是唯一一个同时使用两个数据结构（跳表和哈希表）来实现的Redis对象。好处：既能进行高效的范围查询(如ZRANGEBYSCORE操作，采用了跳表)，也能进行高效（常数复杂度）单点查询（如ZSCORE操作，采用了哈希表进行索引）。

1
2
3
4


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

**跳表是在链表基础改进过来的，实现了一种【多层】的有序链表。**好处：能快速定位数据。

示例：一个层级为3的跳表；

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

L0层级共有5个节点（节点1、2、3、4、5）

L1层级共有3个节点（节点2、3、4）

L2层级共有1个节点（节点3）

通常情况下，跳表的查找过程是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度是O(log N)。

跳表节点结构体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


typedef struct zskiplistNode {
    // Zset对象的元素值
    sds ele;
    // 元素权重值
    double score;
    // 后向指针
    struct zskiplistNode *backward;
    // 节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistlevel {
        struct zskiplistNode *forward;	//指向下一个跳表节点的指针
        unsigned long span;				// 跨度，记录两个节点之间的距离
    } level[];
} zskiplistNode;

每个跳表节点有一个后向指针，指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点时，这样倒序查找方便。

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

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

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

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

跳表结构体

1
2
3
4
5


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

跳表结构包含：

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

跳表节点查询过程

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

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

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

举例：

如果要查找「元素：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」的节点，该节点正是要查找的节点，查询结束。

跳表节点层数设置

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

举例：L2层有1个节点，L1层有6个节点。

如果想要查询节点 6，那基本就跟链表的查询复杂度⼀样，就需要在第⼀层的节点中依次顺序查找，复杂度就是 O(N)。

所以，为了降低查询复杂度，我们就需要维持相邻层结点数间的关系。

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

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

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

相当于每增加⼀层的概率不超过25%，层数越⾼，概率越低，层⾼最⼤限制是 64。

quicklist（Redis 3.2）

Redis 3.2 List对象的底层改由quicklist实现。

quicklist就是【双向链表+压缩列表】，一个quicklist就是一个链表，链表中每个元素又是一个压缩列表。

quicklist解决压缩列表的连锁更新问题的方法：通过控制每个链表节点中的压缩列表的⼤⼩或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越⼩，连锁更新带来的影响就越⼩，从⽽提供了更好的访问性能。

quicklist结构设计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


typedef struct quicklist {
    // 链表头
    quicklistNode *head;
    // 链表尾
    quicklistNode *tail;
    // 所有压缩列表中的总元素个数
    unsigned long count;
    // quicklistNodes 的个数
    unsigned long len;
    ...
} quicklist;

quicklistNode结构：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


typedef struct quicklistNode {
    // 前一个quicklistNode
    struct quicklistNode *prev;
    // 下一个quicklistNode
    struct quicklistNode *next;
    // quicklistNode指向的压缩列表
    unsigned char *zl;	//	指向压缩列表的指针*zl
    // 压缩列表的字节大小
    unsigned int sz;
    // 压缩列表的元素个数
    unsigned int count : 16;
} quicklistNode;

quicklist数据结构：

listpack

quicklist 会控制 quicklistNode 结构⾥的压缩列表的⼤⼩或者元素个数，来规避潜在的连锁更新的⻛险，但是这并没有完全解决连锁更新的问题。因为 quicklistNode 还是⽤了压缩列表来保存元素，压缩列表连锁更新的问题，来源于它的结构设计，所以要想彻底解决这个问题，需要设计⼀个新的数据结构。

Redis 在 5.0 新设计⼀个数据结构叫listpack，⽬的是替代压缩列表，它最⼤特点是 listpack 中每个节点不再包含前⼀个节点的⻓度了，压缩列表每个节点正因为需要保存前⼀个节点的⻓度字段，就会有连锁更新的隐患。

Redis 6.2发行版本中，Redis Hash 对象、Set 对象的底层数据结构的压缩列表还未被替换成listpack，⽽ Redis 的最新代码（还未发布版本）已经将所有⽤到压缩列表底层数据结构的 Redis 对象替换成 listpack 数据结构来实现，估计不久将来，Redis 就会发布⼀个将压缩列表为 listpack 的发⾏版本。

listpack结构设计

listpack entry即每个listpack节点结构如下：

encoding：定义该元素的编码类型，会对不同⻓度的整数和字符串进⾏编码
data：实际存放的数据
len：encoding+data的总⻓度

listpack 没有压缩列表中记录前⼀个节点⻓度的字段，listpack 只记录当前节点的⻓度，当我们向 listpack 加⼊⼀个新元素的时候，不会影响其他节点的⻓度字段的变化，从⽽避免了压缩列表的连锁更新问题。

参考资料

小林coding
《Redis设计与实现》

[Redis]Redis底层数据结构深入学习（详解）

文章目录

Redis数据结构

Redis底层数据结构设计与要点一览

【正文开始】我是分割线

Redis键值对数据库的全景图（Redis对象和数据结构的关系(Redis 3.0)）

SDS，Simple Dynamic String

链表

【链表节点】结构

链表结构设计

链表的优势与缺陷

压缩列表

压缩列表结构的设计

压缩列表节点(entry)的构成

连锁更新

压缩列表的缺陷

哈希表

哈希表的结构设计

哈希冲突

rehash

渐进式rehash

rehash触发条件

整数集合

整数集合的升级操作

不支持降级操作

跳表

练习内容：CPP-Practice/MyskipList

跳表节点结构体

跳表结构体

跳表节点查询过程

跳表节点层数设置

quicklist（Redis 3.2）

quicklist结构设计

listpack

listpack结构设计

参考资料