从 ZSet 到 InnoDB：跳表、B+ 树与红黑树的工程取舍

Redis ZSet 用跳表，InnoDB 用 B+ 树，HashMap 冲突多了会转红黑树。这几句话记住很容易，放在一起却有一个疑问：它们都能在对数时间内查找，为什么不统一用一种结构？

差别藏在查询里。“查一个用户”可能是按 ID 取资料，也可能是按分数找排名；“读一批数据”可能是内存里追几十个指针，也可能需要把磁盘上的几十个页调入内存。数据结构承担的任务不同，复杂度符号只表达了其中一部分。

我用一个积分排行榜贯穿这篇文章：用户资料按 ID 查，积分实时更新，页面展示前十名和自己的排名，数据库保存可追溯的明细。沿着这几种访问，把三个系统放回各自的位置。实现细节以 Redis 7.2.5、OpenJDK 17.0.12 和 MySQL 8.4 文档为边界；版本限定是为了让读者能对照源码，不代表这些版本永远是部署首选。

一、先写查询，再讨论结构

假设一个活动有百万级参与用户。前端打开榜单时，需要拿到前十名的用户 ID 和分数，再补头像、昵称；用户提交任务后积分上涨，需要尽快看到自己的名次。活动结束后，运营还要查询某个积分区间中的用户，核对获奖资格。

这些操作至少有四种不同的定位方式。按用户 ID 查询，只关心这个名字是否存在；按积分查询，关心一个有序区间；按排名查询，关心有序集合中的位置；写入积分，则要同时改变用户的当前值和他在顺序里的位置。把它们笼统写成“增删改查”，会丢掉结构选择最重要的信息。

例如用 HashMap<Long, Long> 保存用户积分，get(userId) 很自然，但前十名需要遍历全部用户并挑出最大值，自己的名次也要统计有多少人排在前面。如果在每次读榜时做一次全量排序，读请求承担了排序成本；若旁边再维护有序索引，写请求承担同步更新成本。这个选择取决于读写比例、结果新鲜度和内存预算，无法由“HashMap 是 O(1)”直接决定。

再看数据库。如果建立 (activity_id, score, user_id) 索引，它可以服务某个活动中的积分排序，但查询某个用户的记录更适合 (activity_id, user_id)。两个索引接受同一次业务写入，分别优化两类读路径。索引数量增加，存储和更新成本也会增加。

访问需求	必须维护什么	单靠哪种结构不够
按用户 ID 取积分或资料	ID 到值的映射	按分数排序的普通树无法直接按 ID 定位
前十名、积分区间	按业务键排列的全局顺序	哈希表没有积分顺序
第几名、某一名是谁	顺序以及区间内元素数量	普通有序结构未必有子树计数或跨度
持久保存、事务更新	页布局、日志、并发控制	内存树本身不提供崩溃恢复

这张表里的“维护什么”比结构名更稳定。未来换语言、换数据库，仍然要回答：读请求给了什么条件，结构凭什么跳过无关数据，写请求要修复哪些索引状态。

已有的 Redis 内部编码、MySQL 联合索引和 HashMap 源码文章分别讨论过单个系统。这里把它们放在相同的访问需求下，比较各自需要维护的状态和成本。

二、同样的 O(log N)，访问单位可能完全不同

二分搜索、平衡二叉树和跳表都能减少比较次数。但一次比较后发生什么，决定了真实代价：数组可以直接计算地址，指针结构要读取下一个节点，数据库可能要先取得一整页。CPU、内存和存储之间的成本差距，会把相同的渐进复杂度拉开。

假设有一百万个键。完全平衡的二叉树大约需要二十层才能覆盖这个数量级；这只是高度估算，红黑树的高度上界并不等于完全平衡树。若每个节点恰好分散在不同的冷页中，一条路径会接触很多页。把许多分隔键放在同一个节点里，让一个节点拥有数百个子节点，树就能更浅。数据库 B+ 树重视的高扇出，首先服务于减少页访问。

做一个纯数学模型：内部节点扇出为 200，每个叶页容纳 100 条记录。三层结构“根 → 内部页 → 叶页”最多覆盖约 200 × 200 × 100 = 4,000,000 条记录。这里的数字是模型参数，不是 MySQL 实测容量。实际扇出受索引键长度、页头、记录格式、填充率、变长字段和主键长度影响；根页和内部页也可能已经驻留内存。

内存里的指针跳转同样不免费。CPU 通常按缓存行搬运数据，连续数组一次载入的附近内容可能马上用到；链表和树的节点如果分散分配，下一次访问未必命中 CPU Cache。分支预测、对象头、分配器、GC 和比较函数也会影响结果。不能因为都在内存，就把这些成本当作零。

这还解释了一个看似反常的实现：小集合用线性扫描。扫描几十个紧凑元素的 O(N)，可能比先计算哈希、再访问桶、再追独立节点更省空间，也可能更快。只有实际规模和工作负载能确定交叉点。Redis 小对象采用紧凑编码，正是在主动接受有限扫描成本。

分析一个结构时，我会把成本拆成定位、读取结果、更新结构、分配空间几个部分。查询复杂度写着 O(log N + M)，其中 M 是返回元素数；即使起点定位极快，返回几十万条记录仍要遍历、编码和传输。结构不会替业务消掉输出成本。

另外，数学上的一次节点访问不等于一次物理磁盘 I/O。InnoDB 先经过 Buffer Pool，操作系统和存储设备也有自己的缓存。反过来，Buffer Pool 命中并不意味着没有成本：查页、锁存、比较、解码记录依然消耗 CPU。MySQL Buffer Pool 文档描述的是页缓存；CPU Cache 讨论的则是更小的硬件访问单位，两者不能混为同一个“缓存命中率”。

三、ZSet 为什么同时保留字典和跳表

ZSet 的业务语义是：member 唯一，每个 member 关联一个 score，整个集合按照分数有序。分数相同可以容纳多个成员，再按 member 的字节序决定先后。对于大集合，Redis 7.2.5 把两种访问路径组合起来：字典按 member 找分数，跳表按 (score, member) 维护顺序。两份索引共享成员字符串，不需要把字符串内容复制两遍。Redis 7.2.5 的 ZSet 源码可以对照 zsetScore、zsetAdd 和 zslInsert 阅读。

ZSet 中按成员定位与按分数排序是两条访问路径

图中同一个 member 从两个方向被定位。客户端问“用户 C 的分数是多少”，给的条件只有 C，字典适合直接查；客户端问“分数在 20 到 40 的用户有哪些”，给的条件属于排序维度，跳表可以先找到区间起点，再顺序向后读。只保留跳表，按 member 查就缺少分数这个定位条件；只保留字典，分数区间就需要全量扫描。

跳表可以从有序链表理解。最底层包含所有元素，高层抽出部分元素建立更稀疏的前向连接。查找时先沿高层跳过大段小于目标的元素，下一跳会越界就下降一层，直到底层找到位置。新元素的层高随机生成，从而在统计意义上保持层级稀疏，不需要像红黑树一样维护旋转规则。

这种随机化给的是期望对数复杂度，不能说每一次操作都具有严格的对数上界。极端层高分布下，跳表仍有线性退化的可能。实际实现还要限制最高层数，承担随机数生成和额外前向指针的成本。这里“实现相对直接”是工程上的理由，不是一个足以证明所有负载都更快的定理。

Span 让排名不必从头数到尾

有序链表可以找前后关系，但回答“这是第几名”需要额外信息。Redis 跳表的每层连接还维护 span，表示沿这次连接跨过多少个底层成员。按 score 和 member 查找时，把经过连接的跨度相加，就能得到位置；反过来，按目标排名查找，可以根据累计跨度判断能否继续向前跳。

例如底层为 A、B、C、D、E，从表头的一条高层连接直接到 D，跨度对应跨过的底层位置数。再向 E 前进一个跨度，就得到 E 的位置。图示位置按从一开始计数，Redis 命令返回的 rank 则从零开始；源码 zslGetRank 与命令层的减一转换要分开看。

插入 B 和 C 之间的新成员时，变化不只是一条底层 next。跨过插入点的高层 span 也要加一，真正插入新节点的层要拆分原跨度。删除执行相反调整。排名快，是因为写路径提前维护了计数信息，并不是因为“有序”天然包含排名能力。

这件事可以迁移到红黑树或 B+ 树：给节点维护子树大小，也能做 order-statistics 查询。代价是每次更新都要修复计数，并处理并发可见性。普通 InnoDB 索引没有为每个业务排名提供这样一个可直接使用的精确序号，因此“找到排序起点”和“直接跳到第十万名”是不同需求。

一次改分数会修复哪些状态

用户 C 从 30 分涨到 55 分，字典先确认 C 已经存在，并取得旧分数。跳表需要检查新分数是否仍落在原先邻居之间；Redis 有可以原地更新分数的路径，位置必须变化时才删除旧位置并重新插入。字典里的分数引用也要与新节点保持一致。

这类更新的风险来自索引一致性：如果业务自行用 Hash 加另一份排序索引，跨两条命令更新就可能出现“资料已更新、榜单仍旧”的中间状态。ZSet 把两条索引的维护封装在单次命令内部，但它不负责数据库和 Redis 之间的跨系统事务，也不自动避免一次业务事件被重复计分。

Redis 的命令执行模型也不能被跳表的潜在并发实现替代。跳表可以设计成并发结构，并不证明 Redis 正是因为需要并发改同一棵跳表而选择它。把数据结构的可能性写成产品的设计动机，需要额外证据。

四、小集合的紧凑编码与跳表的替代方案

只有几个成员时，字典桶、跳表节点、各层指针和独立内存分配会显得昂贵。Redis 使用 Listpack，把 member 和 score 成对、按序放在紧凑内存里。按成员查找和插入位置需要扫描，但少量数据可以接受；内存布局更紧凑，也减少了指针和分配开销。

官方内存优化文档给出的常见默认边界是 zset-max-listpack-entries 128 和 zset-max-listpack-value 64。这是版本与配置边界，不是 ZSet 永久不变的数学性质，更不是可以不经测试调到百万的参数。增加紧凑编码上限，会把更多操作留在线性扫描和内存搬移路径上。Redis 内存优化文档也提醒，扩大编码范围后应测试转换和操作成本。

在独立测试实例中，可以用下面的命令观察编码。它们会创建测试 Key，不要复制到保存业务数据的实例里。OBJECT ENCODING 的具体结果取决于版本、集合大小和配置。

redis-cli ZADD demo:ranking:small 10 A 20 B 30 C
redis-cli OBJECT ENCODING demo:ranking:small
redis-cli MEMORY USAGE demo:ranking:small
redis-cli CONFIG GET zset-max-listpack-entries zset-max-listpack-value

让集合超过当前阈值，再观察编码与内存，就能区分“接口类型”和“内部表示”。TYPE 仍然返回 zset，OBJECT ENCODING 才暴露实际路径。测试时还应记录成员字符串长度、分数和版本，否则两个人测到不同内存占用，无法判断是结构差异还是数据差异。

红黑树也能承担大 ZSet 的有序索引。它是一种近似平衡的二叉搜索树，通过颜色约束和局部旋转控制高度，避免普通二叉搜索树在递增插入后退化成链表。用 (score, member) 作为完整排序键，可以定位积分区间；增加子树计数，可以支持排名；再配字典，可以按 member 快速找旧分数。

跳表更容易把顺序遍历表达成底层前向链接，红黑树则给出确定性的高度约束。这两者都可以继续做内存布局优化，也都需要处理写入后的结构维护。仅仅说“红黑树不能做范围查询”是错误的；区别在访问代价、增补元数据、实现复杂度和实际测试结果。

如果集合读多写少，排序数组也是候选。二分查起点，再连续遍历，局部性很好；插入中间则可能搬移大量元素。批量构建、周期重排的榜单，与每秒持续改分的榜单，完全可以采用不同布局。结构选择应包含这个经常被忽略的朴素方案。

五、InnoDB 把有序结构组织成页

InnoDB 面临的是持久化记录。数据可能大于内存，存储读写以页为重要单位。它的普通索引采用教科书通常称为 B+ 树的组织方式：内部页负责导航，叶页保存索引记录。MySQL 文档使用 B-tree 这个术语，不能因为文档少了加号就断言它是“内部节点也存完整业务记录”的另一种教科书布局。空间索引采用 R-tree，也不应一并算成 B+ 树。InnoDB 索引物理结构给出默认索引页大小 16KB，并说明页大小在初始化实例时确定。

InnoDB 的页导航、叶页范围扫描与二级索引回表

图中内部页不是“一个分隔键对应一个单独磁盘对象”。一页里放许多分隔记录，取得页面后可以在页内继续定位，把下一层的选择尽量集中完成。叶页按键顺序连接，范围查询找到第一条满足条件的记录后，可沿叶层向后扫描。逻辑相邻的页不保证物理磁盘地址连续，顺序扫描仍可能触发更多读页，但无需对每条结果都从根重新导航。

聚簇索引和二级索引存的不是同一种叶记录

在有显式主键的表里，聚簇索引按主键组织，叶记录包含行数据。二级索引叶记录包含索引列和对应的主键值。沿二级索引找到了 score，若查询还要 nickname 而索引不能覆盖，就需拿主键再到聚簇索引取行，这个过程常被称为回表。聚簇与二级索引文档明确了这两类叶记录的区别。

这会影响主键选择。主键很长，多个二级索引里携带的主键也会变长，占更多页；每页可放的记录更少，扫描相同数量结果接触的页可能增加。用更小的整数主键并不是所有业务的唯一正确答案，但“主键宽度影响二级索引”是一条具体的成本传播路径。

也会影响 SQL 的投影。排行榜只需要 user_id 和 score 时，合适的索引可能覆盖查询；一口气 SELECT * 则把头像、简介等无关字段一起取出，增加回表和传输成本。有时候比“换一种树”更有效的优化，是减少一次查询真正需要的字段。

为什么页写入比内存旋转更复杂

叶页有剩余空间时，新记录可以写入当前页；空间不够可能触发页分裂，新的分隔关系继续传到父页。页内数据移动、锁存、日志、脏页和后续刷盘都与这一过程相关。一次内存中的父子指针修改，放进数据库后不能孤立看待。

递增主键通常让新行集中在索引的一端，能减少随机插入导致的空间扰动，但高并发下同一写入区域也可能成为竞争点。随机主键让写入更分散，未必降低整体成本：它可能接触更多页，降低缓存局部性，并改变分裂与填充情况。应该同时观察吞吐、延迟、页使用率和争用，不能把“顺序写”当作无条件的免费优化。

B+ 树也没有自动提供 ACID。崩溃后能否恢复、读者是否看到一致快照、事务怎样隔离，依赖 InnoDB 的日志、MVCC 和锁等机制。可以在内存里写一棵完全正确的 B+ 树，却没有任何断电恢复能力。讨论数据结构和讨论存储引擎，要保留这条边界。

六、HashMap 的红黑树只负责一个冲突桶

HashMap 的第一层是哈希桶数组。Key 的 hash 经过扰动后决定桶下标，正常情况下只需要在一个很短的桶内判断 equals。只有冲突较多的桶才考虑树化，因此不能把整个 HashMap 画成一棵按业务 Key 排序的红黑树。

这棵树组织的是已经落入同一桶的 Key。它可以利用 hash 的差异，必要时利用可比较关系和内部的打破平局规则。这样的桶内导航没有形成整个 Map 的业务顺序：两个数值相邻的用户 ID 可能位于完全不同的桶，entrySet() 迭代不承诺按 ID 排列，按积分区间查找也得不到帮助。

OpenJDK 17.0.12 中，树化相关常量为 TREEIFY_THRESHOLD = 8、MIN_TREEIFY_CAPACITY = 64、UNTREEIFY_THRESHOLD = 6。三个数不能被压缩成“第八个一定树化、第六个一定退化”。在普通 putVal 的链表追加路径里，条件是零起点的 binCount >= TREEIFY_THRESHOLD - 1，通常已有八个节点再追加一个时才调用树化；表容量不足 64 时，treeifyBin 会优先扩容。退化阈值 6 用于扩容拆分后的桶判断，删除还有结构性判断。OpenJDK HashMap 源码中的 putVal、treeifyBin、TreeNode.split 应一起看。

树化多付了节点字段、旋转维护和比较成本，所以正常分布下保留短链表是合理的。扩容则可能利用更多 hash 位，把挤在一起的 Key 分开；如果所有 Key 的完整 hash 都相同，增加桶数也分不开它们。两种冲突在症状上相似，改善路径却不同。

这里还有一个重要限定：树高有对数上界，不代表任意 Java Key 的查找总能保证只访问一条对数路径。当不同 Key 的 hash 相同，又没有可用的比较关系时，树查询为识别 equals 目标可能搜索多个分支。不能把“树化”写成修复所有恶劣 hashCode() 实现的绝对保证。昂贵的 equals、错误的相等约定和插入后改变 Key 的哈希字段，也不会被旋转解决。

对照排行榜，HashMap 适合当前请求中按用户 ID 拼接已加载的资料，或进程里维护短生命周期的映射。需要线程共享时再选择正确的并发容器；需要自动过期、容量限制和淘汰时，还需要缓存策略。红黑树只改善冲突访问，既不提供排名，也不会限制 Map 的总内存。Java HashMap API明确说明它不保证顺序，也不提供自身同步。

七、把一次排行榜请求走完

先定义业务规则：积分高者排前面，同分暂按 member 的逆字节序排列；用户 ID 采用固定宽度字符串，避免把 user:10 和 user:2 的字节顺序误当成数值顺序。生产榜单如果要求“先达到分数者在前”，需要重新设计完整排序语义，不能依赖 Redis 默认同分规则。

以下命令在独立测试 Key 上展示接口行为。初始 A=10、B=20、C=30、D=40，C 更新为 55。命令返回是依照定义推导的预期值，验证时应同时检查部署版本和编码。

ZADD demo:ranking 10 user:0001 20 user:0002 30 user:0003 40 user:0004
ZSCORE demo:ranking user:0003
# 预期：30
ZADD demo:ranking 55 user:0003
ZRANGE demo:ranking 0 2 REV WITHSCORES
# 预期：user:0003 55、user:0004 40、user:0002 20
ZREVRANK demo:ranking user:0003
# 预期：0，命令层排名从零开始
ZRANGE demo:ranking 20 40 BYSCORE WITHSCORES
# 预期：user:0002 20、user:0004 40

积分查询通过 member 定位；更新要维护 member 映射和积分顺序；前十名从有序结构的一端读取；自己的 rank 利用跨度计算。一个小测试 Key 可能实际走 Listpack，因此不能仅靠这几条命令证明走了跳表，必须配合 OBJECT ENCODING。命令语义见 ZRANGE 文档。

取到前十个 ID 后，应用批量加载用户资料，再用 Map 按 ID 对齐昵称和头像。资料加载结果不必与积分列表的返回顺序一致，Map 负责消除这个对齐问题，但最终页面顺序仍由排行榜结果决定。若直接迭代 HashMap 生成页面顺序，榜单就可能被打乱。

数据库保存活动积分的示例表可以这样设计：

CREATE TABLE activity_score_demo (
  activity_id BIGINT NOT NULL,
  user_id BIGINT NOT NULL,
  score BIGINT NOT NULL,
  PRIMARY KEY (activity_id, user_id),
  KEY idx_rank (activity_id, score DESC, user_id DESC)
) ENGINE=InnoDB;

SELECT user_id, score
FROM activity_score_demo
WHERE activity_id = 7
ORDER BY score DESC, user_id DESC
LIMIT 10;

EXPLAIN ANALYZE
SELECT user_id, score
FROM activity_score_demo
WHERE activity_id = 7
ORDER BY score DESC, user_id DESC
LIMIT 10;

这段 SQL 是 MySQL 8.4 的可验证方案，不是当前机器的数据库实测。它选数值 user_id 降序作为同分规则；只有 ID 编码固定宽度且对应同一数值顺序时，才与前面的字符串 member 规则对齐。建测试表、插入代表性数据、查看实际执行计划，才能确定优化器使用的访问路径。

activity_id = 7 固定联合索引的第一维，剩余记录按 score、user_id 排列，可以定位到该活动的排序区间。查询只拿 user_id 和 score，目的是争取覆盖索引读取。改成只过滤 score，或查询未被覆盖的大字段，访问成本就变了；不能把同一套索引名称当成速度承诺。

持久化与实时榜单之间还需要业务协议。一次积分事件通常有 event_id，落库应保证同一事件不会重复应用。提交后更新 Redis，若进程在两者之间崩溃，榜单可能滞后；如果先更新 Redis 再落库，数据库失败又会留下虚高积分。可根据一致性要求选择事务消息、Outbox、可重放事件和定期对账。单条 ZINCRBY 的原子性解决不了跨系统的“恰好一次”。

还要防止事件乱序。两次绝对分数更新若依次为 55、60，延迟到达的 55 不应覆盖 60。可让更新携带版本，并在 Redis 脚本或应用协议里检查版本；若改用增量，则转而处理重复事件。到底用绝对值还是增量，来自事件交付语义，不由跳表决定。

八、排名、分页和分数精度的边界

ZRANGE 100000 100009 的 rank 起点，可以利用带跨度的跳表定位；InnoDB 的 LIMIT 10 OFFSET 100000 通常需要让执行器处理前面的记录，再跳过它们。即使只返回十条，扫描也不等于十条。“都有有序索引”不能推出“都有同样的排名跳转能力”。

数据库常用 keyset pagination 改善深分页：把上一页最后一条的排序键带到下一页，用边界条件继续扫。对于固定活动的降序榜单，边界是 (score, user_id)，必须包含同分时的稳定维度。

SELECT user_id, score
FROM activity_score_demo
WHERE activity_id = 7
  AND (score < 1000 OR (score = 1000 AND user_id < 42))
ORDER BY score DESC, user_id DESC
LIMIT 10;

这个条件来自降序比较规则。它避免从头跳过大量旧结果，但仍要用执行计划确认 OR 条件形成的具体访问路径。更重要的是，它不提供静态快照：两页之间积分变化，用户可能跨过边界而重复或遗漏。需要稳定导出时，可以冻结榜单版本，或使用数据库的一致性读，并评估长事务代价。

Redis 的 score 使用双精度浮点数，连续整数的精确表达边界是 2^53。在 JavaScript 中可以复现相同的双精度问题：

Number(9007199254740992n) === Number(9007199254740993n)
// true：相邻两个整数转换后合并成同一个值

把积分、时间戳和用户 ID 拼进一个超大整数 score，可能在客户端转换时就丢失低位；服务端收到的值已经相同，跳表无法恢复原始顺序。ZADD 文档说明了分数类型和整数精度范围。这个例子已经在仓库的复现脚本中断言验证。

分数也不是货币金额的自动安全表示。若业务需要精确金额，可以先在确定边界内使用整数最小单位，并检查全链路的数值类型；超出范围或需要复合排序时，则应重新建模。不能单凭“数据库用了 BIGINT”就认为转进 Redis score 后仍然无损。

大集合还有服务级限制。单个 ZSet 在 Redis Cluster 中仍归属一个 Key 的 Slot，不能因为有百万成员就自动均摊到多个分片。超级热点排行榜、巨量返回结果和频繁全榜更新会集中压在负责它的节点。跨分片分榜后再聚合，前十名可以另行计算，但精确全局排名与一致更新就复杂得多。

九、怎样验证结构选择，而不是验证一个口诀

比较跳表和红黑树，应该先限定实现、Key 类型、数据量、分配方式和访问分布。只测随机整数单点查询，无法代表大量同分排行榜；只测插入吞吐，无法代表范围扫描；只在热缓存里测树，无法说明冷页数据库查询。不同语言或对象布局之间的差别，也可能大于结构名之间的差别。

针对排行榜，我会保留几类负载：用户单点查分、前十名、自己的排名、大积分区间和持续改分。按真实比例混合执行，记录吞吐与 p95/p99 延迟，再测编码阈值附近的变化。不能只看平均延迟，扩容、编码转换、页分裂和 GC 都可能表现为少量长尾。

Redis 侧记录 OBJECT ENCODING、MEMORY USAGE、命令统计、慢日志和返回字节数。InnoDB 侧看 EXPLAIN ANALYZE 的实际行数与耗时、Buffer Pool 读页相关指标和锁等待。Java 侧用合适的微基准工具控制预热与 GC，并补业务负载测试；用一次 System.nanoTime() 循环比较两段代码，结果很容易被 JIT、死代码消除和分配行为误导。

实验还要区分两个问题。一个是“同一种能力，用不同结构哪个更适合”；另一个是“在完整系统中，这条请求哪里最慢”。如果页面主要在等待用户资料 RPC，优化 ZSet 的几次指针跳转不一定有可见收益。先画完整链路，再决定微基准是否有必要。

结构或组合	提供的主要能力	付出的主要成本	本例中的位置
哈希表	平均快速的等值定位	桶、冲突、扩容；无业务顺序	用户 ID 到资料或积分
字典 + 带跨度跳表	成员定位、积分排序、排名	双索引、随机层级、指针与跨度维护	大型实时 ZSet
红黑树 / 带计数红黑树	确定性高度约束的有序访问	节点、比较、旋转；排名需额外计数	可替代的内存有序索引
页式 B+ 树	有序页导航与范围读取	页更新、分裂、缓存与日志协作	持久化索引
排序数组或紧凑编码	紧凑遍历、较好的局部性	插入搬移、按成员查找可能扫描	小集合或批量构建结果

所以我不会给跳表、B+ 树和红黑树排一个通用名次。先确认排序键、读写比例、结果规模和存储层级，再比较为满足同一组需求所付的代价。ZSet 把 member 定位与积分顺序拆开，InnoDB 把顺序组织进页，HashMap 把树限制在冲突桶里；这三种安排分别回应了不同的访问问题。

参考与复现

Redis 7.2.5：t_zset.c，重点阅读 zslInsert、zslUpdateScore、zslGetRank、zsetAdd。
Redis：紧凑编码与内存优化。
MySQL 8.4：索引物理结构、聚簇与二级索引。
OpenJDK 17.0.12：HashMap.java。

双精度断言与下一篇缓存访问序列的复现共用仓库脚本 scripts/experiments/cache-policy-traces.mjs，在仓库根目录执行 node scripts/experiments/cache-policy-traces.mjs。脚本不需要外部服务。Redis 命令和 SQL 需要读者另建测试实例；本文没有把预期结果当成本机实测。