Redis 底层数据结构-阿里云开发者社区

在Redis数据结构和对象机制中提到的图中，我们知道，可以通过 redisObject 对象的 type 和 encoding 属性。可以决定Redis 主要的底层数据结构：SDS、QuickList、ZipList、HashTable、IntSet、ZskipList 。

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

先来看看传统的C 语言如何存储字符串的：比如一个 "Redis" 字符串：

为什么不用传统的 C 语言的方式，因为我们知道数组方式在获取字符串长度或者扩容上存在缺陷：比如获得一个数组长度的复杂度为O(N), 而且数组扩容也不太方便。所以自己构建了一种名为简单动态字符串（simple dynamic String）的抽象数据类型。

sdshdr : 表示SDS 类型，共有5种类型。每个类型的数字表示 unit
alloc：还未被使用的空间, 这里为0
len：表示这个 SDS 保存了5 个单位的字符串
buf：char类型的数组，用于保存字符

1.1 SDS 的定义

SDS 位于 src/sds.h 和 src/sds.c 中，它的结构总共有五种（redis 6.0.6）

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
   
   
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
   
   
    //所保存字符串的长度
    uint8_t len; /* used */
    //除了头部与末尾的\0以外，剩余的字节数
    uint8_t alloc; /* excluding the header and null terminator */
    //只有1字节，前5位未使用，后三位表示头部的类型（sdshdr5\8\16\32\64）
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    //用来保存字符串的元素
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
   
   
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
   
   
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
   
   
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

1.2 SDS 和 C 字符串的区别

SDS 能以O(1) 复杂度获取字符串长度：SDS 有 len 属性，而 C 字符串没有
SDS 能杜绝缓冲区溢出 ：
- 缓存区溢出：比如程序在执行拼接操作前，需要先通过内存重分配来扩展底层数组的空间大小——忘记则会产生缓冲区溢出
- SDS 记录自身长度，所以在进行操作时会进行相应的空间扩展再进行修改，不会出现缓冲区溢出
SDS 能减少修改字符串时带来的内存重分配次数 ：
- 空间预分配：对字符串进行空间扩展时，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。
- 惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节记录下来，等待将来使用。
SDS 能实现二进制安全：
- C 字符串中的字符必须符合编码格式，并且除了末尾外，中间不能包含空字符，否则会被误认为是空字符串结尾。这样会使得 C 字符串只能保存文本数据，而不能保存图片、视频等其他二进制数据
- SDS 的 buf 属性则可以存储多种二进制数据，而且以 len 属性表示的长度来判断字符串是否结束
SDS 兼容部分 C 字符串函数：
- 遵从每个字符串都是以空字符串结尾的惯例，可以重用 C 语言库<string.h> 中的一部分函数

二、字典（Dict）

Redis 的字典使用哈希表作为底层实现，代码位于 src/dict.h

2.1 字典的实现

2.1.1 哈希表的结构定义

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

如图是一个大小为4的空哈希表：

table 属性：是一个数组，数组的每个元素都指向 dictEntry 结构的指针，每个 dictEntry 结构都保存着一个键值对。其结构为：

typedef struct dictEntry {
     
     
    //键key
    void *key;
    //值value，可以是指针、int64、double 等类型
    union {
     
     
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //指向下一个 dictEntry 的指针，拉链法解决哈希冲突
    struct dictEntry *next;
} dictEntry;

size 属性：记录哈希表的大小
sizemask 属性：总是等于 size - 1
used 属性：记录哈希表目前已有节点（键值对）的数量

2.1.2 字典的结构定义

Redis 中的字典代码在 src/dict.h 中

typedef struct dict {
   
   
    //指向 dictType 结构的指针
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //索引，当 rehash 不在进行是，值为 01
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

一个没有进行 rehash 的字典

type 属性：指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数

typedef struct dictType {
     
     

    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);

    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);

    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);

    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);

    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);

} dictType;

privdata 属性：保存了需要传给那些类型特定函数的可选参数
ht 属性：包含两个项的数组，数组中的每个项都是一个 dictht 哈希表。一般情况，字典只使用 ht[0] 哈希表，ht[1] 哈希表在对 ht[0] 哈希表进行 rehash 时使用。
rehashidx 属性：如果没有进行 rehash，它的值为 -1。

2.2 哈希冲突

2.2.1 哈希算法

Redis 中计算哈希值和索引值的方法为：

# 利用字典设置的哈希函数,计算键key的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 属性和哈希值来计算出索引值（h[x] 指的是 ht[0] 或者 ht[1]）
index = hash & dict->ht[x].sizemask;

这里的 hashFunction(key)是使用 MurmurHash 算法来计算键的哈希值，这种算法的有点在于即使输入的键是有规律的，算法仍然能给出一个很好的随机分布性。算法的计算速度也非常快。

2.2.2 哈希冲突

前面提到过，Redis 中是通过拉链法来解决哈希冲突，每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，来解决哈希键冲突的问题。代码在 src/dict.c/dictAddRaw 中

dictEntry *dictAddRaw(dict *d, void *key)
{
   
   
    int index;
    dictEntry *entry;
    dictht *ht;
    if (dictIsRehashing(d)) _dictRehashStep(d);               // 1、执行rehash
    //如果索引等于 -1 表明字典中已经存在相同的 key
    if ((index = _dictKeyIndex(d, key)) == -1)                // 2、索引定位
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];          // 3、根据是否 rehash ，选择哈希表
    entry = zmalloc(sizeof(*entry));                          // 4、分配内存空间，执行插入
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    dictSetKey(d, entry, key);                                // 5、设置键
    return entry;
}

其中哈希算法的具体代码就在函数_dictKeyIndex()中

static int _dictKeyIndex(dict *d, const void *key)
{
   
   
    unsigned int h, idx, table;
    dictEntry *he;

    if (_dictExpandIfNeeded(d) == DICT_ERR)                            // 1、rehash 判断
        return -1;
    h = dictHashKey(d, key);                                           // 2、哈希函数计算哈希值
    for (table = 0; table <= 1; table++) {
   
   
        idx = h & d->ht[table].sizemask;                               // 3、哈希算法计算索引值
        he = d->ht[table].table[idx];
        while(he) {
   
                             
            if (key==he->key || dictCompareKeys(d, key, he->key))      // 4、查找键是否已经存在
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;                                // 5、rehash 判断 
    }
    return idx;
}

2.2.3 rehash

同 Java 中的 HashMap 底层数据结构一样，哈希表存储的键值对会增多或者减少，在 Redis 中是通过执行 rehash(重新散列) 来完成对表的扩展和收缩。也就是让哈希表中的负载因子维持在一个合理的范围中。这里的负载因子是：load_factor = ht[0].used / ht[0].size

扩展：1.服务器正在执行 BGSAVE 或者 BGREWRITEAOF 命令并且哈希表的负载因子大于等于 5 时；2.服务器目前没有执行 BGSAVE 或者 BGREWRITEAOF 命令并且哈希表的负载因子大于等于1时，为 ht[1] 分配空间，大小是大于原 ht[0] 两倍的2次幂

从ht[0] 的值移动到 ht[1] 时，需要重新计算原 ht[0] 中元素的哈希值和索引；插入到ht[1] 中，插一个删除一个

ht[0] 中的元素全部迁移完后，释放 ht[0]，将新建的 ht[1] 设置为 ht[0] ，调用的是 dict.c/_dictExpandIfNeeded 函数：

static int _dictExpandIfNeeded(dict *d)
{
       
       
    if (dictIsRehashing(d)) return DICT_OK;
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);          // 大小为0需要设置初始哈希表大小为4
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))                 // 负载因子超过5，执行 dictExpand
    {
       
       
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

收缩：当哈希表的负载因子小于 0.1 时，会对哈希表执行收缩操作，同样会分配 ht[1]，大小等于 max(ht[0].used, DICT_HT_INTIAL_SIZE)。同样也需要迁移元素，具体操作和扩展相同

2.2.4 渐进式 rehash

扩展或者收缩哈希表是需要将 ht[0]中的键值对 rehash 到 ht[1] 中。因为当键值对数量非常多的时候，如果是一次性、集中式的完成大量的 rehash 动作，很可能会导致服务器宕机。所以需要渐进式的 rehash 来完成。渐进式 rehash 的步骤如下：

为 ht[1] 分配空间，在字典中的 rehashidx 变量设置为 0。这步代码在 dict.c/dictExpand 中实现

int dictExpand(dict *d, unsigned long size)
{
     
     
    dictht n;
    unsigned long realsize = _dictNextPower(size);                      // 找到比size大的最小的2的幂
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    if (realsize == d->ht[0].size) return DICT_ERR;

    n.size = realsize;                                                 // 给ht[1]分配 realsize 的空间
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    if (d->ht[0].table == NULL) {
     
                                           // 处于初始化阶段
        d->ht[0] = n;
        return DICT_OK;
    }
    d->ht[1] = n;
    d->rehashidx = 0;                                                  // rehashidx 设置为0，开始渐进式 rehash
    return DICT_OK;
}

在 rehash 进行中对字典的 CRUD 操作时，除了这些制定的操作外。还会顺带将 ht[0] 的所有键值对被 rehash 到 ht[1] 中。 rehash 完成后，会将 rehashidx 属性的值加1。
- rehash 时的 CRUD 操作会在两个哈希表中进行，比如分别在两个表中查找，添加元素在 ht[1] 中添加
当 ht[0] 中所有键值对都被 rehash 到 ht[1] 后，将 rehashidx 属性值设为 -1，rehash 操作完成。

三、压缩列表（ZipList）

从本文开头图中可以看出，压缩列表(ZipList)是列表键和哈希键的底层实现原理。它是为了节约内存而开发出来的。一般用在一个列表中只含有很少的元素或者里面的元素是小整数、长度较短的字符串时， Redis 就会使用 ZipList 来做列表键的底层实现。

3.1 压缩列表的构成

压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含多个节点，每个节点中可以保存相应的数据类型（字节数组或者一个整数值）。如下图

属性	类型	长度	用途
`zlbytes`	`uint32_t`	`4` 字节	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 `zlend` 的位置时使用。
`zltail`	`uint32_t`	`4` 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
`zllen`	`uint16_t`	`2` 字节	记录了压缩列表包含的节点数量：当这个属性的值小于 `UINT16_MAX` （`65535`）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 `UINT16_MAX` 时，节点的真实数量需要遍历整个压缩列表才能计算得出。
`entryX`	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
`zlend`	`uint8_t`	`1` 字节	特殊值 `0xFF` （十进制 `255` ），用于标记压缩列表的末端

如图是一个压缩列表实例：

zlbytes 属性值为 0xd2(十进制 210) ,表示压缩列表总长度为 210 字节
zltail 属性值为 0xb3(十进制 179),表示起始指针p 到末尾指针的偏移量是 179
zilen 属性值为 0x5(十进制 5),表示压缩列表包含了五个 entry 节点
entry1~entry5 :表示各个列表
zlend 属性值表示压缩列表的末端

3.2 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值。其节点都由 previous_entry_length、encoding、content 三个属性组成。如下图：

previous_entry_length 属性: 以字节为单位，记录了压缩列表中的前一个字节的长度。
- 若前一字节的长度小于 254 字节，则 previous_entry_length 的值为 1 字节
- 若前一字节的长度大于等于 254 字节，则 previous_entry_length 的值为5字节：该属性的第一个字节被设置为 254，后面的四个字节用于存储超过 1 字节的剩余长度。
encoding 属性：记录了节点的 content 属性所保存数据的类型以及长度
- 1字节、2字节或者5字节时，值的最高为00、01或者10的是字节数组编码：这种编码表示节点的 content 属性保存着字节数组。
  
  | 编码 | 编码长度 | content 属性保存的值 |
  | ---------------------------------------------- | -------- | -------------------------------------- |
  | 00bbbbbb | 1 字节 | 长度小于等于 63 字节的字节数组。 |
  | 01bbbbbb xxxxxxxx | 2 字节 | 长度小于等于 16383 字节的字节数组。 |
  | 10______ aaaaaaaa bbbbbbbb cccccccc dddddddd | 5 字节 | 长度小于等于 4294967295 的字节数组。 |
- 1字节，值的最高位以11开头的整数编码：整数值的类型和长度由编码除去最高两位之后的其他位记录。
  
  | 编码 | 编码长度 | content 属性保存的值 |
  | ---------- | -------- | :----------------------------------------------------------- |
  | 11000000 | 1 字节 | int16_t 类型的整数。 |
  | 11010000 | 1 字节 | int32_t 类型的整数。 |
  | 11100000 | 1 字节 | int64_t 类型的整数。 |
  | 11110000 | 1 字节 | 24 位有符号整数。 |
  | 11111110 | 1 字节 | 8 位有符号整数。 |
  | 1111xxxx | 1 字节 | 使用这一编码的节点没有相应的 content 属性，因为编码本身的 xxxx 四个位已经保存了一个介于 0 和 12 之间的值，所以它无须 content 属性。 |
content 属性：负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性来决定。

举个保存整数节点的例子：
- encoding 是 11 开头表示存储的是整数类型
- content 表示保存节点值是 10086

为何 ZipList 省能内存？

相对于普通的 list 而言，增加 encoding 属性来选择性让字节和整数类型进行存储
有了 previous_entry_length 属性，遍历元素时可以定位到下一个元素的精确位置，降低搜索的时间复杂度

四、跳表（ZSkipList）

跳表是一种有序数据结构，它就是作为有序列表（Zset）的使用。而且相较于平衡树比较更优雅，在 CRUD 等操作上可以在对数期望时间内完成。

如上图所示，是一个跳跃表实例，最左侧的是 zskiplist 结构，该结构包含的属性有：

header属性：指向跳跃表的表头节点
tail属性：指向跳跃表的表尾节点
level属性：记录跳跃表中层数最大节点的层数
length属性：记录跳跃表的长度，也就是跳跃表目前包含节点的数量

而右侧的四个是 zskiplistNode 结构，该结构包含的属性有：

level属性：节点中用L1、L2、L3等等字样标记节点的各层
backward属性：节点中用 BW字样标记节点的后退指针，它是指向当前结点的前一个节点
score属性：节点中保存的诸如1.0、2.0等等分值
obj属性：节点中的 o1、o2等等是节点所保存的成员对象

4.1 跳跃表结构定义

4.1.1 跳跃表的结构

如开始介绍的图，zskiplist 结构代码在 redis.h/zskiplist 中，其定义如下：

typedef struct zskiplist {
   
   
    //表头节点和表尾节点
    structz skiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大节点的层数
    int level;
} zskiplist;

4.1.2 跳跃表节点的结构

其中 zskiplistNode 结构用于表示跳跃表节点，代码在 redis.h/zskiplistNode 中。

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
   
   
    //对象属性,指向了一个字符串对象
    sds ele;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    //层level
    struct zskiplistLevel {
   
   
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
} zskiplistNode;

level 属性：level 层中可以包含多个元素，层的数量越多，访问其他节点的速度就越快。程序通过幂次定律（power law, 越大的数出现的概率越小）随机生成一个介于1和32之间的值作为 level 数组的大小作为层高:下图是不同层高的节点
前进和后退指针（*forward和* backforward）：用于访问遍历跳跃表中所有节点的路径
span跨度属性：层的跨度是用于记录两个节点之间的距离：如上图箭头上的数字表示节点间的距离
分值和成员（score 、sds ele）：
- 分值是一个 double 类型的浮点数，跳跃表中的所有节点都按分值从小到大排序
- 成员对象（如o1、o2等等），它是一个指针，指向一个字符串对象，这个对象保存着一个SDS 值
  - 在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，分值可以相同。成员对象小的会排在前面（表头）、成员对象较大的节点会排在后面（表尾）。还是这张图，图中 o1、o2和o3三个节点都保存了相同的整数值 10086.0。但是成员对象的排序却是 o1->o2->o3

五、整数集合（IntSet）

当一个集合中只有整数值元素，并且集合中的元素数量不多时，Redis则会使用整数集合作为集合键的底层实现

5.1 整数集合结构定义

intset 可以保存类型为int16_t、int32_t或者int64_t的整数值，而且保证集合中不会出现重复元素。其结构代码在 intset.h/intset 中,下面以32为编码方式为例：

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

以一个具体的整数集合为例：

encoding属性值为 INTSET_ENC_INT16 :表示 contents 数组是一个 16 位的数组
length属性值为5，表示contents 数组中包含五个元素
contents 数组，表示该数组中从小到大存储着五个元素

5.2 整数集合的升级

新元素的类型比现有的类型要长，比如说16位变成32位，在整数集合里叫做升级（upgrade）。经过升级后，才能将新元素添加到整数集合中，升级整数集合并且添加新元素的步骤为：

根据新元素的类型，扩展底层数组的空间大小，为新元素分配空间
将底层数组现有的所有元素都转换成新元素相同的类型，将类型转换后的元素放置在正确的位置上。
将新元素添加到contents数组里面

集合也不会做降级操作，比如在原16位数组中新加了一个32位元素，然后把这个新加的元素删除后，整数集合也不会做降级操作。

六、快速链表（QuickList）

quicklist 结构时一种以 ziplist 为节点的双端链表结构，整体上是一个链表，但是链表中的每一个节点都是一个 ziplist.

6.1 快速链表的结构

其代码结构为，在src/quicklist.h 中

我们先来看看quicklistNode 节点的结构：

typedef struct quicklistNode {
   
   
    //上一个quicklistNode节点
    struct quicklistNode *prev;
    //下一个quicklistNode节点
    struct quicklistNode *next;
    //数据指针，
    unsigned char *zl;
    //表示zl指向 ziplist 的总大小
    unsigned int sz;             /* ziplist size in bytes */
    //表示ziplist里面包含的数据项个数
    unsigned int count : 16;     /* count of items in ziplist */
    //ziplist是否被压缩,1是没有，2是被压缩
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    //预留字段，目前是固定值，表示使用 ziplist 作为数据容器
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    //需要把数据暂时解压，此时设置 recompress = 1,有机会再将数据重新压缩
    unsigned int recompress : 1; /* was this node previous compressed? */
    //Redis 自动化测试时用
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    //扩展字段，目前没有被使用
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

再来看看 quicklistLZF 结构，表示一个被压缩过的 ziplist，它的结构是：

typedef struct quicklistLZF {
   
   
    //压缩后 ziplist 的大小
    unsigned int sz; /* LZF size in bytes*/
    //柔性数组，存放压缩后的 ziplist 字节数组
    char compressed[];
} quicklistLZF;

再看看最后的 quicklist 结构

typedef struct quicklist {
   
   
    //指向头节点（quicklistnode 头节点）
    quicklistNode *head;
    //指向尾节点（最右侧节点）
    quicklistNode *tail;
    //所有ziplist 的数量
    unsigned long count;        /* total count of all entries in all ziplists */
    //quicklist节点的个数
    unsigned long len;          /* number of quicklistNodes */
    //设置ziplist 的大小，存放 list-max-ziplist-size 参数的值
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    //节点压缩深度设置，存放 list-comress-depth 参数的值，为0的时候关闭
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    //尾部增加的书签，只有在大量节点的多余内存使用量可以忽略不计的情况，才分批迭代他们，不使用时不会增加内存开销
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

6.2 快速链表的内部操作

6.2.1 插入操作

可以选择在头部或者尾部插入：

ziplist大小没有超过限制，新数据直接插入到 ziplist 中
ziplist超过限制，那么新创建一个 quicklistNode 节点，然后将新节点插入到 quicklist 双向链表中

从中间位置插入：

需要把当前 ziplist 分裂成两个节点，然后在其中一个节点上插入数据

6.2.2 查找操作

根据node 的个数找到对应的 ziplist,然后再调用 ziplist 的 index 就能成功找到

6.2.3 删除操作

利用 quicklistDelRange 函数：返回1时表示成功删除指定区间元素，返回0表示没有删除任何元素

在区间删除时，会先找到 start 所在的 quicklistNode ，计算删除的元素是否小于删除的 count，如果不满足删除的个数，则会移动至下一个 quicklistNode 继续删除，依次循环直到删除完成为止。

参考资料：

《Redis 设计与实现》

《Redis 开发与运维》

Redis数据结构——快速列表(quicklist)

https://pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html

Redis 底层数据结构

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

1.1 SDS 的定义

1.2 SDS 和 C 字符串的区别

二、字典（Dict）

2.1 字典的实现

2.1.1 哈希表的结构定义

2.1.2 字典的结构定义

2.2 哈希冲突

2.2.1 哈希算法

2.2.2 哈希冲突

2.2.3 rehash

2.2.4 渐进式 rehash

三、压缩列表（ZipList）

3.1 压缩列表的构成

3.2 压缩列表节点的构成

为何 ZipList 省能内存？

四、跳表（ZSkipList）

4.1 跳跃表结构定义

4.1.1 跳跃表的结构

4.1.2 跳跃表节点的结构

五、整数集合（IntSet）

5.1 整数集合结构定义

5.2 整数集合的升级

六、快速链表（QuickList）

6.1 快速链表的结构

6.2 快速链表的内部操作

6.2.1 插入操作

6.2.2 查找操作

6.2.3 删除操作

参考资料：

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

Redis 底层数据结构

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

1.1 SDS 的定义

1.2 SDS 和 C 字符串的区别

二、字典（Dict）

2.1 字典的实现

2.1.1 哈希表的结构定义

2.1.2 字典的结构定义

2.2 哈希冲突

2.2.1 哈希算法

2.2.2 哈希冲突

2.2.3 rehash

2.2.4 渐进式 rehash

三、压缩列表（ZipList）

3.1 压缩列表的构成

3.2 压缩列表节点的构成

为何 ZipList 省能内存？

四、跳表（ZSkipList）

4.1 跳跃表结构定义

4.1.1 跳跃表的结构

4.1.2 跳跃表节点的结构

五、整数集合（IntSet）

5.1 整数集合结构定义

5.2 整数集合的升级

六、快速链表（QuickList）

6.1 快速链表的结构

6.2 快速链表的内部操作

6.2.1 插入操作

6.2.2 查找操作

6.2.3 删除操作

参考资料：

热门文章

最新文章

相关课程

相关电子书

相关实验场景