Redis 底层数据结构

版本：2.9

支持的数据类型：

字符串

Redis 利用原生的 c 字符串进行了一次封装。封装的字符串叫做简单动态字符串：SDS(simple dynamic string)

Redis 使用的简单动态字符串比 c 语言原生的字符串有以下优点：

链表作为最常用的数据结构之一，在 redis 中的使用场景是很多的，其中包括：

Redis 中链表的几个特性：

字典又叫符号表，在 PHP 中叫关联数组，在 JAVA 中叫映射（map），在 Python 中叫字典（dict）。别管这么多叫法，字典就是一种保存键值对的一种数据结构。

Redis 使用 c 语言构建了自己的字典实现。hash 算法使用的是 murmurhash3 算法。遇到键的 hash 值冲突使用的解决方法是链地址法。当需要扩展时，Redis 利用两个哈希表进行渐进式的 rehash。

哈希表内部会通过公式计算一个负载因子。公式为：

load_factor=ht[0].used/ht[0].Size

扩展条件：

收缩条件：负载因子小于 0.1

跳跃表的结构：

跳跃表是一种对标平衡树的一种数据结构。但是比平衡树更简单、更快速、使用更少空间。所以一般都会使用跳跃表。

跳跃表在 Redis 中的使用场景暂时仅限于实现有序集合。

跳跃表的实现参见：http://blog.jobbole.com/111731/

整数集合的使用场景为元素不多且只包含整数元素的集合。

使用 c 数组实现。

压缩列表是 Redis 为了节省内存实现的。当列表键和哈希键的项比较少，并且存储的值比较小时，会使用压缩列表节省内存。