红黑树在Nginx模块中是管理有序、动态、高频操作的核心结构；ngx_rbtree_t为高性能无锁轻量实现，节点须嵌入用户结构体，比较逻辑由用户定义，所有操作时间复杂度O(log n)。
红黑树在 Nginx 模块开发中是管理有序、动态、高频查询/插入/删除状态的核心数据结构。ngx_rbtree_t 不是通用容器，而是为高性能、无锁（单线程上下文）、内存紧凑设计的轻量级实现，适用于连接跟踪、限流计数、缓存索引、会话管理等场景。
理解 ngx_rbtree_t 的底层约束
它不提供内存自动管理，节点必须嵌入用户结构体中（类似 Linux kernel 的 list_head），且比较逻辑完全由用户定义；树本身不保存长度，遍历需手动计数；所有操作（插入、查找、删除）时间复杂度均为 O(log n)，但常数极小，适合事件循环内快速响应。
关键点：
- 每个节点必须包含 ngx_rbtree_node_t 成员，并通过 offsetof 告知树该成员在结构体中的偏移
- 比较函数接收两个 ngx_rbtree_node_t *，需强制转为实际结构体指针后比对业务字段（如 session_id、timestamp）
- 树根（ngx_rbtree_t root）和哨兵节点（ngx_rbtree_sentinel_t）需显式初始化，通常放在模块配置或共享内存段中
典型用法：按时间戳淘汰的连接状态缓存
假设模块需记录活跃 WebSocket 连接的最后活动时间，超时 60 秒即清理。此时红黑树可按 last_active_time 排序，最左节点即最早超时者，便于定时扫描清理。
示例结构定义：
typedef struct {
ngx_rbtree_node_t node;
ngx_connection_t *conn;
ngx_msec_t last_active_time;
u_char session_id[32];
} my_conn_node_t;
插入时调用 ngx_rbtree_insert(&tree, &node->node)；查找指定 session 可写二分逻辑（因不支持哈希，需遍历比较 session_id）；清理超时项只需从最左节点开始向右遍历，遇到未超时即停。
与共享内存（shmtx + slab）配合使用
若状态需跨 worker 进程可见（如全局限流计数），必须将红黑树放在 ngx_shm_zone_t 分配的共享内存中，并用 ngx_shmtx_t 保护写操作。注意：红黑树本身不处理并发，读可无锁（只要无写），写必须加锁；推荐细粒度锁（如 per-bucket 锁）而非全局树锁，避免成为瓶颈。
常见错误：
- 在 shared memory 中直接 malloc 节点 —— 必须用 ngx_slab_alloc 分配，否则越界或碎片
- 忘记在 postconfiguration 阶段初始化树根和哨兵，导致插入崩溃
- 比较函数返回值未严格遵循三态（-1 / 0 / 1），引发树结构错乱
调试与可观测性建议
Nginx 不提供内置树遍历打印接口，调试时建议在开发阶段添加临时 handler（如 /status/mytree），输出节点数量、最小/最大 key、前 10 个节点信息。可借助 ngx_rbtree_min 和 ngx_rbtree_next 手动中序遍历。上线后建议导出指标：当前节点数、平均查找深度、最近一次插入耗时（微秒级），便于容量评估。
