一、问题背景Redis 中相同数量的数据使用 hash 与 zset 存储时空间占用差异究竟有多大这是面试中常见的高频考点核心考察点在于ziplist vs skiplist vs dict三种底层数据结构的空间复杂度。二、数据结构选择规则Redis 根据节点数量动态选择底层数据结构具体阈值如下存储结构ziplist 阈值dict/skiplist 阈值hash节点数 512节点数 512zset节点数 128节点数 128核心结论节点数 128 时hash 和 zset 均使用 ziplist空间占用相同节点数 129~512 时hash 使用 ziplistzset 使用 skiplist节点数 512 时hash 使用 dictzset 使用 skiplist dict三、hash 内部数据结构3.1 ziplist压缩列表当 hash 节点数 512 时采用本质是一段连续的内存块-------------------------------------------------- | prevlen | encoding | data | prevlen | ... | --------------------------------------------------空间占用特点紧凑存储无额外指针开销prevlen 字段使用变长编码1-5字节新增/删除操作可能触发级联更新3.2 dict字典当 hash 节点数 512 时采用本质是哈希表struct dict { dictht table[2]; // 两个哈希表支持渐进式 rehash long rehashidx; // rehash 进度-1 表示未进行 long iterators; // 当前迭代器数量 };空间占用特点每个 key-value 对额外占用一个 dictEntry 指针负载因子 1 时触发扩容空间换时间存在指针开销约 16-24 字节/条目四、zset 内部数据结构4.1 ziplist压缩列表当 zset 节点数 128 时采用有序存储-------------------------------------------------- | score | member | score | member | ... | --------------------------------------------------空间占用特点score 和 member 交替存储紧凑无指针开销查询需要遍历时间复杂度 O(n)4.2 skiplist dict跳跃表 字典当 zset 节点数 128 时采用这是zset 的核心结构struct zset { dict *dict; // member - score 字典O(1) 查询 skiplist *zsl; // 跳跃表按 score 有序 };为什么需要 dictskiplist 查询 member 需要 O(n)加入 dict 后可直接 O(1) 获取 scoredict 和 skiplist 同时存储 member数据冗余五、skiplist 空间占用详解5.1 数据结构定义structskipListNode{doublescore;// 分数8字节robj*obj;// 成员对象指针8字节intbackward;// 后退指针4字节压缩指针structskipListLevel{skipListNode*forward;// 前向指针8字节unsignedintspan;// 跨度4字节}level[];// 柔性数组层数随机};5.2 层数计算公式节点层数根据以下规则随机生成// Redis 源码中的层高计算intrandomLevel(void){intlevel1;while(random()(1/4))// 1/4 概率继续增加层数level;returnlevel;}层数期望推导层数概率累积概率13/475%23/1618.75%33/644.6875%43/2561.171875%期望层数 E 1 1/4 1/16 1/64 … 4/3 层即平均层数约为 1.33 层5.3 空间占用公式对于 n 个节点的 skiplist节点总空间 n × (基础字段 指针开销)基础字段每个节点固定score: 8 字节obj 指针: 8 字节backward 指针: 4 字节每层开销平均 1.33 层forward 指针: 8 字节 × 1.33 ≈ 10.64 字节span: 4 字节 × 1.33 ≈ 5.32 字节总计约 32-36 字节/节点不含 dict六、空间对比分析6.1 阈值区间对比节点数范围hashzset结论 128ziplistziplist空间相同129~512ziplistskiplistzset 更占空间 512dictskiplist dictzset 更占空间6.2 定量空间估算假设存储 1000 个节点key value 各 16 字节数据结构每个节点开销1000节点总空间hash (dict)~48 字节~48KBzset (skiplist)~32 字节~32KBzset (dictskiplist)~80 字节~80KB关键结论zset 在使用 skiplist dict 时空间占用约为 hash 的 1.5~2 倍七、面试追问 FAQ问题回答要点Q: skiplist 为什么用空间换时间多层索引实现二分查找平均 O(log n) 而非 ziplist 的 O(n)Q: dict 和 skiplist 存储相同 member 是否冗余是但保证 O(1) 查到 score 的同时维持有序性Q: 层高公式中 1/4 的物理意义控制空间利用率层数期望常数4/3避免指数增长Q: hash 超过 512 为什么不转 skiplisthash 需要的是 O(1) 查找有序性不是核心需求Q: ziplist 触发条件为何 zset 比 hash 更早zset 需要维护有序性节点数多时遍历成本高更早切换 skiplist八、相关题目题目考察点Redis zset 为什么同时用 dict 和 skiplist数据结构设计原理skiplist 层高为什么是随机而非常数空间与时间平衡Redis 为什么不用 B 树替代 skiplist实现复杂度 vs 场景需求hash 何时从 ziplist 转为 dict阈值配置原理九、总结对比维度hashzset少量数据 (128)ziplist紧凑ziplist紧凑中等数据 (129~512)ziplistskiplist更占空间大量数据 (512)dictskiplist dict最占空间查找时间复杂度O(1)O(1) score 查询有序性无score 有序核心结论zset 在数据量大时空间占用显著高于 hash根源在于 skiplist 的多层索引结构 dict 冗余存储。这是典型的空间换时间设计权衡。根据零声教育教学写作https://github.com/0voice
hash 与 zset 空间占用对比分析
发布时间：2026/5/21 21:27:15
一、问题背景Redis 中相同数量的数据使用 hash 与 zset 存储时空间占用差异究竟有多大这是面试中常见的高频考点核心考察点在于ziplist vs skiplist vs dict三种底层数据结构的空间复杂度。二、数据结构选择规则Redis 根据节点数量动态选择底层数据结构具体阈值如下存储结构ziplist 阈值dict/skiplist 阈值hash节点数 512节点数 512zset节点数 128节点数 128核心结论节点数 128 时hash 和 zset 均使用 ziplist空间占用相同节点数 129~512 时hash 使用 ziplistzset 使用 skiplist节点数 512 时hash 使用 dictzset 使用 skiplist dict三、hash 内部数据结构3.1 ziplist压缩列表当 hash 节点数 512 时采用本质是一段连续的内存块-------------------------------------------------- | prevlen | encoding | data | prevlen | ... | --------------------------------------------------空间占用特点紧凑存储无额外指针开销prevlen 字段使用变长编码1-5字节新增/删除操作可能触发级联更新3.2 dict字典当 hash 节点数 512 时采用本质是哈希表struct dict { dictht table[2]; // 两个哈希表支持渐进式 rehash long rehashidx; // rehash 进度-1 表示未进行 long iterators; // 当前迭代器数量 };空间占用特点每个 key-value 对额外占用一个 dictEntry 指针负载因子 1 时触发扩容空间换时间存在指针开销约 16-24 字节/条目四、zset 内部数据结构4.1 ziplist压缩列表当 zset 节点数 128 时采用有序存储-------------------------------------------------- | score | member | score | member | ... | --------------------------------------------------空间占用特点score 和 member 交替存储紧凑无指针开销查询需要遍历时间复杂度 O(n)4.2 skiplist dict跳跃表 字典当 zset 节点数 128 时采用这是zset 的核心结构struct zset { dict *dict; // member - score 字典O(1) 查询 skiplist *zsl; // 跳跃表按 score 有序 };为什么需要 dictskiplist 查询 member 需要 O(n)加入 dict 后可直接 O(1) 获取 scoredict 和 skiplist 同时存储 member数据冗余五、skiplist 空间占用详解5.1 数据结构定义structskipListNode{doublescore;// 分数8字节robj*obj;// 成员对象指针8字节intbackward;// 后退指针4字节压缩指针structskipListLevel{skipListNode*forward;// 前向指针8字节unsignedintspan;// 跨度4字节}level[];// 柔性数组层数随机};5.2 层数计算公式节点层数根据以下规则随机生成// Redis 源码中的层高计算intrandomLevel(void){intlevel1;while(random()(1/4))// 1/4 概率继续增加层数level;returnlevel;}层数期望推导层数概率累积概率13/475%23/1618.75%33/644.6875%43/2561.171875%期望层数 E 1 1/4 1/16 1/64 … 4/3 层即平均层数约为 1.33 层5.3 空间占用公式对于 n 个节点的 skiplist节点总空间 n × (基础字段 指针开销)基础字段每个节点固定score: 8 字节obj 指针: 8 字节backward 指针: 4 字节每层开销平均 1.33 层forward 指针: 8 字节 × 1.33 ≈ 10.64 字节span: 4 字节 × 1.33 ≈ 5.32 字节总计约 32-36 字节/节点不含 dict六、空间对比分析6.1 阈值区间对比节点数范围hashzset结论 128ziplistziplist空间相同129~512ziplistskiplistzset 更占空间 512dictskiplist dictzset 更占空间6.2 定量空间估算假设存储 1000 个节点key value 各 16 字节数据结构每个节点开销1000节点总空间hash (dict)~48 字节~48KBzset (skiplist)~32 字节~32KBzset (dictskiplist)~80 字节~80KB关键结论zset 在使用 skiplist dict 时空间占用约为 hash 的 1.5~2 倍七、面试追问 FAQ问题回答要点Q: skiplist 为什么用空间换时间多层索引实现二分查找平均 O(log n) 而非 ziplist 的 O(n)Q: dict 和 skiplist 存储相同 member 是否冗余是但保证 O(1) 查到 score 的同时维持有序性Q: 层高公式中 1/4 的物理意义控制空间利用率层数期望常数4/3避免指数增长Q: hash 超过 512 为什么不转 skiplisthash 需要的是 O(1) 查找有序性不是核心需求Q: ziplist 触发条件为何 zset 比 hash 更早zset 需要维护有序性节点数多时遍历成本高更早切换 skiplist八、相关题目题目考察点Redis zset 为什么同时用 dict 和 skiplist数据结构设计原理skiplist 层高为什么是随机而非常数空间与时间平衡Redis 为什么不用 B 树替代 skiplist实现复杂度 vs 场景需求hash 何时从 ziplist 转为 dict阈值配置原理九、总结对比维度hashzset少量数据 (128)ziplist紧凑ziplist紧凑中等数据 (129~512)ziplistskiplist更占空间大量数据 (512)dictskiplist dict最占空间查找时间复杂度O(1)O(1) score 查询有序性无score 有序核心结论zset 在数据量大时空间占用显著高于 hash根源在于 skiplist 的多层索引结构 dict 冗余存储。这是典型的空间换时间设计权衡。根据零声教育教学写作https://github.com/0voice
