我们都知道Redis是一种内存数据库，其支持很多数据类型的操作，比如：String(字符串)、List(集合)、Hash(哈希表)、Set（集合）和 Sorted Set（有序集合），其实这些只是Redis保存键值对的数据类型，也就是数据的保存形式，而Redis底层的数据结构并不是这些，这边文章就带大家了解一下Redis底层的数据结构。
底层数据结构
Redis底层数据结构包括：
- 动态字符串
简单的动态字符串
- 双向链表
双向链表，其实就是通过链表的指针去顺序的寻找元素，时间复杂度是O(n)，效率较低
- 压缩列表
压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。在压缩列表中，如果要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，复杂度就是 O(N) 。
- 哈希表
哈希表，学习Java的同学都知道Java中的一个集合类型HashMap就是一个哈希表，它的实现就是数组+链表的形式实现，将KV对存储在数组中，如果出现哈希冲突的时候，使用链表的形式将冲突的KV对存储。
- 跳表
跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图，我们将链表增加多级索引进行查找，也就是将链表分为多个区间，通过区间范围去查找，会增加查找效率，如果我们不使用跳表形式去查找元素，时间复杂度为O(n)，使用跳表的形式去查找时间复杂度为O(logn)
- 整数数组
整数数组，其实就类似与Java中的List，通过数组的下标去查询元素，时间复杂度是O(n)，效率较低。
下图是Redis的数据类型对应的底层数据结构，下次面试的时候可以对照有序的说出各自类型对应的结构。
时间复杂度
上述Redis底层数据结构的时间复杂度用一张图表示下
Redis如何组织键值对？
Redis为什么快，它的时间复杂度为O(1),是根据key-value对去存储数据，通过key直接可以访问到想要的数据。这里我们可以很快联想到Java中的HashMap数据结构，不错，它正是使用哈希表来保存所有的键值对，这里我们可以称它为全局哈希表。
哈希表在存储大量数据后，难免会发生哈希冲突的情况，也就是同一个元素计算的哈希值一样，会落入同一个哈希桶里，我们都知道Redis是通过链式哈希方式进行解决冲突的，也就说将冲突的哈希值对应的数据直接链到当前哈希桶下面，当然这是Redis的处理方式，Java中的HashMap实现在1.8之后，如果链表长度大于8的话，会将链表转为红黑树，提高查询效率。
在Redis存储数据量过大后，Redis对哈希表做 rehash 操作。
为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。
Redis的rehash操作步骤
- 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
- 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
- 释放哈希表 1 的空间。
Redis 渐进式 rehash
主要针对上述第二步来做优化，Redis不会将所有数据一次性的映射拷贝到哈希表2中，如果这样做的话，会导致Redis线程阻塞，无法服务其他请求。
所以Redis使用渐进式 rehash，也就是说Redis在处理客户端请求的时候，每处理一个请求的时候就会将哈希表1中的第一个索引位置开始，将该索引下的所有数据映射拷贝到哈希表2中，等待处理下一个请求时，在处理哈希表1中的下一个索引位置的所有数据。这样就会节省开销，巧妙扩容。
Redis不同操作复杂度
- 单元素操作 是指每一种集合类型对单个数据实现的增删改查操作。 如：set、get、hget、hset、hdel、等 时间复杂度为O(1)
- 范围操作 是指集合类型中的遍历操作，可以返回集合中的所有数据 如：hgetall、lrange、zset等 时间复杂度O(n)
- 统计操作，是指集合类型对集合中所有元素个数的记录 如：llen 和 scard 时间复杂度为O(1)
- 例外情况，是指某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量 相关命令:lpop、rpop、lpush、rpush。列表头尾进行操作，时间复杂度O(1)
