高效的数据结构
都知道redis快，那为什么redis可以这么快？微秒级
一方面是因为纯内存访问。另一方面，也是更关键的点是redis采用的高效的数据接口。
这一块是很值得学习的。不是总说数据结构和算法没用吗？
redis主要有5中数据类型：string，list，hash，set，sorted set
每种类型都用自己的底层实现数据结构
这是值的数据结构。
redis找到数据，首先要解决键找到值的问题。
redis使用哈希表来保存所有的键值对。
哈希表最大的好处就是可以用O(1)的时间复杂度来查找键值对。
但是当哈希表中数据太多，哈希冲突不可避免。哈希值相同的key放在同一个哈希桶中。
Redis解决哈希冲突的方式就是链式哈希。就是同一个哈希桶中的多个元素用链表来保存。
这样会有另一个问题，当这个桶里的数据越来越多，链越来越长。我们知道链的特性是插入快，查询慢。
所以Redis会对哈希表做rehash操作。rehash会增加桶的数量。
rehash
redis的具体做法，redsi默认使用两个哈希表，哈希表1和哈希表2。
最开始一直使用哈希表1。哈希表2还是空的，没有分配空间。当哈希表1中数据逐渐增多，达到一个阈值。开始进行rehash
- 给哈希表2分配更大的空间。比如2倍
- 把哈希表1中的数据拷贝到哈希表2中，同时重新进行hash映射
- 切换到哈希表2，释放哈希表1的空间
这里的难点在第二步，如果一次性全量copy，会造成redis线程阻塞。redis的方案时进行渐进式rehash
渐进式rehash
简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求 时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝 到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries
rehash是以bucket(桶)为基本单位进行渐进式的数据迁移的，每步完成一个bucket的迁移，直至所有数据迁移完毕
因为在进行渐进式 rehash 的过程中， 会同时使用两个哈希表， 所以在渐进式 rehash 进行期间， 删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 h哈希表1 里面进行查找， 如果没找到的话， 就会继续到 哈希表2 里面进行查找， 诸如此类。
另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到哈希表2 里面， 而 哈希表1 则不再进行任何添加操作： 这一措施保证了 哈希表1包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。
什么时候做 rehash
Redis 会使用装载因子（load factor）来判断是否需要做 rehash。
装载因子的计算方式 是，哈希表中所有 entry 的个数除以哈希表的哈希桶个数。Redis 会根据装载因子的两种 情况，来触发 rehash 操作：
装载因子≥1，同时，哈希表被允许进行 rehash；
装载因子≥5
在第一种情况下，如果装载因子等于 1，同时我们假设，所有键值对是平均分布在哈希表 的各个桶中的，那么，此时，哈希表可以不用链式哈希，因为一个哈希桶正好保存了一个 键值对。 但是，如果此时再有新的数据写入，哈希表就要使用链式哈希了，这会对查询性能产生影 响。在进行 RDB 生成和 AOF 重写时，哈希表的 rehash 是被禁止的，这是为了避免对 RDB 和 AOF 重写造成影响。如果此时，Redis 没有在生成 RDB 和重写 AOF，那么，就 可以进行 rehash。否则的话，再有数据写入时，哈希表就要开始使用查询较慢的链式哈希 了。
在第二种情况下，也就是装载因子大于等于 5 时，就表明当前保存的数据量已经远远大于 哈希桶的个数，哈希桶里会有大量的链式哈希存在，性能会受到严重影响，此时，就立马 开始做 rehash。 刚刚说的是触发 rehash 的情况，如果装载因子小于 1，或者装载因子大于 1 但是小于 5， 同时哈希表暂时不被允许进行 rehash（例如，实例正在生成 RDB 或者重写 AOF），此 时，哈希表是不会进行 rehash 操作的。
采用渐进式 hash 时，如果实例暂时没有收到新请求，是不是就不做 rehash 了？
其实不是的。Redis 会执行定时任务，定时任务中就包含了 rehash 操作。所谓的定时任 务，就是按照一定频率（例如每 100ms/ 次）执行的任务。 在 rehash 被触发后，即使没有收到新请求，Redis 也会定时执行一次 rehash 操作，而 且，每次执行时长不会超过 1ms，以免对其他任务造成影响。
渐进式rehash的问题
在rehash时，需要分配一个新的hash表，在rehash期间，同时有两个hash表在使用，会使得redis内存使用量瞬间突增，在Redis 满容状态下由于Rehash会导致大量Key驱逐。
通过key找到了value。如果value是string，那么取出来就行了。
如果是其他四种集合类型，对集合进行操作又涉及了不同的数据结构。
比如哈希表结构要比链表结构的访问效率更高。
从上图中，看到redis的集合有5中底层的数据结构：哈希表，数组，双向链表，压缩列表，跳表。
数据类型和底层数据结构
整数数组
整数数组和压缩列表的设计，充分体现了 Redis“又快又省”特点中的“省”，也就是节 省内存空间。整数数组和压缩列表都是在内存中分配一块地址连续的空间，然后把集合中 的元素一个接一个地放在这块空间内，非常紧凑。因为元素是挨个连续放置的，我们不用 再通过额外的指针把元素串接起来，这就避免了额外指针带来的空间开销。
压缩列表
压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同 的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的 偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。
在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段 的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查 找，此时的复杂度就是 O(N) 了。
每个元素的元数据的内容
prev_len，表示前一个 entry 的长度。prev_len 有两种取值情况：1 字节或 5 字节。 取值 1 字节时，表示上一个 entry 的长度小于 254 字节。虽然 1 字节的值能表示的数 值范围是 0 到 255，但是压缩列表中 zlend 的取值默认是 255，因此，就默认用 255 表示整个压缩列表的结束，其他表示长度的地方就不能再用 255 这个值了。所以，当上 一个 entry 长度小于 254 字节时，prev_len 取值为 1 字节，否则，就取值为 5 字节。
len：表示自身长度，4 字节；
encoding：表示编码方式，1 字节；
content：保存实际数据。
这些 entry 会挨个儿放置在内存中，不需要再用额外的指针进行连接，这样就可以节省指 针所占用的空间。
跳表
有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳 表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，
当数据量很大时，跳表的查找复杂度就是 O(logN)。
Hash 类型底层结构什么时候使用压缩列表，什么时候使用哈希表呢？
Hash 类型设置了用压缩列表保存数据时的两个阈值，一旦超过了阈值，Hash 类型就会用哈希表 来保存数据了。
hash-max-ziplist-entries：表示用压缩列表保存时哈希集合中的最大元素个数。
hash-max-ziplist-value：表示用压缩列表保存时哈希集合中单个元素的最大长度。
如果我们往 Hash 集合中写入的元素个数超过了 hash-max-ziplist-entries，或者写入的 单个元素大小超过了 hash-max-ziplist-value，Redis 就会自动把 Hash 类型的实现结构 由压缩列表转为哈希表。
不同操作的复杂度
口诀：
1 | 单元素操作是基础； |
范围操作的复杂度一般是 O(N)，比较耗时， 我们应该尽量避免
不过，Redis 从 2.8 版本开始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN），这类操作实现了渐进式遍历，每次只返回有限数量的数据。这样一来，相比于 HGETALL、SMEMBERS 这类操作来说，就避免了一次性返回所有元素而导致的 Redis 阻 塞。