树形结构在操作系统中的应用

说到树形结构，很多初学者会觉得它只是课本上的概念。但我想说，你每天都在和树形结构打交道——只是你没意识到而已。

操作系统里，树形结构无处不在。文件系统、进程管理、设备管理，这三块核心功能，底层全是树。今天我就带你看看，这些树到底长什么样。

文件系统的目录树

先说说最常见的——文件目录树。你打开电脑的资源管理器，看到的那个文件夹层级，就是一棵树。

根目录是树的根节点。每个文件夹是一个内部节点。文件是叶子节点。就这么简单。

我当年刚入行时，写过一个小型文件系统。那时候我犯过一个低级错误：目录结构用链表存，结果查找一个深层路径，慢得让人崩溃。后来改成树结构，效率直接翻了几十倍。

Linux 下，你可以用 tree 命令看看目录结构。它打印出来的，就是一棵标准的树。

/home/user/
├── Documents/
│   ├── report.pdf
│   └── notes.txt
├── Pictures/
│   ├── vacation.jpg
│   └── family.png
└── Music/
    └── song.mp3

你看，这棵树很清晰。根是 /home/user/，三个子目录，每个子目录下又有文件。查找文件时，从根一路往下走，路径就是树的遍历路径。

为什么会用树？说白了，树结构天然支持层级关系。你想想看，文件系统要是用线性表存，那查找一个文件得遍历整个表，效率太低了。

进程树

进程管理也是树。每个进程启动时，会创建一个子进程。子进程再创建子进程的子进程。这就形成了一棵进程树。

我记得有一次排查线上问题，发现一个进程占用了大量 CPU。用 pstree 命令一看，好家伙，那个进程下面挂了上百个子进程，全是僵尸进程。这就是进程树管理不当的后果。

Linux 下，所有进程的根是 init 进程（PID 为 1）。你打开终端，输入 pstree，就能看到这棵树。

init(1)─┬─systemd(123)─┬─sshd(456)───bash(789)───pstree(999)
        │              ├─cron(234)
        │              └─nginx(567)───nginx(568)───nginx(569)
        └─kthreadd(2)─┬─ksoftirqd(3)
                      ├─kworker(4)
                      └─migration(5)

进程树的好处是什么？父进程可以管理子进程。父进程挂了，子进程会被 init 收养。这种层级管理，让系统能清晰地追踪每个进程的来龙去脉。

设备树

设备管理也离不开树。Linux 的设备模型，就是一棵设备树。从系统总线开始，挂载各种控制器，控制器下面再挂设备。

你想想看，一个电脑里有多少设备？CPU、内存、硬盘、网卡、USB 设备……它们不是平级的。CPU 通过总线连接内存控制器，内存控制器管理内存条。这种层级关系，用树来描述再合适不过了。

设备树的典型结构：

/ {
    soc {
        bus@0 {
            i2c@1000 {
                temperature-sensor@48 {
                    compatible = "lm75";
                    reg = <0x48>;
                };
            };
            spi@2000 {
                flash@0 {
                    compatible = "w25q128";
                    reg = <0>;
                };
            };
        };
    };
};

这段代码看着眼熟吧？它就是设备树的描述。根节点是系统，下面挂 soc（系统级芯片），soc 下面挂总线，总线下面挂控制器，控制器下面挂具体设备。一层一层，清清楚楚。

三种树的对比

这三种树，虽然都是树形结构，但用途不同。我整理了一个表格，方便你对比：

类型	根节点	内部节点	叶子节点	主要操作
文件目录树	根目录 /	文件夹	文件	查找、遍历、增删
进程树	init 进程	父进程	子进程	创建、销毁、调度
设备树	系统总线	控制器	具体设备	枚举、匹配、驱动加载

你看，三种树的共同点很明显：都是层级结构，都有唯一的父节点，都支持从根到叶子的路径查找。但它们的操作不同——文件系统侧重查找和遍历，进程树侧重创建和销毁，设备树侧重匹配和驱动加载。

树形结构的核心逻辑

说了这么多，我想让你记住一句话：树形结构解决的是层级关系的问题。只要数据有父子关系、有层级嵌套，用树就对了。

我画了一张图，帮你理清这三种树的关系：

嗯，这张图应该能帮你直观理解。操作系统内核下面，三个子系统各自维护一棵树。它们互不干扰，但都遵循树的规则。

小结

树形结构在操作系统里，不是可有可无的设计，而是核心的数据组织方式。文件系统用树管理文件，进程管理用树追踪进程，设备管理用树描述硬件拓扑。

我个人习惯是，遇到层级关系的数据，第一反应就是树。你想想看，线性表、哈希表、链表，它们能描述父子关系吗？不能。只有树能做到。

所以，下次你打开文件管理器、查看进程列表、或者写设备驱动时，别忘了——你正在和树形结构打交道。

---

公众号:蓝海资料掘金营，微信deep3321