网上有关“redis数据结构使用”话题很是火热，小编也是针对redis数据结构使用寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
前言
续接上文：redis压缩列表ziplist，内存优化之路
本文参考源码版本仍为Redis6.2。
quicklist是Redis底层最重要的数据结构之一，它是Redis对外提供的6种基本数据结构中List的底层实现，在Redis 3.2版本中引入。
在引入quicklist之前，Redis采用压缩链表（ziplist）以及双向链表（linked-list）作为List的底层实现。
当元素个数比较少并且元素长度比较小时，Redis采用ziplist作为其底层存储。
当任意一个条件不满足时，Redis采用linked-list作为底层存储结构。
这么做的主要原因是，当元素长度较小时，采用ziplist可以有效节省存储空间，但ziplist的存储空间是连续的，当元素个数比较多时，修改元素时，必须重新分配存储空间，这无疑会影响Redis的执行效率，故而采用一般的双向链表。
quicklist是综合考虑了时间效率与空间效率引入的新型数据结构。
<hr color=#000000 size=1">
一、quicklist真面目Redis源码中对quicklist的注释为 A doubly linked list of ziplists；也就是说quicklist是由ziplist组成的双向链表，其中每一个链表节点都是一个独立的ziplist结构，因此，从结构上看，quicklist就是ziplist的升级版。
优化的关键在于，如何控制好每个ziplist的大小
quicklist的节点ziplist越小，越有可能造成更多的内存碎片。极端情况下，一个ziplist只有一个数据entry，也就退化成了linked list
quicklist的节点ziplist越大，分配给ziplist的连续内存空间越困难。极端情况下，一个quicklist只有一个ziplist，也就退化成了ziplist
因此，合理配置参数显得至关重要，不同场景可能需要不同配置；redis提供list-max-ziplist-size参数进行配置，默认-2，表示每个ziplist节点大小不超过8KB
二、原理分析数据存储1. quicklistNode结构：typedef?struct?quicklistNode?{struct?quicklistNode?*prev;//前一个quicklistNodestruct?quicklistNode?*next;//后一个quicklistNodeunsigned?char?*zl;?//quicklistNode指向的ziplistunsigned?int?sz;?//ziplist的字节大小unsigned?int?count?:?16;?//ziplist中的元素个数unsigned?int?encoding?:?2;?//编码格式，原生字节数组或压缩存储unsigned?int?container?:?2;//存储方式unsigned?int?recompress?:?1;?//数据是否被压缩unsigned?int?attempted_compress?:?1;?//数据能否被压缩unsigned?int?extra?:?10;?//预留的bit位}?quicklistNode;其中
prev、next指向该节点的前后节点；
zl指向该节点对应的ziplist结构；
sz代表整个ziplist结构的大小；
encoding代表采用的编码方式：1代表是原生的，2代表使用LZF进行压缩；
container为quicklistNode节点zl指向的容器类型：1代表none,2代表使用ziplist存储数据
recompress代表这个节点之前是否是压缩节点，若是，则在使用压缩节点前先进行解压缩，使用后需要重新压缩，此外为1，代表是压缩节点；
attempted_compress测试时使用；
extra为预留
2. quicklist结构quicklist 作为一个链表结构，在它的数据结构中，是定义了整个 quicklist 的头、尾指针，这样一来，可以通过 quicklist 的数据结构，来快速定位到 quicklist 的链表头和链表尾。
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;fill用来指明每个quicklistNode中ziplist长度，当fill为正数时，表明每个ziplist最多含有的数据项数，当fill为负数时，如下：
Length -1: 4k，即ziplist节点最大为4KB
Length -2: 8k，即ziplist节点最大为8KB
Length -3: 16k ...
Length -4: 32k
Length -5: 64k
fill取负数时，必须大于等于-5。可以通过Redis修改参数list-max-ziplist-size配置节点所占内存大小。实际上每个ziplist节点所占的内存会在该值上下浮动。
考虑quicklistNode节点个数较多时，我们经常访问的是两端的数据，为了进一步节省空间，Redis允许对中间的quicklistNode节点进行压缩，通过修改参数list-compress-depth进行配置，即设置compress参数，该项的具体含义是两端各有compress个节点不压缩。
quicklist整体结构：
3. quicklistEntry结构quicklistNode中ziplist中的一个节点
typedef?struct?quicklistEntry?{const?quicklist?*quicklist;quicklistNode?*node;unsigned?char?*zi;unsigned?char?*value;long?long?longval;unsigned?int?sz;int?offset;}?quicklistEntry;其中：
quicklist指向当前元素所在的quicklist;
node指向当前元素所在的quicklistNode结构；
zi指向当前元素所在的ziplist;
value指向该节点的字符串内容；
longval为该节点的整型值；
sz代表该节点的大小，与value配合使用；
offset表明该节点相对于整个ziplist的偏移量，即该节点是ziplist第多少个entry
4. quicklistIter结构quicklist中用于遍历的迭代器：
typedef?struct?quicklistIter?{const?quicklist?*quicklist;quicklistNode?*current;unsigned?char?*zi;long?offset;?/*?offset?in?current?ziplist?*/int?direction;}?quicklistIter;quicklist指向当前元素所处的quicklist;
current指向元素所在quicklistNode;
zi指向元素所在的ziplist;
offset表明节点在所在的ziplist中的偏移量；
direction表明迭代器的方向。
数据压缩quicklist每个节点的实际数据存储结构为ziplist，这种结构的主要优势在于节省存储空间。
为了进一步降低ziplist所占用的空间，Redis允许对ziplist进一步压缩，Redis采用的压缩算法是LZF，压缩过后的数据可以分成多个片段，每个片段有2部分：
一部分是解释字段，另一部分是存放具体的数据字段。
解释字段可以占用1～3个字节，数据字段可能不存在。
解释字段|数据|......|解释字段|数据LZF压缩的数据格式有3种，即解释字段有3种：
000LLLLL：字面型，解释字段占用1个字节，数据字段长度由解释字段后5位决定；L是数据长度字段，数据长度是长度字段组成的字面值加1。例如：0000 0001代表数据长度为2
LLLooooo oooooooo：简短重复型，解释字段占用2个字节，没有数据字段，数据内容与前面数据内容重复，重复长度小于8；L是长度字段，数据长度为长度字段的字面值加2, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：0010 0000 0000 0100代表与前面5字节处内容重复，重复3字节。
111ooooo LLLLLLLL oooooooo：批量重复型，解释字段占3个字节，没有数据字段，数据内容与前面内容重复；L是长度字段，数据长度为长度字段的字面值加9, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：1110 0000 0000 0010 0001 0000代表与前面17字节处内容重复，重复11个字节。
quicklistLZF结构：
/*?quicklistLZF?is?a?4+N?byte?struct?holding?'sz'?followed?by?'compressed'.?*?'sz'?is?byte?length?of?'compressed'?field.?*?'compressed'?is?LZF?data?with?total?(compressed)?length?'sz'?*?NOTE:?uncompressed?length?is?stored?in?quicklistNode->sz.?*?When?quicklistNode->zl?is?compressed,?node->zl?points?to?a?quicklistLZF?*/typedef?struct?quicklistLZF?{unsigned?int?sz;?/*?LZF?size?in?bytes*/char?compressed[];}?quicklistLZF;zs 该压缩node的的总长度
compressed压缩后的数据片段(多个)，每个数据片段由解释字段和数据字段组成
当前ziplist未压缩长度存在于quicklistNode->sz字段中
当ziplist被压缩时，node->zl字段将指向quicklistLZF
1. 压缩LZF数据压缩的基本思想是：数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据内容。
压缩算法的流程如下：遍历输入字符串，对当前字符及其后面2个字符进行散列运算，如果在Hash表中找到曾经出现的记录，则计算重复字节的长度以及位置，反之直接输出数据。
/*?*?compressed?format?*?*?000LLLLL?<L+1>;?literal,?L+1=1..33?octets?*?LLLooooo?oooooooo?;?backref?L+1=1..7?octets,?o+1=1..4096?offset?*?111ooooo?LLLLLLLL?oooooooo?;?backref?L+8?octets,?o+1=1..4096?offset?*/unsigned?intlzf_compress?(const?void?*const?in_data,?unsigned?int?in_len,?void?*out_data,?unsigned?int?out_len)2. 解压缩根据LZF压缩后的数据格式，可以较为容易地实现LZF的解压缩。需要注意的是，可能存在重复数据与当前位置重叠的情况，例如在当前位置前的15个字节处，重复了20个字节，此时需要按位逐个复制。
unsigned?intlzf_decompress?(const?void?*const?in_data,?unsigned?int?in_len,?void?*out_data,?unsigned?int?out_len)基本操作1. 插入元素API定义：
/*?Insert?a?new?entry?before?or?after?existing?entry?'entry'.?*?*?If?after==1,?the?new?value?is?inserted?after?'entry',?otherwise?*?the?new?value?is?inserted?before?'entry'.?*/REDIS_STATIC?void?_quicklistInsert(quicklist?*quicklist,?quicklistEntry?*entry,?void?*value,?const?size_t?sz,?int?after)其中，参数after用于控制在entry之前或者之后插入。
正因为 quicklist 采用了链表结构，所以当插入一个新的元素时，quicklist 首先就会检查插入位置的 ziplist 是否能容纳该元素，这是通过 _quicklistNodeAllowInsert 函数来完成判断的。
REDIS_STATIC?int?_quicklistNodeAllowInsert(const?quicklistNode?*node,?const?int?fill,?const?size_t?sz)?{if?(unlikely(!node))return?0;int?ziplist_overhead;/*?size?of?previous?offset?*/if?(sz?<?254)ziplist_overhead?=?1;elseziplist_overhead?=?5;/*?size?of?forward?offset?*/if?(sz?<?64)ziplist_overhead?+=?1;else?if?(likely(sz?<?16384))ziplist_overhead?+=?2;elseziplist_overhead?+=?5;/*?new_sz?overestimates?if?'sz'?encodes?to?an?integer?type?*/unsigned?int?new_sz?=?node->sz?+?sz?+?ziplist_overhead;if?(likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz,?fill)))return?1;else?if?(!sizeMeetsSafetyLimit(new_sz))return?0;else?if?((int)node->count?<?fill)return?1;elsereturn?0;}_quicklistNodeAllowInsert 函数会计算新插入元素后的大小（new_sz），这个大小等于 quicklistNode 的当前大小（node->sz）、插入元素的大小（sz），以及插入元素后 ziplist 的 prevlen 占用大小。
在计算完大小之后，_quicklistNodeAllowInsert 函数会依次判断新插入的数据大小（sz）是否满足要求，即单个 ziplist 是否不超过 8KB，或是单个 ziplist 里的元素个数是否满足要求。
只要这里面的一个条件能满足，quicklist 就可以在当前的 quicklistNode 中插入新元素，否则 quicklist 就会新建一个 quicklistNode，以此来保存新插入的元素。
这样一来，quicklist 通过控制每个 quicklistNode 中，ziplist 的大小或是元素个数，就有效减少了在 ziplist 中新增或修改元素后，发生连锁更新的情况，从而提供了更好的访问性能。
2. 删除元素quicklist对于元素删除提供了删除单一元素以及删除区间元素2种方案。
1）对于删除单一元素，可以使用quicklist对外的接口quicklistDelEntry实现，也可以通过quicklistPop将头部或者尾部元素弹出。
quicklistDelEntry函数调用底层quicklistDelIndex函数，该函数可以删除quicklistNode指向的ziplist中的某个元素，其中p指向ziplist中某个entry的起始位置。
quicklistPop可以弹出头部或者尾部元素，具体实现是通过ziplist的接口获取元素值，再通过上述的quicklistDelIndex将数据删除
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;02）对于删除区间元素，quicklist提供了quicklistDelRange接口，该函数可以从指定位置删除指定数量的元素
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;1start为需要删除的元素的起始位置，count为需要删除的元素个数。返回0代表没有删除任何元素，返回1并不代表删除了count个元素，因为count可能大于quicklist所有元素个数，故而只能代表操作成功。
总体删除逻辑为：不管什么方式删除，最终都会通过ziplist来执行元素删除操作。先尝试删除该链表节点所指向的ziplist中的元素，如果ziplist中的元素已经为空了，就将该链表节点也删除掉。
3. 更改元素quicklist更改元素是基于index，主要的处理函数为quicklistReplaceAtIndex。
其基本思路是先删除原有元素，之后插入新的元素。quicklist不适合直接改变原有元素，主要由于其内部是ziplist结构，ziplist在内存中是连续存储的，当改变其中一个元素时，可能会影响后续元素。故而，quicklist采用先删除后插入的方案。
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;24. 查找元素quicklist查找元素主要是针对index，即通过元素在链表中的下标查找对应元素。基本思路是，首先找到index对应的数据所在的quicklistNode节点，之后调用ziplist的接口函数ziplistGet得到index对应的数据，源码中的处理函数为quicklistIndex。
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;3关于“redis数据结构使用”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
本文来自作者[迎萱]投稿，不代表同舟号立场，如若转载，请注明出处：https://www.sdtzcl.com/tz/2814.html
评论列表（4条）
我是同舟号的签约作者“迎萱”！
希望本篇文章《redis数据结构使用》能对你有所帮助！
本站[同舟号]内容主要涵盖：生活百科,小常识,生活小窍门,知识分享
本文概览：网上有关“redis数据结构使用”话题很是火热，小编也是针对redis数据结构使用寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。前言续...