分享好友 站长动态首页 网站导航

讲讲Redis各个数据类型的底层数据结构

2022-05-30 09:00 · 头闻号数据库

哈喽，大家好，我是指北君。

前段时间有朋友面试京东的时候，遇到这样的面试题。

讲讲Redis的数据类型以及其对应的底层数据结构

那么今天指北君带大家了解一下Redis基本数据类型对应的底层数据结构。

1. 前言

Redis的键值对中的常见数据类型有String (字符串)、List(列表)、Hash(哈希)、Set(集合)、Zset(有序集合)。那么其对应的底层数据结构有SDS(simple dynamic string)、链表、字典、跳跃表、压缩列表、快速列表，整数集合等。

下面我们来了解一下其底层数据结构的精妙之处。

2. Redis底层数据结构

2.1 SDS

Redis自定义了一种简单动态字符串(simple dynamic string)，将其作为Redis的默认字符串表示。

其主要结构如下：

redis6.0中SDS定义如下 (越来越节约使用内存了，内存是省出来的!)

typedef char *sds;


struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; 
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; 
    uint32_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; 
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};

相对于C语言的字符串，SDS具有以下优点。

2.2 链表

链表是大家比较熟悉的数据结构了，链表提供了高效的节点重排能力，顺序访问，通过增删节点调整长度等特点。Redis List对象的底层实现之一就是链表。

每一个链表节点使用如下的结构来表示。



typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

而多了listNode可以通过prev 和 next 指针组成一个双端队列如下图：

多个节点可以组成一个链表，Redis使用了List结构来持有这些节点，操作更方便。其结构如下：

typedef struct list {
    listNode *head;  //链表头节点指针
    listNode *tail;  //链表尾节点指针
    void *(*dup)(void *ptr); // 用于复制链表节点所保存的值
    void (*free)(void *ptr); // 用于释放链表节点所保存的值
    int (*match)(void *ptr, void *key); //用于对比链表节点所保存的值和另一个输入值是否相等
    unsigned long len; // 链表所包含的节点数量
} list;

简单结构如下图：

Redis链表具有如下特性：

2.3 字典

字典是一种用于保存键值对的抽象数据结构。

在字典中，一个键(key)可以和一个值(value)进行关联，称之为键值对。字典中每个键都是独一无二的，并且程序都是通过key来操作更新value或者删除数据等。

Redis的字典使用哈希表作为底层实现的， 一个哈希表可以包含多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

下面再讲一下哈希表，哈希表节点，以及字典的实现。

哈希表及哈希表节点结构，字典结构 如下：

//字典结构
typedef struct dict {
    dictType *type; // 类型特定的函数
    void *privdata;  //私有数据
    dictht ht[2]; //长度为2的哈希表数组， 一般情况下字典仅使用 ht[0]哈希表， ht[1]在rehash的时候会使用到。
    long rehashidx; 
    unsigned long iterators; 
} dict;

//哈希表结构
typedef struct dictht {
    dictEntry **table; //哈希数组
    unsigned long size; //哈希表大小
    unsigned long sizemask; //哈希表掩码，用于计算索引值， 总是等于size-1
    unsigned long used; //表示已有节点数量
} dictht;

//哈希节点
typedef struct dictEntry {
    void *key; //键
    union { //value值，包含了多种类型的值，不同类型的值可以使用不同的数据结构存储，节省内存。
        void *val;  //其值可以是一个指针
        uint64_t u64; //其值也可以是一个uint64_t 整数
        int64_t s64; //其值可以是一个int64_t 整数
        double d; //其值可以是一个double 
    } v;
    struct dictEntry *next; //指向像一个哈希节点
} dictEntry;

普通状态下的字典结构示意图：

添加新建的机制是大家比较熟悉的思路啦。

使用字典设置的哈希函数计算key的哈希值，

哈希表保存的键值逐渐增多或者减少地过程中，程序会对哈希表进行扩展或者收缩，这个过程称之为rehash。

rehash过程中会使用上面的ht[0] ht[1]，具体过程这里就不详细说了，会另外专门写一篇来介绍。

2.4 跳跃表

跳跃表(skiplist )是一种有序数据结构，它在每个节点中维护多个指向其他节点的指针，从而可以快速访问。其支持平均O(logN) 复杂度的节点查找。

Zset使用了跳跃表和字典作为其底层实现。其好处就是可以进行高效的范围查询，也可以进行高效的单点查询。

在源码中其结构如下：

typedef struct zskiplistNode { //跳跃表节点 sds ele; //

typedef struct zskiplistNode { //跳跃表节点
    sds ele; //成员对象，各个节点中成员对象唯一的。
    double score; //分值
    struct zskiplistNode *backward; //后退指针
    struct zskiplistLevel { //层， 最大32层
        struct zskiplistNode *forward; //前进指针
        unsigned long span; //跨度
    } level[];
} zskiplistNode;

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

typedef struct zset { // zset的数据结构使用了 字典dict 和 zskiplist
    dict *dict;
    zskiplist *zsl;
} zset;

关于跳跃表节点的各参数解释如下：

下面我们画一个跳跃表的示意图：

图中如果要访问节点3，则只需要通过头节点第四层的前进指针，就可以找到此节点。

如果需要增加元素的时候，会先使用高层前进指针去遍历，并对比score值，然后逐步缩小插入元素的位置范围，然后确定最终的位置。这样其平均时间复杂度为O(logN). 相比于链表的O(N)的时间复杂度来说，其效率大大提高。只不过其代价就是需要多一点的内存空间。

个人感觉和MySql的索引有点类似。

2.5压缩列表 ziplist

压缩列表是 Redis中list和 hash 对象的底层实现之一。压缩列表是为了节约内存而开发的，是由一系列连续编码的内存块组成。其结构示意如下：

其中各节点说明如下：

其中每一个压缩列表节点entry由如下部分组成：

由于previous_entry_length 记录了前一个节点的长度，而且其可能为1个字节或者5个字节，如果前一个节点的长度从254之下增加到254之上，那么previous_entry_length 的值就要使用5个字节类表示。而如果后面的节点均存在同样的情况，那么压缩列表就会出现连锁更新，导致内存空间重新分配，从而导致压缩列表增加节点或者删除节点的最坏时间复杂度位O(N2).

新版本的redis中，引入了listpack。其目的是替换ziplist，整体结构类似。

其entry结构如下：

len保存了当前节点encoding及data的长度综合，从而可以避免连锁更新

2.6快速列表

快速列表(quicklist)可以看成是双向链表和压缩列表的一种组合。Redis3.2之后 list对象使用快速列表作为其底层实现。

快速列表使用了quickListNode节点组成双向链表，然后在每个快速列表节点内部使用压缩列表存储数据，从而可以控制压缩列表的长度，避免连锁更新带来的性能影响。

其中快速列表的源码结构如下：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        
    unsigned long len;          
    int fill : QL_FILL_BITS;              
    unsigned int compress : QL_COMP_BITS; 
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             
    unsigned int count : 16;     
    unsigned int encoding : 2;   
    unsigned int container : 2;  
    unsigned int recompress : 1; 
    unsigned int attempted_compress : 1; 
    unsigned int extra : 10; 
} quicklistNode;

quickList 中维护了一个quicklistBookmark数组，并且有执行qulickListNode 头尾的指针。

每一个quicklistBookmark 中有一个quickListNode的指针，同时每一个quickListNode又有指向前一个后一个node的指针。

其结构示意图如下：

2.7 整数集合

整数集合(intset) 是集合键底层实现之一，当一个集合只包含整数元素的时候，Redis会使用整数集合作为集合键的实现。

整数集合的源码如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

整数集合底层是一个数组，如果每一个元素都在16位以内的整数类型(-32768 到 32767)，则数组的每个元素都为int16_t ， 如果新加的整数超过这个范围，并且在32位以内的话， 整个数组中的每一个元素都会升级成int32_t 表示的整数， 如果新加入的是64 位才能表示的整数的话，所以的元素又会再一次升级。

但是整数集合不支持降级，及 整数集合中如果有一个64位的整数，即使移除此元素，整个集合也不会降级。

这样做具有一定的灵活性，而且可以节省内存。当需要升级的时候才进行升级。

总结通过以上 Redis 底层数据结构可以看出，其设计核心总是在节约内内存，提高访问速度。所以Redis快，这小巧妙的底层设计也是功不可没。同时我们也可以根据着些设计思想去优化我们自己的代码，优秀的设计总是值得去学习的。

免责声明：本平台仅供信息发布交流之途，请谨慎判断信息真伪。如遇虚假诈骗信息，请立即举报

举报
反对 0
打赏 0
更多相关文章

评论

0

收藏

点赞