跳跃表与跳跃树：Antithesis 如何用奇特数据结构解决测试难题？

BugBash 2026导航栏信息导航栏包含产品相关、解决方案、公司信息和资源四个板块。产品相关板块有 What is Antithesis?、How Antithesis works、How were different 等内容解决方案板块涵盖 Problems we solve、Security approach、Fintech、Blockchain、Databases、Cloud infrastructure、Customer stories、Working with Antithesis 等公司信息板块包含 Contact us、Backstory、Leadership、Careers、Brand资源板块有 Docs、Blog、Log in、Book a demo。博客文章跳跃表有什么用文章作者是 Will WilsonCEO发表于 2026 年 4 月 16 日。不久前作者加入 Phil Eaton 的读书俱乐部研读《多核编程的艺术》期间谈到了跳跃表。在作者职业生涯大部分时间里跳跃表是小众数据结构应用场景不多。但大约六年前Antithesis 遇到问题其扩展结构发挥了作用。什么是跳跃表跳跃表是随机化的数据结构可作为二叉搜索树的直接替代品具有相同接口和渐近复杂度。有人喜欢它是因为可实现相对简单且易于理解的无锁并发版本也有人出于个人喜好。从实现看可看作链表加“快速通道”。从基本链表开始添加一系列链表每层节点数量逐渐减少高层节点通过概率随机选择每个节点有 50% 概率被提升到上一层。这有助于搜索可利用高层链表更快跳到目标节点。在普通链表中查找节点需 O(n) 时间而跳跃表查找节点时间复杂度为 O(log n)。问题所在Antithesis 多次运行客户软件查找漏洞模糊测试器注入不同故障测试代码做不同随机决策形成时间线分支树。有很多查询需求相当于对树进行折叠操作。但测试软件输出数据量大存入分析型数据库当时用 Google BigQuery该数据库并行扫描大量数据计算聚合结果快但按 ID 获取特定行的点查询慢。而在数据库中用父指针表示树回答查询需逐个节点遍历树在 BigQuery 中每次操作会全表扫描基本查询会对整个数据集进行 O(深度) 次读取。拆分数据存储在不同数据库会带来新问题如插入需同时写入两个系统保持一致性需类似两阶段提交技术且当时 BigQuery 一致性语义宽松不清楚能否保持同步。什么是跳跃树跳跃树类似跳跃表是一棵树。它有 0 层树上面有一系列树每棵树节点数量约是下一层的 50%。从根节点到叶子节点的路径上的节点及高层树对应节点形成跳跃表所以跳跃树是共享结构的跳跃表集合。存储跳跃树需为每一层创建 SQL 表每个表为节点创建一行有列存储上一层最近祖先节点和当前节点与上一层祖先节点间所有节点。可通过链式 JOIN 操作查找节点祖先用固定数量 JOIN 的非递归 SQL 查询查找祖先节点约需 40 次 JOIN 操作。当时 BigQuery 按扫描数据量收费表大小几何分布使查询费用相当于两次普通表扫描。不过也有缺点如查询文本大但用 JavaScript 编译器生成 SQL。在公司前六年Antithesis 多数测试属性通过这种方式评估直到编写了自己的分析型数据库。跳跃表、跳跃树、跳跃图……后来发现跳跃树与跳跃图密切相关跳跃图是基于跳跃表的分布式数据结构。这说明奇特数据结构可能节省大量时间和金钱。此外Andy Pavlo 称“编写良好”的树比跳跃表更高效但跳跃表“完全朴素的实现”也有足够性能在 SQL 编写代码时有用。感谢 Phil Eaton 建议撰写此文。结尾福利读到文章结尾可领取免费贴纸把它们贴在任何地方等着收获赞美。