Redis为什么可以在微秒级别响应请求 ？

一方面 是由于它是内存型的数据库，内存的操作本身就很快
另一个方面，这个就是Redis本身的数据结构造成的，因为我们对Redis的操作就是基于对数据结构的CURD等等

Redis有什么数据结构？

基本可以感知的有 String(简单动态字符串) List(双向链表) Hash(哈希) SortedSet(跳表) Set(整数数组),包括他们之间也有很大的联系，
图示 ：

这些数据结构都是值的底层实现，键和值本身之间用什么结构组织？rehash?

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。一个哈希表其实就是一个数组，数组中的每个元素称为一个哈希桶.每个哈希桶里面都存放了键值对数据,
如果过值是数据结构也是一样，因为哈希桶中元素保存的并不是值的本身，而是值的指针,如图(../img/全局哈希表.jpg)
Redis查找元素是基于Hash计算，就算有10W，100W个键，找到对应的key也是O(1)复杂度,BUT,如果往Redis中写入了太多的数据之后，操作会突然的变慢
这是由于哈希表的冲突问题和rehash可能带来的操作阻塞

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

当如果想Redis写入越来越多的数据，哈希冲突(指两个或多个key的哈希值和哈希桶计算对应关系是，正好落在了同一个哈希桶中)就是不可避免的，
通常情况下哈希桶的个数肯定是小于Key的数量

rehash解决?

v1 :redis的哈希冲突解决就是链式哈希，就是指同一个哈希桶中的多个元素用一个链表来保存，他们之间依次用指针连接，如

但是这样也无法做到一劳永逸，因为链表越长，查找元素的时间就会越长,效率会越来越低，Redis有一个更好的解决方法,Redis的Rehash操作

v2: redis_rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。
为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

1.给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
2.把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
3.释放哈希表 1 的空间。
但是这样也会存在一个问题，如果哈表1切换为哈希2，那么哈希1全量copy到哈希2，会造成Redis线程阻塞，无法是其他请求处理

v3: 渐进式rehash，简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，
顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：(../img/渐进式rehash过程.jpg)
这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

为什么集合类型有那么多的底层结构，它们都是怎么组织数据的，都很快吗？

集合类型的底层结构有五种：整数数组，双向链表，哈希表，压缩列表，跳表

重要的有压缩列表和跳表

压缩列表

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。
跳表:
有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位

不同操作的复杂度

集合类型的操作类型很多，有读写单个集合元素的，例如 HGET、HSET，也有操作多个元素的，例如 SADD，还有对整个集合进行遍历操作的，例如 SMEMBERS。这么多操作，它们的复杂度也各不相同。而复杂度的高低又是我们选择集合类型的重要依据。
1.单元素操作是基础；
2.范围操作非常耗时；
3.统计操作通常高效；
4.例外情况只有几个。

第一，单元素操作，是指每一种集合类型对单个数据实现的增删改查操作。

例如，Hash 类型的 HGET、HSET 和 HDEL，Set 类型的 SADD、SREM、SRANDMEMBER 等。这些操作的复杂度由集合采用的数据结构决定，
例如，HGET、HSET 和 HDEL 是对哈希表做操作，所以它们的复杂度都是 O(1)；
Set 类型用哈希表作为底层数据结构时，它的 SADD、SREM、SRANDMEMBER 复杂度也是 O(1)。
但是也有特殊情况，例如，如果一次SADD M个元素，那么操作复杂度就是 O(M)

第二，范围操作，是指集合类型中的遍历操作，可以返回集合中的所有数据

比如 Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，
比如 List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)，比较耗时，我们应该尽量避免。
Redis 从 2.8 版本开始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN），这类操作实现了渐进式遍历，每次只返回有限数量的数据。
这样一来，相比于 HGETALL、SMEMBERS 这类操作来说，就避免了一次性返回所有元素而导致的 Redis 阻塞。也就是说 SCAN M个元素，负责度就是 O(M)

第三,统计操作，是指集合类型对集合中所有元素个数的记录

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

第四，例外情况，是指某些数据结构的特殊记录

例如压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来，对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，
它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有 O(1)，可以实现快速操作。

什么是简单动态字符串，和常用的字符串是一回事吗？

— 后续跟新中，String是一个好朋友吗？