5 种基本数据结构底层编码、String 44 字节分界线推导、跳表 vs 红黑树、渐进式 rehash。

Redis 数据结构与底层

校招考察频度：★ 高频（核心必背·高频生死线） 一句话速记：String 内部三大件（int/embstr/raw，44 字节界限定一次内存分配）；ZSet 双剑合璧（跳表区间查，dict 秒查分）；Hash 渐进式 rehash 双表平滑迁移防阻塞。

Redis 之所以被称为高性能内存数据库之王，其优雅紧凑的数据结构与底层内存编码居功至伟。面试官问 Redis，第一问通常从“每种类型的底层实现、以及为什么这么设计”开始深挖。

一、String（字符串）内部编码与 44 字节推导（绝杀考点！）

面试官：“Redis 的 String 底层就是 SDS 吗？它有几种内部编码？为什么以 44 字节为界？”

String 内部实际上有 3 种编码：

embstr 与 raw 内存分配布局对比

Redis 默认使用 jemalloc 作为底层内存分配器。jemalloc 在分配内存时，有一套固定档位：8, 16, 32, 64 字节。为了尽量省内存，Redis 期望将一个字符串对象塞进 64 字节 的最小常用内存块里。
redisObject 占用 16 字节：
- type（4 bit） + encoding（4 bit） + lru/lfu（24 bit） = 4 字节
- refcount（引用计数） = 4 字节
- *ptr（数据指针） = 8 字节（64 位系统）
- 合计：4 + 4 + 8 = 16 字节。
SDS 头部（sdshdr8）占用 3 字节：
- len（1 字节） + alloc（1 字节） + flags（1 字节） = 3 字节。
C 字符串末尾必须保留的 \0 占 1 字节。
最终计算：64 字节 - 16字节(redisObject) - 3字节(sdshdr8) - 1字节('\0') = 44 字节！
收益：小于等于 44 字节时，embstr 只需要调用 1 次 malloc 即可在连续内存中分配完毕，CPU 缓存命中率（Cache Locality）极高；超过 44 字节则退化为 raw，需要调用 2 次 malloc 分别分配。

基本类型	底层编码实现	编码转换条件与机制
String	`int`、`embstr`、`raw`	整数走 int；长短字符串以 44 字节为界在 embstr 和 raw 之间切换。
List	quicklist（快速列表，Redis 3.2+） 7.0+ 内部引入 listpack	quicklist 是由双向链表和紧凑列表组合而成：外部是链表，每个链表节点内是一个连续的 ziplist/listpack，兼顾增删效率与紧凑内存。
Hash	listpack（元素少且值小） hashtable（哈希表）	当键值对少于 512 个且所有值长度小于 64 字节时用紧凑压缩格式；超限转为 hashtable。
Set	intset（整数集合） hashtable（哈希表）	所有元素均为整数且数量少于 512 个时，用紧凑有序的 intset（二分查找）；否则转 hashtable。
ZSet	listpack（元素少且值小）跳表（skiplist） + dict（字典）	元素少于 128 个且每个元素小于 64 字节用紧凑格式；否则采用跳表+字典双结构。

跳表是在有序单链表之上，通过为每个节点随机生成层高（概率投硬币法），建立起多级稀疏索引通道，查找时间复杂度达到 $O(\log n)$ 。

跳表多层索引结构：空间换时间实现 O(log n) 查找

区间范围查询（ZRANGEBYSCORE）更简单高效：
在跳表中做范围查询，只需要 $O(\log n)$ 找到区间的左边界节点，然后沿着第 1 层的双向链表顺序向后遍历即可，性能极高；而红黑树必须进行中序遍历（In-order Traversal），跨节点来回回溯，实现复杂且 CPU 缓存不友好。
实现简单、更易维护：
红黑树插入删除节点时，需要频繁进行变色（Re-color）和极其繁琐的左旋右旋（Rotation）来保持平衡；而跳表的层高是通过纯随机数决定的，插入节点只需修改相邻几层的指针，无需全局重平衡。
并发友好（扩展性）：
跳表在需要支持并发时（如无锁并发跳表），只需要对局部相邻节点加锁即可；红黑树一次旋转可能波及整个树的大片节点，锁粒度极大。

跳表擅长范围查找和排名操作（ $O(\log n)$ ）；
但如果业务想以 $O(1)$ 速度直接查询“某个用户的分数是多少（ZSCORE key member）”，跳表依然需要 $O(\log n)$ 。因此 Redis 额外附带一个 dict 字典，存储 member -> score 映射，实现 $O(1)$ 查分！

当 Hash 表需要扩容或收缩时，Redis 不会一次性把 ht[0] 的所有键值对全量迁移到 ht[1]，否则如果有数百万个 Key，会直接导致单线程主循环卡死数十秒！

平滑迁移三步走：

为 ht[1] 分配更大内存空间，将内部计数器 rehashidx 置为 0，标记开始 rehash。
在 rehash 期间，每次对字典执行增删改查时，顺带把 ht[0] 在 rehashidx 索引位置上的桶节点全部迁移到 ht[1]，然后 rehashidx++；同时后台定时任务也会定期迁移一点。
读写规则：
- 插入操作：直接写入 ht[1]，保证 ht[0] 只减不增；
- 查找/更新/删除操作：先查 ht[0]，找不到再查 ht[1]。
随着业务操作的持续进行，ht[0] 最终被彻底搬空，释放 ht[0] 内存，将 ht[1] 设为新的 ht[0]，rehash 结束。