Redis 原理 - List

List 数据结构

• Redis 3.2 前,使用 压缩列表zipList 或 双向链表linkedList
  当同时满足下面两个条件时,使用zipList存储数据
  
  
  
  • list保存的每个元素长度小于64字节
    
  • 列表中数据个数少于512个
    
  
  
• Redis 3.2 及之后的底层实现方式: quickList
  quickList 是一个基于 zipList 的双向链表, quickList 的每个节点都是一个 zipList , 结合了双向链表和 zipList 的优点
  

双向链表就不多说了,就是基础的数据结构
压缩列表(zipList)

1. struct ziplist<T> {
2.     int32 zlbytes; // 整个压缩列表占用字节数
3.     int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
4.     int16 zllength; // 元素个数
5.     T[] entries; // 元素内容列表，挨个挨个紧凑存储
6.     int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
7. }
9. struct entry {
10.     int prevlen; // 前一个 entry 的字节长度
11.     int encoding; // 元素类型编码
12.     byte[] content; // 元素内容
13. }

复制代码

• 优势: 内存连续,高效顺序访问,减少内存碎片.
  
• 劣势: 当数据量过大时,zipList就不那么好用了. 因为为了保证它存储内容在内存中的连续性,插入的复杂度为O(N),而且如果超出zipList内存大小,还会做重新分配的内存空间,并将内容复制到新的地址. 如果数量大的话,重新分配内存和拷贝内存会消耗大量时间. 所以不适合大型字符串,也不适合存储量多的元素..
  

适用场景: 少量数据, 读远大于写,提供高效的读取操作

快速列表(quickList)

是zipList和linkedList的结合体,是将linkedList按段切分,每一段用zipList来紧凑存储

1. typedef struct quicklist {
2.     quicklistNode *head; // 指向quicklist的头节点
3.     quicklistNode *tail; // 指向quicklist的尾节点
4.     unsigned long count; // 压缩列表中总元素数量
5.     unsigned int len; //链表节点的个数 quicklistNode
6.     int fill : 16; // ziplist大小限定，由list-max-ziplist-size给定
7.     unsigned int compress : 16; // 节点压缩深度设置，由list-compress-depth给定
8. } quicklist;
10. typedef struct quicklistNode {
11.     struct quicklistNode *prev; // 指向上一个ziplist节点
12.     struct quicklistNode *next; // 指向下一个ziplist节点
13.     unsigned char *zl; // 数据指针，如果没有被压缩，就指向ziplist结构，反之指向quicklistLZF结构
14.     unsigned int sz; // 指向的ziplist的字节数
15.     unsigned int count : 16; // 指向的ziplist的元素个数
16.     unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
17.     unsigned int container : 2;  // 预留字段，存放数据的方式，1--NONE，2--ziplist
18.     unsigned int recompress : 1;     // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
19.     unsigned int attempted_compress : 1; /* node can't compress; too small */
20.     unsigned int extra : 10; // 扩展字段
21. } quicklistNode;
23. typedef struct quicklistLZF {
24.     unsigned int sz; // LZF压缩后占用的字节数
25.     char compressed[]; // 柔性数组，存放压缩后的ziplist字节数组
26. } quicklistLZF;

复制代码

在向quicklist添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的 ziplist 是否能容纳该元素，如果能够容纳，那么就直接保存到ziplist，如果不能容纳，才会新建一个Node节点,并保存到新的 ziplist 中。

总结

quickList 结合了 ziplist 和 双向链表的优点, 相当于把 双向链表 拆分为 一段段的 ziplist , 每一段的 ziplist 是连续存储的, 可以做到高效的顺序访问,有利于减少内存碎片.

List的常用命令

• LPUSH key element ... 向列表的左侧插入一个或多个元素
  
• RPUSH key element ... 向列表的右侧插入一个或多个元素
  
• LPOP key 移除并返回列表左侧的第一个元素
  
• RPOP key 移除并返回列表右侧的第一个元素
  
• LRANGE key start stop 返回索引范围内的所有元素
  
• BLPOP key timeout 移除并返回列表左侧的第一个元素,没有元素时会阻塞等待指定的时间
  
• BRPOP key timeout 移除并返回列表右侧的第一个元素,没有元素时会阻塞等待指定的时间
  
• 更多的List命令,请查阅 官方文档
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！