集大成者Redis

Redis的快主要表现在，它接受到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。

• Redis是内存数据库，所有操作都是在内存中完成，内存的访问速度本身就很快

• Redis中的键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，高效的数据结构是Redis快速处理数据的基础

Redis中数据结构

底层数据结构共6种：

• 简单动态字符串

• 双向链表

• 压缩列表

• 哈希表

• 跳表

• 整数数组

数据类型和底层数据结构对应关系

从上图可以看出，String类型的底层实现只有一种数据结构，就是简单动态字符串，List、Hash、Set、Sorted Set底层都有两种实现结构，它们的特点是一个键对应了一个集合的数据，这些数据结构都是值的底层实现。

键和值的结构组织

为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。

一个哈希表其实就是一个数组，数组的每个元素称为一个哈希桶，所以一个哈希表由多个哈希桶组成，每个哈希桶中保持了键值对数据。哈希桶中实际上并不保存值本身，而是指向具体值的指针。

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

全局哈希表

这个哈希表中保存了所有的键值对，称为全局哈希表，有了它只需要O(1)的时间复杂度来快速查找到键值对。

哈希表操作阻塞

某一时刻，可能哈希表的操作变慢了，因为存在哈希冲突问题和refresh可能带来操作阻塞。

随着数据量的增加，哈希冲突不可避免，Redis使用链表法（同一个桶中多个元素用一个链表来保存）来解决冲突。

哈希冲突

如上图所示，entry1、entry2、entry3都需要保存在哈希桶3中，导致了哈希冲突，因此使用*next指针来链接它们。

哈希冲突链上的元素只能通过指针逐一查找来操作，随着数据的增大，冲突变多，链表过长，进而导致这个链表上元素的查找耗时长，效率低下。

为了解决链表过长导致查找效率低下这个问题，Redis对哈希表做refresh操作（增加现有桶的数量），让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中元素数量，减少单个桶中的冲突。

为了使refresh操作更高效，Redis默认使用两个全局哈希表（哈希表1和哈希表2）：

1. 刚插入数据时，默认使用哈希表1，此时哈希表2并没有被分配空间

2. 随着数量逐步增多，Redis开始执行refresh

   1. 给哈希表2分配更大空间（哈希表1的2倍）

   2. 把哈希表1中的数据重新映射并拷贝到哈希表2中（这里涉及大量数据拷贝，优化：渐进式，每处理一个请求，从哈希表1的第一个索引位置开始，将所有entry拷贝到哈希表2中）

   3. 释放哈希表1的空间

哈希冲突解决方式

refresh中第二步的优化操作，如上图所示，巧妙的将一次性大量拷贝的开销，分摊到了多次处理请求的过程中。

集合数据操作效率

Redis的键和值是通过哈希表组织的：

• String类型的数据，找到哈希桶就能直接增删改查，操作复杂度O(1)

• 集合类型的数据

  1. 通过全局哈希表查找到对应的哈希桶位置

  2. 在集合中再增删改查

集合类型的数据：

1. 操作效率与集合底层数据结构有关，使用哈希表实现的集合要比使用链表实现的集合访问效率高

2. 操作效率与操作本身的执行特点有关，读写一个元素的操作要比读写所有元素的效率高

总共有5种底层的数据结构：

数据结构	操作特征	操作复杂度
整数数组	顺序读写，通过下标访问	O(n)
双向链表	顺序读写，通过指针逐个访问	O(n)
哈希表	通过计算哈希值访问	O(1)
压缩列表	可快速定位头尾	O(n)
跳表	通过多级索引访问	O(logn)

压缩列表

类似数据，数组中每一个元素都对应保存一个数据，不同点在于表头有zlbytes（列表长度）、zktail（列表尾的偏移量）、zllen（类别中entry个数），在列表尾部zlend（列表结束符）。

压缩列表的查找

在压缩列表中：

• 查找第一个和最后一个元素：通过表头三个字段和长度直接定位，时间复杂度O(1)

• 查找其他元素：逐个查找，时间复杂度O(n)

跳表

有序链表只能逐一查找元素，导致操作缓慢，跳表在链表的基础上，增加多级索引，通过索引位置的几个跳转，实现数据的快速定位，时间复杂度O(logn)。

跳表的查找

操作的效率

集合类型的操作很多：

• 读写单个集合元素：HGET、HSET

• 操作多个元素：SADD

• 对整个集合进行遍历：SMEMBERS

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

单元素操作

每一种集合类型对单个数据实现的增删改查操作：

• Hash类型的HGET、HSET、HDEL：O(1)

• Set类型的SADD、SREM、SRANDMEMBR：O(1)

操作的复杂度由集合采用的数据结构决定。

集合类型支持同时对多个元素进行增删改查，此时时间复杂度由当元素操作的时间复杂度和元素个数决定：

• Hash类型的HMGET、HMSEZT：O(m)，同时操作m个元素

• Set类型的SADD

范围操作

集合类型中的遍历操作，可以返回集合中所有数据：

• Hash类型的HGETALL

• Set类型的SMEMBERS

也可以返回一个范围内的部分数据：

• List类型的LRANGE：O(n)

• ZSet类型的ZRANGE：O(n)

2.8版本，增加HSCAN操作，渐进式遍历，避免了一次性返回所有元素导致Redis阻塞。

统计操作

集合类型对集合中所有元素个数的记录。例如LLEN和SCARD，时间复杂度O(1)，因为当集合类型采用压缩列表、双向链表、整数数组时，这些数据结构中会专门记录元素的个数。

例外情况

某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。

对于List类型的LPOP、RPOP、LPUSH、RPUSH操作时在列表的头尾进行增删元素，通过偏移量直接定位，时间复杂度是O(1)。