epoll 在 Linux 内核底层使用 红黑树（Red-Black Tree） 来管理感兴趣的文件描述符（File Descriptors, FDs），这主要是基于性能、稳定性和功能需求的综合考量。
高效的增、删、改、查操作 (O(log N))
epoll 的工作流程涉及频繁对监控列表进行操作（通过 epoll_ctl 系统调用）：
- 添加 (EPOLL_CTL_ADD)：将一个新的 FD 加入监控集合。
- 修改 (EPOLL_CTL_MOD)：更改某个 FD 的监控事件类型（如从读变写）。
- 删除 (EPOLL_CTL_DEL)：将不再需要的 FD 移出监控集合。
- 查询：在执行上述操作前，内核需要先找到对应的 FD 是否已经在集合中。
红黑树作为一种自平衡二叉搜索树，能够保证在最坏情况下，这些操作的时间复杂度都稳定在 （ 为监控的 FD 数量）。相比之下，select 和 poll 使用的是线性数组或链表，查询和删除的复杂度是 ，当连接数达到万级甚至百万级时，性能差距巨大。
稳定的最坏情况性能
虽然 哈希表（Hash Table） 在平均情况下的查询复杂度是 ，但在内核中使用哈希表存在一些挑战：
- 最坏情况：哈希冲突可能导致性能退化到 。
- 动态扩容：当监控的 FD 数量剧增时，哈希表的重新哈希（Rehash）操作会产生巨大的瞬间开销和不确定的延迟。
- 内存开销：哈希表通常需要预分配较大的连续内存空间。
红黑树提供了确定性的 性能，不会有哈希冲突导致的极端情况，且随着 FD 数量的增加，内存增长是平滑的。
FD 的天然特性：有序可比较
在 Linux 中，文件描述符（FD）本质上是非负整数。这种天然的顺序性使得它们非常适合作为平衡二叉树的键（Key）。通过 FD 大小进行排序，红黑树可以非常快速地定位到特定的节点。
解决 select/poll 的瓶颈
在 select 模型中，内核每次被调用都要遍历整个 FD 集合。而 epoll 采用了“空间换时间”的策略：
- 红黑树（Interest List）：持久化地存储在内核空间，记录所有需要监控的 FD。这样，每次调用
epoll_wait时，不需要像select那样重复地从用户态拷贝成千上万个 FD 到内核态。 - 就绪链表（Ready List）：这是一个双向链表。当 FD 状态改变时，内核通过回调机制（Callback）直接将该节点挂载到就绪链表中。
总结
选择红黑树是因为它在 的时间复杂度下，为内核提供了最稳健、最高效的 FD 管理方式。它在频繁的增删改查操作中表现极其出色，是 epoll 能够支持“ C10M ”（千万级并发）目标的关键基石之一。
| 数据结构 | 查询/增删复杂度 | 优势 | 劣势 |
|---|---|---|---|
| 数组/链表 (select/poll) | 实现简单 | 并发高时性能线性下降 | |
| 哈希表 | 平均 , 最坏 | 平均速度最快 | 扩容开销大，性能波动，最坏情况不可控 |
| 红黑树 (epoll) | 性能稳定，适合大规模并发，增删改查均衡 | 相对哈希表平均稍慢（微秒级差异） |