文档章节

redis 数据结构

H
 Haloooooo
发布于 2017/04/04 13:09
字数 1463
阅读 10
收藏 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
青岛
程序员

暂无文章

Python基础案例教程

一、超市买薯片 # 用户输入薯片的单价danjia = float(input("薯片的单价"))# 用户输入购买袋数daishu = int(input("购买的袋数"))# 计算总价zongjia = danjia * daishu# 输出结果...

linuxprobe16
46分钟前
0
0
采用CXF框架发布webservice

package cn.it.ws.cxf.a;import javax.jws.WebParam;import javax.jws.WebResult;import javax.jws.WebService;@WebService(serviceName="languageManager")public interface ......

江戸川
48分钟前
0
0
HashMap工作原理及实现

HashMap工作原理及实现 1. 概述 什么时候会使用HashMap?他有什么特点? 知道HashMap的工作原理吗? 知道get和put的原理吗? 知道hash的实现吗?为什么要这样实现? 如果HashMap的大小超过了...

傅小水water
56分钟前
1
0
swagger如何屏蔽某些接口,不对外公开--使用@ApiIgnore

@ApiIgnore@RestController@RequestMapping(value = "/i18nTest")public class I18nTestController {// @Resource// private LocaleMessageSourceService localeMessageSourceSe......

karma123
59分钟前
1
0
大数据技术学习,大数据处理为何选择Spark,而不是Hadoop

大数据处理为何选择Spark,而不是Hadoop。 一.基础知识 1.Spark Spark是一个用来实现快速而通用的集群计算的平台。 在速度方面,Spark扩展了广泛使用的MapReduce计算模型,而且高效地支持更多...

董黎明
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部