redis数据类型底层结构的归纳与总结

redis有5大基本的数据类型和3个拓展类型。和他们的底层数据结构。

redis 5大基本数据类型：

• string
• hash
• list
• sort set
• set

redis 3个拓展类型：

• GEO
• HyperLogLog
• BitMap

redis 6大底层数据结构

• 简单的动态字符串
• 双选链表
• 压缩列表
• 跳表
• 哈希表
• 整数数组

除了string外使用简单的动态字符串外，其他的四个类型都由两个数据结构实现。

我们来看下他们的映射关系：

• string->简单的动态字符串
• list->双向链表、压缩列表
• hash->压缩列表、哈希表
• sort set-> 压缩列表、跳表
• set->哈希表和整数数组

string数据结构（简单的动态字符串：sds）

直接看下sds的数据结构：

struct sdshdr {
    //元素长度
    int len;
    //未使用长度
    int free;
    //保存元素
    char buf[];
}

list数据结构

压缩列表存储满足条件 list保存的字符串对象元素长度小于64字节 list保存的对象元素数量小于512个 其他双向链表

Hash数据结构

压缩列表存储满足条件 hash保持对象的键和值的长度小于64字节 hash保存对象的键值对数量小于512个 其他的哈希表存储

sort set数据结构

压缩列表存储满足条件 sort set 保存对象的元素长度小于64字节 sort set 保存底下的元素个数小于128个 其他的跳表存储

这里有两个疑问：

1. 压缩列表如何存储key/value 也就是sore 和 member的映射关系？
2. 跳表是如何存储key/value，索引是如何组织的

压缩列表是第一位置存储key，下一个位置存储value，依次类推。所以这里的个数会发现默认值配置 了128个而不是512（虽然这些配置是可以在redis.conf中进行修改）。

跳表存储：跳表（skiplist：构建索引） + 哈希表（dict：存储key/value）组合模式。每一个entry元素以sore值构建组织跳表索引，dict构建 key/value的存储。

set数据结构

整数数组（intset）的存储满足的条件： set存储对象的元素为int的类型 set存储对象的元素元素个数小于512 其他的用哈希表保存

这里有个疑问： 我们set元素并不是key/value形式，用哈希表怎么存？ set中哈希表存储方式：key为set的值，value为null。 关于intset： intset这里值得注意的是intset存储是有序的，内部通过二分法实现元素的查找

typedef struct intset {
    //编码方式
    uint32_t encoding;

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

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

} intset;

总结：知道的redis各个数据类型应用的数据结构，我们就知道很多操作的时间复杂度。这个对redis一些优化理解有很多的帮助。比如zsort使用的是跳表，跳表的查询和修改的时间复杂度O(logN)那么对应zsort读写炒作时间复杂度也就是O(logN)。还有这里有很多颠覆认知的东西，比如sort set和set从字面上看好像类型，但是从数据结构上看两个是天差地别就和java和javascript一样毫无关系，还有set使用哈希表作为数据结构也是我们难以想象的，至少在不知道这些数据结构之前。