Redis作为内存数据库，访问速度快是最大的特点，那么，什么情况下，Redis也会变慢呢？
Redis底层数据结构
Redis有5种基本数据类型：String，List，Hash，Set，ZSet
有6种底层数据结构：
- 简单动态字符串SDS
- 压缩列表 ZipList
- 快表 QuickList
- 字典/哈希表 Dict
- 整数集 IntSet
- 跳表 ZSkipList
键值访问
Redis用了一个全局的哈希表保存所有的键值对，一个哈希表，其实是一个数组，数组里的每一个元素对应为一个哈希桶。每个哈希桶保存键值对数据。
哈希桶中元素保存的是指向值的地址指针，这样即使值是一个集合，也能通过指针找到。
如图是全局哈希表的键值访问过程：
哈希表的查找依赖哈希计算，O(1)的时间复杂度找到键值对。
为什么哈希表操作变慢了？
既然是哈希表，可能存在哈希冲突。redis解决哈希冲突的方法是链地址法，即同一个哈希桶中的多个元素用一个链表来保存，它们之间用指针相连。
看到这，肯定有个疑问，如果冲突的元素越来越多，就会导致在这个链上查找的耗时变长，对于追求快的Redis来说，这是不能接受的。
所以，Redis会对哈希表做rehash操作。可以理解为和Java里的HashMap扩容一样。增加现有哈希桶数量，让增多的元素在更多的桶之间分散保存。
redis中rehash的方法是：
1. redis默认使用了2个全局哈希表
2. 当插入数据时，默认使用哈希表1
3. 随着数据增多，redis进行rehash操作，为哈希表2分配更大的内存空间，如是哈希表1的两倍；
4. 把哈希表1中的数据重新映射到哈希表2中
5. 释放哈希表1的内存
其中 数据重新映射 这一步涉及大量数据拷贝，如果让主线程一次全部迁移完，会造成redis线程阻塞。
为了避免这一问题，redis使用了渐进式rehash
简单地说，就是在拷贝数据过程中，不是一次拷贝完。而是每处理一个请求时，从哈希表1的第一个索引位置开始，将这个位置上所有元素拷贝到哈希表2中，等处理下一请求时，再拷贝下一索引位置的数据，整个过程如下：
集合数据结构的操作
集合类型的底层结构是：整数数组，双向链表，哈希表，压缩列表，跳表
哈希表、整数列表、双向链表的操作特征都是顺序读写，操作复杂度是O(N)，效率比较低。
压缩列表：
- 类似数组，表头有3个字段zlbytes、zltail、zllen，分别表示列表长度、列表尾的偏移量、列表中entry个数。
- 表尾还有一个zlend，表示列表结束
查找定位列表的第一个元素和最后一个元素，可以通过表头3个字段的长度直接定位，复杂度O(1)，查找其他元素时，只能逐个查找了，复杂度O(N)。
跳表
- 跳表是在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位
如图所示，
- 单链表查找元素33，需要找6次；
- 增加一级索引（每两个元素选一个出来作为索引，索引再通过指针指向原始链表），只需要找4次；
- 增加二级索引（从一级索引中再抽取部分元素作为二级索引），只需要找3次；
当数据量很大时，跳表查找的复杂度是O(logN)
redis底层数据结构查找的时间复杂度如下表：
| 名称 | 时间复杂度 |
|---|---|
| 哈希表 | O(1) |
| 跳表 | O(logN) |
| 双向链表 | O(N) |
| 压缩列表 | O(N) |
| 整数数组 | O(N) |
思考：压缩列表和整数数组的查找时间复杂度比较高，为什么redis还要用它们呢？
内存利用率
数组和压缩列表都是非常紧凑的数据结构，比起链表，占用的内存更少，而redis是内存数据库，需要尽可能的优化，提高内存利用率；
数组对CPU高速缓存支持更友好
