redis 底层数据结构

有序集合

　　跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。具有如下性质：

由很多层结构组成；

每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点；

最底层的链表包含了所有的元素；

如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；

链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；

　　Redis中跳跃表节点定义如下：

typedef struct zskiplistNode {

    //层

    struct zskiplistLevel{

          //前进指针

          struct zskiplistNode *forward;

          //跨度

          unsigned int span;

    }level[];

    //后退指针

    struct zskiplistNode *backward;

    //分值

    double score;

    //成员对象

    robj *obj;

} zskiplistNode

　　多个跳跃表节点构成一个跳跃表：

typedef struct zskiplist{

    //表头节点和表尾节点

    structz skiplistNode *header, *tail;

    //表中节点的数量

    unsigned long length;

    //表中层数最大的节点的层数

    int level;

}zskiplist;

　　搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。

　　插入：首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到从底层到k层。

　　删除：在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

字符串

Redis的字符串，不是 C 语言中的字符串，它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示

　　SDS定义：

struct sdshdr{

    //记录buf数组中已使用字节的数量

    //等于 SDS 保存字符串的长度

    int len;

    //记录 buf 数组中未使用字节的数量

    int free;

    //字节数组，用于保存字符串

    char buf[];

}

　　用SDS保存字符串 “Redis”具体图示如下：

　　SDS 数据类型的定义:

len 保存了SDS保存字符串的长度

buf[] 数组用来保存字符串的每个元素

free j记录了 buf 数组中未使用的字节数量

列表

　　链表是一种常用的数据结构，C 语言内部是没有内置这种数据结构的实现，所以Redis自己构建了链表的实现

　　链表定义：

typedef  struct listNode{

      //前置节点

      struct listNode *prev;

      //后置节点

      struct listNode *next;

      //节点的值

      void *value;  

}listNode

　　通过多个listNode结构组成列表，这是一个双向列表

typedef struct list{

    //表头节点

    listNode *head;

    //表尾节点

    listNode *tail;

    //链表所包含的节点数量

    unsigned long len;

    //节点值复制函数

    void (*free) (void *ptr);

    //节点值释放函数

    void (*free) (void *ptr);

    //节点值对比函数

    int (*match) (void *ptr,void *key);

}list;

　　Redis链表特性：

双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。

无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。

带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。

多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

字典

　　字典又称为符号表或者关联数组、或映射（map），是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。C 语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己构建的。

　　哈希表结构定义

typedef struct dictht{

    //哈希表数组

    dictEntry **table;

    //哈希表大小

    unsigned long size;

    //哈希表大小掩码，用于计算索引值

    //总是等于 size-1

    unsigned long sizemask;

    //该哈希表已有节点的数量

    unsigned long used;

}dictht

　　哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

typedef struct dictEntry{

    //键

    void *key;

    //值

    union{

         void *val;

         uint64_tu64;

         int64_ts64;

    }v;

    //指向下一个哈希表节点，形成链表

    struct dictEntry *next;

}dictEntry

　　key 用来保存键，val 属性用来保存值，值可以是一个指针，也可以是uint64_t整数，也可以是int64_t整数。

　　注意这里还有一个指向下一个哈希表节点的指针，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过next这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。