Redis 数据结构
##数据结构
Redis数据结构
String(字符串)、List(列表)、Hash（哈希）、Set(集合)和Sorted Set(有序集合)
Redis 底层数据结构
简单字符串、双向链表、压缩列表、哈希表、跳表和整数数组
对映关系
String: 简单动态字符串
List: 双向链表、压缩列表
Hash: 压缩列表、哈希表
Sorted Set: 压缩列表、跳表
Set: 哈希表、整数数组
Redis结构实现
键和值绑定
Redis使用哈希表保存所有键位。一个哈希表(数组)，数组的每个元素统称为一个哈希桶。每个哈希桶保存键值对数据，并且哈希桶和元素绑定通过指针的方式。
哈希冲突
哈希冲突是指两个key的哈希之后值相同，导致落在同一个哈希桶中。
解决方案
链式哈希也会叫做哈希冲突链，同一个哈希桶相同的key用一个链表来保存，然后用指针依次连接。
rehash
数据量太大哈希桶的hash链过长，导致查询时间增加。就要使用rehash扩容hash桶数量，把每个哈希桶的哈希链数据尽可能分散到更多的哈希桶。
Redis使用两个哈希表，哈希表1和哈希表2。 如果哈希表1达到阈值就会进行rehash，给哈希表2分配更大的空间。然后把哈希表1的数据重新映射到哈希表2，然后释放哈希表1。
如果把哈希表1数据一次性映射到哈希表2就会导致主线程阻塞，无法响应其他的请求
渐进式rehash
就是把哈希表1copy哈希表2数据时，分到每次请求执行。这样就会把一次性的copy数据分摊到多从处理请求，避免长时间阻塞主线程操作。·
集合数据操作效率
Redis底层数据结构时间复杂度
| 名称 | 时间复杂度 |
|---|---|
| 哈希表 | O(1) |
| 跳表 | O(logN) |
| 双向链表 | O(N) |
| 压缩链表 | O(N) |
| 整数数组 | O(N) |
特征介绍
整数数组和双向链表
操作特征都是通过顺序读写，通过数组下标或者链表的方式逐个元素访问，操作效率比较低
压缩列表
压缩列表就是一个数组，和数组不同有三个字段 zlbytes(列表长度)、zltail(列表尾的偏移量)、zllen(列表的元素个数)；表尾有zlend表示列表结束。
查询第一个和最后一个元素是可以通过表头三个字段直接定位，复杂度O(1)，其他元素就需要遍历, 复杂度O(N)。
跳表
跳表在链表基础上增加多级索引，通过索引的位置几个跳转，实现快速定位数据
跳表查询过程就是在多级索引上跳来跳去,最后定位到元素。当数据量很大时，查询复杂度O(logN)。
问题
整数数组和压缩列表在查找时间复杂度方面并没有很大的优势，那为什么 Redis 还会把它们作为底层数据结构呢？
两个方面:
- 内存利用率，数组和压缩列表都是非常紧凑的，比链表占用的内存要少。大量的数据存在内存中，提供内存的利用率。
- 数组对CPU高速缓冲比较友好，集合数据比较少，采用内存紧凑排列的方式存储。数据超过阈值后，转为哈希和跳表数据结构存储，保证查询效率。
