第 1 篇：「每次搜索 500ms 的噩梦」— 从暴力遍历到索引

开场一杯咖啡的时间有多长你有多久没打开一个中等规模的代码库了几年前我打开一个 10K 符号的 TypeScript 项目想搜索buildQuery函数。IDE 卡了半秒钟。然后一秒。然后我就去喝咖啡了。这不是夸张的比喻。当时的搜索引擎就是这么慢。每一次搜索都从头开始扫描整个项目。那是一段黑暗的日子。问题的解剖为什么会这么慢让我们追踪一次典型的搜索过程。场景用户在 VSCode 输入搜索框查找getUser函数。暴力搜索的流程打开 /src 工作区 ├─ components/ │ ├─ Button.tsx (1500 个 AST 节点) │ ├─ Input.tsx (2000 个 AST 节点) │ ├─ Form.tsx (3500 个 AST 节点) │ └─ ... 200 个文件 ├─ utils/ ├─ services/ └─ types/ 对每个文件执行 ↓ 1️⃣ 读取文件内容 (磁盘 I/O) ↓ 2️⃣ 用 Tree-sitter 构建 AST (CPU 密集) ↓ 3️⃣ 遍历整个 AST 树逐个检查节点名称 ↓ 4️⃣ 如果匹配就记录位置 ↓ 5️⃣ 合并所有文件的结果 返回用户 ✗ (几秒后)成本分析数字说话对于一个5K 符号、200 个文件的项目步骤文件数单位成本总成本读文件2005ms1000ms解析 AST20010ms2000ms遍历搜索20050ms10000ms其他GC、调度等--1000ms总计--~14000ms是的14 秒。这就是首次搜索。后续搜索同样慢因为没有缓存。内存隐形的杀手构建的 AST 树 ├─ 每个文件的 AST100-500 KB取决于代码复杂度 ├─ 200 个文件 × 300 KB 平均 60 MB ├─ 搜索时临时对象10-20 MB └─ 总计~70-90 MB 就这一次搜索 打开两个搜索框翻倍。 IDE 运行一小时内存缓慢爬升。如果项目是50K 符号内存需求可能突破500 MB导致 IDE 本身变卡。常见的聪明想法都不行 想法 1用正则表达式 并发搜索// 我们用正则匹配再开 8 个线程肯定快consttasksfiles.map(fileworker.search(file,/getUser/g));constresultsawaitPromise.all(tasks);问题正则仍需读取每个文件、构建 AST → 瓶颈不变并发收益有限I/O 瓶颈不是 CPU 瓶颈8 个线程 vs 200 个文件 → 还是要队列等待平均速度快 30%仍然 350ms 想法 2用 grep 之类的系统工具grep-rgetUsersrc/问题grep 是文本匹配不是代码理解搜get会匹配函数名getUser()✓ 真匹配注释// get the user info✗ 噪音字符串please get me✗ 噪音变量const get_user_data ...✗ 误匹配噪音比率30-50%你要手动过滤 想法 3内存缓存constcachenewMapstring,SymbolLocation[]();functionsearch(query:string){if(cache.has(query)){returncache.get(query);// 缓存命中直接返回 ✓}// 否则执行搜索存入缓存constresultdoSearch(query);cache.set(query,result);returnresult;}看起来很聪明但文件一改缓存失效 → 要全部重建回到原点多个 IDE 窗口同时编辑 → 缓存不同步 → 显示错误结果IDE 关闭缓存消失 → 下次启动又要重新构建没解决根本问题只是拖延症时间复杂度的噩梦传统方案的数学模型总时间 Σ (读文件 构建AST 遍历搜索) × 文件数 或者用 Big-O 表示 O(n × m × k) 其中 n 文件数 (200) m 平均 AST 节点数 (5000) k 每个节点的检查时间 (1μs) 实际200 × 5000 × 1μs 1000ms ← 理论最优 但加上 I/O、GC、内存分配等开销 → 5-15 秒 ⚠️这个复杂度是线性的、不可优化的。如果项目翻倍到 400 个文件、10K 符号时间也会翻倍。这就是为什么LoopAgent 从设计之初就要求索引系统。解决方案的方向我们需要什么1️⃣ 预处理一次使用多次第一次启动耗时但只做一次 读所有文件 → 建索引 → 存磁盘 之后每次搜索 直接查表 → 毫秒级返回2️⃣ 将时间复杂度从 O(n×m) 降到 O(log n)暴力遍历 200 个文件 → O(n) 索引查哈希表/树 → O(log n) 对数复杂度 vs 线性复杂度 → 这是天壤之别。3️⃣ 离线构建在线查询离线IDE 启动、文件保存时 增量更新索引后台 在线用户搜索时 查现成的索引 无需等待毫秒级返回4️⃣ 支持语义搜索不仅返回匹配结果还要排序 最可能你要的排在第一个 示例搜query A. buildQuery() ← 精确匹配排第一 B. queryUserData() ← 包含词排第二 C. query the database ← 在注释中排最后为什么索引系统是必须的看似复杂但收益巨大指标暴力遍历索引倍数首次搜索500ms7ms71x10 次搜索总时间5000ms70ms71x内存占用50MB15MB3.3x 省内存启动卡顿有首次搜索卡无-真实数据from LoopAgent 项目基准测试见文末。下一篇预告我们现在知道问题有多严重。但怎么解决下一篇会介绍SQLite FTS5Full-Text Search 5——这是一个内置的全文搜索引擎可以把 500ms 变成 7ms。关键概念你要了解倒排索引Inverted Index从词映射到文档BM25 排序算法式地判断这个结果有多相关词干化getUser 和 getUsers 是同一个词短语查询搜build query返回同时包含两个词的结果等着我。下一篇会很精彩。参考数据运行基准测试看自己的项目npmrun benchmark:search预期结果标准工作区5K 符号Workspace size: ~5K symbols 暴力遍历: 450ms avg FTS5 索引: 7ms avg Speedup: 64x Memory (暴力): 48 MB Memory (FTS5): 16 MB