ccran 的个人博客 ccran 的个人博客

记录精彩的程序人生

目录
Redis设计与实现(3)跳表、整数集合
/  

Redis设计与实现(3)跳表、整数集合

Redis设计与实现(3)跳表、整数集合

1. 跳表

sorted set命令基本使用:

127.0.0.1:6379> zadd class:123 100 xiaoming 99 xiaobai 100 xiaohui
(integer) 3
127.0.0.1:6379> zrange class:123 0 -1 withscores
1) "xiaobai"
2) "99"
3) "xiaohui"
4) "100"
5) "xiaoming"
6) "100"

Redis使用跳表作为sorted set值的实现,以及在集群节点中用作内部数据结构。

skiplist.png

跳表节点zskiplistNode:

typedef struct zskiplistNode {
    struct zskiplistNode *backward;// 后退指针
    double score;// 分值
    robj *obj; // 成员对象
    struct zskiplistLevel {// 层
        struct zskiplistNode *forward;// 前进指针
        unsigned int span;// 跨度
    } level[];
} zskiplistNode;

跳表zskiplist:

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表头节点和表尾节点
    unsigned long length;// 表中节点的数量
    int level;// 表中层数最大的节点的层数
} zskiplist;

1、每层存在前进指针与跨度,层级越高,跨度越大,筛选数据越多。

2、跳表节点根据分值从小到大排序,通过跨度的累加可以计算一个节点的排位。

3、从头结点的层级0开始,依赖前进指针可以正向遍历所有节点;从尾结点通过后退指针可以反向遍历所有节点

4、CRUD可以达到log(N)的时间复杂度,相当于层每次筛选了一半的数据。

2. 整数集合

set基本命令使用:

127.0.0.1:6379> sadd numbers 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding numbers
"intset"
127.0.0.1:6379> sadd names ccran 1 2 2 ccran
(integer) 3
127.0.0.1:6379> object encoding names
"hashtable"

Redis对于集合中都是整数值并且数量不多时,使用整数集合(intset)作为set的底层实现。

intset.png

整数集合intset:

typedef struct intset {
    uint32_t encoding;// 编码方式
    uint32_t length; // 集合包含的元素数量
    int8_t contents[];// 保存元素的数组
} intset;

1、contents存储整数结合,并且从小到大排序,且不包含重复项。

2、length记录了contents的长度

3、contents数组中每个元素的类型依赖于编码方式encoding。

encoding可选INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64

contents类型对应int16_t、int32_t、int64_t

能存储的数据大小对应2Byte、4Byte、6Byte所能容纳的大小

4、当大于当前encoding数据范围所能容纳的数需要添加到集合中时,需要进行升级(upgrade)操作。

1)根据新元素的类型, 扩展整数集合底层数组的空间大小, 并为新元素分配空间。

2)将底层数组现有的所有元素都转换成与新元素相同的类型, 并将类型转换后的元素放置到正确的位上, 而且在放置元素的过程中, 需要继续维持底层数组的有序性质不变。(有点类似于一轮插入排序)

好处:1)适配多种数据类型,更灵活 2)节省内存

5、不支持降级

6、时间复杂度分析

查找:O(logN)有序二分

插入与删除:O(N) 涉及元素的移动


标题:Redis设计与实现(3)跳表、整数集合
作者:ccran
地址:https://ccran.online/articles/2020/07/25/1595682553898.html