Redis 很快，主要原因有两点，一是基于内存存储，二是归功于键值存储的数据结构！几乎是以 微秒级别索引到数据！那么快速的 Redis 有没有什么慢操作了？想知道这个问题，得从他的数据结构入手进行分析！

一、Redis 中的数据结构有哪些？

• String 类型的底层实现只有一种数据结构

• 其他类型都有两种底层实现结构，即一个键对应了一个集合的数据。

二、键和值用什么结构组织

其实说的就是全局的数据结构，即键和值的索引方式，很简单就是一个全局的大的哈希表！

• 每个哈希槽都有一个 entry

• 每个 entry 保存了 key 和 value 的指针

• 两个指针分别保存了内存中真实的 key 和 value 的地址

三、为什么哈希表操作变慢了

前面说了，全局使用哈希表存储时 的复杂度，但是哈希表数据量大了，会有一个问题，就是 哈希冲突！

1. 给哈希表 2 分配两倍哈希表 1 的空间；

2. 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；

3. 释放哈希表 1 的空间。

• 每次处理请求时，将当前请求 value 所在的哈希槽上的所有 entry 都进行一次拷贝

• 到某一次请求结束，当前哈希表是可以被全部拷贝完成的

• 当然，对于没有全部拷贝完的中间过程，进行键值匹配时是需要在两个哈希表进行分别查找的（这也没关系，也就是两次 罢了）

四、集合底层数据结构

集合中的五种数据结构：整数数组、双向链表、哈希表、压缩列表和跳表！

Redis 数据结构

大家好，我是小林。 Redis 为什么那么快？ 除了它是内存数据库，使得所有的操作都在内存上进行之外，还有一个重要因素，它实现的数据结构，使得我们对数据进行增删查改操作时，Redis 能高效的处理。 因此，这次我们就来好好聊一下 Redis 数据结构，这个在面试中太常问了。 注意， Redis 数据结构并不是指 String（字符串）对象、List（列表）对象、Hash（哈希）对象、Set（集合）对象和 Zset（有序集合）对象，因为这些是 Redis 键值对中值的数据类型，也就是数据的保存形式，这些对象的底层实现的方式就用到了数据结构 。 我画了一张 Redis 数据类型（也叫 Redis 对象）和底层数据结构的对应关图，左边是 Redis 3.0版本的，也就是《Redis 设计与实现》这本书讲解的版本，现在看还是有点过时了，右边是现在 Github 最新的 Redis 代码的（还未发布正式版本）。 可以看到，Redis 数据类型的底层数据结构随着版本的更新也有所不同，比如： 在 Redis 3.0 版本中 List 对象的底层数据结构由「双向链表」或「压缩表列表」实现，但是在 3.2 版本之后，List 数据类型底层数据结构是由 quicklist 实现的； 在最新的 Redis 代码（还未发布正式版本）中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。 这次，小林把新旧版本的数据结构说图解一遍，共有 9 种数据结构：SDS、双向链表、压缩列表、哈希表、跳表、整数集合、quicklist、listpack。 不多

https://xiaolincoding.com/redis/data_struct/data_struct.html

压缩列表

• zlbytes，记录整个压缩列表占用对内存字节数；

• zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；

• zllen，记录压缩列表包含的节点数量；

• zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）

• 紧凑存储，无内存碎片问题

• 会有 连锁更新 问题，具体详见上面推荐的 小林Coding 的文章

跳表

五、不同操作的复杂度

1. 单元素（即 value 只有一个）的增删改查为

2. 范围操作为 ，scan 操作为渐进式遍历，复杂度会低一点

3. 集合长度统计为 ，由于有字段专门记录长度

4. 压缩列表和双向链表头尾操作都为 ，有偏移量字段

六、小结

• 可用 scan 命令代替范围操作

• 双向链表和压缩列表头尾快，那么就用这两种数据结构作FIFO的场景使用而非随机访问