红黑树用于内存管理中高效组织空闲/已分配区间，解决快速查找合适地址块问题；采用地址树与大小树双索引结构，支持o(log n)的查找、插入、删除及合并操作。
红黑树本身不直接管理内存地址分配，而是作为底层数据结构，高效支撑内存管理器对“空闲/已分配区间”的组织与查询。它不替代 malloc/free，也不参与物理页帧调度，而是解决“如何快速找一块合适大小的空闲地址区间”这个核心问题。
为什么选红黑树而不是链表或数组
在动态分区分配场景中（如用户态内存池或内核 buddy 系统的辅助索引），需要频繁执行以下操作：
- 按起始地址查找重叠或相邻区间（合并回收时）
- 按大小快速找到“≥请求尺寸”的最小可用块（最佳适配）
- 插入新释放的区间、删除已分配区间
- 支持高并发下的低锁粒度操作（如基于区间的读写锁分离）
普通链表查区间耗时 O(n)，排序数组插入删除 O(n)；而红黑树能同时保证：区间按地址有序（支持范围合并）、按大小建索引（需额外字段）、所有操作稳定在 O(log n)。
关键设计：双索引红黑树结构
单棵树无法兼顾“地址顺序”和“大小查询”，实际实现常采用两个红黑树协同：
- 地址树：节点键为区间起始地址，值包含 {start, size, is_free}，用于合并回收（检查前后邻接）、遍历全部空闲块
- 大小树：节点键为区间 size（可加哈希桶处理相同大小），值为指向地址树中对应节点的指针；支持 O(log n) 找到 ≥req_size 的最小空闲块
分配时先查大小树定位候选块，再通过指针访问地址树完成切割与更新；释放时先插入地址树，再根据合并结果同步更新大小树。
区间操作的典型流程
以一次 8KB 分配为例：
- 在大小树中查找 key ≥ 8192 的最左节点 → 得到一个 16KB 空闲块引用
- 从地址树中取出该块：[0x100000, size=16384]
- 若 size > req + 最小分割阈值（如 256B），则拆分为 [0x100000, 8192]（分配）和 [0x102000, 8192]（插入回两棵树）
- 更新地址树：删除原节点，插入新空闲节点；更新大小树：移除旧 size 键，插入新 size 键
回收时，先插入地址树，再检查 left/right 邻居是否空闲——若相邻，合并后从两棵树中删除旧节点、插入新合并节点。
工程落地注意事项
真实系统中需规避红黑树常见陷阱：
- 节点不能只存 raw pointer，须封装为带 refcount 或 arena_id 的结构，防止跨内存池误操作
- 大小树键建议用 size + 地址低位哈希 组合，避免相同 size 区间键冲突
- 为减少内存开销，节点常复用区间结构体本身（即“intrusive rbtree”），不额外 malloc 节点内存
- 多线程下推荐 per-CPU 红黑树 + 全局迁移机制，而非全局锁——Linux slab 分配器即采用类似思路
