redis 数据结构
redis 数据结构
Haloooooo 发表于11个月前
redis 数据结构
  • 发表于 11个月前
  • 阅读 7
  • 收藏 2
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

 

redis对象 redis 数据结构
字符串对象  SDS(简单动态字符串)
列表对象  压缩列表(ziplist) 或 链表(linkedlist)
哈希对象  压缩列表 或 字典
集合对象  整数集合 或 字典
有序集合对象  压缩列表 或 跳跃表和字典

 

类型 编码 对象
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象。
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象。
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象。
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双端链表实现的列表对象。
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象。
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象。
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象。
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象。
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象。
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳跃表和字典实现的有序集合对象。

 

REDIS_STRING

编码raw结构

sds字符串 

 

struct sdshdr{

      //记录 buf 数组中已使用字节的数量

int len; 

//纪录buf未使用字节的数量

int free

//存放字符串

char buf[];

};

作用 : 作为redis 的部分键 和 值

REDIS_LIST 

 

列表实现通过 链表和压缩列表

linkedlist 

 

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;
typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所包含的节点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

} list;

作用 :链表为列表键 链表节点为值  实现redis 发布与订阅, 慢查询, 监视器, 等等。

 

REDIS_HASH

哈希键的实现 字典 /压缩列表

字典的实现

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表 rehash 时使用ht[1]
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时,值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

 

哈希表的实现

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码,用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

哈希表的节点

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;

} dictEntry;

通过链表解决冲突问题

负载因子为0.5 时扩张 小于0.1收缩

 

REDIS_SET  

通过整数集合和字典实现

 

整数集合结构 只有小整数 才会在这里 其余都是在字典中实现

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

REDIS_ZSET

 

有序集合通过跳跃表和字典实现或压缩列表

有序集合的跳跃表和字典实现

跳跃表的实现

 

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

跳跃表的节点实现

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值 double 类型的浮点数, 跳跃表中的所有节点都按分值从小到大来排序
    double score;

    // 成员对象 指向sds对象 值
    robj *obj;

    // 层 层高范围1-32  第一层level[0]
    struct zskiplistLevel {

        // 前进指针 指向当前层的下一个节点
        struct zskiplistNode *forward;

        // 跨度 纪录与同层下一节点之间的距离
        unsigned int span;

    } level[];

} zskiplistNode;

 

有序集合的实现

typedef struct zset {

    zskiplist *zsl; // 跳跃表

    dict *dict;  // 字典

} zset;

zset 结构中的 dict 字典为有序集合创建了一个从成员到分值的映射, 字典中的每个键值对都保存了一个集合元素: 字典的键保存了元素的成员, 而字典的值则保存了元素的分值。 通过这个字典, 程序可以用 O(1) 复杂度查找给定成员的分值, ZSCORE 命令就是根据这一特性实现的, 而很多其他有序集合命令都在实现的内部用到了这一特性。

为什么有序集合需要同时使用跳跃表和字典来实现?

在理论上来说, 有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现, 但无论单独使用字典还是跳跃表, 在性能上对比起同时使用字典和跳跃表都会有所降低。

举个例子, 如果我们只使用字典来实现有序集合, 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留, 但是, 因为字典以无序的方式来保存集合元素, 所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时, 程序都需要对字典保存的所有元素进行排序, 完成这种排序需要至少 O(N \log N) 时间复杂度, 以及额外的 O(N) 内存空间 (因为要创建一个数组来保存排序后的元素)。

另一方面, 如果我们只使用跳跃表来实现有序集合, 那么跳跃表执行范围型操作的所有优点都会被保留, 但因为没有了字典, 所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(\log N) 。

因为以上原因, 为了让有序集合的查找和范围型操作都尽可能快地执行, Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

参考文献 《redis设计与实现》

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 20
码字总数 16080
×
Haloooooo
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: