高级数据结构-01：跳表

预备知识

二项分布

$B(t, p)$ 表示一个随机变量，其物理意义为在这一系列 $t$ 次独立试验中所观察到的总成功次数。二项分布 $B(t, p)$ 的数学期望为 $tp$ ，方差为 $tp(1-p)$ 。

负二项分布

负二项分布是反向等待。 $NB(s, p)$ 表示一个随机变量，其物理意义为：在恰好获得第 $s$ 次成功之前，我们必须经历的“失败”的总次数。负二项分布 $NB(s, p)$ 的数学期望为 $\frac{s(1-p)}{p}$ ，其方差为 $\frac{s(1-p)}{p^2}$ 。

几何分布

几何分布可以被视为负二项分布在 $s=1$ 时的特例，即只关心第一次成功出现前所经历的过程。几何分布描述了在独立伯努利试验中，第 $k$ 次才首次成功的概率。换言之，前 $k-1$ 次试验全部失败，第 $k$ 次试验成功。其可以表达为： $P(X=k) = (1-p)^{k-1}p$ ，其中 $k$ 可以取任何正整数。

如果将随机变量定义为获得第一次成功所需的总试验次数（包含那一次成功），那么其数学期望 $E[X]$ 等于 $\frac{1}{p}$ ；如果将其严格定义为首次成功前遭遇的失败次数，则期望为 $\frac{1-p}{p}$ 。

伯努利不等式

在评估有限元素组成的跳转表中，所有节点中可能出现的理论最大层数上界时，需要利用到一个关键的概率放缩技巧——伯努利不等式：设 $n$ 与 $k$ 均为正整数，有 $(1 - \frac{1}{2^k})^n \ge 1 - \frac{n}{2^k}$ 。

回到跳转表的问题。考虑到 $k$ 作为一个代表层数的变量，必然是一个大于等于 1 的正整数。当 $k \ge 1$ 时， $2^k \ge 2$ ，因此 $x$ 的取值范围被框定在 $[-0.5, 0)$ 的区间内，符合伯努利不等式 $x \ge -1$ 的约束。因此得出结论： $(1 - \frac{1}{2^k})^n \ge 1 - n(\frac{1}{2^k})$ ，整理后即为 $(1 - \frac{1}{2^k})^n \ge 1 - \frac{n}{2^k}$ 。

跳转表

回顾常见的几种数据结构对有序序列的存储：

有序数组：支持利用二分查找算法实现 $O(\log n)$ 的快速定位，但其缺陷在于插入与删除操作由于需要进行大规模的内存数据搬移，导致时间复杂度退化为 $O(n)$ ；
单链表：虽然允许在已知内存位置进行 $O(1)$ 的原位插入与删除，但由于缺乏随机访问能力，其查找任何一个节点都必须从头进行线性遍历，耗时同样高达 $O(n)$ ；
平衡树：在处理完全随机顺序的数据插入时表现良好，但一旦遭遇近似有序或完全有序的数据序列，为了抵御结构退化为单链表的风险，算法必须强制介入并执行大量繁琐且易出错的树旋转重构操作以维持严苛的平衡约束（参考红黑树和伸展树）。

跳转表是一种寻求“高性能与低复杂度并存”的替代方案。第 0 层保存所有节点，保证它本质上仍是一条完整有序链表；越高的层节点越稀疏，用于跨越大量低层节点。搜索时先在高层快速逼近目标，再逐层下降到更密集的下层进行精确定位。

节点数据结构

一个标准跳转表的数据结构定义包含了全局配置常量与节点实体两个部分。

首先，系统必须定义两个全局参数：

// 跳表允许的最大层数，用于限制随机晋升带来的最高高度。
const int MAX_LEVEL = 16;
// 节点从当前层晋升到更高一层的概率。
const float P = 0.5;

概率因子 P 决定了相邻两层之间节点的稀疏程度，通常设定为 $0.5$ 或 $0.25$ 。而 MAX_LEVEL 则是为了防止在小概率情况下，某个节点的层数无限制增长导致内存溢出而设定的上限。对于一个预期最大容量为 $N$ 的系统，物理层数上限通常可参照 $L(N) = \log_{1/p} N$ 设置。若系统采用 $P=0.5$ ，并设置 MAX_LEVEL = 16，则跳转表在理论上可支撑约 $2^{16} = 65536$ 个元素，并保持预期对数级访问性能。

接下来是跳转表节点定义。跳转表节点有一组动态长度的前进指针数组：

// 跳表节点保存键值以及从低层到高层的前进指针。
struct Node {
    // 用于排序和查询的键值。
    int value;

    // forward[i] 指向当前节点在第 i 层的后继节点；不存在后继时为 nullptr。
    vector<Node*> forward;

    // level 是节点实际拥有的层数，构造时为每一层初始化空指针。
    Node(int val, int level) : value(val), forward(level, nullptr) {}
};

vector<Node*> forward 扮演了旁路的角色。数组中的每一个元素 forward[i] 都明确指向了当前节点在第 $i$ 层级的直系后继节点的内存内存地址。如果当前节点在某一层是链表的尾部，则该指针将指向 nullptr。

另外，节点的“层数”不是全局固定的。一个普通节点可能只有第 0 层指针，少数节点会拥有更高层的 forward 指针。因此访问 forward[i] 前必须保证该节点确实拥有这一层；代码中通过节点创建时的 level 和全局当前高度 level 来控制这一点。

层数设置

既然跳转表拥有多层结构，那么算法在执行搜索时，应该从哪一层作为起点开始遍历？理想的搜索起点应当设定在一个特定的层数 $L$ ：在这一层中，我们预期恰好能够遭遇 $1/p$ 个节点，符合 $L(n) = \log_{1/p} n$ 。

对每一层节点密度做期望值计算。假设当前跳转表系统中总共容纳了 $n$ 个独立节点。由于每一个节点的层高生成过程都遵循概率为 $p$ 的几何分布（每次晋升的成功率均为 $p$ ），如果我们将最底层的一般链表定义为第 1 层（在数组索引中对应 0），那么任意一个随机节点能够晋升并存活在第 $l$ 层的概率等于 $p^{l-1}$ 。

将系统内节点总数乘以单节点存在于该层的概率，即可得出在第 $l$ 层的预期节点总数规模，记作 $\#(n, l)$ ：

$\#(n, l) = n \cdot p^{l-1}$

我们希望找到一个层数标识符 $L(n)$ ，使得如果系统刚好生长到这一层，该层内存在的节点数量期望值恰好等于 $\frac{1}{p}$ 。我们将这一目标条件转化为：

$n \cdot p^{L(n)-1} = \frac{1}{p}$

$p^{L(n)} = n^{-1}$

$L(n) \cdot \log(p) = \log(n^{-1}) = -\log(n)$

$L(n) = -\frac{\log(n)}{\log(p)} = \frac{\log(n)}{\log(1/p)}=\log_{1/p} n$

由此得出期望层数： $L(n) = \log_{1/p} n$ 。

随机层数生成

一个新节点在插入系统时，其最终层数取决于一个独立且无记忆性的随机晋升过程。

这种机制通过 randomLevel 函数实现：

int randomLevel() {
    // 节点至少出现在第 1 层，即数组下标 0 对应的基础链表。
    int lvl = 1;

    // 每次循环表示一次独立晋升尝试；达到最大层数后停止。
    while ((rand() % 100) < (P * 100) && lvl < MAX_LEVEL) {
        // 晋升成功后增加节点层数，并继续尝试下一层。
        lvl++;
    }

    // 返回新节点最终拥有的层数。
    return lvl;
}

由于每一个节点的层高是在其插入瞬间通过本地随机数独立决定的，它能够减少外部输入顺序对结构形态的影响。无论开发者是向跳转表中输入随机乱序数字，还是输入严格递增序列，跳转表的宏观多层结构分布都由随机层数机制控制，不会像朴素二叉搜索树那样，在有序输入下退化成一条线性链表（最坏 $O(N)$ ）。

搜索

跳转表的目标是查明系统内是否存在包含特定键值的节点。

搜索过程的循环不变量是：current 永远停在一个值严格小于 target 的节点上，并且在当前层不能再向右越过任何小于 target 的节点。向右移动负责扩大已排除范围，向下移动负责提高搜索精度。最终落到第 0 层后，目标若存在，只可能是 current->forward[0]。

// 搜索 target 是否存在于跳表中。
bool search(int target) {
    // 从虚拟头节点开始；头节点不保存有效业务键值。
    Node* current = header;

    // 从最高有效层向第 0 层下降。
    for (int i = level - 1; i >= 0; i--) {

        // 在第 i 层向右移动，直到下一个节点为空或键值已经不小于 target。
        while (current->forward[i] && current->forward[i]->value < target) {
            // 保持循环不变量：current 的键值始终小于 target。
            current = current->forward[i];
        }

        // 当前位置是第 i 层中不超过 target 插入位置的最后一个节点。
    }

    // 第 0 层包含所有节点，目标若存在只能位于 current 的直接后继。
    current = current->forward[0];

    // 后继存在且键值相等时搜索成功。
    return current && current->value == target;
}

插入

相较于单纯的只读搜索操作，将一个全新节点植入跳转表体系不仅要求精准找到其落脚点，还必须确保这个新节点能够与各层原有的链路网络对接，不能造成任何链表断裂。在此处，使用 update 来更新跳表的状态。

update 记录下在每一层最终停留的最后一个节点的内存地址。换句话说，update[i] 保存了在第 $i$ 层中，新节点未来插入位置左侧紧邻的那个“前驱节点”。有了这本日志，当新节点随机生成了自己的楼层高度后，系统就可以按照 update 的信息，直接找到每一层需要被剪断并重新拼接的链表接头。

每一次做插入时，先搜索并记录每一层的前驱，再按新节点高度逐层执行普通链表插入。update 数组避免了“插入时重新找前驱”的重复工作，也保证不同层的指针能按同一个逻辑完成拼接。

void insert(int value) {
    // update[i] 保存第 i 层中插入位置左侧的前驱节点。
    vector<Node*> update(MAX_LEVEL, header);
    // current 是搜索插入位置时使用的游标。
    Node* current = header;

    // 第一阶段：沿搜索路径定位插入位置，并记录每一层前驱。
    for (int i = level - 1; i >= 0; i--) {
        // 在当前层尽量向右移动到最后一个小于 value 的节点。
        while (current->forward[i] && current->forward[i]->value < value) {
            current = current->forward[i];
        }
        // current 即为新节点在第 i 层的前驱。
        update[i] = current;
    }

    // 第 0 层后继若等于 value，说明键已存在，插入失败。
    if (current->forward[0] && current->forward[0]->value == value) {
        cout << "Duplicate value: " << value << endl;
        return;
    }

    // 第二阶段：随机生成新节点层数。
    int newLevel = randomLevel();

    // 若新节点层数超过当前跳表高度，需要扩展有效层数。
    if (newLevel > level) {
        // 新增层原本只有头节点，因此这些层的前驱都是 header。
        for (int i = level; i < newLevel; i++) {
            update[i] = header;
        }
        // 刷新跳表当前有效高度。
        level = newLevel;
    }

    // 第三阶段：创建新节点并在各层执行链表插入。
    Node* newNode = new Node(value, newLevel);

    // 从第 0 层到 newLevel - 1 层分别重连指针。
    for (int i = 0; i < newLevel; i++) {
        // 新节点先接上原前驱的后继，避免丢失右侧链表。
        newNode->forward[i] = update[i]->forward[i];
        // 前驱再指向新节点，完成第 i 层插入。
        update[i]->forward[i] = newNode;
    }
}

删除

删除算法是插入算法的逆操作。它同样依赖 update 数组来锁定目标节点的左侧前驱。在成功确认目标身份后，算法会指令各层的前驱节点将指针跨越目标节点，将其从数据结构中抹除。

删除后还要清理“幽灵层级”：如果最高层只剩下头结点，没有任何真实节点，那么这一层对搜索没有帮助，应当降低跳表当前高度。否则搜索会从空的高层开始，虽然不影响正确性，但会引入不必要的空检查。

bool erase(int value) {
    // update[i] 保存第 i 层中目标节点左侧的前驱节点。
    vector<Node*> update(MAX_LEVEL, nullptr);
    // 从虚拟头节点开始搜索待删除节点。
    Node* current = header;

    // 第一阶段：定位目标节点，同时记录各层前驱。
    for (int i = level - 1; i >= 0; i--) {
        // 向右移动到最后一个键值小于 value 的节点。
        while (current->forward[i] && current->forward[i]->value < value) {
            current = current->forward[i];
        }
        // 第 i 层中 current 是目标可能位置的前驱。
        update[i] = current;
    }

    // 第 0 层包含所有节点，目标只能是前驱的直接后继。
    current = current->forward[0];

    // 后继不存在或键值不匹配时，跳表中没有目标值。
    if (!current || current->value != value) return false;

    // 第二阶段：逐层断开目标节点。
    for (int i = 0; i < level; i++) {
        // 若第 i 层前驱未指向目标节点，说明目标节点不在该层及更高层。
        if (update[i]->forward[i] != current) break;

        // 前驱直接连接目标节点的后继，跳过目标节点。
        update[i]->forward[i] = current->forward[i];
    }

    // 第三阶段：若最高层已无真实节点，则降低跳表有效高度。
    while (level > 1 && !header->forward[level - 1]) {
        level--;
    }

    // 第四阶段：释放目标节点内存并返回成功。
    delete current;
    return true;
}

算法时间复杂度

反向搜寻路径

在评估常规数据结构的搜索成本时，直观方法是顺着代码执行轨迹，从跳表头节点出发，自上而下、从左向右统计比较次数。然而，由于前向探索会持续遇到未知随机节点，正向分析的概率状态较复杂。这了采用反向回溯的思路：假设已经站在成功锁定的目标节点上，再沿着一条最短路径反向退回到跳表的左上角原点。

尽管在真实实现中，所有节点的层数在插入时已经确定；但在反向分析中，可以假设节点高度在路径访问到相应层时才被揭示。只有当反向路径到达某一层指针时，才判断该节点是否拥有更高一层，判断概率仍为 $p$ 。这种视角保留了随机层数的无记忆性，使状态转移可以按马尔可夫过程处理。

在这个未知的反向爬升过程中，如果我们截取任意一个瞬间，假设我们此刻正悬停在某个未知节点 $x$ 的第 $k$ 层的左侧边缘。我们的雷达对 $x$ 节点左侧的世界一无所知，对 $x$ 节点本身的最终高度也一无所知，我们唯一能够确认的客观事实是：既然我们能够踏足这里，说明 $x$ 节点的层高至少达到了 $k$ 级（Situation a）。

立足于这个至少为 $k$ 级的基准点，我们有两条岔路口：

岔路口一（向左撤退）：Situation b。当我们试图在当前节点继续向更高的 $k+1$ 层攀登时，若 $x$ 的高度刚好停留在 $k$ 层，则无法继续向上，只能沿着第 $k$ 层向左移动到上一个前驱节点。基于已经知道 $x$ 高度至少为 $k$ 的条件，它不再继续向上突破 $k$ 的条件概率，等同于高度生成过程中未发生晋升的概率，即 $1-p$ 。
岔路口二（向上爬升）：Situation c。 $x$ 节点的真实高度突破了 $k$ 的限制，至少达到了 $k+1$ 或更高。这意味着我们完全不需要进行任何耗时的向左撤退，可以直接在当前原地的电梯井中，垂直向上攀升一个层级，抵达第 $k+1$ 层。同理，在高度至少为 $k$ 的已知条件下，高度继续突破延伸到 $k+1$ 的条件概率，精确地等价于随机函数判定提升成功的概率，即 $p$ 。

期望代价 $C(k) = k/p$

在明确了基本的状态转移规律后，我们引入一个核心的数学分析函数：定义 $C(k)$ 为在一条拥有无穷无尽元素的假想跳转表中，为了实现在垂直空间内总共向上爬升 $k$ 个独立层级，我们预期所需耗费的总体移动步数（包含所有的向左和向上动作）。

逻辑起点：如果根本不需要爬升任何高度（ $k=0$ ），预期代价自然是零，因此得到边界条件： $C(0) = 0$ 。
状态组装：如果我们需要爬升 $k$ 层，我们在踏出第一步时将面临前文所述的概率分岔。由此构建出预期代价的递归状态转移方程：

$C(k) = (1-p) \times (\text{处于 Situation b 时的后续代价}) + p \times (\text{处于 Situation c 时的后续代价})$

对两种情境下的后续代价进行精细拆解：

Situation b（向左撤退）：向左平移消耗 1 次移动，但垂直高度没有增加，因此仍需完成 $k$ 层爬升。由于假设列表无穷，向左移动后的节点仍服从相同的随机模型。因此，这种情况下未来的整体预期代价等于已经消耗的 1 步，加上再次面对爬升 $k$ 层的预期成本 $C(k)$ 。数学表达为： $1 + C(k)$ 。
Situation c（垂直爬升）：我们同样耗费了 1 步动作，但这 1 步让我们成功地在垂直方向上斩获了 1 个层级。此时，我们距离爬升 $k$ 层的宏伟目标，仅仅只剩下 $k-1$ 层需要征服。因此，这种情况下的未来整体预期代价等于： $1 + C(k-1)$ 。

代入概率方程式中，得到：

$C(k) = (1-p)(1 + C(k)) + p(1 + C(k-1))$

这就是分析跳转表搜索代价的核心等式。接下来对这个等式进行代数化简。

$C(k) = (1-p) + (1-p)C(k) + p + pC(k-1)$

$C(k) = 1 + C(k) - pC(k) + pC(k-1)$

$0 = 1 - pC(k) + pC(k-1)$

$pC(k) = 1 + pC(k-1)$

在等式两端同时除以概率常量 $p$ ：

$C(k) = \frac{1}{p} + C(k-1)$

这个最终形态是一阶线性常系数差分方程。它说明每增加一层爬升目标，预期步数增加常数 $\frac{1}{p}$ 。由于基准点是 $C(0) = 0$ ，连续 $k$ 次展开迭代后得到：

$C(k) = \frac{k}{p}$

即在一个无穷宽的理想跳转表中，向上攀登 $k$ 层的预期移动次数为 $\frac{k}{p}$ 。

搜索成本界定

上述基于 $C(k)$ 的推导建立在列表具有无穷宽度的理想化假设之上。在真实系统中，跳转表容纳的元素总量 $n$ 是有限的。在处理包含 $n$ 个元素的有界结构时，可以将反向探测切分为两个阶段来计算。

第一阶段：从最下层爬升至 $L(n)$

在起始阶段，我们完全可以照搬 $C(k)$ 的结论。从最底层的 Level 1 开始向上反向攀爬，一直攀爬到前文推导出的理想启动层级 $L(n)$ ，我们总共需要跨越 $L(n) - 1$ 个高度阶梯。根据无穷列表的保守公式，这一阶段所需的预期移动步数的绝对上限为：

$\frac{L(n) - 1}{p}$

为何说这只是一个保守上限？因为在有限长度的跳表中，反向向左试探时可能提前到达虚拟头节点（Header）。一旦到达头节点，就无法继续向左，只能沿着头节点向上移动，在这个过程中不再产生水平向左动作。因此，实际步数不会超过该上界。
第二阶段：达到 $L(n)$ 后左移与爬升

当反向路径到达 $L(n)$ 这一层时，跳表中的节点密度已经很低。根据之前的推导，整个跳表中能够生长到 $L(n)$ 层或更高层级的节点，其预期总数为 $\frac{1}{p}$ 。因此，即使继续向左经过这一层以上的所有高层节点，剩余水平左移次数的期望也被限制在 $\frac{1}{p}$ 这个常数内。

在解决横向位移后，剩余任务是继续向上，直到到达跳表的最高层。那么，一个包含 $n$ 个元素的跳表，其预期最大层数 $M$ 有多高？

这需要进一步的概率计算。任意一个节点高度超过 $k$ 层的概率是 $p^k$ ；反过来，它无法超过 $k$ 层的概率就是 $(1-p^k)$ 。由于系统中存在 $n$ 个相互独立的节点，所有节点都无法超过 $k$ 层的联合概率就是 $(1-p^k)^n$ 。那么这座大厦中至少有一个超级节点突破了 $k$ 层（也就是最大高度 $M$ 大于 $k$ ）的概率 $Prob\{M > k\}$ ，自然就等于：

$1 - (1 - p^k)^n$

可以使用伯努利不等式！将该不等式 $(1-p^k)^n \ge 1-np^k$ 代入并进行反向放缩，得到：

$1 - (1 - p^k)^n \le 1 - (1 - n p^k) = n p^k$

通过更严格的负二项分布与期望界分析，可以证明跳表预期最大层数 $E[M]$ 满足：

$E[M] \le L(n) + \frac{1}{1-p}$

这意味着，当反向路径已经到达 $L(n)$ 层时，继续向上到达最高层的额外期望层数不超过 $\frac{1}{1-p}$ 。
总期望搜索成本

现在将上述三部分合并。为了完成一次搜索，并反向退回原点，预期总体步数开销构成为：

$[\text{第一阶段爬升}] + [\text{第二阶段仅剩的向左位移}] + [\text{第二阶段最后的冲刺登顶}]$

$\text{总开销} \le \frac{L(n) - 1}{p} + \frac{1}{p} + \frac{1}{1-p}$

$\text{总开销} \le \frac{L(n)}{p} - \frac{1}{p} + \frac{1}{p} + \frac{1}{1-p} = \frac{L(n)}{p} + \frac{1}{1-p}$

将 $L(n) = \log_{1/p} n$ 代回：

$\text{总搜索期望代价} \le \frac{\log_{1/p} n}{p} + \frac{1}{1-p}$

在这个数学方程式中， $p$ 是预先设定的常数。因此，决定公式增长趋势的主要变量是 $L(n)$ 。在渐进符号体系下，常数项被忽略，跳转表的期望查找开销为 $O(\log n)$ 。

$p$ 的调整

在掌握时间复杂度的数学推理之后，出现了一个实际的工程抉择：既然概率因子 $p$ 在公式中扮演着重要的调优角色，那么究竟应当如何取值，才能使系统达到较好的工作状态？

这本质上是“计算时间”与“存储空间”的权衡。

如果压低 $p$ 的数值，新节点向上晋升的概率会降低。这会导致多数节点层数较低，从而减少保存多层指针所需的内存体积（理论上平均每个节点挂载的指针数为 $\frac{1}{1-p}$ ）。代价是高层索引更稀疏，搜索过程中需要更多底层水平移动，导致搜索耗时增加。
如果抬高 $p$ 的数值，系统中会出现更多高层节点。高层索引更密集，搜索路径通常更短；代价是需要保存更多指针，内存开销增加。

参数 p 的设定值	归一化搜索时间膨胀倍率 (即 L(n)/p)	内存开销：平均每个节点的包含指针数 (即 1/(1−p))
1/2	1.00	2.00
1/e	0.94…	1.58…
1/4	1.00	1.33…
1/8	1.33…	1.14…
1/16	2.00	1.07…

如果业务场景可以接受个别查询时间的小幅波动，为了获得较好的时空折中，可以将 $p$ 设定为 $\frac{1}{4}$ ；如果业务更重视每次查询响应时间的一致性，则可使用 $p=\frac{1}{2}$ 以降低方差。Redis 的跳表实现采用了这一思路，其源码宏定义为 ZSKIPLIST_P = 0.25。