文档章节

redis 数据结构

H
 Haloooooo
发布于 2017/04/04 13:09
字数 1463
阅读 11
收藏 2

 

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设计与实现》

 

© 著作权归作者所有

共有 人打赏支持
H
粉丝 0
博文 29
码字总数 36527
作品 0
青岛
程序员
私信 提问

暂无文章

聊聊flink的Table API及SQL Programs

序 本文主要研究一下flink的Table API及SQL Programs 实例 // for batch programs use ExecutionEnvironment instead of StreamExecutionEnvironmentStreamExecutionEnvironment env = Stre......

go4it
17分钟前
0
0
mysqldump应用

备份单个库/表数据或库/表结构 命令行下具体用法如下: mysqldump -u用戶名 -p密码 -d 数据库名 表名 > 备份文件名 1、导出数据库为dbname的表结构(其中用戶名為root,密码为dbpasswd,生成的...

阿dai
25分钟前
0
0
shell脚本与Python的交互

1、Python针对shell获取传入,输出参数 传入:"$num" 例如: $0表示文件名,$1表示shell获取的第一个参数 输出:通过打印shell结果的方式,输出参数给Python。 例如: echo "{$iplist}",Python调...

一口今心
27分钟前
0
0
Euler 今日问世!国内首个工业级的图深度学习开源框架,阿里妈妈造

阿里妹导读:千呼万唤始出来!阿里妈妈正式公布重磅开源项目——图深度学习框架Euler。这是国内首个在核心业务大规模应用后开源的图深度学习框架。此次开源,Euler内置了大量的算法供用户直接...

阿里云官方博客
34分钟前
0
0
TiDB 3.0 Beta Release Notes

2019 年 1 月 19 日,TiDB 发布 3.0 Beta 版,对应 master branch 的 TiDB-Ansible。相比 2.1 版本,该版本对系统稳定性、优化器、统计信息以及执行引擎做了很多改进。 TiDB 新特性 支持 Vi...

TiDB
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部