第三章 Redis核心数据结构与底层原理：SDS、跳跃表、压缩列表、quicklist

面试问题：Redis 的 String 类型为什么用 SDS 而不是 C 字符串？

面试官考察点：对Redis底层数据结构设计意图的理解、二进制安全性、与C语言的对比分析能力

回答框架：对比C字符串缺陷 → SDS数据结构（len/free/buf）→ 解决的四类问题 → 预分配策略

简短示例回答：C字符串获取长度需O(n)遍历，且空格截断不二进制安全。SDS用len字段O(1)获取长度，free字段记录未使用空间，支持预分配减少扩容次数；buf字节数组存储任意二进制数据。

可能追问：SDS预分配策略是什么？大于1MB时如何处理？

避坑提醒：不要只说“二进制安全”四个字，需解释C字符串以'\0'结尾判断长度导致无法保存图片等二进制数据。

面试问题：Redis ZSet 为什么用跳跃表实现？为什么不用红黑树或B+树？

面试官考察点：对跳跃表结构与复杂度的掌握、不同数据结构的权衡分析、Redis场景的适配性

回答框架：跳跃表结构（多层链表）→ 范围查询优势 → 与红黑树的对比 → 与B+树的对比

简短示例回答：跳跃表支持O(logN)单点操作和O(logN)范围遍历，代码实现简单、无旋转操作。红黑树范围遍历需中序遍历，跳跃表直接沿底层链表顺序扫描；B+树磁盘优化在纯内存场景无优势。

可能追问：跳跃表每层索引的节点概率是多少？Redis如何决定层高？

避坑提醒：不要只说“跳跃表比红黑树快”，要强调范围查询场景下跳跃表的链表顺序访问优势；同时承认红黑树单点插入/删除性能并不差。

面试问题：Redis List 底层是怎么实现的？quicklist 相比早期版本有什么改进？

面试官考察点：数据结构演进背景、压缩列表内存布局、quicklist的设计权衡

回答框架：早期版本（linkedlist + ziplist）→ 问题（内存碎片/指针开销）→ quicklist 结构（双向链表+多个ziplist节点）→ 参数配置（list-max-ziplist-size）

简短示例回答：Redis 3.2后List底层用quicklist，它是双向链表每个节点内嵌ziplist。避免了纯链表高指针内存开销，同时权衡了ziplist链式更新问题。通过list-max-ziplist-size控制每个ziplist长度，list-compress-depth控制压缩深度。

可能追问：压缩列表中连锁更新（cascade update）是怎么产生的？如何避免？

避坑提醒：不要认为ziplist是“压缩过的链表”，它本质是一块连续内存，通过entry长度字段查找；连锁更新概率极低，面试时说明“时间复杂度理论上较高但实际很少触发”即可。