Redis基础01-redis的数据结构

       Redis虽然底层是用C语言写的，但是底层的数据结构并不是直接使用C语言的数据结构，而是自己单独封装的数据结构；

       Redis的底层数据结构由，简单动态字符串，链表，字典，跳跃表，整数集合等几种数据结构组成；

1.简单动态字符串

1.定义：

简单动态字符串：SDS（simple dynamic string）redis 自己构建的；数据结构如下：

struct sds{ 
    int free;//未使用长度 
    int len;//字符长度
    char buff[];//字符数组
}

结尾的一个字节不算在len的长度里面；

2.SDS和C字符串的差别（了解就好）

　　 相同点：都是n+1的长度，都是以\0结尾；

   不同点：1.获取字符串长度复杂度不同；

　　　　　　 2.杜绝缓存区溢出

         3.减少字符修改造成的内存再分配次数； 　　3.1空间预分配；3.2惰性空间释放；

         4.二进制安全；

         5.兼容部分C字符串；

2.链表

1.链表和节点的实现

struct listNode{
    struct listNode *prev;
    struct listNode *next;
    void *value;
}
typeof struct list{
    listNode *head;//第一个
    listNode *tail;//最后一个节点
    unsigned int len;//长度
    void *(*dup)(void *ptr);//复制节点函数
    void (*free)(void *ptr)；//节点值释放函数
    int (*match)(void *ptr,void *key)//节点比对函数
 
}list;

特点：双端（链表带有pre和next两个指针）；

　　　无环（表头的pre和表尾的next都是NULL）；

　　   带表头指针和表尾指针；

　　   求链表长度计数器（len是链表节点的计数器），

　　　多态（dup,free,match三个属性设置特定类型，可以保存不同类型的值）

3.字典

1.定义及实现

字典：又称符号表，关联数组或映射，是一种用于保存键值对的抽象数据结构；
在字典中，一个字和一个值进行关联，这些键和值就称为键值对；

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

• 哈希表

typedef struct dictht{
    dictEntry **table;//哈希表数组
    unsigined long size;//哈希表数组大小
    unsigined long sizemask;//哈希表大小掩码，值总是size-1
    unsigined long used;//哈希表数组已有节点的数量
}

哈希表节点

typeof struct dictEntry{
    void *key;//键
    union{//值
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    struct dictEntry *next;//指向另一个哈希表节点的指针，可以将多个哈希值相同的键值对连接在一次
}

 字典

typedef struct dist{
    dictype *type;//类型特定函数
    void  *privdata;//私有数据
    dictht ht[2];//哈希表
    in trehashidx;//rehash索引//当rehash不在进行时，值为-1
}dict;

typedef struc dictType{
    unsigned int (*hashFunction)(const void *key);//计算哈希值的函数
    void *(*keyDup)(void *privdata,const void *key);//复制键的函数
    void *(*valDup)(void *privdata,const void *obj);
    int (*keyCompare)(void *privdata,const void *key1,const void *key2);
    void (*keyDestructor)(void *privdata,void *key);
    void (*valDestructor)(void *privdata,void * obj);
} dictType ;

2.哈希算法

MurmurHash算法来计算键的哈希值。

3.解决键冲突

使用链地址法来解决键冲突；

4.rehash

哈希表的扩展与收缩

5.渐进式rehash

4.跳跃表

跳跃表 是一种有序数据结构，它可以在每个节点中维持多个只指向其他节点的指针，从而达到快速访问节点的目的。

使用的场景：在redis中，一个是实现有序集合键；一个是集群节点中用作内部数据结构；

1.跳跃表节点

层
前进指针
跨度
后退指针
分值和成员

5.整数集合

当一个集合质保和整数值元素，并且这个集合的元素数量不多时；

1.整数集合的实现

整数集合是Redis用于保存整数值的集合抽象数据结构；
typedef struct intset{
    uint32_t encoding;//决定contents里面保存的数据类型
    uint32_t length;//整数集合包含的元素数量
    int8_t contents[];
}inset;

2.升级

3.降级

6.压缩列表

是一种节约内存而开发的顺序型数据结构

1.压缩列表的构成

2.压缩列表节点的构成

• previous_entry_length

• encoding

• content

3.连锁更新

每个previous_entry_length属性都记录前一个界定啊的长度：
如果节点小于254，则需要用1字节长的空间保存这个长度值；如果大于或等于254字节，则用5字节长的空间保存这个长度值

7.对象

Redis基于上面的数据结构创建了五种不同类型的对象系统：
            字符串对象，列表对象，哈希对象，集合对象和有序集合对象；
            
Redis的对象系统实现了基于引用计数技术的内存回收机制；
Redis对象带有访问时间记录信息。

 typedef redisObject{
    unsigned type:4；//类型
    unsigned encoding:4;//编码
    void *ptr;//只想底层实现数据结构的指针
} robj;

• 对象的类型与编码

• 编码和底层实现

每种类型的对象都至少使用了两种不哦那个的编码；

1.字符串对象

字符串对象的编码可以是int,row,或embstr

2.列表对象(REDIS_LIST)

列表对象可以是ziplist或linkedlist

linkedList使用的是双端链表作为底层实现，每个双端链表的节点都保存一个对象；

字符串对象是五种redis对象中被其他对象嵌套的对象

• 编码转换

当满足单个字符长度小于64，元素数量小于512的时候，使用ziplist,不能就使用linkedlist

3.哈希对象

哈希对象的编码可以是ziplist或者hashtable;

hasttable底层是通过字典实现的

• 编码转换

键和值的长度小于64，且数量都小于512的时候，使用ziplist

4.集合对象

集合对象的编码可以是inset或hasetable;

• 编码转换

1.当都是int类型；2.当总长度不超过512；使用intset否则hashtable

5.有序集合对象

有序集合可以是ziplist或者skiplist

7.类型检查和命令多态

Redis中操作间的命令分为两种。

其中一种命令可以对任何类型的键执行，比如DEL命令，EXPIRE命令，RENAME命令，TYPE命令，OBJECT命令等；

另一种是只能对特定类型键执行；

• 类型检查的实现

在执行指令的时候，服务器会先判断RedisObject的类型是否有相关的指令，没有的话，不能执行

• 多态命令的实现

一个命令可以同时用于处理多种不同类型的键；

8.内存回收

通过引用计数技术实现内存回收机制；
typedef struct redisObject{
    
    //.....
    int refcount;//引用计数
    //.....
    
}

对象引用计数信息会随着对象的使用状态而不断变化；
创建一个对象的时候，值会被初始化为1；
被新程序使用时，引用计数会增1；
不再被程序使用会减1；
当对象引用计数值为0，对象锁占用的内存会被释放；

9.对象共享

10.对象的空转时长

typedef struct redisObject{
    // ...
    
    unsigned lru : 22 ;
    // ...
    
}robj;

空转时长就是通过将当前时间及拿去键的值对象的lru时间计算得出的

Object IDLETIME 命令可以打印出给定键的空转时长；
这个命令在放键的值对象时，不会修改值对象的lru属性；

volatile-lru 或者 allkeys-lru

Redis基础01-redis的数据结构

原文：https://www.cnblogs.com/perferect/p/12671860.html