0%

redis数据结构之quiclist

背景介绍

Redis中list数据结构,也就是队列,使用quicklist作为底层存储结构,quicklist本质上是一个双向链表

数据结构

quicklist本身的结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
* 'count' is the number of total entries.
* 'len' is the number of quicklist nodes.
* 'compress' is: -1 if compression disabled, otherwise it's the number
* of quicklistNodes to leave uncompressed at ends of quicklist.
* 'fill' is the user-requested (or default) fill factor. */
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;

可以看到有head和tail,方便从首尾两个方向做push和pop操作,quicklistNode结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
* We use bit fields keep the quicklistNode at 32 bytes.
* count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
* encoding: 2 bits, RAW=1, LZF=2.
* container: 2 bits, NONE=1, ZIPLIST=2.
* recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
* attempted_compress: 1 bit, boolean, used for verifying during testing.
* extra: 12 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;
unsigned int sz; /* ziplist size in bytes */
unsigned int count : 16; /* count of items in ziplist */
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;

其中prev和next分别指向之前和之后的Node,而zl表示存储数据的ziplist,关于ziplist前面已经介绍过了,这里要注意的是一个ziplist是存储了多个元素的,在插入数据的时候会根据情况选择增加一个新的Node还是将数据插入到当前已经存在的Node的zl中,这样应该也是一种节约内存的方式

总结

双向链表学过数据结构的都会知道,这里做的优化是使用ziplist,在一个Node里面存储多条数据以节省内存,具体的规则优点复杂这里不介绍了

Reference

  1. quicklist
如果您觉得这些内容对您有帮助,你可以赞助我以提高站点的文章质量