Redis - zset底层数据结构实现

前言

zset为有序的，自动去重的集合数据类型，zset数据结构底层实现为字典(dict) + 跳表(skiplist)，当数据比较少时，用ziplist编码结构存储，element和score各占一个entry.
ele1 - score1 - ele2 - score2 ...
redis.conf有以下两个参数控制

# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
zset-max-ziplist-entries 128  
zset-max-ziplist-value 64   

zset-max-ziplist-entries 128 // 元素个数超过128，将用skiplist编码
zset-max-ziplist-value 64 // 单个元素大小超过64byte，将用skiplist编码

实验

127.0.0.1:6379> zadd a-zset 100 a 200 b 150 c
(integer) 3
127.0.0.1:6379> zrange a-zset 0 -1 withscores
1) "a"
2) "100"
3) "c"
4) "150"
5) "b"
6) "200"
127.0.0.1:6379> object encoding a-zset
"ziplist"

加入的元素个数较少，且key的长度小于64byte时，使用ziplist有序存储元素。

127.0.0.1:6379> zadd a-zset 100 aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffggggg 200 b 150 c
(integer) 3
127.0.0.1:6379> object encoding a-zset
"skiplist"

往zset添加一个长度为65byte的key，此时底层选用skiplist存储元素。

zet数据结构

typedef struct zset{
    dict *dict;
    zskiplist *zsl;
}zset

typedef struct zskiplist{
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zskiplistNode{
    sds ele;      // 元素key
    double score;    // 元素分值
    struct zskiplistNode * backward;
    struct zskiplistLevel{
          struct zskiplistNode *forward;    // 指向前一个节点
          unsigned long span;    // 记录当前层元素之间的跨度，可以快速查询到排名
  } level[]  // 层高，表示该节点在每一层的情况
}zskiplistNode;

利用dict可以以O(1)时间复杂度判断某个key'是否存在，以及取出key的分值。
skiplist是一个有多个索引层，一个数据层的数据结构，索引层和数据层都是有序的双向列表。
每个索引层的元素，都有两个指针字段，分别指向当前索引层下一个元素，以及下一索引层的本元素。
索引层1： 23 ----------- 52 ----------- 65 --------------- 76 ---------- null
索引层2: 23 ----43---- 52 ----59---- 65 -----70------- 76 ----84---- null
数据层： 23 -32-43-47- 52 -55-59-61- 65 --67-70-74- 76 -79-84--86-null

N: 节点数量
index: 1 --- N/2^1
index: 2 --- N/2^2
index: 3 --- N/2^3
index: k --- N/2^k
顶层只有两个元素： 2^k = N / 2 --- > k = log2(N-1)
时间复杂度：每一个索引层最多查找两次，层数为 log2(N-1) ---> 2 * log2(N-1) = log(N)，与二分查找时间复杂度一样。