Linvis Blog

Redis基本数据结构-3

2020-06-07

intset

数据结构

1
2
3
4
5
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

encoding的编码，来决定一个整数占几位

image-20200603222329184

长度分别对应8,4,2

如果插入的数据长度大于当前的编码，会导致扩容

查询

intset是有序的，所以查找用的二分查找

如果已存在，直接返回

插入

按顺序插入，其实也是二分插入

删除

没啥好说的，当成有序列表的元素删除就行

quicklist

List的一种实现，由List和ziplist组成

List的另一种实现，当元素较少的时候，直接用ziplist，这种情况，其实也可以当成只有一个节点的quicklist

简述

通过双向链表，把多个ziplist连接起来

ziplist提高空间利用

数据结构

1
2
3
4
5
6
7
8
9
10
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 : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

  • head/tail 首尾节点

  • count，quicklist Node的个数

  • fill

    正数表示ziplist的最大数据项数

    负数

    image-20200603223619828

image-20200603223431460

1
2
3
4
5
6
7
8
9
10
11
12
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;

  • zl

    ziplist地址

  • prev/next

    前后节点

  • encoding

    ziplist还可以进一步被压缩，这个表示ziplist是否被压缩了

LZF压缩的基本思想

数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据内容

这有点像什么呢，HTTP2里的Hpack头部压缩，把重复的内容记成一个字典，然后存储字典中关键字的索引，以减少原始数据的长度

创建

没啥好说的

1
2
3
4
5
6
7
8
9
10
11
12
quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;

    quicklist = zmalloc(sizeof(*quicklist));
    quicklist->head = quicklist->tail = NULL;
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    quicklist->fill = -2;
    quicklist->bookmark_count = 0;
    return quicklist;
}

添加元素

运行从头部插入和尾部插入quicklistPushHead和quicklistPushTail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

任意位置插入

  • 需要向当前quicklistNode的第一个元素(entry)前面插入元素，则插入前一个quicklistNode中，前一个不存在就创建一个
  • 需要向当前quicklistNode的最后一个元素(entry)后面插入元素，则插入下一个quicklistNode，不存在就创建
  • 不满时上述两种情况，将当前所在的quicklistNode以当前待插入位置作为基准，拆分成左右两个quicklistNode，之后将需要插入的数据插入到其中一个拆分出来的quicklistNode中

查找/删除

先查Node节点，然后从ziplist中查找/删除

Tags: redis源码阅读 数据库
← Redis基本数据结构-2 Go语言sync.Pool源码分析 →

扫描二维码，分享此文章