← Back to Blog
EN中文

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

在高性能系统编程中，我们经常面临一个残酷的二选一：是追求极致的内存布局和缓存友好性，还是享受标准库容器带来的便利？

当我们使用 std::map 或 std::set（或者其他语言中的类似结构）时，往往忽略了它们背后的隐性成本：每一次插入都伴随着一次堆内存分配。成千上万个微小的节点散落在堆内存的各个角落，不仅导致了严重的内存碎片，更让 CPU 的缓存预取机制失效——在遍历树时，CPU 不得不在内存中“跳来跳去”，即所谓的 Pointer Chasing（指针追逐）。

今天，我们来解构一种在工业级基础设施（如操作系统内核、游戏引擎、高频交易系统）中广泛使用的模式：侵入式红黑树 (Intrusive Red-Black Tree)。我们将使用 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 函数，它通过 pointer casting 将 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)$ 随机访问

标准的红黑树只能通过 Key 进行查找。如果我们想查找“第 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);
}

设计权衡与总结

这种设计并非没有代价。

优点：

  • 性能极致：零分配、高缓存命中。
  • 功能强大：同时支持 Key 查找和 Index 查找。
  • 灵活：对象生命周期由用户控制，不再受容器束缚。

缺点：

  • 侵入性：你的业务结构体必须“被污染”，包含红黑树节点字段。
  • 安全性：用户必须确保对象在从树中移除前不被销毁（虽然 Zig 的所有权模型对此有一定帮助，但仍需小心）。

在系统级编程中，当性能成为瓶颈时，侵入式数据结构往往是打破天花板的那把锤子。Zig 语言通过 fieldParentPtr 和显式的内存模型，让这种古老而硬核的技术变得更加清晰和安全。