当前位置：首页 > news >正文

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

news 2026/4/19 23:16:30

BugBash 2026导航栏信息

导航栏包含产品相关、解决方案、公司信息和资源四个板块。产品相关板块有 What is Antithesis?、How Antithesis works、How we're 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 Wilson，CEO，发表于 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 多数测试属性通过这种方式评估，直到编写了自己的分析型数据库。