20 Redis
Redis的快主要表现在，它接受到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。
- Redis是内存数据库，所有操作都是在内存中完成，内存的访问速度本身就很快
- Redis中的键值对是按一点的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，高效的数据结构是Redis快速处理数据的基础
0.1. Redis中数据结构
底层数据结构共6种：
- 简单动态字符串
- 双向链表
- 压缩列表
- 哈希表
- 跳表
- 整数数组
从上图可以看出，String类型的底层实现只有一种数据结构，就是简单动态字符串，List、Hash、Set、Sorted Set底层都有两种实现结构，它们的特点是一个键对应了一个集合的数据，这些数据结构都是值的底层实现。
0.1.1. 键和值的结构组织
为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。
一个哈希表其实就是一个数组，数组的每个元素称为一个哈希桶，所以一个哈希表由多个哈希桶组成，每个哈希桶中保持了键值对数据。哈希桶中实际上并不保存值本身，而是指向具体值的指针。
如下图所示，哈希桶中的entry元素中保存了*key和*value指针，分别指向了实际的键和值，这样即使值是一个集合，也可以通过*value指针被查找到。
这个哈希表中保存了所有的键值对，称为全局哈希表，有了它只需要O(1)的时间复杂度来快速查找到键值对。
0.1.2. 哈希表操作阻塞
某一时刻，可能哈希表的操作变慢了，因为存在哈希冲突问题和refresh可能带来操作阻塞。
随着数据量的增加，哈希冲突不可避免，Redis使用链表法（同一个桶中多个元素用一个链表来保存）来解决冲突。
如上图所示，entry1、entry2、entry3都需要保存在哈希桶3中，导致了哈希冲突，因此使用*next指针来链接它们。
哈希冲突链上的元素只能通过指针逐一查找来操作，随着数据的增大，冲突变多，链表过长，进而导致这个链表上元素的查找耗时长，效率低下。
为了解决链表过长导致查找效率低下这个问题，Redis对哈希表做refresh操作（增加现有桶的数量），让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中元素数量，减少单个桶中的冲突。
为了是refresh操作更高效，Redis默认使用两个全局哈希表（哈希表1和哈希表2）：
- 刚插入数据时，默认使用哈希表1，此时哈希表2并没有被分配空间
- 随着数量逐步增多，Redis开始执行refresh
- 给哈希表2分配更大空间（哈希表1的2倍）
- 把哈希表1中的数据重新映射并拷贝到哈希表2中（这里涉及大量数据拷贝，优化：渐进式，每处理一个请求，从哈希表1的第一个索引位置开始，将所有
entry拷贝到哈希表2中） - 释放哈希表1的空间
refresh中第二步的优化操作，如上图所示，巧妙的将一次性大量拷贝的开销，分摊到了多次处理请求的过程中。
0.1.3. 集合数据操作效率
Redis的键和值是通过哈希表组织的，
- String类型的数据，找到哈希桶就能直接增删改查，操作复杂度
O(1) - 集合类型的数据
- 通过全局哈希表查找到对应的哈希桶位置
- 在集合中再增删改查
集合类型的数据：
- 操作效率与集合底层数据结构有关。使用哈希表实现的集合要比使用链表实现的集合访问效率高。
- 操作效率与操作本身的执行特点有关。读写一个元素的操作要比读写所有元素的效率高。
总共有5中底层的数据结构：
| 数据结构 | 操作特征 | 操作复杂度 |
|---|---|---|
| 整数数组 | 顺序读写，通过下标访问 | O(n) |
| 双向链表 | 顺序读写，通过指针逐个访问 | O(n) |
| 哈希表 | 通过计算哈希值访问 | O(1) |
| 压缩列表 | 可快速定位头尾 | O(n) |
| 跳表 | 通过多级索引访问 | O(logn) |
0.1.3.1. 压缩列表
类似数据，数组中每一个元素都对应保存一个数据，不同点在于表头有zlbytes（列表长度）、zktail（列表尾的偏移量）、zllen（类别中entry个数），在列表尾部zlend（列表结束符）。
在压缩列表中：
- 查找第一个和最后一个元素：通过表头三个字段和长度直接定位，时间复杂度
O(1) - 查找其他元素：逐个查找，时间复杂度
O(n)
0.1.3.2. 跳表
有序链表只能逐一查找元素，导致操作缓慢，跳表在链表的基础上，增加多级索引，通过索引位置的几个跳转，实现数据的快速定位，时间复杂度O(logn)
0.1.4. 操作的效率
集合类型的操作很多：
- 读写单个集合元素：HGET、HS
- 操作多个元素：SADD
- 对整个集合进行遍历：SMEMBERS
单元素操作时基础，范围操作非常耗时，统计操作通常高效、例外情况只有几个。
0.1.4.1. 单元素操作
每一种集合类型对单个数据实现的增删改查操作。
- Hash类型的HGET、HSET、HDEL：
O(1) - Set类型的SADD、SREM、SRANDMEMBR：
O(1)
这次操作的复杂度由集合采用的数据结构决定。
集合类型支持同时多多个元素进行增删改查，此时时间复杂度由当元素操作的时间复杂度和元素个数决定：
- Hash类型的HMGET、HMSEZT：
O(m)，同时操作m个元素 - Set类型的SADD
0.1.4.2. 范围操作
集合类型中的遍历操作，可以返回集合中所有数据：
- Hash类型的HGETALL
- Set类型的SMEMBERS
也可以返回一个范围内的部分数据：
- List类型的LRANGE：
O(n) - ZSet类型的ZRANGE：
O(n)
2.8版本，增加HSCAN操作，渐进式遍历，避免了一次性返回所有元素导致Redis阻塞。
0.1.4.3. 统计操作
集合类型对集合中所有元素个数的记录。例如LLEN和SCARD，时间复杂度O(1)，因为当集合类型采用压缩列表、双向链表、整数数组时，这些数据结构中会专门记录元素的个数。
0.1.4.4. 例外情况
某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。
对于List类型的LPOP、RPOP、LPUSH、RPUSH操作时在列表的头尾进行增删元素，通过偏移量直接定位，时间复杂度是O(1)。