Redis的数据结构

1.Redis五种value结构

分别为String，Hash，list，set，zset。
Redis 的键值对中的 key 就是字符串对象，⽽ value 可以是字符串对象，也可以是集合数据类型的对象，
⽐如 List 对象、Hash 对象、Set 对象和 Zset 对象。
2.Redis底层数据结构

Redis中value的底层数据结构实现如图：

Redis 是使用了⼀个「哈希表」保存所有键值对，哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对。哈希表其实就是⼀个数组，数组中的元素叫做哈希桶。
哈希桶存放的是指向键值对数据的指针（dictEntry*），如许通过指针就能找到键值对数据，然后由于键值对的值可以保存字符串对象和集合数据类型的对象，所以键值对的数据结构中并不是直接保存值本身，⽽是保存了 void * key 和 void * value 指针，分别指向了现实的键对象和值对象，如许⼀来，即使值是集合数据，也可以通过 void * value 指针找到。

 void * key 和 void * value 指针指向的是 Redis 对象，Redis 中的每个对象都由 redisObject结构表示，如下图：

 
象结构⾥包含的成员变量：

• type，标识该对象是什么类型的对象（String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对 象）；
  
• encoding，标识该对象使⽤了哪种底层的数据结构；
  
• ptr，指向底层数据结构的指针。
  

2.1 SDS

2.2链表 

2.3 压缩列表

压缩列表的最大特点，就是它被设计成⼀种内存紧凑型的数据结构，占用⼀块连续的内存空间，不仅可以利用CPU 缓存，而且会针对不同长度的数据，举行相应编码，这种方法可以有效地节省内存开销。
压缩列表是 Redis 为了节约内存而开辟的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。

• zlbytes，记录整个压缩列表占用内存字节数；
  
• zltail，记录压缩列表「尾部」节点距离起始地点由多少字节，也就是列表尾的偏移量；
  
• zllen，记录压缩列表包含的节点数量；
  
• zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）
  
• prevlen，记录了「前⼀个节点」的长度；
  
• encoding，记录了当前节点现实数据的类型以及⻓度；
  
• data，记录了当前节点的现实数据；
  

在压缩列表中，假如我们要查找定位第⼀个元素和最后⼀个元素，可以通过表头三个字段的⻓度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。
压缩列表的缺点：存在连锁更新问题，缩列表新增某个元素或修改某个元素时，假如空间不不够，压缩列表占⽤的内存空间就必要重新分配。而当新插⼊的元素较大时，可能会导致后续元素的 prevlen 占⽤空间都发生变化，从而引起「连锁更新」 问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的降落。

• 假如前⼀个节点的⻓度小于 254 字节，那么 prevlen 属性必要用1字节的空间来保存这个长度值；
  
• 假如前⼀个节点的⻓度大于即是 254 字节，那么 prevlen 属性必要⽤5 字节的空间来保存这个长度值。
  

应用场景：压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发⽣连锁更新，也是能接受的。
2.4哈希表

能以 O(1) 的复杂度快速查询数据。存在哈希冲突问题。
Redis 采用了「链式哈希」来解决哈希冲突，rehash
在现实使用哈希表时，Redis 界说⼀个 dict 结构体，这个结构体⾥界说了两个哈希表（ht[2]）
为了克制 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的环境，所以 Redis 采⽤了渐进式 rehash，也就是将数据的迁移的工作不再是⼀次性迁移完成，而是分多次迁移。
rehash的触发条件，rehash 的触发条件跟负载因⼦（load factor）有关系
负载因子 = 哈希表已保存节点数量 / 哈希表大小
2.5整数集合

整数集合本质上是⼀块连续内存空间，它的结构界说如下：
typedef struct intset {
uint32_t encoding; //编码⽅式
uint32_t length; //集合包含的元素数量
int8_t contents[]; //保存元素的数组
} intset;
contents 数组的真正类型取决于 intset 结构体⾥的 encoding 属性的值。
整数集合会有⼀个升级规则，就是当我们将⼀个新元素加⼊到整数集合里面，假如新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时，整数集合必要先辈行升级。

2.6跳表（跨度和元素权重）

Redis 只有在 Zset 对象的底层实现用到了跳表，跳表的优势是能⽀持平均 O(logN) 复杂度的节点查找。
Zset 对象在使⽤跳表作为底层实现的时候，并不是指向跳表数据结构，⽽是指向了zset结构，它包含两个
数据结构⼀个是跳表，⼀个是哈希表。如许的好处是既能举行高效的范围查询，也能举行高效单点查询。

跳表节点查询过程：（重要根据元素权重和元素大小来查询数据）

• 假如当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下⼀个节点。
  
• 假如当前节点的权重「即是」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下⼀个节点。
  

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)
Redis 则采⽤⼀种奥妙的方法是，跳表在创建节点的时候，随机⽣成每个节点的层数，并没有严酷维持相邻两层的节点数量比例为2:1的环境。
详细的做法是，跳表在创建节点时候，会生成范围为[0-1]的⼀个随机数，假如这个随机数小于 0.25（相称于概率 25%），那么层数就增长 1 层，然后继续⽣成下⼀个随机数，直到随机数的结果⼤于 0.25 结束，终极确定该节点的层数。
2.7quicklist

quicklist 就是「双向链表 + 压缩列表」组合，由于⼀个 quicklist 就是⼀个链表，⽽链表中的每个元素又是⼀个压缩列表。
quicklist 解决压缩列表的缺点的办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。 由于压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

 
在向 quicklist 添加⼀个元素的时候，不会像普通的链表那样，直接新建⼀个链表节点。而是会查抄插⼊位置的压缩列表是否能容纳该元素，假如能容纳就直接保存到 quicklistNode 结构⾥的压缩列表，假如不能容纳，才会新建⼀个新的 quicklistNode 结构。
2.8listpack

Redis 在 5.0 新设计⼀个数据结构叫 listpack，目的是替代压缩列表，它最⼤特点是 listpack 中每个节点不再包含前⼀个节点的长度了，压缩列表每个节点正由于必要保存前⼀个节点的长度字段，就会有连锁更新的隐患。

 listpack 没有压缩列表中记录前⼀个节点⻓度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加⼊⼀个新元素的时候，不会影响其他节点的长度字段的变化，从而克制了压缩列表的连锁更新问题。
参考：《小林coding》，网址：www.xiaolincoding.com

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。