★ FEATURED ARTICLE 【免费下载链接】fsearchWhole-disk file search for macOS: fuzzy names, typo tolerance, indexed content grep. ~1 ms over 8M files.项目地址https://gitcode.com/gh_mirrors/fsea/fsearch点击查看免费下载fsearch 是一款面向 macOS 的全盘文件搜索工具它把整块磁盘扫成一张内存映射的扁平索引表之后按名称查找任意文件只需约1 毫秒7.7M 文件 p50 1.3 ms支持模糊文件名搜索、拼写容错还能用三元组索引 grep 文件内容。这篇文章带你拆开它名称索引的三个核心设计——DFS 布局、名称驻留interning、字符掩码——看看“在某个文件夹里搜索”是如何从逐条路径过滤变成一次区间查询的。30 秒上手安装 fsearch 并跑第一次搜索 cargo build --release ./target/release/fsearch install # 安装到 ~/.local/bin/fsearch fsearch fsearch main # 按名称找文件容忍 typo fsearch readme in:~/Developer # 限定在某文件夹内搜索 fsearch ext:rs grep:apply_dir # 搜索文件内容首次全盘爬取约 20 秒一次性之后守护进程通过 FSEvents 事件保持索引新鲜。完整数据见 README.md。DFS 布局把磁盘存成一张“目录页码表” 想限定在~/Developer里搜索朴素做法是扫过每个条目、逐条比对路径前缀——7.7M 次字符串比较又慢又无法提前剪枝。fsearch 的做法写在 index.rs 开头的布局注释 里所有条目按目录块、以深度优先DFS顺序写入同一个 blob。这样带来两个天然性质一个目录的直接子项是连续的块内还按名称排序便于按路径二分查找见 lookup()一个目录的整棵子树恰好是单一区间dir_start..dir_end见 descendants()。于是in:~/Developer不再是一个过滤器而是一个范围界先二分定位目录然后只扫这一个区间。查询层的实现只有一行核心逻辑——scope_range() 把路径换算成(dir_start, dir_end)两个下标。可以类比书的目录每一章占一段连续页码“读第三章”就是翻到第 X 页读到第 Y 页而不需要逐页问“这页属于第三章吗”。子树终点dir_end的算法也很巧先取自身块的末尾再从下往上向父目录折叠取最大值index.rs#L301-L307一次线性扫描搞定。名称驻留7.5M 条目其实只有 ~2M 个名字 真实磁盘上条目名高度重复几百万个index.html、test.py、README.md。fsearch 利用这一点做名称驻留interning每个不同的名称只存一次每个条目只保留一个 4 字节的 name idindex.rs#L9-L11 的注释7.5M 条目共享 ~2M 个不同名称。好处有两层名称级判定只需算一次。一个查询的词元token是否可能匹配某个名称对 2M 个不同名称各算一次而不是对 7.5M 条目各算一次score_names()。反向索引支持选择性搜索。索引维护一张名称 → 携带它的条目反查表index.rs#L285-L298。若匹配名称的条目总数不多阈值 6 万见 SELECTIVE查询直接只访问这些条目候选多时才做一次顺序全扫search_base()。驻留过程本身也很讲究按条目顺序插入首次出现即分配 id用自研的轻量 FxHash 而非 SipHash——驻留 750 万个名称时哈希器的选择直接决定建索引的速度index.rs#L462-L483。字符掩码一次 64 位 AND 淘汰大半磁盘 ✂️驻留之后每个名称还附带一个 64 位“条码”name_mask。它记录这个名称由哪些字符类别组成char_mask()位段含义0–25出现过哪些 a–z / A–Z 字母26–35出现过哪些数字36–40.、-/_、空格、高位字节、其他符号41–63名称中每个“词首字母”的散列位查询词元同样带掩码。于是 Token::fits() 只需一次miss self.mask !m判断词元里含某个类别的字符而名称里完全没有直接淘汰——绝大多数磁盘名称在这一步就被拒之门外根本不需要读名称本体且该判断无分支、可被 SIMD 向量化。高 23 位是拼写容错的入场券typo 匹配只可能发生在“某个词的首字母与词元首字母相同”的名称上name_mask() 的词首位 start_bit()。所以搜mian想找main.rs时首字母不是 m 的名称连 typo 逻辑都不用进入就被掩码排除了。一次搜索的完整旅程从词元到 1.3 ms 把上面三块拼起来一次fsearch readme in:~/Developer是这样跑的解析普通词 模糊词元x精确、^x前缀、x$后缀、!x排除外加ext:in:size:mtime:grep:等过滤器Query::parse()。名称级评分2M 个不同名称先过掩码预筛再跑 fzf 风格模糊打分结果存成稀疏 NameTable且按查询键缓存——你继续敲下一个字符时如果查询只是“收窄”直接复用上一次结果names()边打字边搜索不卡顿。圈定区间in:被换算为子树区间dir_start..dir_endDFS 布局的回报。两条策略候选 ≤ 6 万条目走“选择性”路径只访问带匹配名称的条目否则单次顺序全扫配合每个目录预先算好的 memo该目录路径上哪些词元已被文件夹满足和 top-k 缓冲第 k 名的分数自动成为淘汰线。合并 overlay 中尚未压实的新条目按分数输出。索引保鲜新文件 0.1 秒内出现 首次爬取并行getattrlistbulk一个系统调用带回数百条目的名称、类型、大小、mtime无需逐文件 statwalk.rs#L1-L6。持续更新每条 FSEvents 事件的处理方式统一为“重新列该目录并 diff”diff 幂等回放历史、重复事件都无害live.rs#L1-L8事件桥接见 fsevents.rs。零停机生效变更先进 overlay 删除位集搜索同时覆盖基础索引与 overlay重启时只回放保存的 event id 之后的变化而不是重扫全盘。实测成绩7.7M 文件名称搜索 1.3 ms 在 M4 Max7.7M 文件和文件夹上README.md#L13-L23操作耗时全盘按名称找文件p501.3 ms搜索文件内容p50 9 ms新/重命名/删除的文件出现~0.1 s首次爬盘~20 s一次性守护进程内存30–135 MB与开源项目 fff 的对比数据见 README.md#L25-L37对比脚本为 demo/vs_fff.py演示视频见 demo/fsearch-vs-fff.mp4。小结 DFS 布局子树 单一连续区间文件夹范围从“逐条过滤”变成“区间界定”这是 1 ms 搜索的地基。名称驻留7.5M 条目只占 ~2M 个名字名称级判定只做一次还能反查做选择性搜索。字符掩码一个 u64 位掩码 一次 AND淘汰绝大多数候选高位词首位再为 typo 容错提前剪枝。三个设计互相咬合布局决定扫描范围驻留缩小评分对象掩码决定哪些名称值得评分——这就是 fsearch 能在八百万文件上做到毫秒级模糊搜索的完整内幕。赞分享【免费下载链接】fsearchWhole-disk file search for macOS: fuzzy names, typo tolerance, indexed content grep. ~1 ms over 8M files.项目地址https://gitcode.com/gh_mirrors/fsea/fsearch点击查看免费下载相关推荐Unison 名称段反引号转义机制在命名空间中使用关键字与保留运算符的完整指南Unison 名称段反引号转义机制在命名空间中使用关键字与保留运算符的完整指南 导读 在 Unison 这门编程语言中命名空间namespace中的名称编程语言编译器语言运行时开发工具kube-prometheus 组件名称与命名空间覆盖指南自定义部署命名空间与 Prometheus/Alertmanager CR 名称kube prometheus 组件名称与命名空间覆盖指南自定义部署命名空间与 Prometheus/Alertmanager CR 名称 导读 kube p云原生可观测性指标监控监控大盘告警Error Prone MislabeledAndroidString 检查器识别 android.R.string 中名称与内容不符的内置字符串资源Error Prone MislabeledAndroidString 检查器识别 android.R.string 中名称与内容不符的内置字符串资源 在 A静态分析代码质量开发工具创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
