高效的数据结构

redis中的数据结构有2种意思：

• （redis本质上是一个hashmap）
• redis键值对中的值的数据类型，也就是数据的保存形式，常用的有5种：String(字符串)、List(列表)、Hash(哈希)、Set(集合)、Sorted Set(有序集合)。这几种几种对外暴露的数据结构它们的底层编码方式都是做了不同的优化的。
• 上面数据结构的底层实现。底层数据结构一共有6种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

从上面可以看出：

• String的底层是（简单动态字符串）
• List的底层是（双向链表和压缩链表）
• Hash的底层是（压缩链表和哈希表）
• Set的底层是（整数数组和哈希表）
• Sorted Set底层（压缩链表和跳表）

也就是说

• String类型的底层实现只有一种数据结构，也就是简单动态字符串。
• 而List、Hash、Set和Sorted Set这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据

为什么要提供这么多的数据结构呢？

• 当然是为了追求速度，不同数据类型使用不同的数据结构速度才得以提升。每种数据类型都有一种或者多种数据结构来支撑
• redis之所以采用不同的数据结构，其实是在性能和内存使用效率之间的平衡。

redis本质就是一个哈希表

键和值用什么结构组织？

redis是一个k-v数据库。为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。

• 一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。也就是说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。
• 不管是键类型还是值类型，哈希桶中的元素保存的都不是值本身，而是指向具体值的指针。

如下图中可以看到，哈希桶中的entry元素中保存了*key和*value指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过*value指针被查找到

因为这个哈希表保存了所有的键值对，所以，它也叫做全局哈希表。

• 哈希表的最大好处就是让我们可以用O(1)的时间复杂度来快速查找到键值对----我们只需要计算键的哈希值，就可以知道它对应的哈希桶位置，然后就可以访问相应的entry元素
• 这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有10万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。

也就是说，整个数据库就是一个全局hash表，而hash表的时间复杂度就是O(1)，只需要计算每个键的hash值，就知道对应的hash桶的位置，定位桶里面的entry找到对应数据，这个也是redis块的原因之一。

但是，如果你只是了解哈希表O(1)复杂度和快速查找特性，那么，当你往redis中写入大量数据之后，就可能发现操作有时候会突然变慢了。原因是哈希表的冲突问题和rehash可能带来的操作阻塞

为什么哈希表操作变慢了？

因为哈希冲突

• 这里的哈希冲突，也就是指，两个key的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。

• 毕竟，哈希桶的个数通常要少于key的数量，hash冲突是不可避免

哈希冲突怎么办？

redis解决哈希冲突的方式，就是链式哈希。

• 所谓的链式哈希，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间一次用指针连接。如下图：
  

• entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，导致了哈希冲突。此时，entry1 元素会通过一个*next指针指向 entry2，同样，entry2 也会通过*next指针指向entry3。这样一来，即使哈希桶 3 中的元素有 100 个，我们也可以通过 entry 元素中的指针，把它们连起来。这就形成了一个链表，也叫作哈希冲突链。

• 但是，这里依然存在一个问题，哈希冲突链上的元素只能通过指针逐一查找再操作，如果哈希表中写入的数据越来越多，哈希冲突的可能也会越来越多，这就会导致某些哈希冲突链过长，也就是一个哈希桶下面挂了太多的数据的，那么其性能就会下降。

怎么解决呢？

• redis对会哈希表做rehash操作
• 什么是rehash操作呢？rehash也就是增加现有的哈希桶数量，让逐渐增大的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

渐进式rehash

那具体怎么做呢？

其实，为了使得rehash操作更加高效，redis默认使用了两个全局哈希表：哈希表1和哈希表2.一开始，当你刚插入数据时，默认使用哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，redis开始执行rehash，这个过程分为三步：

• 把哈希表2分配更大的空间，比如是当前哈希表1大小的两倍
• 把哈希表1中的数据重新映射并拷贝到哈希表2中
• 释放哈希表1的空间

至此，我们就可以从哈希表1切换到哈希表2，用增大的哈希表2保存更多的数据，而原来的哈希表1操作留作下一次rehash扩容备用。

上面步骤有一个问题，那就是第二步涉及大量的数据拷贝，如果一次性把哈希表1中的数据都迁移完，会造成redis线程阻塞，无法服务其他请求。此时，redis就无法快速访问数据了。

为了避免这个问题，redis采用了渐进式rehash

简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的entries。如下图所示：

这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

另外，渐进式rehash执行时，除了根据键值对的操作来进行数据迁移，redi本身还会有一股定时任务在执行rehash，如果没有键值对操作，这个定时任务会周期性的搬移一些数据到新的哈希表中

数据结构操作效率

因为redis本质是一个哈希表：

• 对于String类型来说，找到哈希桶就能直接进行增删改查了，所以，哈希表的O(1)操作复杂度也就是它的复杂度了
• 但是，对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步操作。

那集合类型的操作效率又是怎么样的呢？

集合数据操作效率

和String类型不同，一个集合类型的值：

• 第一步是通过全局哈希表找到对应的哈希桶位置
• 第二步是在集合中再增删改查。

那么，集合的操作效率和哪些因素相关呢？

• 首先，与集合的底层数据结构有关。比如，使用哈希表实现的集合，要比使用链表实现的集合访问效率更高
• 其次，操作效率和这些操作本身的执行特点有关，比如读写一个元素的操作要比读写所有元素的效率高

那集合类型的底层数据结构和操作复杂度是什么样的呢？

有哪些底层数据结构

整数数组和双向链表：通过数组下标和链表指针逐个元素访问，操作复杂度O(n)

双端链表

列表 List 更多是被当作队列或栈来使用的。队列和栈的特性一个先进先出，一个先进后出。双端链表很好的支持了这些特性。

• 前后节点：链表里每个节点都带有两个指针，prev 指向前节点，next 指向后节点。这样在时间复杂度为 O(1) 内就能获取到前后节点。
  

• 头尾节点：头节点里有 head 和 tail 两个参数，分别指向头节点和尾节点。这样的设计能够对双端节点的处理时间复杂度降至 O(1) ，对于队列和栈来说再适合不过。同时链表迭代时从两端都可以进行。
  

• 链表长度：头节点里同时还有一个参数 len，和上边提到的 SDS 里类似，这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表，直接拿到 len 值就可以了，这个时间复杂度是 O(1)。

这些特性都降低了 List 使用时的时间开销。

zipList 压缩列表

引入：

• 双端链表我们已经熟悉了。但是有一个问题：如果在一个链表节点中存储一个小数据，比如一个字节。那么对应的就要保存头节点，前后指针等额外的数据。

• 这样就浪费了空间，同时由于反复申请与释放也容易导致内存碎片化。这样内存的使用效率就太低了。

• 于是，压缩列表上场了！

压缩列表是 List 、hash、 sorted Set 三种数据类型底层实现之一。

怎么实现

当一个列表只有少量数据的时候，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现。

• ziplist 是由一系列特殊编码的连续内存块组成的顺序型的数据结构，ziplist 中可以包含多个 entry 节点，每个节点可以存放整数或者字符串
• ziplist 在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表占用字节数、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N)

• 它是经过特殊编码，专门为了提升内存使用效率设计的。所有的操作都是通过指针与解码出来的偏移量进行的。

• 并且压缩列表的内存是连续分配的，遍历的速度很快。

后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。

总结

压缩列表实际上类似一个数组，数组中的每一个元素都对应保存一个数组。和数组不同的是：

• 压缩列表在表头有三个字段zlbytes、zltail、zllen，分别表示列表长度、列表尾的偏移量、链表中entry个数
• 压缩列表的表尾还有一个zlend，表示链表结束。

具体如下图：

• 在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度O(1)
• 如果要查找其他元素，就只能逐个查找，此时复杂度O(N)

跳表

为什么要引入跳表呢？

• 有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。
• 具体来说，跳表是在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。如下图：
  • 如果我们要在链表中查找33这个元素，只能从头开始遍历链表，查找6次，直到找到33为止。为此，复杂度是O(N)，查找效率很低。
  • 为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。这些索引再通过指针指向原始的链表。比如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。此时，我们只需要 4 次查找就能定位到元素 33 了。
  • 如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取 1、27、100 作为二级索引，二级索引指向一级索引。这样，我们只需要 3 次查找，就能定位到元素 33 了。
    
• 从上面可以看出，跳表每一层都有一条有序的链表，最底层的链表包含了所有的元素。这样跳跃表就可以支持在 O(logN) 的时间复杂度里查找到对应的节点。

sorted set 类型的排序功能便是通过「跳跃列表」数据结构来实现。

下面这张是跳表真实的存储结构，和其它数据结构一样，都在头节点里记录了相应的信息，减少了一些不必要的系统开销。

总结

• 跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的
• 跳跃表支持平均 O（logN）、最坏 O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

关于SDS简单动态字符

问题：redis是用C语言实现的，为啥还有搞一个SDS动态字符串呢

回答：

• 字符串结构使用最官方，通常用于我们缓存登录后的用户信息，key = userId，value = 用户信息 JSON 序列化成字符串。
• C 语言中字符串的获取 「MageByte」的长度，要从头开始遍历，直到 「\0」为止，Redis 作为唯快不破的男人是不能忍受的。
• C 语言字符串结构与 SDS 字符串结构对比图如下所示：

从上面可以看出，SDS与C字符串区别

• O(1)时间复杂度获取字符串长度
  • C语言需要遍历到’\0’时结束，时间复杂度为O(N)
  • SDS中len保存当前字符串长度，时间复杂度为O(1)
• 空间预分配
  • SDS被修改后，程序不仅会为SDS分配所需要的必须空间，还会分配额外的未使用空间
  • 分配规则如下：如果对SDS修改后，len的长度小于1M，那么程序将分配和len相同长度的未使用空间
  • 举个例子，如果 len=10，重新分配后，buf 的实际长度会变为 10(已使用空间)+10(额外空间)+1(空字符)=21。如果对 SDS 修改后 len 长度大于 1M，那么程序将分配 1M 的未使用空间。
• 惰性空间释放
  • 当对SDS进行缩短操作时，程序并不会回收多余的内存空间，而是使用free字段将这些字节数量记录下来不释放
  • 后面如果需要使用append操作，则直接使用free中未使用的空间，减少了内存的分配
• 二进制安全
  • 你已经知道了 Redis 可以存储各种数据类型，那么二进制数据肯定也不例外。但二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如 ‘\0’ 等。
  • 前面我们提到过，C 中字符串遇到 ‘\0’ 会结束，那 ‘\0’ 之后的数据就读取不上了。但在 SDS 中，是根据 len 长度来判断字符串结束的。
  • 看，二进制安全的问题就解决了。

合理的数据编码（什么时候使用哪种数据结构）

对于每一种数据类型来说，底层的支持可能是多种数据结构，什么时候使用哪种数据结构，这就涉及到了编码转换问题

那我们就来看看，不同的数据类型是如何进行编码转化的：

• String：存储数字的话，采用 int 类型的编码，如果是非数字的话，采用 raw 编码；
• List：List 对象的编码可以是 ziplist 或 linkedlist，字符串长度 < 64 字节且元素个数 < 512 使用 ziplist 编码，否则转化为 linkedlist 编码；
  注意：这两个条件是可以修改的，在 redis.conf 中：

list-max-ziplist-entries 512
list-max-ziplist-value 64

• Hash：Hash 对象的编码可以是 ziplist 或 hashtable。
  • 当 Hash 对象同时满足以下两个条件时，Hash 对象采用 ziplist 编码：
    • Hash 对象保存的所有键值对的键和值的字符串长度均小于 64 字节
    • Hash 对象保存的键值对数量小于 512 个。
  • 否则就是 hashtable 编码。
• Set：
  • Set 对象的编码可以是 intset 或 hashtable，intset 编码的对象使用整数集合作为底层实现，把所有元素都保存在一个整数集合里面。
  • 保存元素为整数且元素个数小于一定范围使用 intset 编码，任意条件不满足，则使用 hashtable 编码；
• Zset：
  • Zset 对象的编码可以是 ziplist 或 zkiplist，当采用 ziplist 编码存储时，每个集合元素使用两个紧挨在一起的压缩列表来存储。
  • Ziplist 压缩列表第一个节点存储元素的成员，第二个节点存储元素的分值，并且按分值大小从小到大有序排列。
  • 当 Zset 对象同时满足一下两个条件时，采用 ziplist 编码：
    • Zset 保存的元素个数小于 128。
    • Zset 元素的成员长度都小于 64 字节。
  • 如果不满足以上条件的任意一个，ziplist 就会转化为 zkiplist 编码

整数数组和压缩列表在查找时间复杂度方面并没有很大的优势，那为什么 Redis 还会把它们作为底层数据结构呢？

• 内存利用率，整数数组和压缩列表的设计，充分体现了 Redis“又快又省”特点中的“省”，也就是节省内存空间。整数数组和压缩列表都是在内存中分配一块地址连续的空间，然后把集合中的元素一个接一个地放在这块空间内，非常紧凑。因为元素是挨个连续放置的，我们不用再通过额外的指针把元素串接起来，这就避免了额外指针带来的空间开销。
• 充分利用CPU缓存，因为数组和压缩列表的内存是连续的，符合程序的局部性原理，就可以充分利用CPU高速缓存，速度会更快
• 另外，当数组元素超过阈值时，会自动转为hash和跳表，保证查询效率

不同操作的复杂度

集合类型的操作类型有很多，有读写单个集合元素的，比如HSET、HSET，也有操作多个元素的，比如SADD，还有对整个集合进行遍历操作的，比如SRANGE。这么多操作，它们的复杂度也各不相同，而复杂度的高低又是我们选择集合类型的重要依据。我们在使用时，应该规避高复杂度的操作。怎么记忆这些操作的时间复杂度呢？口诀如下：

• 单元素操作是基础
• 范围操作非常耗时
• 统计操作通常高效
• 例外情况只有几个

第一，单元数操作，是指每一种集合类型对单个数据实现的增删改查操作。例如，Hash 类型的 HGET、HSET 和 HDEL，Set 类型的 SADD、SREM、SRANDMEMBER 等。

• 这些操作的复杂度由集合采用的数据结构决定，比如，HGET、HSET 和 HDEL 是对哈希表做操作，所以它们的复杂度都是 O(1)；Set 类型用哈希表作为底层数据结构时，它的 SADD、SREMSRANDMEMBER 复杂度也是 O(1)。
• 另外，集合类型也支持同时对多个元素进行增删改查，比如Hash类型的 HMGET 和 HMSET。此时，这些操作的复杂度，就是由单个元素操作复杂度和元素个数决定的。比如，HMSET增加M个元素时，复杂度就从O(1)变成O(M)了

第二，范围操作，也就是集合类型中的遍历操作，可以返回集合中的所有数据。比如 Hash类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，比如 List类型的 LRANGE 和 ZSet 类型的 ZRANGE。

• 这些操作的复杂度一般是O(N)，比较耗时，我们应该尽量避免
• 不过，Redis从2.8版本开始提供了SCAN系列操作（比如HSCAN、SSCAN、ZSCAN），这些操作实现了渐进式遍历，每次只返回有限数量的数据，这样一来，相比于HGETALL、SMEMBERS 这类操作来说，就避免了一次性返回所有元素而导致的redis阻塞

第三，同一操作，是指集合类型对集合中所有元素个数的记录，比如LLEN和SCARD。这类操作复杂度只有O(1)，这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录了元素的个数统计，因此可以高效的完成相关操作

第四，例外情况，是指某些数据结构的特殊记录，比如压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来，对于LIST类型的LPOP、RPOP、LPUSH、RPUSH这四个操作，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度是O(1)，可以实现快速操作

小结

redis的底层数据结构，既包括redis中用来保存每个键和值的全局哈希表结构，也包括了支持集合类型实现的双向链表、压缩列表、整数数组、哈希表和跳表这五大底层结构。

redis为什么能够快速的操作键值对呢？

• 一方面是因为O(1)复杂度的哈希表被广泛使用，包括String、Hash、Set，它们的操作复杂度基本有哈希表决定
• 另一方面，sorted set也采用了O(logN)复杂度的跳表。
• 不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是O(N)。怎么解决呢？可以使用其他命令来替代，比如可以用SCAN来代替，避免在redis内部产生费时的全集合遍历操作。
• 而对于复杂度比较高的list类型，它的底层实现结构是双向链表和压缩列表，其操作的时间复杂度都是O(N)，因此，建议因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。