redis数据结构

一，概述

    本文主要简单介绍下redis的主要数据结构，分别是动态字符串、链表、字典、跳跃表、整数集合、压缩列表。

二，简单动态字符串

    redis自己构建了一个名为简单动态字符串（simple dynamic string，SDS）的抽象类型。SDS作为redis的默认字符串，在redis的数据库里，包含字符串值的键值对在底层都是由SDS实现的。

free：bug数组中未使用字节数量。

len：SDS所保存字符串长度。

buf：char类型数组，以空字符 '\0' 结尾。

空字符的1字节，不计算入len长度，由于redis本身是有C语言编写，加空字符结尾是为了使用C语言字符串的特性，同时又比C语言字符串多了len和free属性，比如获取字符串长度，C语言需要去遍历字符串直到空字符结尾，而SDS直接获取len属性即可，复杂度仅为O(1)。

SDS相比C字符串另一个好处是，它的空间分配策略杜绝了缓冲区溢出，SDS的空间分配策略，解除了字符串长度和底层数组间的关联，也就是在SDS中，buf的长度并不一定是字符串长度。

空间预分配：用于优化SDS的字符串增长操作。

当字符串变长后，如果变更后的长度小于buf长度，那么不会重新分配内存空间，若变更后的长度大于buf长度，那么就需要内存重新分配空间，这时，若len属性的值小于1MB，那么程序分配和len属性值同样大小的未使用空间，这时len属性值和free属性值相同，即变更后的buf长度，等于len +free + 1的值；若变更后len属性值大于等于1MB，那么程序会分配1MB的未使用空间。    

惰性释放空间：用于优化SDS字符串缩短操作。

当SDS缩短字符串长度时，内存并不会马上释放多余空间，而是会以free记录的形式将数量记录起来，可以等待后续扩展字符串使用。

三，链表

redis使用链表作为列表键的底层实现，除了列表键之外，发布与订阅、慢查询、监视器等功能也用到了链表。

由多个listNode组成的双端链表

代码：

typedef struct listNode{

    struct listNode *prev；//前置节点

    struct listNode *next；//后置节点

    void *value；//节点的值

}listNode

redis使用list来持有listNode链表：

代码：

typedef struct list{

    listNode *head；//表头节点

    listNode *tail；//表尾节点

    unsinged long len；//链表所包含的节点数量

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

    void (*free) (void *ptr)；//节点值释放函数

    int (*macth) (void *ptr,void *key)；//节点值对比函数

}list

链表特性：

1，双端：链表节点带有 prev和next指针，获取某个节点的前置节点和后置节点的复杂度为o(1)。

2，无环：表头节点指针和表尾节点指针都指向null，对链表的访问以null为终点。

3，带表头指针和表尾指针：通过list结构的head和tail，程序获得表头节点指针和表尾节点指针复杂度为o(1)。

4，带链表长度计数器：len属性对list持有的链表节点进行计数，程序获取链表节点数量复杂度为o(1)。

5，多态：链表节点使用void* 指针来保存节点值，并可通过list结构的dup，free，match三个属性节点设置特定函数。

四 字典

redis的数据库使用字典来作为底层实现，对数据库的增、删、改、查操作也是构建在对字典的操作上。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，redis的字典使用哈希表作为底层实现。

哈希表：

typedef struct dictht{

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

    unsigned long size；//哈希表大小

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

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

}dictht

哈希表节点：

typedef struct dictEntry {

    void *key;//键

    union{ //值

        void *val;

        uint64_tu64;

        int64_ts64;

    } v;

    struct   dictEntry *next；//指向下一个哈希表节点，形成链表

}dictEntry 

字典：

typedef struct dict{

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

    void *privdata；//私有数据

    dictht ht[2]；//哈希表

    int  trehashidx；//rehash索引，当rehash不在进行时，值为-1

}dict

type：是一个指向dictType结构的指针。

privdata：保存需要传给特定函数的可选参数。

ht：两个数组，一般情况下只使用ht[0]哈希表，ht[10]哈希表用作扩展备份。

哈希算法：

根据字典dict的type，计算键key的哈希值，再使用哈希表的sizemask和刚计算的哈希值，计算出索引值，使用murmurhash2算法。

rehash：

负载因子 = ht[0].used / ht[0].size ；

服务器目前没有执行bgsave或者bgrewriteaof命令，负载因子大于等于1 ，即进行rehash扩展操作。

服务器目前正在执行bgsave或者bgrewriteaof命令，负载因子大于等于5，即进行rehash扩展操作。

另，负载因子小于0.1时，进行收缩操作。

rehash不是一次性全部扩展完成，而是渐进式的，

dict里的trehashidx值，就是渐进式rehash的进度计数器，trehashidx为0时，rehash开始，在rehash期间，每次对字典执行添加、删除、查找、更新操作时，程序除了指定操作外，还会顺带将ht[0]哈希表在trehashidx索引上的所有键值对rehash到ht[1]，rehash完成后，trehashidx加1，当所有ht[0]都rehash到ht[1]后，trehashidx置为-1。

五 跳跃表

跳跃表不做多介绍，redis只有少数几个地方用到了，一个是实现有序集合键，一个是集群节点中用作内部数据结构。

header：指向跳跃表的表头节点。

tail： 指向跳跃表的表尾节点。

level：记录跳跃表内，层数最大的那个节点的层数（表头节点层数不计算内）。

length： 跳跃表长度，即跳跃表节点数（表头节点不计算内）。

六 整数集合

整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，redis就会使用整数集合作为集合键的底层实现。

保存类型可以 int16_t，int32_t，int64_t 的整数值，集合中不会出现重复元素。

typedef struct inset{

    uint32_t encoding；//编码方式

    uint32_t  length；//集合包含的元素数量

    int8_t  contexts[]；//保存元素的数组

}inset

contexts[] 数组是整数集合的 底层实现，整数集合的每个元素都是contexts数组的一个数组项，各个项在数组中按值的大小从小到大排列，并且不包含重复项。

七 压缩列表

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

当列表键只包含少量列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，那么redis会把压缩列表当做列表键的底层实现。

当哈希键只包含少量键值对，并且每个键值对的键和值要么是小整数值，要么就是长度比较短的字符串，那么redis会把压缩列表当做哈希键的底层实现。

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

zlbytes：记录整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配或者计算zlend的位置时使用。

zltail：记录压缩列表 表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾节点地址。

zllen：记录压缩列表包含的节点数量，当这个属性小于uint16_max(65535)时，这个属性的值就是包含的节点数量，当大于65535时，需要真实遍历才能计算得出。

entryX：列表节点。

zlend：特殊值oxff（十进制255），标记压缩列表末端。

压缩列表节点

previous_entry_length：字节为单位，长度为1字节或5字节。当前一节点长度小于254字节，previous_entry_length为1字节；当前一节点长度大于等于254字节，previous_entry_length为5字节，属性第一个子节被设置成OxFE，之后四个字节则保存前一节点长度。

encoding：记录节点content保存的数据类型及长度

content：保存节点的值

参考文献《redis设计与实现第二版》