linux - 深入了解 Linux 2.6 完全公平调度器

Question

我正在研究这个链接上使用 RED-BLACK_TREE 数据结构的 CFS 调度算法 http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler

我的问题是:在CFS中使用红黑树的目的是什么，为什么不能使用AVL树？

Answer 1

注意:我是从纯粹的算法角度(基本搜索树操作在实践中的性能)回答这个问题，我不知道 Linux 开发者是否有其他选择 RB 的内部原因树(它可能会让它们做某些 AVL 树不会做的事情)。

一般来说，两者是可以互换的，就功能而言，它们也可以与基本的搜索树、treaps、splay 树等互换。区别在于实际性能，因为所有平衡搜索树(AVL 和 RB 树都是平衡的)具有相同的理论性能。

根据这两种数据结构(AVL、RB)的维基页面，AVL 树在查询方面表现更好，在插入和删除方面表现更差。如果您查看一个实现，这很容易注意到:平衡 AVL 树涉及更多，导致实践中性能较慢。

所以我的猜测是，他们可以使用 AVL 树(除非他们利用 RB 树具有而 AVL 树不具有的结构属性，这不太可能)，但他们更关心插入和删除性能而不是查询性能，所以他们选择了 RB。

还值得一提的是，C++、Java 和 .NET 中的许多内置数据结构在其实现中都使用了红黑树，这可能也是因为它们在所有操作上的性能相似。