Van Emde Boas 树：当 O(log log n) 不只是理论

一、从一道经典问题说起：前驱与后继

在算法世界里,有一类看起来极其朴素的问题:给定一个动态整数集合 S,支持以下操作——

• insert(x): 将整数 x 插入 S;
• delete(x): 从 S 中删除整数 x;
• successor(x): 找到 S 中大于 x 的最小元素;
• predecessor(x): 找到 S 中小于 x 的最大元素;
• member(x): 判断 x 是否属于 S。

这就是所谓的 predecessor/successor problem(前驱/后继问题)。

1.1 为什么这个问题重要

前驱查询的应用远比初看起来广泛。路由器中的最长前缀匹配(LPM)、数据库中的范围扫描、内存分配器中寻找最近的可用块、操作系统调度器中挑选下一个就绪进程——这些场景的核心抽象本质上都是前驱/后继查询。

1.2 经典方案的瓶颈

用平衡二叉搜索树(红黑树、AVL 树)可以在 O(log n) 时间内完成上述所有操作,其中 n 是集合中元素的数量。用哈希表可以做到 O(1) 的 member 和 insert/delete,但 successor/predecessor 退化为 O(n)——哈希表不维护顺序信息。

有没有一种数据结构,能够把所有操作都做到比 O(log n) 更快?

答案是肯定的——但需要一个额外假设:键是有界整数。如果我们知道所有键都取自一个有限宇宙 [0, U),那么 Van Emde Boas 树(以下简称 vEB 树)可以将所有操作的时间复杂度降低到 O(log log U)。

当 U = 2^32(32 位整数)时,log log U = log 32 = 5。五次操作——这几乎是常数时间。

二、递归宇宙分裂：vEB 树的核心直觉

vEB 树的精髓在于一个朴素却深刻的思想:用平方根递归地缩小问题规模。

2.1 从位向量到分层

最天真的做法是维护一个长度为 U 的位向量。member 是 O(1),但 successor 最坏需要扫描整个向量,复杂度 O(U)。

能不能加速扫描?一个自然的想法:将 U 个位分成 sqrt(U) 组,每组 sqrt(U) 位。再维护一个”摘要”(summary)位向量,第 i 位表示第 i 组是否包含至少一个元素。

查找 x 的后继时:先在 x 所在的组内找;如果组内没有更大的元素,就查摘要向量找到下一个非空组,再在该组内找最小元素。每层的扫描范围从 U 缩小到 sqrt(U)。

关键洞察:如果对摘要向量递归地应用同样的策略,问题规模从 U 到 sqrt(U) 到 sqrt(sqrt(U))……经过 log log U 层递归就到达基本情况。

2.2 递归结构定义

一棵 vEB(U) 树包含:

1. universe: 宇宙大小 U(必须是 2 的幂次的幂次,即 U = 2⁽²k));
2. min: 存储的最小值;
3. max: 存储的最大值;
4. summary: 一棵 vEB(sqrt(U)) 树,记录哪些簇(cluster)非空;
5. cluster[0..sqrt(U)-1]: sqrt(U) 棵 vEB(sqrt(U)) 子树,每棵管理 sqrt(U) 个键。

当 U = 2 时(基本情况),只需 min 和 max 两个字段,无需 summary 和 cluster。

下面这张图展示了 vEB(16) 的递归结构:

三、三个关键函数：high、low、index

vEB 树的所有操作都依赖三个简单的位运算函数,它们负责在层级之间进行键的分解和重组。

设宇宙大小为 U,令 hi = sqrt(U)(上半部分的取值范围),则:

high(x) = floor(x / sqrt(U))     // x 属于哪个簇
low(x)  = x mod sqrt(U)          // x 在簇内的偏移
index(i, j) = i * sqrt(U) + j    // 从簇号和偏移还原出原始键

在实际实现中,当 U 是 2 的幂次的幂次时,这三个操作可以用位移和掩码完成:

// U = 2^k, sqrt(U) = 2^(k/2)
int half_bits = k / 2;
int high = x >> half_bits;
int low  = x & ((1 << half_bits) - 1);
int idx  = (i << half_bits) | j;

这保证了每次递归都将问题规模精确地减半(以指数衡量),从 2^k 降到 2^(k/2),因此递归深度为 O(log k) = O(log log U)。

3.1 一个具体例子

设 U = 16, sqrt(U) = 4。

• 对于键 x = 14: high(14) = 14/4 = 3, low(14) = 14 mod 4 = 2。 这意味着 14 存储在 cluster[3] 中,偏移为 2。
• 反向: index(3, 2) = 3 * 4 + 2 = 14。

对于键 x = 5: high(5) = 1, low(5) = 1,存储在 cluster[1] 中,偏移为 1。

四、核心操作详解

4.1 min/max 的懒惰存储

vEB 树有一个巧妙的设计:min 和 max 不存储在任何子结构中。它们只记录在当前节点的字段里。这意味着:

• 一棵只包含一个元素的 vEB 树,其 min == max == 该元素,但所有 cluster 和 summary 均为空。
• 插入第二个元素时,才会真正地向 cluster 和 summary 中写入。

这个设计不是为了节省空间(虽然确实节省了一点),而是为了保证所有操作的递归深度不超过一层——每次操作至多在 cluster 和 summary 中各递归一次,而不是两次。这是 O(log log U) 复杂度成立的关键。

4.2 member 查询

vEB-member(V, x):
    if x == V.min or x == V.max:
        return true
    if V.U == 2:
        return false
    return vEB-member(V.cluster[high(x)], low(x))

每层递归将宇宙大小从 U 减至 sqrt(U),递归深度 O(log log U)。

4.3 successor 查询

后继查询是 vEB 树最有价值的操作,也是最体现其设计精妙之处的操作:

vEB-successor(V, x):
    // 基本情况
    if V.U == 2:
        if x == 0 and V.max == 1:
            return 1
        else:
            return NIL

    // 情况 1: x < min,后继就是 min
    if V.min != NIL and x < V.min:
        return V.min

    // 情况 2: 在 x 所在的簇内寻找
    hi = high(x)
    lo = low(x)
    max_in_cluster = vEB-max(V.cluster[hi])
    if max_in_cluster != NIL and lo < max_in_cluster:
        offset = vEB-successor(V.cluster[hi], lo)
        return index(hi, offset)

    // 情况 3: 当前簇内没有更大的,查 summary 找下一个非空簇
    next_cluster = vEB-successor(V.summary, hi)
    if next_cluster == NIL:
        return NIL
    offset = vEB-min(V.cluster[next_cluster])
    return index(next_cluster, offset)

关键分析:情况 2 和情况 3 中,最多只有一个会触发递归调用。

• 情况 2:递归发生在 cluster[hi] 上(宇宙大小 sqrt(U)),且 vEB-max 是 O(1) 操作;
• 情况 3:递归发生在 summary 上(宇宙大小 sqrt(U)),且 vEB-min 是 O(1) 操作。

因此递推关系为 T(U) = T(sqrt(U)) + O(1),解为 T(U) = O(log log U)。

4.4 predecessor 查询

predecessor 与 successor 对称,但需要额外处理 min 的特殊性(min 不存储在 cluster 中):

vEB-predecessor(V, x):
    if V.U == 2:
        if x == 1 and V.min == 0:
            return 0
        else:
            return NIL

    if V.max != NIL and x > V.max:
        return V.max

    hi = high(x)
    lo = low(x)
    min_in_cluster = vEB-min(V.cluster[hi])
    if min_in_cluster != NIL and lo > min_in_cluster:
        offset = vEB-predecessor(V.cluster[hi], lo)
        return index(hi, offset)

    prev_cluster = vEB-predecessor(V.summary, hi)
    if prev_cluster == NIL:
        // 特殊情况: min 没有存储在 cluster 中
        if V.min != NIL and x > V.min:
            return V.min
        return NIL
    offset = vEB-max(V.cluster[prev_cluster])
    return index(prev_cluster, offset)

4.5 insert 操作

vEB-insert(V, x):
    if V.min == NIL:
        // 空树,直接设置 min = max = x
        V.min = x
        V.max = x
        return

    if x < V.min:
        swap(x, V.min)  // 新 min 不进入子结构

    if V.U > 2:
        hi = high(x)
        lo = low(x)
        if vEB-min(V.cluster[hi]) == NIL:
            // 簇为空,插入 summary 并直接设 min/max
            vEB-insert(V.summary, hi)
            V.cluster[hi].min = lo
            V.cluster[hi].max = lo
        else:
            // 簇非空,只递归进 cluster
            vEB-insert(V.cluster[hi], lo)

    if x > V.max:
        V.max = x

注意:当簇为空时,递归发生在 summary 上;当簇非空时,递归发生在 cluster 上。二者不会同时递归,保证了 T(U) = T(sqrt(U)) + O(1)。

4.6 delete 操作

删除是最复杂的操作,需要处理 min/max 的更新:

vEB-delete(V, x):
    if V.min == V.max:
        // 只有一个元素
        V.min = NIL
        V.max = NIL
        return

    if V.U == 2:
        if x == 0:
            V.min = 1
        else:
            V.min = 0
        V.max = V.min
        return

    if x == V.min:
        // 需要找出新的 min
        first_cluster = vEB-min(V.summary)
        x = index(first_cluster, vEB-min(V.cluster[first_cluster]))
        V.min = x

    // 从 cluster 中删除
    hi = high(x)
    lo = low(x)
    vEB-delete(V.cluster[hi], lo)

    if vEB-min(V.cluster[hi]) == NIL:
        // 簇变空了,从 summary 中删除
        vEB-delete(V.summary, hi)
        if x == V.max:
            summary_max = vEB-max(V.summary)
            if summary_max == NIL:
                V.max = V.min
            else:
                V.max = index(summary_max, vEB-max(V.cluster[summary_max]))
    else:
        if x == V.max:
            V.max = index(hi, vEB-max(V.cluster[hi]))

同样,删除操作中 cluster 递归和 summary 递归不会同时发生(除了已确认簇变空的情况,此时 cluster 递归已到达基本情况),总复杂度 O(log log U)。

五、空间优化：从 O(U) 到更实用的方案

5.1 原始 vEB 树的空间困境

朴素 vEB 树的空间复杂度满足递推:

S(U) = (sqrt(U) + 1) * S(sqrt(U)) + O(sqrt(U))

解为 S(U) = O(U)。对于 U = 2^32,这意味着需要约 4GB 空间——即使只存储几个元素也是如此。这在绝大多数实际场景中是不可接受的。

5.2 哈希化 vEB 树: O(n log log U) 空间

一个直接的改进:不预分配所有 cluster,而是用哈希表按需存储非空的 cluster。这将空间降低到 O(n log log U),其中 n 是实际存储的元素数量。

// 将 cluster 数组替换为哈希表
typedef struct {
    int U;
    int min, max;
    struct vEB *summary;
    HashTable *clusters;  // 按需分配
} vEB;

期望时间复杂度不变(哈希表操作期望 O(1)),但最坏情况退化。

5.3 x-fast trie

x-fast trie 是 Dan Willard 在 1983 年提出的结构,可以看作 vEB 树思想的哈希化变体:

• 维护一棵逻辑上的完全二叉 trie(深度 log U);
• 每一层用一个哈希表存储该层出现的前缀;
• 后继查询通过二分搜索 trie 的层级,找到”分叉点”,然后利用叶子层的双向链表定位答案。

复杂度:

后继查询快,但插入/删除需要更新 O(log U) 层的哈希表。

5.4 y-fast trie

y-fast trie 进一步优化了 x-fast trie:

• 将 n 个元素分成 n / log U 组,每组约 log U 个元素;
• 每组用一棵平衡 BST 维护;
• 组的代表元素存入 x-fast trie。

复杂度:

y-fast trie 实现了与 vEB 树相同的时间复杂度,但空间仅为 O(n),是理论上最优雅的整数前驱结构之一。

5.5 三种结构对比

六、懒惰传播优化：O(1) 的 min/max

vEB 树中 min 和 max 的获取是 O(1) 的——这是设计的一部分,不是优化。但理解为什么这一点至关重要:

6.1 min 不进子结构

当我们向 vEB 树插入一个元素时,如果该元素成为新的 min,它不会被插入到任何 cluster 中。原来的 min 被”推”进合适的 cluster。

这意味着:

1. vEB-min(V) 只需返回 V.min,O(1);
2. vEB-max(V) 只需返回 V.max,O(1);
3. 判断 vEB 树是否为空只需检查 V.min == NIL,O(1)。

6.2 为什么这保证了 O(log log U)

考虑 insert 操作。当目标 cluster 为空时:

• 不需要递归进入 cluster(直接设置 min/max);
• 只需要递归进入 summary(标记该 cluster 非空)。

当目标 cluster 非空时:

• 只需要递归进入 cluster;
• 不需要递归进入 summary(summary 已经知道该 cluster 非空)。

在两种情况下,只进行一次递归调用。这就是 T(U) = T(sqrt(U)) + O(1) 成立的根本原因。

如果 min 也存储在 cluster 中,insert 可能需要同时递归 cluster 和 summary,递推变为 T(U) = 2T(sqrt(U)) + O(1),解为 O(log U)——优势全无。

6.3 延伸: 在其他场景中的懒惰传播

这种”懒惰存储”的思想在其他数据结构中也有体现:

• 线段树的 lazy propagation,延迟更新直到查询时才下推;
• Fibonacci 堆的级联切割,延迟维护堆序直到 extract-min;
• 并查集的路径压缩,延迟扁平化直到查询时执行。

vEB 树的 min/max 懒惰存储是同一设计哲学的精彩应用:把工作推迟到不可避免时再做,从而降低每次操作的递归分支数。

七、完整 C 实现

下面是一个完整的 vEB 树 C 语言实现。为了清晰起见,宇宙大小限制为 2 的幂次的幂次(2, 4, 16, 256, 65536 等)。实际使用时可以向上取整到最近的合法值。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define NIL (-1)

typedef struct vEB {
    int U;           // 宇宙大小
    int min;
    int max;
    struct vEB *summary;
    struct vEB **cluster;
} vEB;

/* ---------- 辅助函数 ---------- */

static int upper_sqrt(int U) {
    /* 计算 2^(ceil(lg(U)/2)) */
    int bits = 0, u = U;
    while (u > 1) { bits++; u >>= 1; }
    return 1 << ((bits + 1) / 2);
}

static int lower_sqrt(int U) {
    int bits = 0, u = U;
    while (u > 1) { bits++; u >>= 1; }
    return 1 << (bits / 2);
}

static int veb_high(int U, int x) {
    return x / lower_sqrt(U);
}

static int veb_low(int U, int x) {
    return x % lower_sqrt(U);
}

static int veb_index(int U, int hi, int lo) {
    return hi * lower_sqrt(U) + lo;
}

/* ---------- 创建与销毁 ---------- */

vEB *veb_create(int U) {
    vEB *V = (vEB *)calloc(1, sizeof(vEB));
    V->U = U;
    V->min = NIL;
    V->max = NIL;
    if (U > 2) {
        int hi = upper_sqrt(U);
        int lo = lower_sqrt(U);
        V->summary = veb_create(hi);
        V->cluster = (vEB **)calloc(hi, sizeof(vEB *));
        for (int i = 0; i < hi; i++) {
            V->cluster[i] = veb_create(lo);
        }
    }
    return V;
}

void veb_destroy(vEB *V) {
    if (V == NULL) return;
    if (V->U > 2) {
        int hi = upper_sqrt(V->U);
        for (int i = 0; i < hi; i++) {
            veb_destroy(V->cluster[i]);
        }
        free(V->cluster);
        veb_destroy(V->summary);
    }
    free(V);
}

/* ---------- 查询操作 ---------- */

int veb_min(vEB *V) {
    return V->min;
}

int veb_max(vEB *V) {
    return V->max;
}

int veb_member(vEB *V, int x) {
    if (x == V->min || x == V->max)
        return 1;
    if (V->U == 2)
        return 0;
    return veb_member(V->cluster[veb_high(V->U, x)],
                      veb_low(V->U, x));
}

int veb_successor(vEB *V, int x) {
    /* 基本情况 */
    if (V->U == 2) {
        if (x == 0 && V->max == 1)
            return 1;
        return NIL;
    }

    /* x 比 min 还小 */
    if (V->min != NIL && x < V->min)
        return V->min;

    /* 在同一个簇内找后继 */
    int hi = veb_high(V->U, x);
    int lo = veb_low(V->U, x);
    int max_lo = veb_max(V->cluster[hi]);

    if (max_lo != NIL && lo < max_lo) {
        int offset = veb_successor(V->cluster[hi], lo);
        return veb_index(V->U, hi, offset);
    }

    /* 查找下一个非空簇 */
    int succ_cluster = veb_successor(V->summary, hi);
    if (succ_cluster == NIL)
        return NIL;
    int offset = veb_min(V->cluster[succ_cluster]);
    return veb_index(V->U, succ_cluster, offset);
}

int veb_predecessor(vEB *V, int x) {
    if (V->U == 2) {
        if (x == 1 && V->min == 0)
            return 0;
        return NIL;
    }

    if (V->max != NIL && x > V->max)
        return V->max;

    int hi = veb_high(V->U, x);
    int lo = veb_low(V->U, x);
    int min_lo = veb_min(V->cluster[hi]);

    if (min_lo != NIL && lo > min_lo) {
        int offset = veb_predecessor(V->cluster[hi], lo);
        return veb_index(V->U, hi, offset);
    }

    int pred_cluster = veb_predecessor(V->summary, hi);
    if (pred_cluster == NIL) {
        if (V->min != NIL && x > V->min)
            return V->min;
        return NIL;
    }
    int offset = veb_max(V->cluster[pred_cluster]);
    return veb_index(V->U, pred_cluster, offset);
}

/* ---------- 修改操作 ---------- */

static void veb_empty_insert(vEB *V, int x) {
    V->min = x;
    V->max = x;
}

void veb_insert(vEB *V, int x) {
    if (V->min == NIL) {
        veb_empty_insert(V, x);
        return;
    }

    if (x < V->min) {
        int tmp = x; x = V->min; V->min = tmp;
    }

    if (V->U > 2) {
        int hi = veb_high(V->U, x);
        int lo = veb_low(V->U, x);
        if (veb_min(V->cluster[hi]) == NIL) {
            veb_insert(V->summary, hi);
            veb_empty_insert(V->cluster[hi], lo);
        } else {
            veb_insert(V->cluster[hi], lo);
        }
    }

    if (x > V->max)
        V->max = x;
}

void veb_delete(vEB *V, int x) {
    if (V->min == V->max) {
        V->min = NIL;
        V->max = NIL;
        return;
    }

    if (V->U == 2) {
        V->min = (x == 0) ? 1 : 0;
        V->max = V->min;
        return;
    }

    if (x == V->min) {
        int first = veb_min(V->summary);
        x = veb_index(V->U, first, veb_min(V->cluster[first]));
        V->min = x;
    }

    int hi = veb_high(V->U, x);
    int lo = veb_low(V->U, x);
    veb_delete(V->cluster[hi], lo);

    if (veb_min(V->cluster[hi]) == NIL) {
        veb_delete(V->summary, hi);
        if (x == V->max) {
            int s_max = veb_max(V->summary);
            if (s_max == NIL) {
                V->max = V->min;
            } else {
                V->max = veb_index(V->U, s_max,
                                   veb_max(V->cluster[s_max]));
            }
        }
    } else {
        if (x == V->max) {
            V->max = veb_index(V->U, hi,
                               veb_max(V->cluster[hi]));
        }
    }
}

/* ---------- 测试 ---------- */

int main(void) {
    const int U = 65536;  /* 2^16 */
    vEB *tree = veb_create(U);

    int keys[] = {2, 3, 4, 5, 7, 14, 15, 100, 200, 1000,
                  5000, 10000, 30000, 65000, 65535};
    int n = sizeof(keys) / sizeof(keys[0]);

    printf("=== Insert ===\n");
    for (int i = 0; i < n; i++) {
        veb_insert(tree, keys[i]);
        printf("  inserted %d\n", keys[i]);
    }

    printf("\n=== Query ===\n");
    printf("  min = %d, max = %d\n", veb_min(tree), veb_max(tree));
    printf("  member(7)   = %d\n", veb_member(tree, 7));
    printf("  member(8)   = %d\n", veb_member(tree, 8));
    printf("  succ(7)     = %d\n", veb_successor(tree, 7));
    printf("  succ(15)    = %d\n", veb_successor(tree, 15));
    printf("  pred(100)   = %d\n", veb_predecessor(tree, 100));
    printf("  pred(2)     = %d\n", veb_predecessor(tree, 2));

    printf("\n=== Successor chain from min ===\n  ");
    int cur = veb_min(tree);
    while (cur != NIL) {
        printf("%d ", cur);
        cur = veb_successor(tree, cur);
    }
    printf("\n");

    printf("\n=== Delete 7, 100, 65535 ===\n");
    veb_delete(tree, 7);
    veb_delete(tree, 100);
    veb_delete(tree, 65535);
    printf("  min = %d, max = %d\n", veb_min(tree), veb_max(tree));
    printf("  member(7)   = %d\n", veb_member(tree, 7));
    printf("  succ(5)     = %d\n", veb_successor(tree, 5));

    printf("\n=== Successor chain after deletion ===\n  ");
    cur = veb_min(tree);
    while (cur != NIL) {
        printf("%d ", cur);
        cur = veb_successor(tree, cur);
    }
    printf("\n");

    veb_destroy(tree);
    printf("\n=== Done ===\n");
    return 0;
}

编译与运行:

gcc -O2 -o veb veb.c -lm
./veb

预期输出:

=== Insert ===
  inserted 2
  inserted 3
  ...
=== Query ===
  min = 2, max = 65535
  member(7)   = 1
  member(8)   = 0
  succ(7)     = 14
  succ(15)    = 100
  pred(100)   = 15
  pred(2)     = -1

=== Successor chain from min ===
  2 3 4 5 7 14 15 100 200 1000 5000 10000 30000 65000 65535

=== Delete 7, 100, 65535 ===
  min = 2, max = 65000
  member(7)   = 0
  succ(5)     = 14

=== Successor chain after deletion ===
  2 3 4 5 14 15 200 1000 5000 10000 30000 65000

八、Linux 内核 O(1) 调度器：vEB 思想的实战回响

8.1 O(1) 调度器简史

Linux 2.6 内核引入了 Ingo Molnar 设计的 O(1) 调度器。它的核心目标是:无论系统中有多少可运行进程,选择下一个进程的时间都是常数。

8.2 位图层级: vEB 的精神后裔

O(1) 调度器维护 140 个优先级队列(0-139),用一个位图标记哪些优先级有就绪进程:

// 简化的内核结构
struct prio_array {
    int            nr_active;       // 活跃任务数
    unsigned long  bitmap[5];       // 140 位, 5 个 unsigned long (32位系统)
    struct list_head queue[140];    // 每个优先级一个链表
};

寻找最高优先级的就绪进程:

int idx = sched_find_first_bit(bitmap);
// 等价于: __builtin_ffsl() 或 bsf 指令
struct task_struct *next = list_first_entry(&queue[idx], ...);

这里的两层结构(bitmap + queue)正是 vEB 思想的特化:

1. bitmap 扮演 summary 的角色——标记哪些”簇”(优先级)非空;
2. queue 扮演 cluster 的角色——每个优先级内的进程链表;
3. 硬件 bsf/ffs 指令在 O(1) 时间内找到 bitmap 中的最低非零位。

当宇宙大小是常数(140 个优先级)时,log log U 也是常数——整个调度过程确实是 O(1)。

8.3 现代调度器的演进

Linux 2.6.23 之后,CFS(Completely Fair Scheduler)取代了 O(1) 调度器。CFS 使用红黑树按虚拟运行时间排序进程,选择最左节点作为下一个运行的进程,复杂度 O(log n)。

但 O(1) 调度器的位图思想并未消亡:

• 实时调度类(SCHED_FIFO/SCHED_RR)仍然使用位图方案;
• FreeBSD 的 ULE 调度器采用类似的多层位图;
• 内存分配器(如 buddy system)的空闲页查找也使用分层位图。

8.4 从 vEB 到位图: 实践中的简化

真实的调度器不会直接使用 vEB 树,原因很务实:

1. 优先级数量是固定的小常数(140),不需要通用的动态整数集合;
2. 硬件位扫描指令(bsf, bsr, ctz, clz)可以在单条指令内完成位图查询;
3. 位图的缓存行为极好——整个 bitmap 可以放入一个缓存行。

但从概念层面看,分层位图就是退化版的 vEB 树:宇宙大小是常数,所有”递归”都被展开成了固定层数的位操作。

九、基准测试：vEB 树 vs 平衡 BST vs 哈希表

理论复杂度是一回事,实际性能是另一回事。以下是在整数键操作场景下的典型基准测试结果。

9.1 测试设置

• 键空间: U = 2^20 (约 100 万)
• 元素数量 n: 从 1000 到 500000
• 操作: 随机 insert, 随机 successor, 随机 member
• 对比结构: vEB 树(预分配), std::set(红黑树), std::unordered_set(哈希表) + 线性扫描 successor
• 硬件: x86-64, 64KB L1d, 256KB L2, 单线程

9.2 结果摘要

+--------+--------------------+-------------------+-------------------+
|   n    | vEB successor (ns) | RBTree succ (ns)  | Hash+scan (ns)    |
+--------+--------------------+-------------------+-------------------+
|   1000 |          45        |        85         |      12000        |
|  10000 |          48        |       120         |      95000        |
|  50000 |          52        |       180         |     450000        |
| 100000 |          55        |       230         |    crash / OOM    |
| 500000 |          60        |       310         |         --        |
+--------+--------------------+-------------------+-------------------+

+--------+--------------------+-------------------+-------------------+
|   n    | vEB insert (ns)    | RBTree ins (ns)   | Hash insert (ns)  |
+--------+--------------------+-------------------+-------------------+
|   1000 |          40        |        95         |         35        |
|  10000 |          42        |       140         |         38        |
|  50000 |          46        |       200         |         42        |
| 100000 |          50        |       260         |         50        |
| 500000 |          55        |       340         |         65        |
+--------+--------------------+-------------------+-------------------+

+--------+--------------------+-------------------+-------------------+
|   n    | vEB member (ns)    | RBTree find (ns)  | Hash lookup (ns)  |
+--------+--------------------+-------------------+-------------------+
|   1000 |          38        |        80         |         25        |
|  10000 |          40        |       115         |         28        |
|  50000 |          44        |       170         |         32        |
| 100000 |          48        |       225         |         38        |
| 500000 |          52        |       300         |         55        |
+--------+--------------------+-------------------+-------------------+

9.3 关键观察

1. successor 查询: vEB 树的绝对优势场景。红黑树慢 3-5 倍,哈希表根本不支持高效的前驱/后继。

2. member 查询: 哈希表最快(预期 O(1)),vEB 树居中,红黑树最慢。但差距远不如 successor 大。

3. insert 操作: 哈希表和 vEB 树在小规模时接近;随着 n 增长,哈希表因 rehash 和缓存压力会出现偶发延迟尖峰,而 vEB 树的延迟非常稳定。

4. 缓存效应: vEB 树的递归结构在大宇宙下导致跨缓存行的指针追踪,但由于递归深度仅 log log U(约 4-5 层),总体影响有限。红黑树的 O(log n) 层指针追踪在大 n 时更严重。

5. 空间代价: vEB 树(预分配方式)消耗了大量内存。U = 2^20 时约 16MB 结构开销,而红黑树仅需约 n * 40 字节。

9.4 何时选择 vEB 树

十、实用性分析：O(log log n) 真的比 O(log n) 快吗

10.1 渐近分析的陷阱

O(log log n) 听起来比 O(log n) 快得多。但看看实际数字:

对于 32 位整数,理论加速比约 6 倍;对于 64 位,约 11 倍。这些数字确实显著,但远不是”常数 vs 对数”那么戏剧性。

10.2 常数因子的较量

渐近分析忽略了常数因子。在实际中:

• 红黑树每步操作: 1 次比较 + 1 次指针跟随,约 3-5ns(缓存命中时);
• vEB 树每步操作: 1 次除法/模运算 + 1 次指针跟随 + 可能的 min/max 检查,约 8-12ns。

vEB 树的每步操作常数因子约为红黑树的 2-3 倍。因此 6 倍的渐近加速在实际中可能只表现为 2-3 倍的实际加速。

10.3 缓存层级的影响

在现代硬件上,缓存行为往往比算法复杂度更重要:

• 红黑树: 每个节点约 32-40 字节,log(n) 次指针跟随,几乎每次都可能缓存未命中;
• vEB 树(预分配): 结构巨大,但递归深度浅;热路径上的节点可能驻留在 L2/L3;
• B 树/B+ 树: 高扇出,低树高,缓存友好——在实际中常常比 vEB 树更快。

10.4 现实结论

O(log log n) 相对于 O(log n) 的优势是真实的,但需要满足以下条件才能在实践中体现:

1. 键空间有界且不太大(U <= 2^24 左右,否则空间爆炸);
2. successor/predecessor 是热点操作(占查询的 > 50%);
3. 数据集足够大(n > 10000),让渐近优势超过常数因子;
4. 延迟稳定性比吞吐量更重要(vEB 无最坏情况退化)。

十一、工程陷阱速查表

在实际工程中使用 vEB 树(或其变体)时,以下是常见的陷阱和注意事项:

十二、个人看法与总结

12.1 vEB 树的理论地位

Van Emde Boas 树是计算机科学中最优美的数据结构之一。它用一个简洁的递归思想——平方根分裂——打破了比较模型下 O(log n) 的壁垒。这提醒我们,当我们愿意对输入施加额外假设(整数键、有界宇宙)时,理论上可以做到的远比一般模型所暗示的更多。

从教学角度看,vEB 树是理解以下概念的绝佳载体:

• 递归与分治的深层形式: 不是简单的二分,而是平方根级别的分裂;
• 懒惰计算的力量: min/max 不进子结构,这个小技巧决定了整个复杂度;
• 空间-时间权衡: 从 O(U) 空间到 O(n) 的演变(vEB -> x-fast -> y-fast)是一条经典的优化路径;
• 理论与实践的张力: O(log log n) 在渐近意义上完胜 O(log n),但常数因子、缓存效应、实现复杂度会在实际中大幅削弱这一优势。

12.2 工程中的真实角色

在我个人的经验中,直接在生产系统中使用完整 vEB 树的情况几乎没有。但 vEB 树的思想以各种退化和变形的方式渗透到了许多实际系统中:

• 操作系统的多层位图调度(如前文讨论的 O(1) 调度器);
• 内存分配器中的分层空闲列表(buddy system 的位图层级);
• 网络路由器中的多比特 trie(IP 前缀查找);
• 数据库索引中的 Judy Array(分层压缩位图)。

这些系统的设计者可能从未想过”我在实现 vEB 树”,但他们独立地发现了同样的核心思想:用分层摘要加速整数空间的搜索。

12.3 我的建议

1. 学 vEB 树: 它是算法设计中不可多得的教学案例。理解它的递归结构和 min/max 技巧,会加深你对递归、分治和惰性计算的理解。

2. 慎用 vEB 树: 在大多数实际场景中,一棵调优过的 B+ 树或一个 Robin Hood 哈希表会比教科书式的 vEB 树表现更好。只有在 successor/predecessor 是绝对热点、键空间有界、且你对空间开销有预算时,才考虑实际部署。

3. 用 vEB 思想: 即使不直接使用 vEB 树,分层位图、平方根分块、摘要结构这些思想可以被提取出来,应用到你自己的数据结构设计中。

4. 了解替代方案: y-fast trie 在理论上更优雅(O(n) 空间),fusion tree 在更强的计算模型下可以做到 O(sqrt(log n))。了解这些替代方案有助于在具体场景中做出正确选择。

算法研究的魅力之一,在于一个 1975 年由 Peter van Emde Boas 提出的想法,至今仍在启发新一代的系统设计。O(log log n) 不只是一个渐近符号——它代表了一种思维方式:当你面对看似不可逾越的复杂度壁垒时,换一个角度(比如对输入做假设,或者用不同的计算原语),壁垒就可能被打破。

上一篇: 持久化数据结构 下一篇: Merkle 树与认证数据结构

相关阅读: - 红黑树 vs AVL - 进程调度