Yuxu Ge
文章 · 2026-02-25

侵入式红黑树：内存布局与索引效率的终极平衡

高性能系统编程强制了一种选择：优化内存布局和缓存效率，或接受标准库容器的便利。std::map 和 std::set 这样的容器在易用性背后隐藏了显著成本。每次插入都伴随堆内存分配；成千上万个散落的微小分配导致内存碎片并禁用 CPU 缓存预取。树遍历时 CPU 在内存中跳跃—指针追逐—而非访问连续数据。

侵入式红黑树通过直接在业务对象中嵌入树的链接字段来绕过这一权衡。这种模式在性能关键的基础设施中广泛使用：操作系统内核、游戏引擎和高频交易系统。Zig 提供了优雅的工具来安全透明地实现它，在一个单一结构中结合零分配开销、缓存局部性和 O(log N) 随机访问。

什么是"侵入式"？

在标准容器（非侵入式）中，容器负责分配节点内存和持有数据。数据对容器一无所知。

// 非侵入式：容器包裹数据
const Node = struct {
    left: ?*Node,
    right: ?*Node,
    data: UserData, // 数据被拷贝或指针引用
};

而在侵入式设计中，数据本身就是节点。业务对象"知道"自己是容器的一部分，它主动嵌入了所需的链接字段（如 left、right、parent）。

// 侵入式：数据嵌入节点
const UserData = struct {
    id: u64,
    name: []const u8,
    // 侵入式节点，直接嵌入业务结构体
    rb_node: RbNode, 
};

这种反转带来了实质性的优势：

  1. 零额外分配：插入元素时不需要 malloc 新节点，因为节点已在对象内部。
  2. 缓存友好：业务数据和树的链接信息在内存中是连续的。
  3. 多重索引：一个对象可以同时嵌入多个不同的节点（如 rb_node、list_node），从而同时存在于红黑树和链表中，无需复杂的反向指针维护。

Zig 实现：fieldParentPtr 的魔法

在 C++ 中，侵入式容器通常通过复杂的模板和继承（CRTP）来实现。而在 Zig 中，"从节点恢复对象"的逻辑可以用 fieldParentPtr 以更优雅和显式的方式处理。

首先，定义嵌入式的红黑树节点。注意我们增加了一个 size 字段，这对于下文讨论的高效索引至关重要。

const Color = enum { red, black };

/// 侵入式红黑树节点，嵌入业务对象中
pub const RbNode = struct {
    parent: ?*RbNode = null,
    left: ?*RbNode = null,
    right: ?*RbNode = null,
    color: Color = .red,
    /// 子树大小（包括自身），用于实现 O(log N) 的随机访问
    size: usize = 1, 
};

接下来是容器的核心逻辑。注意 getEntry 函数，它通过指针转换将 RbNode 的指针还原为宿主对象 T 的指针。这一机制是侵入式容器的核心。

pub fn IntrusiveRbTree(comptime T: type, comptime field_name: []const u8) type {
    return struct {
        const Self = @This();
        root: ?*RbNode = null,

        /// 从 Node 指针“反推”回业务对象 T 的指针
        fn getEntry(node: *RbNode) *T {
            return @fieldParentPtr(T, field_name, node);
        }

        fn getSize(node: ?*RbNode) usize {
            if (node) |n| return n.size;
            return 0;
        }

        // ... 插入与旋转逻辑 ...
    };
}

核心特性：size 计数与 O(log N) 随机访问

标准的红黑树仅支持基于键的查找。要查找"第 100 小的元素"通常需要 O(N) 的遍历。

在我们的设计中，每个节点维护了一个 size 字段：当前节点加其左右子树的总节点数。这让红黑树具备了类似数组的特性：

/// 获取排名为 index 的元素，时间复杂度 O(log N)
pub fn at(self: *Self, index: usize) ?*T {
    var curr = self.root;
    var idx = index;

    while (curr) |n| {
        const left_sz = getSize(n.left);
        if (idx < left_sz) {
            // 目标在左子树
            curr = n.left;
        } else if (idx == left_sz) {
            // 当前节点即为目标
            return getEntry(n);
        } else {
            // 目标在右子树，索引减去左子树数量和当前节点
            idx -= left_sz + 1;
            curr = n.right;
        }
    }
    return null;
}

这种设计适合需要频繁通过排名或索引访问数据的场景——排行榜、有序序列的随机采样——同时保持了 O(log N) 的插入和删除性能。代价是每次旋转和变色操作都需要更新受影响路径上的 size，但这仅构成每次操作的常数级别开销。

完整演示

让我们看看如何在实际代码中使用它：

const std = @import("std");

// 业务对象
const Monster = struct {
    hp: i32,
    attack: i32,
    // 嵌入节点，使其成为树的一部分
    node: RbNode = .{},

    // 比较函数，决定树的排序
    pub fn compare(self: *Monster, other: *Monster) i32 {
        if (self.hp < other.hp) return -1;
        if (self.hp > other.hp) return 1;
        return 0;
    }
};

test "intrusive tree demo" {
    // 定义一个以 "node" 字段为钩子的红黑树
    var tree = IntrusiveRbTree(Monster, "node"){};

    // 对象在栈上或任何地方分配，容器不负责分配
    var m1 = Monster{ .hp = 100, .attack = 10 };
    var m2 = Monster{ .hp = 200, .attack = 50 };
    var m3 = Monster{ .hp = 50, .attack = 5 };

    // 插入指针，零内存分配
    tree.insert(&m1);
    tree.insert(&m2);
    tree.insert(&m3);

    // 验证顺序 (按 HP 排序: 50, 100, 200)
    // 获取第 1 个元素 (索引 1)，应该是 HP=100 的 m1
    const found = tree.at(1); 
    try std.testing.expect(found.?.hp == 100);
}

设计权衡

这种设计存在明确的权衡。

优点：

缺点：

当系统编程中性能成为瓶颈时，侵入式数据结构通常能提供必要的突破。Zig 的 fieldParentPtr 和显式的内存模型使这一经典技术相比传统的 C++ CRTP 方法更加透明和安全。

© 2026 Yuxu Ge ·