Redis 底层数据结构
前言
redis对外有一些5种基本类型，内部其实还是用的自己封装的数据结构，这篇文章主要是讲解数据结构的。
- 简单动态字符串（SDS）
- 链表
- 字典
- 跳跃表
- 整数集合
- 压缩列表
简单动态字符串（SDS）
直接看SDS模型，
/** 保存字符串对象的结构*/struct sdshdr {// buf 中已占用空间的长度int len;// buf 中剩余可用空间的长度int free;// 数据空间char buf[];};
重点是 数据空间 char buf[]; ，如果我们存储一个“redis”，那么buf=[‘r’,‘e’,‘d’,‘i’,‘s’,’/0’]。另外它定义了空间长度、空间剩余长度，这有一下几点好处：
- 快速给出长度值，复杂度O(1)
- 避免缓冲区益处，明确了剩余大小，下次改写可以直接扩充，
- 减少修改字符串带来的内存分配次数
- 可以保存二进制数据和文本文数据
C 字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。
链表
typedef struct listNode{struct listNode *prev;struct listNode * next;void * value;}
这个结构比较简单，没有太复杂，list内部就是链表实现的，
- 双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）
- 无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
- 表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
- 长度计数器：链表中存有记录链表长度的属性 len
- 多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。
字典
看下代码：
// 字典结构typedef struct dict {// 类型特定函数dictType *type;// 私有数据void *privedata;// 哈希表dictht ht[2];// rehash 索引in trehashidx;}// 哈希表结构typedef struct dictht {//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码，用于计算索引值unsigned long sizemask;//该哈希表已有节点的数量unsigned long used;}typeof struct dictEntry{//键void *key;//值union{void *val;uint64_tu64;int64_ts64;}struct dictEntry *next;}
词典结构图解：
既然用的hash，那就涉及到hash冲突、扩容等问题，这里讲解一下扩容rehash，这里跟Java hashmap不一样，
- 先新建一个dictht，叫做 h1 ，空间是h0的2倍
- 然后把h0的dictEntry 全部rehash到h1，最后把h1跟h0互换
- 给h0一个空白哈希表，释放h0
这其中rehash到h1不是一下子完成的，而是当执行CURD操作时，才去rehash，当然这里存在一个问题，rehash后数据就移动到h1了，这里就可能存在h0查不到，所以我想这段期间有可能就要双读写h1、h0 。
- 在渐进式rehash过程中，rehashidx来表明下一次要rehash的数组索引值，也就是h0中的数组的索引，一开始等于-1，rehash的时候等于0，慢慢把ho的数组中h0[0]的链表rehash到h1上，完成后rehashidx++；同时h0的数组这个索引下置为null。这样慢慢就把h0的数组一步一步hash到h1。
- 删除、查找、更新等操作都会对h0、h1同时操作，
- 添加操作则会只去h1，保证h0只减不增。不然的话，rehashidx就没啥用了。
跳跃表
主要用作有序结构，在跳跃表中会指向其他节点，所以会有顺序关系，跳跃表跟hash表结合做有序集合 zset，成员做hash 的 key，用score做hash value，value 也指向其他成员，当然指向的成员也应该与顺序的。
typedef struct zskiplist {//表头节点和表尾节点structz zskiplistNode *header,*tail;//表中节点数量unsigned long length;//表中层数最大的节点的层数int level;}zskiplist;typedef struct zskiplistNode{//层struct zskiplistLevel{//前进指针struct zskiplistNode *forward;//跨度unsigned int span;} level[];//后退指针struct zskiplistNode *backward;//分值double score;//成员对象robj *obj;}
从结构图中我们可以清晰的看到，header，tail分别指向跳跃表的头结点和尾节点。level 用于记录最大的层数，length 用于记录我们的节点数量。
跳跃表的特点：
- 跳跃表是有序集合的底层实现之一
- 主要有zskiplist 和zskiplistNode两个结构组成
- 每个跳跃表节点的层高都是1至32之间的随机数，这也是有利于
- 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的对象必须是唯一的
- 节点按照分值的大小从大到小排序，如果分值相同，则按成员对象大小排序
跳跃表为什么比红黑树、平衡树好？
- 跳跃表结点的层数是随机生成，不严格要求上层的 1 / 2 1/2 1/2位置在下层结点一定有层，采取随机方法赋予结点的层数就有避免了调整结点层数的问题。
- 算法实现难度上来比较，skiplist比平衡树要简单得多，平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
- 在做范围查找的时候，平衡树比skiplist操作要复杂。
我们前面提到过，Redis中的sorted set，是在skiplist, dict和ziplist基础上构建起来的:
- 当数据较少时，sorted set是由一个ziplist来实现的。
- 当数据多的时候，sorted set是由一个叫zset的数据结构来实现的，这个zset包含一个dict + 一个skiplist。dict用来查询数据到分数(score)的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）。
下两个条件之一满足的时候，ziplist会转成zset（具体的触发条件参见t_zset.c中的zaddGenericCommand相关代码）：
当sorted set中的元素个数，即(数据, score)对的数目超过128的时候，也就是ziplist数据项超过256的时候。
当sorted set中插入的任意一个数据的长度超过了64的时候。
整数集合
typedef struct intset{//编码方式uint32_t enconding;// 集合包含的元素数量uint32_t length;//保存元素的数组int8_t contents[];}
具体看下看下参考博客
压缩列表
看下参考博客
参考博客
深入浅出Redis-redis底层数据结构（上）
深入浅出Redis-redis底层数据结构（下）
Redis 为什么用跳表而不用平衡树？
柔光的暖阳◎
小灰灰
╰+攻爆jí腚メ
骑猪看日落
我会带着你远行
还没有评论，来说两句吧...