Redis 键值类型及其存储结构

键值类型

键的数据类型是字符串，值的类型有：字符串、列表、Hash、集合、有序集合。

键的存储和查找

       Redis底层键的存储类似于Java中其他Hash存储结构：数组+链表的组合。数组中存储的是Key Hash函数对数组长度取模后相等的所有key组成列表的首元素，查找则是首先根据hash定位到数组位置所指向的列表首元素，然后遍历列表找到Hash值相等的key。

      

图1 Redis Key hash数据结构简单示意图

键的过期实现

检查过期可以为每个key设置timer或定时遍历所有key，但都有明显资源和性能消耗问题，Redis采用的实践：

1. 查找是触发： 当查找KEY返回之前检查是否过期。
2. 定期随机检查：定期随机抽查100条key，检测过期。

列表

列表采用压缩列表或双向循环链表的数据结构存储。

当列表中存储的数据量比较小的时候，列表采用压缩列表的方式实现。

1. 列表中保存的单个数据（有可能是字符串类型的）小于 64 字节；
2. 列表中数据个数少于 512 个

压缩列表是为了节约内存而存在的。

Hash类型

Hash类型也同样使用压缩列表和散列表的组合。Redis 使用压缩列表来实现Hash类型有两个前提：

1. Hash中保存的键和值的大小都要小于 64 字节。
2. Hash中键值对的个数要小于 512 个。

其他情况下Redis 就使用散列表来实现字典类型。哈希函数 使用MurmurHash2。

有序集合（sortedset）

SortedSet 使用压缩列表和跳表组合来存储有序集合。Redis使用压缩列表来实现有序集合的前提：

1. 所有数据的大小都要小于 64 字节；
2. 元素个数要小于 128 个。

       跳表结构是在链表结构上增加索引层，以支持快速地按照得分值、得分区间获取数据。

图2 跳表增加索引层示意图

跳表的插入：根据索引找到位置，直接插入

图3 跳表插入示意图

删除： 删除节点及对应索引。如上图删除元素7则将删除最底层的元素相应索引层中的索引7元素。

跳表索引动态更新

跳表元素的删除和增加会破坏跳表的索引的平衡性，跳表通过随机函数的方法来维持平衡：将数据插入随机索引层：随机数生成随机层次，进而插入随机索引层

数据结构持久化到硬盘

将内存中数据结构和数据持久化到硬盘有两种方式：

第一种是清除原有的存储结构，只将数据存储到磁盘中。当需要从硬盘还原数据到内存的时候，重新将数据组织成原来的数据结构。Redis 采用的就是这种持久化思路。

第二种方式是保留原来的存储格式，就是除了具体数据外还保存这相关数据结构的信息，如散列表需要将散列表的大小、每个数据被散列到的槽的编号等信息，都保存在硬盘中。当从硬盘中还原数据到内存中时，避免了重新计算Hash。