数据结构与底层实现
Redis 的价值一半在数据结构：每种类型底层有多种编码，按数据特征自动切换。面试主线：每种类型的底层实现、为什么 zset 用跳表。
5 种基本类型
| 类型 | 底层编码 | 切换条件 |
|---|---|---|
| string | SDS（简单动态字符串） | 无切换，始终 SDS |
| list | 3.2 前 ziplist 链 3.2+ quicklist（内部 ziplist 节点） 7.0+ listpack |
元素少时压缩，多时链表 |
| hash | listpack / hashtable | 元素少或值小时压缩 |
| set | intset / hashtable | 全整数且少时 intset |
| zset | listpack / 跳表 + dict | 元素少时压缩 |
- SDS：C 字符串的升级版，记录长度、预分配空间、二进制安全，避免 O(n) 求长和缓冲区溢出
- listpack/ziplist：连续内存紧凑存储，省内存但读写要移位，所以只在元素少时用
- intset：有序整数数组，二分查找，全整数集合的省内存方案
- hashtable：渐进式 rehash，扩容时新旧表并行，逐步迁移避免一次性阻塞
跳表：zset 的核心
跳表:多层链表加速查找
跳表是多层有序链表：底层全量有序，上层是稀疏的“快速通道”。查找从顶层开始，逐层下降，期望复杂度 O(log n)。
为什么 zset 用跳表 + dict 双结构：
- dict 存成员到分数的映射，O(1) 查分数
- 跳表按分数排序，O(log n) 范围查询、排名
- 为什么不用红黑树/平衡树：跳表实现简单、调试容易、范围查询天然友好；内存上每层指针的代价可接受。Redis 作者明确说过这是工程取舍
zset 同分时按成员字典序排序。
高级类型
| 类型 | 底层 | 用途 |
|---|---|---|
| bitmap | string 的位操作 | 签到、在线状态，省内存 |
| HyperLogLog | 概率结构 | 亿级 UV 统计，误差约 0.81%，固定 12KB |
| GEO | geohash 编码进 zset | 附近的人 |
| Stream | 紧凑链表 | 消息队列（见高级应用篇） |
| Bitfield | 位域操作 | 计数器压缩 |
面试追问
- zset 为什么用跳表？ 有序范围查询天然适合，实现比平衡树简单。加 dict 保证成员查分数 O(1)
- SDS 比 C 字符串强在哪？ 记录长度 O(1) 求长、预分配减少扩容、二进制安全（可存 \0）
- ziplist 什么时候变链表？ 元素数量或单个元素大小超过阈值。压缩编码省内存但写复杂
- 渐进式 rehash 是什么？ 扩容不一次性迁移，新旧表并存，每次操作搬一点，避免大表扩容阻塞
- HyperLogLog 的精度？ 12KB 内存统计上亿基数，标准误差 0.81%。不能精确计数，要精确就用 string 计数