Featured image of post linux 内核当中的各种树型结构总结
kernel

linux 内核当中的各种树型结构总结

算法课

华东理工大学教授：罗永军。QQ ：15512356 QQ 群：567554289

B 站上的系列视频：

https://www.bilibili.com/video/BV1H84y1M7mL

B 站上的 ID 是：三金蝈蝈

他系统的讲解了算法知识，真的让没参加过算法竞赛的我大开眼界。很多人赢在了高中，或者说赢在了专注和韧性上。

内核当中用到的树

在 Linux内核中，树型数据结构是常用的数据结构之一，因其在很多系统资源管理和算法优化方面具有重要作用。下面是一些Linux 内核中常用的树型数据结构：

1. 红黑树（Red-Black Tree）

介绍：

红黑树是一种自平衡的二叉查找树，每个节点包含一个额外的颜色属性，可以是红色或黑色。它的插入、删除和查找操作都可以在对数时间内完成。由于其良好的平衡特性，红黑树在Linux 内核中得到了广泛应用。

用途：

  • 进程调度 ：在 Linux内核的进程调度中，红黑树用于实现按优先级排序的队列（如 rt 调度器的任务队列）。
  • 内存管理 ：用于管理内存区域的分配与回收，尤其在页表的管理中。
  • 文件系统 ：在文件系统（如ext4）中，红黑树用于索引和管理文件块，减少查找时间。

相关接口：

  • RB_TREE 、 RB_ROOT 、 RB_NODE
  • rb_insert(), rb_remove(), rb_find(), rb_next()

2. AVL 树（AVL Tree）

介绍：

AVL树是一种自平衡的二叉查找树，通过维护树的平衡因子（每个节点的左右子树高度差）来保证其高度始终保持对数级别。与红黑树相比，AVL树的平衡更加严格，查找操作时间更短，但插入和删除操作的开销较大。

这个东西是前苏联的数学家维尔斯基和兰迪斯两个人发明的。这两个人都在 2000 年左右去世了。

用途：

  • 网络协议栈 ：在一些网络协议的实现中，AVL 树用于快速查找网络路由或 IP地址。
  • 内存分配 ：一些内存管理系统中也使用 AVL 树来管理内存区域。

相关接口：

  • 在 Linux 内核中，AVL 树不如红黑树普遍使用，但也有部分内核子系统使用AVL 树实现。

3. 二叉搜索树（Binary Search Tree，BST）

介绍：

二叉搜索树是最简单的树型数据结构，每个节点包含一个键值和两个子节点，且每个节点的左子树的键值小于该节点的键值，右子树的键值大于该节点的键值。

用途：

  • 内核的资源管理 ：在一些简单的资源管理场景下，可能会使用二叉搜索树来快速查找某个资源。

相关接口：

  • Linux 内核中通常不直接使用纯粹的二叉搜索树，而是基于红黑树、AVL树等更复杂的数据结构进行扩展。

4. B树（B-Tree）

介绍：

B树是一种自平衡的多路查找树，适合用于存储大量数据，并且广泛应用于数据库和文件系统中。B树的特点是节点可以有多个子节点，且其数据是有序的，能够高效地进行范围查找。

用途：

  • 文件系统 ：在 Linux 内核的文件系统（如 ext4、XFS等）中，B树用于索引和管理文件系统中的数据块，支持高效的文件查找和文

件块分配。

  • 数据库管理系统 ：B树也常用于内核中的数据库管理系统（如一些高性能的键值存储系统）。

相关接口：

  • 在 Linux内核中，B树的实现较为复杂，通常使用其他专门的数据结构（如红黑树）来简化操作，但某些文件系统可能使用B+ 树（B树

的变种）来优化性能。

5. Trie 树（前缀树）

介绍：

Trie树（也称为前缀树）是一种多叉树，用于高效地存储字符串集合。它通过共享前缀来减少存储空间，并能够快速进行字符串的查找、插入和删除操作。前缀树又称为“单词查找树”、“字典树”。

https://blog.csdn.net/u014745069/article/details/117391183 ，这篇博客讲的很透彻了。

用途：

  • 路由查找 ：在网络协议栈中，Trie 树被用来进行快速的路由表查找。
  • 文件路径查找 ：在文件系统中，Trie 树可以用于快速匹配文件路径。
  • DNS、IPv6 地址等 ：在处理 DNS 查询、IPv6 地址匹配等问题时，Trie树也很常见。

相关接口：

  • radix tree 是 Linux内核中实现的一种变种，可以用于高效存储和查找数据。

6. Radix 树（基数树）

介绍：

Radix树是一种压缩的前缀树，它通过合并具有共同前缀的节点来优化空间消耗。它非常适合处理大量稀疏数据或具有公共前缀的数据。这个东西还有一个变种叫 Adaptive Radix Tree （自适应基数树），这个东西非常适合用于 CPU 的 cache 。有两篇文章可以结合起来一起看：

https://zhuanlan.zhihu.com/p/644667990

https://zhuanlan.zhihu.com/p/271739790

https://blog.csdn.net/yi_wen/article/details/119805160

看过没用过还是容易忘记的。需要记住的是 ART 是一种对 Radix 进行空间优化之后的一种算法。它的应用太重要了，是内核当中对内存管理使用的一种数据结构。可以说它的地位十分重要。ART是基数树的升级版，他对基数树在缓存命中方面低效的缺点提出了解决方案。同时使用延迟展开和路径压缩的方式来降低树高，可以在存在异常数据的情况下让树高降低。

在速度方面还是有非常大的优势的，dense （密集）的情况下速度和哈希表持平，sparse （稀疏）的情况下速度也略微超过FAST（FAST 是特定硬件上进行特定优化的算法）。

用途：

  • 内核内存管理 ：Linux 内核使用 Radix 树来实现虚拟内存页表的查找。
  • 网络协议栈 ：Radix 树也用于网络协议栈中的路由查找等。

相关接口：

  • Linux 内核提供了 radix_tree 的实现，广泛用于页表管理等资源管理场景。

7. Splay 树

介绍：

Splay 树是一种自调整二叉搜索树，它通过一种称为 “splaying” 的操作，使得最近访问的元素总是位于树的根部。它不保证树始终平衡，但能够在许多情况下提供较好的性能。与之类似的还有 Treap 树，FHQ-treap ，94 年的大佬已经把名子写在算法里面了。

https://www.bilibili.com/video/BV1gm4y1U7Hq

可以关注这个三金蝈蝈来学习一系列的算法，可是看到这个比较复杂的视频，我好像直接就放弃了。不同于文科的理解性记忆，算法的记忆像是魔法。真的是难记，能记住的必是刷了大量算法竞赛题的人。对于普通人而言能记住它可以用于优化最近搜索的情况就行了。

用途：

  • 内核调度 ：在某些调度策略中，Splay树可以被用来优化最近访问的任务的调度。

小结：

在 Linux 内核中，树型数据结构的应用十分广泛，最常见的是 红黑树 和 Radix树 ，它们广泛应用于进程调度、内存管理、文件系统和网络协议栈等多个领域。其他树型数据结构（如AVL 树、B树、Trie树等）则在特定的应用场景中发挥作用。不同的树型结构依据其性能特征（如平衡性、查找速度、插入/删除复杂度等）选择适合的场景应用。经典的数据结构就这么一点点，7 颗树请记住。

更高阶的数据结构是图。https://www.thepaper.cn/newsDetail_forward_14264768 。

图论是模拟现实世界网络结构的有效工具。但在寻找大数据之间的联系时，图论有其局限性，许多复杂系统不能只用成对的连接来表示。要如何扩展图论，揭示其无法捕捉到的高阶相互作用呢？科学家们发展出超图，甚至引入拓扑学、马尔可夫链、张量等数学工具，来探索广阔的数据世界。

自然是数学的，人性是文学的。将不同维度的复杂关系具象化，总结规律并加以应用。

图论有一个欧拉的哥尼斯堡七桥问题：

https://www.cnblogs.com/prpl/p/10947348.html

现代拓扑学的开创者是庞加莱：

https://www.thepaper.cn/newsDetail_forward_22960714

我是废物。