Epoll内部数据结构

epoll池红黑树：

在Linux内核中，实现Epoll池的数据结构采用的是红黑树（一种自平衡二叉查找树）去实现的，保证了所有的增、删、改、查操作的平均时间复杂度维持在 O(logN) 的对数级水平。

红黑树：

一种自平衡二叉查找树。它的 root.left 的值一定会比 root 本身的值更小，root.right 的值一定会比 root 本身的值更大。所以我们要检索一个值时，每到一个节点我们都可以通过一个二分的方式去快速的过滤掉一半的结果，本质上就是二分查找的过程。

但二分查找树的左子树与右子树的数据规模要处于一个量级之内，不能出现完全失衡的极端情况，这样二分就会失效。

所以红黑树自身通过一定方式将两颗子树上的节点数量维持在了一个量级之内，最多相差一倍（根据下面4、5两条特性保证最多相差一倍）。

特性：

• 根节点是黑色节点
• 红黑树的根节点是黑色的，叶节点（都是 nil 节点）也是黑色的。
• 除此之外其他都是红的。
• 且从根节点到叶节点的路径上不能出现两个连续的红色节点。
• 从任意一条根节点到叶节点的路径中，都包含有相同数目的黑色节点。

有争论说 Hash map 能用，为什么要用 红黑树？

因为 Hash map 是渐进式桶结构，随着存入数据量的增多，桶渐进式增大，但每次扩容的时候都需要有每一个操作的一个使用方法去将数据由旧桶转移向扩容后的新桶。这个扩容的流程相对来说挺复杂的，更致命的是 Hash map 扩容之后，如果数据量变少想缩容，那成本也不低。

完全基于FD去作为Key 是完全不足够的。打个比方说：我们监听事件，看这个事件下查询有那些FD，有那些loop threat，在这种情况下FD作为Key是局限的，实现不了对应完全的查询工作。

相对下，用红黑树可以在监听事件的基础上，将对应的FD也拼接进树中，用这样的二维复合键，我们就能保证在上面那种情况下，实现对应完全的查询工作。在使用联合键的情况下，红黑树 比 Hash map 更加灵活。

而且在数据规模比较小的时候，Hash map 的作用并不如 红黑树 好，因为时间复杂度 BigO(N) 和 BigO(logN) 相差不大。虽然 Hash map 是一个常熟级别的时间复杂度，但是它的常数项是非常大的，是一个高常数系数的常数级别时间复杂度。

就绪事件队列：

针对于FD中就绪的IO event，通常由于数量有限，且每个事件都要单一处理，没有优先级之分，因此可以采用简单的双向链表实现。