Linux内核在TCP方面使用链表，在进程调度方面使用RB树。
从算法效率的角度来看，这是有道理的。您将会一次又一次地收到一堆数据包，因此在列表末尾进行O(1)插入很好。
对于进程调度，完全公平调度程序使用红黑树，在选择任务时具有O(1)时间。
据我所知，这两者都没有以“平坦”的方式实现 - 链表是一堆带有指向其他节点的指针的节点，就像树一样。就我所知，这意味着这些结构的局部性应该很差。
从我所见过的情况来看，缓存区域常常比算法效率更加重要。
Linux所编写的数据集是否具有使这些结构的算法效率优于其他缓存效率的特点？
我是否误解了什么？有人进行过分析吗？
我对使用链表的部分问题有一些答案，我相信你会在CFS调度器的这个页面中找到一些有趣的信息，特别是它提到红黑树具有良好的最坏时间复杂度，例如插入、搜索和删除操作，这似乎确实是一个非常理想的调度器属性。
我敢打赌，内核应该已经经历了很多性能分析，这些数据结构在实际应用中似乎表现良好。
这篇博客文章提供了有关内核链表使用情况的一些好数据。这些数据显然是通过在正常使用期间保持每个操作的计数器来收集的，历时三天。
+--------------------+-----------+
| Operation | Frequency |
+--------------------+-----------+
| Empty Test | 45% |
| Delete | 25% |
| Add | 23% |
| Iterate Start | 3.5% |
| Iterate Next | 2.5% |
| Replace | 0.76% |
| Other Manipulation | 0.0072% |
+--------------------+-----------+
正如你所看到的，在实际访问元素的操作中仅占总量的6％，而插入和删除则占了近一半。这是一个使用链表会更加合理的用例。请注意，该数据是针对整个内核而不是特定的TCP代码收集的，因此每次使用链表时的基本原理可能并不相同，但汇总数据确实表明这些选择总体上是明智的。
我认为还要牢记的是，内核的设计必须能够从最小的嵌入式设备扩展到处理大量数据的超级计算机，这时，算法效率可能开始严重超过缓存问题。