Redis总共有8种基础数据结构， 用encoding判断数据结构源码

object encoding numb(键名) 可以查看当前键是用的什么数据结构

3.0的源码
case REDIS_ENCODING_INT: return "int";  字符串类型之一,只有单个数字
case REDIS_ENCODING_RAW: return "raw";  字符串类型之一,当字符串数量很长的时候用这个
case REDIS_ENCODING_EMBSTR: return "embstr"; SDS简单字符串
case REDIS_ENCODING_LINKEDLIST: return "linkedlist"; 列表
case REDIS_ENCODING_HT: return "hashtable"; 哈希表
case REDIS_ENCODING_SKIPLIST: return "skiplist"; 跳跃表
case REDIS_ENCODING_INTSET: return "intset"; 整数集合
case REDIS_ENCODING_ZIPLIST: return "ziplist"; 压缩列表(6.0已废弃)

第一跟第二没什么数据结构，主要是分析冲SDS开始下面的几种

1. SDS（Simple Dynamic String）简单动态字符串

• 结构

  
  
  redis设计与实现
• 用途
  当 Redis 需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis就会使用 SDS 来表示字符串值，比如在 Redis 的数据里面，包含字符值的键值对在底层都是由 SDS实现的。

> set msg "hello world"
OK
> object encoding msg
embstr
这一条语句里面 redis会创建一对键值对
键值对的键是一个字符串对象，它底层保存这一个“msg“的SDS
键值对的值也是一个字符串对象，值的底层保存一个“hello world”的SDS

2. 链表(list)

• 结构

  
  
  image.png

• 用途
  链表在 Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。

3. 字典(dict)

• 结构

  
  
  普通状态下的字典(没有进行rehash)
  
  

  这里面有几个数据结构，字典(dict)，hash表(ht)，哈希节点(entry)

1. 字典(dict)：字典表里最重要的是哈希表数组dictht ht[2];，这边的定义为2，一个是平常使用的，另外一个是rehash的时候用到的，将ht[0]的数据重新计算转移到ht[1]，包含扩容等，类似于jvm里面的复制删除算法
2. hash表(dictht)：这里面主要包含了多个hash节点，hash节点是真正存储key,value的地方
3. hash节点(dicEntry)：正式保存key，value的地方

• 用途
  字典，又称为符号表(symbol table)、关联数组(associative array)或映射(map)，是一种用于保存键值对(key-value pair)的抽象数据结构。在字典中，一个键 (key)可以和一个值 (value)进行关联(或者说将键映射为值)这些关联的键和值就称为键值对。

例如上面的set msg "hello world" 这里面就是新建了两个SDS对象,分别为键msg跟值"hello world"，他们就用字典联系在一起

哈希算法：
每次有新的键值数据被创建时，都会先用哈希算法计算哈希值

// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
h = dictHashKey(ht, key) & ht->sizemask;

Redis用murmurhash2来实现hash值的计算

• 解决hash冲突
  主要用的是在上面代码dictEntry实体中的next字段。当hash值发生冲突时直接把发生冲突的新节点的next字段指向新节点(这么做的原因是如果链表没有提供指向链表末尾节点的指针，如果把新节点添加到老节点后面，如果老节点后面已经有冲突，可能会一直next寻址下去，增加了寻址时间)

• rehash及其扩容
  当哈希节点里面的数据数量(?????)达到一定程度是会进行扩容或者收缩
  (1)假设现在用的是ht[0],如果是扩容的话，扩容的数量为原数据量的两倍，假设ht[0].used的值为4，及扩容后ht[1].szie = 2*=8(如果是收缩的话则除于2)
  (2)然后将ht[0]的数据rehash进去到ht[1]，直到ht[0]清空，这个是慢慢执行的，dict.rehashIdx就是记录这个用的
  (3)直到全部清空，ht[0]变成空数组，下次rehash时数据放到它里面，一直这样循环

5. 跳跃表(zskiplist)

跳跃表( skiplist) 是一种有序的数据结构, 它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的.
他分为跳跃表zskiplist 跟跳跃表节点zskiplistNode
一个跳跃表里面有多个跳跃表节点

skiplistNode主要的属性是backward向前回退的指针,score分值,obj对象

完整的跳跃表的结构

跳跃表图示

• 用途
  跳跃表只用在zset有序集合喝集群节点做内部数据库用，一般使用时只在zset里使用

redis为什么不用跳跃表，要用b树，跳跃表的好处是啥

6. 整数集合(intset)

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

> sadd tIntset 1 2 3 4
4
> object encoding tIntset
intset

• 结构

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

• 自动升级
  三个类型的上下限分别为：int16_t（-32768，32767），int32_t（-2147483648，2147483647），int64_t
  默认存储为了节省空间，选用的是int16，当需要存储的数据超过int16时（比如存入32777），会自动升级成int32，但是相反的，是不允许降级的，尽管没有超过的数值。

7. 压缩列表(ziplist，有点像数组)

• 压缩列表是由一系列的特殊编码的连续内存块组成的顺序型设计模式

// 源码里的布局说明
 * The general layout of the ziplist is as follows:
 *
 * <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

image.png

• 弊端：连锁更新
  压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

/*
 * 保存 ziplist 节点信息的结构
 */
typedef struct zlentry {
    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;
    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小
    unsigned int lensize, len;
    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 当前节点值所使用的编码类型
    unsigned char encoding;
    // 指向当前节点的指针
    unsigned char *p;
} zlentry;

• prevrawlensize 前置节点的长度，该属性用于遍历压缩列表(当前节点的指针-prevrawlensize =上个节点的指针，下面的privious_entry_length即prevrawlensize )

  
  
  redis设计与实现

8. 快速列表(quicklist)

• redis 3.2后新增的数据结构，原理为双向压缩列表(双向列表结合压缩表)

• 结构
  每个quicklistNode节点是一个压缩列表，里面配置着压缩列表的最大的节点数量，当数量多的时候就新建一个quicklistNode放置，简单来说就是由多个压缩列表组合成的一个list，主要目的是解决压缩列表数量大的时候更新时候会有连锁更新的问题

  
  
• 代码

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* 单个压缩列表的最大数量*/
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;



typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    unsigned int sz;
    int offset;
} quicklistEntry;