Redis 底层数据结构

string

字符串对象的底层实现有三种可能：int，raw，embstr.

int

如果一个字符串对象，保存的值是一个整数值，并且这个整数值在 long 的范围内，那么 redis 用整数值来保存这个信息，并且将字符串编码设置为 int.

127.0.0.1:6379> set test 1
OK
127.0.0.1:6379> object encoding test
"int"
127.0.0.1:6379>

raw

如果字符串对象保存的是一个字符串, 并且长度大于 32 个字节，它就会使用SDS（简单动态字符串）数据结构来保存这个字符串值，并且将字符串对象的编码设置为raw.

127.0.0.1:6379> set test faldfjasdflsjdflsjdflsajflajflsajflsadjflsdjdfasdfasdgsdgdsgasdgasdgasdfasdfsadfsad
OK
127.0.0.1:6379> object encoding test
"raw"

embstr

如果字符串对象保存的是一个字符串, 但是长度小于 32 个字节，它就会使用embstr来保存了，embstr编码不是一个数据结构，而是对 SDS 的一个小优化，当使用 SDS 的时候，程序需要调用两次内存分配，来给 字符串对象 和 SDS 各自分配一块空间，而embstr只需要一次内存分配，因为他需要的空间很少，所以采用 连续的空间保存，即将 SDS 的值和 字符串对象的值放在一块连续的内存空间上。这样能在短字符串的时候提高一些效率。

127.0.0.1:6379> set test hello
OK
127.0.0.1:6379> object encoding test
"embstr"

浮点数如何保存

redis 的字符串数据类型是支持保存浮点数，并且支持对浮点数进行加减操作，但是 redis 在底层是把浮点数转换成字符串值，之后走上面三种编码的规则的。对浮点数进行操作时，也是从字符串转换成浮点数进行计算，然后再转换成字符串进行保存的。

编码转换条件

这块的知识其实是很符合我们的认知的，比如 int编码只可以保存整数，那么当我们对一个 int 编码的字符串对象，修改它的值，它自然就会使用 raw 编码了。但是有一个特性，Redis 没有为embstr编码提供任何的修改操作，这也就是为什么它只是个编码而不是一个数据结构的原因。所以在 Redis 中，embstr编码的值其实是 只读的，只要发生修改，立刻将编码转换成 raw.

总结：

编码	使用条件
int	可以用 long 保存的整数
embstr	字符串长度小于 32 字节（或者浮点数转换后满足）
raw	长度大于 32 的字符串

list

涉及到的数据结构，压缩列表, 双向链表, 快速列表。

在 Redis 3.2 版本之前，列表对象底层由 压缩列表和双向链表配合实现，当元素数量较少的时候，使用压缩列表，当元素数量增多，就开始使用普通的双向链表保存数据。

但是这种实现方式不够好，双向链表中的每个节点，都需要保存前后指针，这个内存的使用量 对于Redis这个内存数据库来说极其不友好。

因此在 3.2 之后的版本，作者新实现了一个数据结构，叫做 quicklist. 所有列表的底层实现都是这个数据结构了。它的底层实现基本上就是将 双向链表和压缩列表进行了结合，用双向的指针将压缩列表进行连接，这样不仅避免了压缩列表存储大量元素的性能压力，同时避免了双向链表连接指针占用空间过多的问题。

127.0.0.1:6379> lpush test 123 323 43
(integer) 3
127.0.0.1:6379> object encoding test
"quicklist"
127.0.0.1:6379>

总结

编码	使用条件
quicklist	所有数据

set

inset

当集合中的所有元素都是整数，且元素的数量不大于 512 个的时候，使用 intset 编码。(这个数量是可以在配置文件设置)

127.0.0.1:6379> sadd test 3 1 23  43
(integer) 4
127.0.0.1:6379> object encoding test
"intset"
127.0.0.1:6379>

hashtable

当元素不符合全部为整数值且元素个数小于 512时，集合对象使用的编码方式为hashtable.

字典的每一个键都是一个字符串对象，其中保存了集合里的一个元素，字典的值全部被设置为 NULL.

127.0.0.1:6379> sadd test ab cd
(integer) 2
127.0.0.1:6379> object encoding test
"hashtable"

总结

编码	使用条件
intset	所有元素都是整数且元素个数小于 512(这个数量是可以在配置文件设置)
hashtable	其他数据

zset

ziplist

当元素个数少于128个，并且所有元素成员的长度小于64字节，使用该编码。(该参数可以在配置文件中配置)
每个集合的元素 (key-value), 使用两个紧挨着的压缩列表的节点来表示，第一个节点保存集合元素的成员 (member), 第二个节点保存集合元素的分支 (score).

在压缩列表的内部，集合元素按照分值从小到大进行排序。

127.0.0.1:6379> zadd test 10 a 29 b 43 c
(integer) 3
127.0.0.1:6379> object encoding test
"ziplist"

skiplist

当使用 skiplist 编码的时候，内部同时使用了跳跃表和字典来保存数据。原因如下：

• 当我们只使用字典来实现，我们可以以 O(1) 的时间复杂度获取成员的分值，但是由于字典是无序的，当我们需要进行范围性操作的时候，需要对字典中的所有元素进行排序，这个时间复杂度至少需要 O(nlogn).
• 我们只使用跳跃表来实现，我们可以在 O(logn) 的时间进行范围排序操作，但是如果要获取到某个元素的分值，时间复杂度也是 O(logn).

因此，将字典和跳跃表结合进行使用，可以在 O(1) 的时间复杂度下完成查询分值操作，而对一些范围操作，使用跳跃表可以达到 O(logn) 的是缠绵复杂度。

127.0.0.1:6379> zadd test 10 a 20 b 30 fjaljlfdjflajdflsjflsajfdlsjflsajdlfjsaldfjsdljflsjflsdjflsdjflsdjflsdjflsdjflsjdlfjaldfjajdflajflajfdlsadjflsdjlfjasdfjasdjfljflsdjflsajflsadjflsadjflasjdlf
(integer) 1
127.0.0.1:6379> object encoding test
"skiplist"

根据上面可以看见，当元素的长度大于64字节的时候，就变成了skiplist。

总结

编码	使用条件
ziplist	元素数量少于 128 且 所有元素成员的长度小于 64 字节（可以在配置文件中配置）
skiplist	不满足上述条件的其他情况

hash

ziplist

ziplist 编码下的哈希对象，使用了压缩列表作为底层实现数据结构，用两个连续的压缩列表节点来表示哈希对象中的一个键值对。实现方式类似于上面的有序集合的场景。

127.0.0.1:6379> hset test a 2 b 3
(integer) 2
127.0.0.1:6379> object encoding test
"ziplist"

hashtable

哈希结构本身在结构上和字典 (hashtable) 就颇为相似，因此哈希对象中的每一个键值对都是字典中的一个键值对。

• 字典的每一个键都是一个字符串对象，对象中保存了键值对的键。
• 字典的每一个值都是一个字符串对象，对象中保存了键值对的值。

127.0.0.1:6379> hset test abc aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer) 1
127.0.0.1:6379> object encoding test
"hashtable"

当向hash中放入一个很长的元素的时候，就会变成hashtable

总结

编码	使用条件
ziplist	键值对的键和值的长度都小于 64 字节，且 键值对个数小于 512（可以在配置文件中配置）
hastable	不满足上述条件的其他条件