redis数据结构

redis数据结构列表：
简单动态字符串（sds)
链表（list）
字典（dict）
跳跃表（skiplist）
整数集合（intset）
压缩列表（ziplist）

一： 基本数据结构
1.1：简单动态字符串（sds)
1.1.1 数据结构定义

struct sdshdr{
    int len;
    int free;
    char buf[];
};

1.1.2 字段解释
len: 已使用字节的数量
free: 未使用字节的数量
buf：字节数组

1.1.3 图示

image.png

1.1.4 特性
遵循c字符串以空字符结尾的惯例，所以可重用一部分c字符串函数库里面的函数。
获取字符串长度的时间复杂度为o(1)
当sds进行修改时候，api会在必要时扩展sds的空间，以杜绝缓冲区溢出。
空间预分配和惰性空间释放来减少改变字符串时带来的内存重分配次数
buf存储字节数组，无编码问题。

1.2：链表（list)
1.2.1 数据结构定义

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} ListNode;

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;

1.2.2 字段解释
listNode:
prev: 指向前置节点
next: 指向后置节点
value: 节点的值
list:
head: 指向表头节点
tail：指向表尾节点
len：链表所包含的节点数量
dup、free、match 为实现多台链表所需对类型特定函数

1.2.3 图示

image.png

1.2.4 特性
双端：获取前置和后置节点的复杂度为o(1)
无环：表头节点的前置节点和表尾节点的后置节点为null
带表头和表为指针：list的head和tail保存表头和表尾节点指针，获取表头和表尾节点的复杂度为o(1)
带链表长度计数器：list的len属性保存节点数量，获取节点数量的复杂度为o(1)
多态：链表节点使用void*指针来保存节点值，并且可以通过dup,free,match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

1.3：字典（dict）
1.3.1 数据结构定义

/**
 * 哈希表节点
 */
typedef struct dictEntry
{
    void *key;
    union {
        void *val;
        unsigned int tu64;
        int ts64;
    } v;

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

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

//保存一簇操作指定类型键值对的函数
typedef struct dictType
{
    //计算hash值的函数
    unsigned int (*hashFunction)(const void *key);

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

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

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

    //删除键的函数
    void (*keyDestructor)(void *privdata, void *key);

    //删除值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

typedef struct dict
{
    //保存一簇用于操作制定类型键值对的函数，
    //redis会为用途不同对字典设置不同对类型特定函数
    dictType *type;

    //私有数据，保存需要传给那些类型特定函数当可选参数
    void *privdata;

    //哈希表，ht[0]作为存储使用，ht[1]rehash时使用
    dictht ht[2];

    //rehash索引
    //当rehash不再进行时，值为-1
    int trehashidx;
};

1.3.2 字段解释
dictEntry: 哈希表节点
key: key
val: value
next: 指向下一个哈希表节点，形成链表

dictHt: 哈希表
table: 哈希表节点数组
size: 哈希表大小
sizemask: 哈希表大小掩码，总是等于size-1，用于哈希算法
used: 该哈希表已有节点的数量

dictType: 函数簇

dict: dictHt封装
type: 函数簇
privdata: 私有数据
ht: 哈希表数组，ht[0]保存日常所用，ht[1]平常为空表，用于rehash。
trehashidx: rehash索引，当rehash不再进行时，值为-1.

1.3.3 图示

image.png
image.png
image.png

1.3.4 特性
用链地址法解决键冲突，被分配到同一个索引上的多个节点用next指针构成一个单向链表。
总是将新节点添加到链表的表头位置
哈希表采用渐进式rehash，rehash过程：
1: 将rehashidx置为0；
2: rehash期间，每次执行添加、删除、查找、更新操作，程序除操作ht[0]外，还会将ht[0]在rehashidx上的所有键值对rehash到ht[1]，rehash完成后，rehashidx增1；
3: rehash期间，字典删除，查找，更新操作会在两个表中同时进行；
4: rehash期间，字典插入会只操作ht[1]；
5: rehash结束，将rehashidx置为-1；

1.4：跳跃表（skiplist)
1.2.1 数据结构定义

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    //层
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

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

1.2.2 字段解释
zskiplistNode:
zskiplistLevel: 层
backward:后退指针
score: 分数
obj: 指向成员对象(sds)

zskiplist:
header,tail : 表头和表尾节点
length: 表中节点的数量
level: 表中层数最大的节点的层数
1.2.3 图示

image.png
image.png

1.2.4 特性
有序，按节点分值进行排序
每个跳跃表节点的层高都是1-32之间的随机数

1.5：整数集合（intset）
1.2.1 数据结构定义

typedef struct intset {
  uint32_t encoding;
  uint32_t length;
  int*_t contents[];
}intset;

1.2.2 字段解释
encodiing: 编码方式
length: 集合包含元素的数量
contens: 保存元素的数组
1.2.3 图示

image.png

1.2.4 特性
升级操作：新元素的类型比集合中现有所有的元素的类型都要长时，整数集合需要先进行升级，然后将新元素添加到整数集合里面；
不会降级；
底层实现为数组，且有序、无重复。

1.6：压缩列表
1.2.1 数据结构定义
压缩列表

image.png

压缩列表节点：

image.png

1.2.2 字段解释
压缩列表：
zlbytes: 记录整个压缩列表所占用的内存字节数；在对压缩列表进行内存重份额皮，或者计算alend对位置时使用；
zltail: 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无需便利整个压缩列表就可以确定表尾节点的地址。
zllen： 记录压缩列表包含的节点数量，2字节长（超过65535需要便利压缩列表）；
entryx: 压缩列表包含的各个节点；
zlend: 特殊值0xff，用于标记压缩列表的末端；

压缩列表节点：
previous_entry_length: 记录压缩列表中前一个节点的长度。这个字段可以是1字节或者5字节.用5字节保存时，第一字节的值为0x05。用于从后往前遍历；
encoding: 记录content属性所保存数据的类型以及长度。这个字段可以是1字节、2字节、5字节。
content: 保存节点的值，节点值可以是一个字节数组或者整数。值的类型由节点的encoding属性决定。
1.2.3 图示

image.png
image.png

1.2.4 特性
由于节点的previous_entry_length不定长，当添加或删除一个节点时，可能会引起连锁更新（一连串的空间重分配操作），但在实际应用中规模较小。
是一种为节约内存而开发的顺序型数据结构。

下一章将记录redis对象及数据结构的应用。
参考：
《redis设计与实现》
http://zhangtielei.com/ redis数据结构之skiplist。