标签：#红黑树 #Linux内核 #CFS调度器 #HashMap #Nginx

预计阅读时间：12分钟

开篇-一棵树上挂满了进程

Linux操作系统里同时运行着几百个进程。有的在看视频，有的在处理请求，有的躲在后台扫磁盘。CPU只有几个核心，该让谁跑、让谁等？

Linux的答案是：红黑树。每个可运行的进程都挂在CFS调度器的红黑树上，按"虚拟运行时间"排序。每次调度，CPU就选树上vruntime最小的进程运行。

不止Linux。Java的HashMap在冲突严重时，链表会变成红黑树。Nginx用红黑树管理超时事件。为什么这些系统不约而同地选择了红黑树？

应用一：Linux CFS调度器——谁该用CPU

CFS（Completely Fair Scheduler）是Linux的进程调度器。它的核心思想很简单：让每个进程都能公平地分到CPU时间。

怎么衡量公平？每个进程有一个值叫 vruntime（虚拟运行时间）：

• 进程运行的时间越长，vruntime越大
• 优先级高的进程，vruntime增长得慢（权重高，跑得少也能排前面）
• 优先级低的进程，vruntime增长得快（权重低，跑得多也排后面）

所有可运行的进程按vruntime排序，存在一棵红黑树里：

调度时选vruntime最小的进程——就是树的最左节点。O(log n)。

新进程加入时，计算它的vruntime，插入到正确的位置。O(log n)。

进程运行了一段时间后，vruntime增加，需要更新它在树上的位置。删除旧位置，插入新位置。两次O(log n)。

为什么用红黑树而不是数组或链表？

堆也能O(log n)插入删除，但堆不支持"按值查找"。CFS需要频繁更新某个进程的vruntime，堆没有"找到某个值并更新"的能力。红黑树是BST，有查找能力，所以能胜任。

为什么不用AVL树？ CFS的调度是高频操作，进程的插入、删除、更新非常频繁。红黑树的写操作旋转次数更少，在这种"写多读少"的场景下比AVL树更合适。

应用二：Java HashMap——从链表到树的进化

Java8之前，HashMap用链表处理哈希冲突。当冲突严重时，链表越来越长，查找从O(1)退化到O(n)。

Java8的优化：链表长度>8且数组>64时，链表转红黑树。

转树后，查找从O(n)变成O(log n)。8个元素的链表最坏查8次，红黑树最多查log₂(8)=3次。

为什么是8？ 不是拍脑袋定的。哈希冲突是泊松分布，正常情况下链表长度超过8的概率不到0.06%。如果链表真的超过了8，说明要么哈希函数分布有问题，要么有人在恶意攻击（构造大量相同哈希值的数据）。转树是一种"保底机制"——正常情况下用链表（O(1)），极端情况下用红黑树（O(log n)）。

为什么不直接用树？ 树比链表复杂得多。链表插入删除O(1)，红黑树O(log n)。在冲突不严重的情况下，链表更快更简单。转树只在极端情况下触发，是"锦上添花"不是"画蛇添足"。

这个设计体现了工程智慧：两套机制互补，简单场景用简单方案，极端场景用保底方案。

应用三：Nginx定时器——谁超时了

Nginx是高性能Web服务器，一个Worker进程可能同时处理几万条连接。每条连接都有超时时间——多久没收到数据就断开。

怎么高效管理几万个定时事件？

Nginx用红黑树按超时时间排序存储所有定时事件。每次事件循环，检查树的最小值（最早超时的），如果当前时间已经超过超时时间，就触发超时处理。

当前时间=90ms：检查最左节点10ms，已超时→处理→删除。下一个最左80ms，已超时→处理→删除。下一个50ms...如此往复，直到最左节点未超时为止。

为什么用红黑树？

• 插入新连接的超时时间：O(log n)
• 删除已关闭连接的定时器：O(log n)
• 找最早超时的（最左节点）：O(log n)（或维护一个指针做到O(1) amortized）

如果用数组或链表，几万个定时器的插入删除会变成瓶颈。红黑树让Nginx能轻松管理数万条连接的定时事件。

总结

金句：红黑树在工程界的地位，可以用一句话概括——它不完美，但足够好。查询比AVL树稍慢，插入删除旋转更少。Linux选它调度进程，Java选它保底HashMap，Nginx选它管理定时器。在"读"和"写"的永恒权衡中，红黑树找到了一个让大多数人满意的平衡点。

觉得有收获？转发给你的技术伙伴。

你日常用的编程语言和框架里，还有哪些地方悄悄用了红黑树？比如C++的std::map、Java的TreeSet、Linux的内存管理——你有没有好奇过，为什么它们不选AVL树或B+树？评论区聊聊你的猜测。