Redis的数据结构

===================================================================================

1.对象结构

Redis中每个对象都由一个redisObject结构表示， typedef struct redisObject{    unsigned type:4;     //类型    unsigned encoding:4: //编码    void *prt;           //指向底层实现数据结构的指针 } type类型保存对象的类型 ----------------------------- 类型常量:对象名称:type命令的输出 REDIS_STRING:字符串对象:string REDIS_LIST:列表对象:list REDIS_HASH:哈希列表:hash REDIS_SET:集合对象:set REDIS_ZSET:有序集合对象:zset ----------------------------- encoding记录了对象的编码，则编码也决定了对象使用哪种数据结构来实现 ----------------------------- type类型:编码常量:对象 REDIS_STRING:REDIS_ENCODING_INT:整数值实现的字符串对象 REDIS_STRING:REDIS_ENCODING_EMBSTR:使用embstr编码的简单动态字符串实现的字符串对象 REDIS_STRING:REDIS_ENCODING_RAW:使用简单动态字符串实现的字符串对象 REDIS_LIST:REDIS_ENCODING_ZIPLIST:使用压缩列表实现的列表对象 REDIS_LIST:REDIS_ENCODING_LINKEDLIST:双端链表实现的列表对象 REDIS_HASH:REDIS_ENCODING_ZIPLIST:使用压缩列表实现的哈希对象 REDIS_HASH:REDIS_ENCODING_HT:使用字典实现的哈希对象 REDIS_SET:REDIS_ENCODING_INTSET:使用整数集合实现的集合对象 REDIS_SET:REDIS_ENCODING_HT:使用字典实现的集合对象 REDIS_ZSET:REDIS_ENCODING_ZIPLIST:使用压缩列表实现的有序集合对象 REDIS_ZSET:REDIS_ENCODING_SKIPLIST:使用跳跃表字典实现的有序集合对象

2.压缩列表-ziplist

压缩列表可以作为列表键和哈希键的实现之一。 当哈希键的只包含少量的键值对时，而且每个键和值都是小整数值，或者每个键和值都是长度比较短的字符串时 Redis就会使用ziplist作为哈希键的实现，即OBJECT KEY输出会是ziplist。 ziplist结构 ------------------------------ |zlbytes|zltail|zllen|entry1|...|entryn|zlend| 其中， zlbytes，记录压缩列表占用的内存字节数； zltail，记录压缩列表最后一个节点距离压缩列表的起始地址有多少字节，从而可以很快确定尾节点； zllen，压缩列表的节点数，如果zllen大于等于65535（UNIT16_MAX）,则需要遍历所有节点，才能知道节点数； entry1...entryn，节点 zlend，标记列表的结尾 压缩列表的节点entry1...entryn的结构 ------------------------------ |previous_entry_length|encoding|content| 其中， previous_entry_length，记录前一个节点的长度，previous_entry_length长度可以是1字节或5字节，                         如果前节点长度小于254，则该属性用1字节记录前节点的长度；如果前节点大于等于254，则属性用5字节来记录，如0xFE00002766，0xFE表示属性是5字节，                         2766则前节点长度为10086，所以通过previous_entry_length可以遍历前节点 encoding， content，保存节点的值，可以是一个字节数组或整数， 压缩列表遍历： 压缩列表的起始地址和zltail=>>尾节点地址（entryn），entryn的起始地址-entryn.previous_entry_length=>>entryn-1节点的起始地址， 类似地，一直遍历到头节点。 连锁更新 假如压缩列表的节点长度都是小于254，则节点的preious_entry_length都是用1字节来保存的，新一个节点entry_new的长度大于等于254，则头节点entry1的previous_entry_length的1字节则保存不了新节点的长，需要重新分配内存，类似地entry2也需要重新分配内存。。。直到entryn，产生了连锁更新。

3.字典

用于保存键值对(key-value)的数据结构 typedef struct dict{     dictType *type;//类型特定函数     void *privdate;//私有数据     //哈希表数组，包含2个哈希表，重点关注这个属性     dictht ht[2];     //rehash索引     in trehashidx; } 对于字典中的哈希表数据，一般只使用ht[0]来保存哈希节点数据，当进行rehash时，使用ht[1]。 有新哈希节点进来时，会首先计算出节点key的哈希值，根据哈希值和哈希表(dictht)的sizemask（即掩码）， 从而算出哈希数组的索引，从而确定哈希节点在数组中的位置，如果table[i]已经有哈希节点，则让已有节点作用新节点的next属性， 这样可以新节点靠前，从而提高命中率。 rehash-重新散列，即重新扩展或缩小哈希节点数据 当哈希对象中节点变多时，为使得负载因子控制在一定合适的范围，就是让节点尽量落在哈希表的节点数组的头节点上，而不是连上已有节点的链表上，从而提高命中时间。 每次扩展时，哈希表dictht的table数组的长度会乘以2位，即是2的幂次方增长。 当哈希对象中节点变少时，重新散列则可以节省内存空间 每次缩小时，哈希表dictht的table数组的长会除以2位，即是以2来开方缩减， 每次进行rehash，会给dict中的ht[1]进行内存空间分配，待ht[0]的数据全部转到ht[1]后，再重新将ht[0]指向ht[1]，ht[1]又变成空表。 哈希表-dictht typedef struct dictht{     //哈希节点数组（哈希表），用来保存哈希节点数据     dictEntry **table;          //哈希节点数组的大小     unsigned long size;     //哈希表大小的掩码，用来计算哈希节点应该放在哈希表上哪个位置，即哈希表的索引     //它的值总是等于size - 1     unsigned long sizemask;     //哈希表已保存节点的数量     unsigned long used; } 哈希节点-dictEntry typedef struct dictEntry{     void *key; //节点的键     //节点的值     union{         void *val;         unit64_tu64;         int64_ts64;     } v;     //下个节点，从而形成链表     struct dictEntry *next; } dictEntry;

4.哈希对象-hash

哈希对象编码可以是ziplist（压缩列表）或者hashtable（字典） 当使用ziplist作为底层实现来储存数据时，保存键值对时，压缩列表中的键节点和值节点紧密连在一起的， 键节点在前面，值节点在后面。 在redis的配置文件中， //哈希对象中所有节点的键和值的字符串长度都小于64字节 hash-max-ziplist-value 64 //所有键值对节点的数量小于512个 hash-max-ziplist-entries 512

当且仅当上面两个条件满足时，才会继续使用ziplist来保存哈希对象的数据；否则，会转而使用字典来实现哈希对象底层实现。

5.跳跃表-skiplist

跳跃表是一个有序数据结构，通过每个节点维持多个指向其他节点的指针，从而可以快速访问节点。 跳跃表查找节点的时间复杂度平均O(logN)、最坏O(N)，跳跃表可以作为Redis中有序集合对象的实现之一。 跳跃表由zskiplist和zskiplistNode两个结构来定义： zskiplist结构 typedef struct zskiplist{     //跳跃表的头节点     zskiplistNode *header;     //跳跃表的尾节点     zskiplistNode *tail;     //跳跃表里层数最大的节点的层数（不包括头节点）     unsigned long level;     //跳跃表里的节点数量（不包括头节点）     int length; } zskiplistNode结构 typedef struct zskiplistNode{     //层     struct zskiplistLevel{         //前进指针         zskiplistNode *forward;         //到前进指针的跨度         unsigned int span;     } level[];     //后退指针     zskiplistNode *backward;     //分值     double score;     //成员对象     robj *obj; } 层-level[] zskiplistNode跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，一般来说，层的数量越多，访问节点的速度就赶快。 前进指针-level[i].forward 前进指针可以访问到表尾方向的节点，这样，则可以从表头遍历到表尾的节点。 跨度-level[i].span 跨度用来记录两个节点的距离，跨度越大，节点距离越远，所有指向NULL的前进节点跨度都为0，说明它没有指向节点，遍历也结束了。 后退指针-backward 每个跳跃表节点的只有一个后退指针，则它只能后退前一个节点，而不像前进指针-level[i].forward可以有多个。 分值和成员 跳跃表的所有分值-score都从小到大排序，成员-obj指针指向一个字符串对象。 在跳跃表中，每个成员都是唯一的，而分值可以有相同的，相同分值的节点情况下，成员越小，排序越靠前，是按照字典的规则，按照"ABCDEF"的顺序，比如分值都是100，则field越小的排前面， 1)"abc" 2)100 3)"acc" 4)100 5)"baa" 6)100。 首先比较第一个字符，a的排在前，相同然后后面一位，同理b在c的前面。

6.有序集合-zset

有序集合的编码可以是ziplist或skiplist 当用zkiplist作为zset的实现时，每个有序集合元素都使用两个压缩列表节点紧挨在一起保存在ziplist，成员节点排前面，分值节点排后面。 当用skiplist作为zset的实现时，还会使用到字典-dict来作为另一个实现，skiplist和dict一起作为zset的实现： typedef struct zset{     zskiplist * zsl;     dict *dict; } 使用skiplist跳跃列表作为zset集合实现时，可以根据分值来对有序集合进行分值范围操作，比较方便，因为跳跃表就是根据分值大小排序的； 但如果操作某个成员时，从而遍历整个跳跃表则显得比较慢了，时间复杂度为O(N)，则需要额外使用字典-dict来保存成员-member和分值-score关系，使用了字典后， 操作某个成员时，查找的时间复杂度只需要为O(1)，从而比较快了。 虽然skiplist和dict都保存了有序集合的元素，但成员-member和分值-score都使用指针来同一个元素的成员和分值。

额外说明一点，Redis在初始化服务器时，会初始化0-9999的数字作为缓存，类似于java也会有-128到127的整数缓存，这是同样的道理。

有序集合的编码转换 //有序集合保存的元素小于128个 zset-max-ziplist-entries 128 //有序集合的所有元素成员member的长度都小于64个字节 zset-max-ziplist-value 64 当以上两个条件都同时满足时，有序集合会使用ziplist编码来保存元素，否则，则转换成skiplist和dict保存元素。