redis性能为何如此突出？

1. 纯内存操作，内存操作本身就很快。
2. 键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，所以高效的数据结构是 Redis 快速处理数据的基础。

redis类型有哪些？

1. string 字符串
2. list 列表
3. hash 哈希
4. set 集合
5. sorted set 有序集合

底层数据结构有哪些及分别对应了哪些类型？

1. 简单动态字符串
2. 双向链表
3. 压缩列表
4. 哈希表
5. 跳跃表
6. 整数数组

类型对应的数据结构

String 类型的底层实现只有简单动态字符串。而 List、Hash、Set 和 Sorted Set (四种类型称为集合类型)，两种底层数据结构实现，特点是一个键对应了一个集合的数据。

键和值用什么结构去组织，怎么快速找到键的？

一个全局哈希表(可以理解为数组)，数组的key是计算出来的哈希值，元素是哈希桶，哈希桶保存了键值指针，*key和*value，所以在查找键的速度还是很快的。

全局哈希表

全局哈希表带来的问题

1. hash冲突

我们知道hash值计算必然会产生冲突的问题，redis采用了下拉式解决哈希冲突，也称之为链式哈希。

哈希冲突解决方式

这种解决方式在数据量可能会引起哈希表冲突过多，会导致某个链上效率低下。

哈希表冲突多，链上效率变慢？

redis采用rehash，默认使用两张哈希表，当第1张哈希表冲突过多时，采用rehash，rehash分三步:

• 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
• 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
• 释放哈希表 1 的空间。
  至此，哈希表1留作下次的rehash时使用。

redis单线程，如果rehash(第二步)到2表数据量大时造成严重阻塞？

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

渐进式rehash

什么是压缩列表？

压缩列表

• zlbytes(列表长度)
• zltail(列表尾的偏移量)
• zllen列表的 entry 个数
• zlend(列表结束)
  查找第一个元素和最后一个元素O(1)，其他元素O(N)

什么是跳表？

增加多级索引。

跳表

结构复杂度

回归题目答案总结

• 单元素操作是基础
  如：(hash类型HGET、HSET 和 HDEL，Set 类型的 SADD、SREM、SRANDMEMBER)，都为O(1),如果同时添加多个元素此时为O(N)

• 范围操作很耗时
  如：Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者范围类如List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。O(N),可以尝试使用SCAN解决，避免一次返回所有数据阻塞。

• 统计操作通常高效
  集合类型对集合中所有元素个数的记录，例如 LLEN 和 SCARD。这类操作复杂度只有 O(1)，压缩列表、双向链表、整数数组这些数据结构时，记录了总数

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