一、Redis底层数据结构

Redis 能以微妙级别的速度，根据 key 找到 value。Redis 为什么能这么快呢？ 当然，首先是因为 Redis 将数据都存在了内存中，内存的读取速度肯定是比磁盘高效很多的。其次，Redis 的快速也依赖于其高效的数据结构。

一、Redis 键值对索引由哈希表完成

我们都知道，Redis 是键值对保存数据的。那么 Redis 是如何保存这个键值对的呢？
实际上，Redis 使用了哈希表结构来保存所有键值对。也就是说，我们可以根据 key，在哈希表中很快找到其对应 value。
但是， key 是 String 类型，而 value 是由很多不同数据类型的，哈希表是怎么存储这些 value 的呢？
实际上，哈希表数组对应存储的，并不直接是值本身，而是指向这个值的地址的指针。也就是说，实际上哈希桶存储的是 key,value。如下图：

image.png

这个哈希表保存的是所有的键值对，称为 全局哈希表。通过这个全局哈希表，我们能很快地计算 key 对应的哈希值，找到对应的哈希桶，取出 value 的地址，再根据这个地址去访问操作 value。

哈希表的冲突与Rehash
当然，虽然数据的增加，可能会导致哈希冲突，也就是多个 key 映射到了同一个哈希桶。 Redis 这里会根据链式哈希解决冲突，也就是同一个哈希桶中的多个元素通过链表保存。
当哈希冲突越来越严重时，可能导致这个冲突链表很长。这样，就会降低 Redis 的操作效率。

所以，Redis 会对哈希表做 rehash 操作。也就是增加哈希桶的数量，再将 entry 元素重新 hash 到新的哈希桶。

实际上， Redis 是这么操作的：Redis 默认有两个全局哈希表。 一开始插入数据时，使用哈希表1，随着数据增多，Redis 使用 rehash 操作，为哈希表2分配当前哈希表1两倍的空间，再将哈希表1的数据重新映射到哈希表2中，然后再释放哈希表1的空间。

但是，rehash 的过程涉及到大量的数据拷贝。如果一次性将所有哈希表1的数据迁移到哈希表2中，必定会阻塞线程，无法处理当前请求。

所以，Redis 采用了 渐进式 rehash：
在拷贝数据到哈希表2时，Redis 照常处理请求，然后把这个请求中对应访问到的哈希桶位置的冲突链表中的 entry 拷贝到哈希表2中。 这种分摊式处理的操作就是渐进式 rehash。
这里可能有个问题，就是如果 哈希表1 上的某个 哈希桶，一直没有被访问到，那不就一直拷贝不到哈希表2 了吗？ 其实，Redis 会在空闲的时候，将哈希表1的数据迁移到哈希表2中，上面提到的场景，针对的是请求量大时，为了不阻塞当前请求而进行的操作。

二、Redis 不同的数据类型有不同的底层数据结构支持

Redis 在通过全局哈希表找到 value 对应位置以后，就对不同的数据类型进行实际操作了。
那么 Redis 不同的数据类型都有哪些底层数据结构来支持呢？
Redis 支持的数据数据结构有 string, list, hash, set, order set
其中，string 类型不是集合类的类型，直接通过简单动态字符串存储就好。
而其余的集合类数据类型，底层的数据存储结构包括：双向链表、压缩列表、哈希表、整数数组、跳表。以下是不同数据类型的底层数据结构实现：

image.png

双向链表、整数数组是很常见的数据类型了。哈希表上面也提到过了。这里主要说一下压缩列表和跳表。

压缩列表实际上和数组的区别就是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾偏移量和列表中的 entry 个数。以及在表尾还有 zlend 表示列表结束。

image.png

压缩列表比起普通数组，在操作上，就是提高了查找定位第一个元素和最后一个元素的效率。可以通过表头的三个字段直接定位。其余元素的查找依然是 O(n) 复杂度。

然后是跳表。
跳表是在链表的基础上，增加了多级索引，通过索引位置的几次跳转，实现数据的快速定位。

image.png

比起链表，跳表的查询效率大大提高到了 O(logn)