Linux 内核为什么大量使用红黑树
哪些公司问过
答案要点
- 红黑树查找、插入、删除最坏都是 O(log n),性能可预期
- 插入删除的旋转次数有常数上界,适合修改频繁的场景
- 相比 AVL 平衡要求更宽松,删除时维护代价更低
- B 树面向块设备,在纯内存场景下优势不明显且实现复杂
- 典型应用:CFS 调度队列、VMA 管理、定时器等
易错点
- 说红黑树查找比 AVL 快,其实 AVL 更平衡查找通常略快
- 把 B 树与红黑树的取舍说成谁更快,忽略磁盘与内存的场景差异
- 只说复杂度,不提旋转次数有界这一关键优势
面试官常见追问
- 为什么不用哈希表?
- 内核 rbtree 的侵入式设计有什么好处?
- 新版内核 VMA 管理还用红黑树吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。