Redis系列（六）：数据结构QuickList（快速列表）源码解析
1.介绍Redis在3.2版本之前List的底层编码是ZipList和LinkedList实现的 在3.2版本之后，重新引入了QuickList的数据结构，列表的底层都是QuickList实现 当List对象中元素的长度比较小或者数量比较少的时候，采用ZipList来存储 当List对象中元素的长度比较大或者数量比较多的时候，采用LinkList来存储 这两种存储方式的优缺点 LinkedList便于在表的两端进行Push和Pop操作，在插入节点复杂度很低，但是它的内存开销很大，首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针。 其次；双向链表的各个节点时单独的内存块，地址不连续，节点多了容易产生内存碎片 ZipList存储在一段连续的内存上，所以存储效率很高，但是它不利于修改操作，插入和删除操作需要频繁的申请释放内存。 特别是当ZipList长度很长的时候，一次Realloc可能导致大批量的数据拷贝 QuickList可以看作一个双向列表，但是列表的每个节点都是一个ziplist， 其实就是linkedlist和ziplist的结合。quicklist中的每个节点ziplist都能够存储多个数据元素。 2.示意图
? ? ?3.源码实现typedef struct quicklist { quicklistNode *head; // 指向quicklist的头部 quicklistNode *tail; 指向quicklist的尾部 unsigned long count; 列表中所有数据项的个数总和 unsigned int len; quicklist节点的个数，即ziplist的个数 int fill : 16; ziplist大小限定，由list-max-ziplist-size给定 unsigned int compress : 16; 节点压缩深度设置，由list-compress-depth给定 } quicklist; count用来统计所有数据项的个数总和，len用来统计quicklist的节点个数， 因为每个节点ziplist都能存储多个数据项，所以有了这两个统计值。 typedef quicklistNode { struct quicklistNode *prev; 指向上一个ziplist节点 struct quicklistNode *next; 指向下一个ziplist节点 unsigned char *zl; 数据指针，如果没有被压缩，就指向ziplist结构，反之指向quicklistLZF结构 unsigned int sz; 表示指向ziplist结构的总长度(内存占用长度) unsigned int count : 16; 表示ziplist中的数据项个数 unsigned int encoding : 2; 编码方式，1--ziplist，2--quicklistLZF unsigned int container : 2; 预留字段，存放数据的方式，1--NONE，2--ziplist unsigned int recompress : 1; 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩 unsigned int attempted_compress : 测试相关 unsigned int extra : 10; 扩展字段，暂时没用 } quicklistNode; QuickList的迭代器结构,指向迭代器节点元素 quicklist的迭代器结构 typedef quicklistIter { const quicklist *quicklist; 指向所在quicklist的指针 quicklistNode *current; 指向当前节点的指针 unsigned char *zi; 指向当前节点的ziplist long offset; 当前ziplist中的偏移地址 int direction; 迭代器的方向 } quicklistIter; 表示quicklist节点中ziplist里的一个节点结构 typedef quicklistEntry { 指向所在quicklist的指针 quicklistNode *node; 指向当前节点的ziplist unsigned char *value; 当前指向的ziplist中的节点的字符串值 long long longval; 当前指向的ziplist中的节点的整型值 unsigned int sz; 当前指向的ziplist中的节点的字节大小 int offset; 当前指向的ziplist中的节点相对于ziplist的偏移量 } quicklistEntry; 创建QuickList fill: -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes） -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。 -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。 -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值） -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。 compress: 0 特殊值，表示不压缩 1 表示quicklist两端各有一个节点不压缩，中间的节点压缩 2 表示quicklist两端各有两个节点不压缩，中间的节点压缩 3 表示quicklist两端各有三个节点不压缩，中间的节点压缩 quicklist *quicklistCreate(void) { struct quicklist *quicklist; 声明指针 quicklist = zmalloc(sizeof(*quicklist)); 分配内存 quicklist->head = quicklist->tail = NULL; 设定头尾指针 quicklist->len = 0; 设定长度 quicklist->count = 设定数据项总和 quicklist->compress = 设定压缩深度 quicklist->fill = - 设定ziplist大小限定 return quicklist; } 创建QuickListNode REDIS_STATIC quicklistNode *quicklistCreateNode() { quicklistNode *node; node = zmalloc(sizeof(*node)); 申请内存 node->zl = NULL; 初始化指向ziplist的指针 node->count = 初始化数据项个数 node->sz = 初始化ziplist大小 node->next = node->prev = NULL; 初始化prev和next指针 node->encoding = QUICKLIST_NODE_ENCODING_RAW; 初始化节点编码方式 node->container = QUICKLIST_NODE_CONTAINER_ZIPLIST; 初始化存放数据的方式 node->recompress = 初始化再压缩标记 node; } ? （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
