目录遍历与并发 IO

在渲染目录树或统计占用空间时，需要在目录层级上做遍历。遍历由两部分组成：读取单个目录的条目，以及决定下一步进入哪个子目录。耗时主要来自系统调用次数与元数据访问的随机性，因此遍历过程的组织方式会直接影响整体开销。

目录条目的流式读取

列举目录时，底层通常一次返回一批条目，而不是把整个目录读入内存。接口形式一般有两种：

• 一次性返回全部名称的数组
• 返回迭代器或游标，逐批产出条目

前者实现简单，代价是目录条目极多时内存占用随条目数增长；后者把内存占用压到单批大小。多数系统调用层提供的是分批语义，语言运行时再包装成数组或迭代器。在迭代器形式下，遍历过程中对目录的并发修改是否可见取决于实现，通常不提供快照语义。

async function* walk(root) {
  const stack = [root];
  while (stack.length > 0) {
    const dir = stack.pop();
    for await (const entry of readDirBatched(dir)) {
      if (entry.isDirectory) stack.push(entry.path);
      else yield entry.path;
    }
  }
}

递归与显式栈

递归写法与树结构同构，可读性较高，但深度受调用栈限制，在很深的目录下可能触发栈溢出。显式栈把待访问目录放在堆上，深度不再受语言调用栈约束，也便于在遍历中途暂停与恢复。广度优先与深度优先的区别就在于待访问集合的组织方式：

两种方式访问的条目总数相同，差异体现在顺序与中间状态的内存占用。选择取决于输出顺序的约束以及与上层视图的衔接方式：树形视图的展开顺序与深度优先的子树连续特征一致，按层统计则接近广度优先。

符号链接成环的检测

符号链接可以指向祖先目录，从而构成环。仅靠深度上限只能缓解，无法判定环。常见做法有两种：

• 记录已访问目录的标识（例如设备号与 inode 号组合），遇到重复即停止
• 记录从根到当前节点的路径链，检测链内是否出现重复标识

标识集合的做法把每个目录的标识放入集合，内存占用与已访问目录数成正比，但能覆盖从不同路径到达同一目录的情况；路径链做法只保留当前链，内存占用更小，代价是需要在回溯时维护链的增删。是否跟随符号链接本身也是策略选项，多数工具提供不跟随、完全跟随与只在指定层级跟随等模式。

并发遍历的调度

列举与取属性属于等待型操作，串行执行会把等待时间累加。并发遍历把这些操作提交到多个任务上，同时用信号量把在途请求数限制在固定上限：

function createLimiter(max) {
  let active = 0;
  const queue = [];
  const next = () => {
    if (active >= max || queue.length === 0) return;
    active += 1;
    const task = queue.shift();
    task.fn().then(task.resolve, task.reject)
      .finally(() => { active -= 1; next(); });
  };
  return (fn) => new Promise((resolve, reject) => {
    queue.push({ fn, resolve, reject });
    next();
  });
}

并发度的取值需要与存储介质和访问方式匹配。机械介质上并发度过高会引入寻道竞争，增加单次访问的等待；固态介质与网络文件系统在并发度提高时，受寻道竞争影响的幅度不同。并发度还受进程可用文件描述符数量的约束，超过上限会以打开失败的形式表现出来。需要说明的是，这里的取舍依赖介质特性与缓存状态，不能脱离条件直接比较。

剪枝与提前停止

在遍历前声明忽略规则，可以减少访问量。规则一般按名称或路径后缀匹配，命中后不再进入该目录。剪枝生效的时机越靠前，节省的调用次数越多，因此在读取子目录之前判断，命中规则的目录不会产生后续的读取与属性调用。越过某深度或累计条目数达到上限时提前返回，也能把不可控的耗时变成可控的耗时。

缓存同样影响总耗时。同一进程内重复遍历时，操作系统的目录项缓存与属性缓存会吸收部分调用；跨进程或缓存被逐出后，成本回到介质的实际速度。度量遍历性能时需要说明缓存是否预热，否则两次测量的差异可能来自缓存状态而非遍历组织方式。

小结

目录遍历的核心是可枚举的条目序列与对子目录的调度。流式读取控制单次内存占用，显式栈解除深度限制，成环检测确保终止，并发度与剪枝共同决定调用次数与时延。比较不同方式时应当固定缓存状态与并发度，再观察指标差异，否则结论不成立。