你知道 Redis数据结构底层实现吗？一文详解，彻底弄懂( 二 ) _Redis

这就涉及到了渐进式rehash，redis考虑到大量数据迁移带来的cpu繁忙(可能导致一段时间内停止服务)，所以采用了渐进式rehash的方案。步骤如下：

为ht[1]分配空间，同时持有两个哈希表(一个空表、一个有数据) 。
维持一个技术器rehashidx，初始值0 。
每次对字典增删改查，会顺带将ht[0]中的数据迁移到ht[1],rehashidx++(注意：ht[0]中的数据是只减不增的) 。
直到rehash操作完成，rehashidx值设为-1 。

它的好处：采用分而治之的思想，将庞大的迁移工作量划分到每一次CURD中，避免了服务繁忙。
4. 跳跃表

这个数据结构是我面试中见过最多的，它其实特别简单。学过的人可能都知道，它和平衡树性能很相似，但为什么不用平衡树而用skipList呢?

文章插图

4.1 skipList & AVL 之间的选择

从算法实现难度上来比较，skiplist比平衡树要简单得多。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当。
在做范围查找的时候，平衡树比skiplist操作要复杂。
skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的。

可以看到，skipList中的元素是有序的，所以跳跃表在redis中用在有序集合键、集群节点内部数据结构
4.2 源码
跳跃表节点：
typedef struct zskiplistNode {// 后退指针 struct zskiplistNode *backward;// 分值 double score;// 成员对象 robj *obj;// 层 struct zskiplistLevel {// 前进指针 struct zskiplistNode *forward;// 跨度 unsigned int span;} level[]; } zskiplistNode;跳跃表：
typedef struct zskiplist {// 表头节点和表尾节点 struct zskiplistNode *header, *tail;// 表中节点的数量 unsigned long length;// 表中层数最大的节点的层数 int level; } zskiplist;它有几个概念：
4.2.1 层(level[])
层，也就是level[]字段，层的数量越多，访问节点速度越快。(因为它相当于是索引，层数越多，它索引就越细，就能很快找到索引值)
4.2.2 前进指针(forward)
层中有一个forward字段，用于从表头向表尾方向访问。
4.2.3 跨度(span)
用于记录两个节点之间的距离
4.2.4 后退指针(backward)
用于从表尾向表头方向访问。
案例
level0 1---------->5level1 1---->3---->5level2 1->2->3->4->5->6->7->8比如我要找键为6的元素，在level0中直接定位到5，然后再往后走一个元素就找到了。
5. 整数集合(intset)

Reids对整数存储专门作了优化，intset就是redis用于保存整数值的集合数据结构。当一个结合中只包含整数元素，redis就会用这个来存储。

127.0.0.1:6379[2]> sadd number 1 2 3 4 5 6(integer) 6127.0.0.1:6379[2]> object encoding number"intset"源码
intset数据结构：
typedef struct intset {// 编码方式 uint32_t encoding;// 集合包含的元素数量 uint32_t length;// 保存元素的数组 int8_t contents[]; } intset;你肯定很好奇编码方式(encoding)字段是干嘛用的呢？

如果 encoding 属性的值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组里的每个项都是一个 int16_t 类型的整数值（最小值为 -32,768，最大值为 32,767 ）。
如果 encoding 属性的值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组里的每个项都是一个 int32_t 类型的整数值（最小值为 -2,147,483,648，最大值为 2,147,483,647 ）。
如果 encoding 属性的值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组里的每个项都是一个 int64_t 类型的整数值（最小值为 -9,223,372,036,854,775,808，最大值为 9,223,372,036,854,775,807 ）。

说白了就是根据contents字段来判断用哪个int类型更好，也就是对int存储作了优化。
说到优化，那redis如何作的呢？就涉及到了升级。
5.1 encoding升级
如果我们有个Int16类型的整数集合，现在要将65535(int32)加进这个集合，int16是存储不下的，所以就要对整数集合进行升级。
它是怎么升级的呢(过程)？
假如现在有2个int16的元素:1和2，新加入1个int32位的元素65535 。