Redis 是基于键值对内存数据库。
Redis 支持五种基本数据类型：String, Hash, list, set, Sorted Set.
以及三种特殊类型：GEO, BitMap, HyperLog。
String
String 的底层类型是SDS(Simple Dynamic String, 简单动态字符串)。
数据结构：
struct sdshdr {
uint32_t len; // 已用长度
uint32_t alloc; // 实际分配长度
char buf[]; // 字节数组，存放数据
};
优点是：
- 动态扩容，避免静态数组大小限制。
- len 字段使得O(1)获取数组长度。
- 检查SDS内存是否足够，避免缓冲区溢出。
- 二进制安全。不以空字符
\0判断字符串结束。
缺点是：
维护 len, alloc 字段需要额外空间，如果数据较短，额外空间占据大量内存。
list
redis3.2 以前，底层是双向链表 linkedlist 或者压缩列表 ziplist。3.2之后是快速链表 quicklist。
压缩列表底层是数组，redis 分配一块连续内存空间。每个元素保存一个数据。
表头额外三个字段：zlbytes, zltail, zllen 分别表示 字节长度，尾偏移量，长度。查找首尾元素，复杂度O(1)。
双向链表底层是链表。
如果列表对象长度均小于64字节，且元素小于512，则为压缩列表，否则双向链表。
快速链表可以认为是 linkedlist，但是节点元素是 ziplist。
用 ziplist 取代节点，使得一个节点分配更多数据，解决prev, next 指针内存占用多问题。
同时控制 ziplist 大小，避免连续内存空间太大，分配效率低。
hash
redis 维护一个全局哈希表来快速查询数据。
哈希表底层是数组+链表。通过散列将key映射到数组某个桶。桶中多个元素按照链表排列。
链表是顺序查找，如果太长，影响查询性能。redis 的解决办法是 rehash。
redis 维护两个全局哈希表。一个表是运行表，存放数据。一个表是空闲表。rehash 时，设置空闲表的长度，一般是运行表的两倍。之后将运行表的数据拷贝到空闲表。清空运行表，作为下次 rehash 的空闲表。
为了避免一次全量拷贝导致业务线程阻塞，redis 采用渐进式 hash，少量多次。
set
如果数据量不大， 且值是整数，使用inset。否则使用哈希表。
inset 类似 ziplist，都是数组加上表头字段。
zset
数据量不大，底层是 ziplist。在数组中，元素按照 score 有序存储。
数据量大，底层是 跳表。
跳表是在单向链表的基础上建立多级索引。将时间复杂度从单向链表的O(n)优化为二分查找的O(logN)。但是增加多级索引内存。
GEO
GEO 底层是 sortedset。它适用于是经纬度信息的范围查询。
对于经度纬度两个坐标，GEO采用 GEOHASH 将经纬度编码为一个值，将值作为 score 存入 sortedset。
GEOHASH：以经度为例。[-180, 180]表示经度。
第一次二分，0表示[-180, 180]的左边半部分，[-180, 0]，1表示右边半部分[0, 180]。假设选择0.[-180, 0]
第二次二分，0表示[-180, 0]的左边半部分，[-180, -90]，1表示右边半部分[-90, 0].
以此类推，将N次二分的值组装成经度编码。同样获得纬度编码。
将经度编码作为奇数位，纬度编码作为偶数位，组成一个编码。
Bitmap
bitmap 的底层是 String。可以理解为 bit 数组。每位代表一个二值状态，比如签到(0表示未签到，1表示签到)。
HyperLog
有时我们要统计集合不重复元素，比如UV.
可以用 set 去重，但是如果不重复元素太多，比如超过百万个，则占用大量存储空间。
HyperLog 使得占用少量空间计算不重复元素。
它基于概率计算，因此结果存在误差。