当前位置：首页 > news >正文

访问者模式：数据结构主导遍历，外部处理数据”

news 2026/7/25 15:01:37

这是一个非常深刻的问题。你的观察很敏锐：在 Lucene 众多数据结构中，BKD 树是少数几个将“访问者模式”作为核心遍历接口来公开的。

这个设计的核心原因，在于**BKD 树自身复杂的分支结构和数据布局**，使得它必须将“如何遍历”的复杂性封装在内部，而把“如何处理数据”的决策权交给外部访问者。

### 🧭 BKD 树的“地图”只有它自己知道

你提到的那句“数据结构的灵魂在于遍历”，完美概括了这一点。BKD 树的内部结构极其复杂，任何想要遍历它的外部代码都无法独立完成：

1. **多维树形结构**：BKD 树是一棵递归划分的多维空间树。遍历时，在每一个内部节点都必须决定“走左还是走右”，或者“两边都走”。这种分支逻辑是树结构固有的。
2. **磁盘存储与压缩**：BKD 树的节点和叶子块以高度优化的二进制格式存储在磁盘上。数据经过前缀压缩、变长编码等处理。外部访问者不知道如何解码这些字节流，只有 `BKDReader` 本身清楚。
3. **查询时的剪枝优化**：BKD 树最大的优势就是通过**边界盒**进行剪枝。在遍历时，需要根据查询范围判断当前节点的边界盒是`INSIDE`（完全包含）、`OUTSIDE`（不相交）还是`CROSSES`（部分相交）。这个“走法”的判断逻辑，被封装在 `IntersectVisitor` 的 `compare()` 方法中，由外部提供，但“怎么走”由 `BKDReader` 控制。

### 🎯 访问者模式：把“走法”和“做法”分离

这正是访问者模式在 BKD 树上的精妙应用。它将两个不同层面的职责清晰地分开了：

| 角色 | 职责 | 对应 BKD 树的组件 |
| :--- | :--- | :--- |
| **数据结构 (`BKDReader`)** | 提供“走法”：控制遍历的流程、递归、IO、解码。它持有“地图”，决定下一步怎么走。 | `PointValues.intersect()` 方法 |
| **访问者 (`IntersectVisitor`)** | 提供“做法”：处理被访问到的数据节点，并告诉数据结构如何做决策（是剪枝、全部收集、还是继续深入）。 | `IntersectVisitor` 接口 |

你把它们分开理解，就能看懂为什么 BKD 要这么设计了：

* **访问者控制“做法” (`visit`)**：当遍历到一个叶子块时，`BKDReader` 会调用 `visitor.visit(docID, packedValue)`，把数据和文档ID交给访问者。访问者只负责处理这个点，例如将其加入结果集。
* **访问者参与“走法”决策 (`compare`)**：在遍历内部节点时，`BKDReader` 会把当前节点的边界盒（`minPackedValue`/`maxPackedValue`）交给访问者的 `compare` 方法。这个方法返回 `Relation` 枚举：
* `CELL_INSIDE_QUERY`：整个节点都被查询覆盖，可以批量收集，无需再深入。
* `CELL_OUTSIDE_QUERY`：节点与查询无关，直接剪枝。
* `CELL_CROSSES_QUERY`：节点边界与查询部分相交，需要继续深入遍历。

### 🌳 访问者模式在 Lucene 中的其他体现

其实，访问者模式在 Lucene 中并非 BKD 树的专利，你只是在这里第一次深刻地感受到它。它还被用于：

* **存储字段访问**：`StoredFieldVisitor` 用于在读取存储字段时，让调用者决定加载哪些字段、如何处理它们。
* **空间查询遍历**：`AbstractVisitingPrefixTreeQuery` 也使用 `VisitorTemplate` 来遍历前缀树节点。
* **查询树遍历**：社区曾讨论过为 `Query` 树引入访问者模式 (`QueryVisitor`) 来辅助查询重写和优化。

### 💎 总结

**只有 BKD 树使用 `PointValues.intersect(IntersectVisitor)` 这种访问者模式，根本原因在于它的多维树形结构和磁盘存储形式决定了“如何遍历”是一个极其复杂的内部细节，必须封装起来。** 访问者模式在这里完美地解耦了“数据的存储与遍历逻辑”和“数据的处理逻辑”，让外部的查询代码无需关心 BKD 树内部的复杂实现，同时又能灵活地定义查询行为。

你现在对访问者模式的理解，已经触及到了它在复杂数据结构中的真正价值所在。

这是一个直击本质的好问题。它正好触及了 Lucene 不同数据结构在设计哲学和访问模式上的根本差异。

其他结构（如倒排索引、DocValues）之所以不采用 BKD 树那种“访问者模式”，是因为它们的**数据访问模式**和**外部查询的交互方式**完全不同。

下面我们来对比分析：

---

### 1. 倒排索引 (Inverted Index)

倒排索引的核心是 **“词项 (Term) → 文档列表 (Posting List)”** 的映射。其访问模式是典型的**精确查找或范围扫描**。

- **查询入口**：查询（如 `TermQuery`）会直接通过 `TermsEnum`（词典迭代器）**精确查找或定位**到某个词项。
- **遍历方式**：一旦定位到词项，其对应的文档 ID 列表（Postings）通常是连续存储或通过跳表（Skip List）组织。查询逻辑（如 `Scorer`）会**线性遍历**这个列表，并计算每篇文档的分数。
- **为什么不用访问者模式**：
- **数据流是单向的**：从“一个词”流向“多个文档”，没有复杂的“走左还是走右”的分支决策。
- **剪枝逻辑不同**：倒排的剪枝主要发生在词项层面（例如，通过 `BooleanQuery` 对多个词项的文档列表进行 `And`/`Or` 合并），而不是在遍历一个文档列表的内部时。
- **如果需要用**：如果强行用，就得定义一个 `PostingVisitor`，当遍历文档列表时，其 `visit(docId, freq, positions)` 会被调用。但它并不能为遍历流程提供复杂的“走法”决策，因为你不需要“跳过这个区间”或“深入这个子树”，你只需要顺序读下去。

---

### 2. DocValues (文档值)

DocValues 的核心是 **“文档 ID → 值”** 的映射。其访问模式是典型的**随机访问**或**排序/聚合时的批量读取**。

- **查询入口**：DocValues 不参与“查找”，而是为“获取”服务的。在排序（Sort）、聚合（Facet/Group）或函数查询（Function Query）时，系统会根据一个文档 ID，**直接跳转**到该文档对应的值进行读取。这就是 `get(docId)` 方法。
- **遍历方式**：除了随机访问，在某些场景（如 `SortedSetDocValues`）下，会遍历所有**不同的值**（`TermsEnum`），然后再获取包含该值的文档列表。
- **为什么不用访问者模式**：
- **交互模型不匹配**：访问者模式是“数据结构主导遍历，外部处理数据”。而 DocValues 的使用场景（排序）是“外部主导计算，按需索取数据”。外部需要的是“给我文档 X 的值”，而不是“数据结构，请遍历所有你认为是绿色的值，然后把它们交给我”。
- **剪枝能力**：DocValues 本身没有 BKD 树那种“边界盒剪枝”的能力。对 DocValues 的过滤（如 `NumericRangeQuery` 利用 DocValues），实际上是在 BKD 树上完成的。BKD 找到符合条件的文档 ID 后，再通过 DocValues 去获取其他字段的值。

---

### 3. 核心差异：剪枝策略与数据组织

为什么 BKD 树必须用访问者模式？因为它的 **“剪枝”发生在遍历的每一个步骤中**。

- **BKD 树**：它是一个多维空间。查询（如“经度在 10-20，纬度在 30-40”）就像在地图上画一个框。BKD 树遍历时，必须不断判断“当前这个节点代表的矩形是否和我的查询框相交？”。这个判断是**遍历流程的一部分**，必须由外部查询（它知道框的大小）来告诉树（它知道自己节点的矩形边界），这就形成了 `compare(边界盒)` 的交互。
- **倒排 & DocValues**：它们的遍历**不依赖外部剪枝**。你查到“苹果”这个词，就去读它的文档列表，不需要查询来告诉你“要不要继续读”。DocValues 的 `get(docId)` 更直接，根本不需要遍历。

---

### 💎 总结

一句话：**BKD 树的遍历结果（哪些节点需要深入）是“走一步看一步”的，必须依赖外部逻辑来判断；而倒排和 DocValues 的访问路径是预定义的，不需要外部干预。** 这就是为什么 BKD 树会采用访问者模式，而其他结构不会。

这个问题问得很好。在我之前的回复里，我们分析了 Lucene 为什么在 BKD 树上选择访问者模式，而没有用在倒排或 DocValues 上。这其实正好引出了一个更通用的设计问题：**什么时候该用访问者模式？**

简单来说，就是当你的数据结构**稳定（很少变）**，但需要对它执行**不确定、可能会扩展的操作**时，访问者模式就是一个很好的选择。

### 🎯 什么时候应该考虑访问者模式？

通常，当你遇到以下情况时，可以考虑使用访问者模式：

1. **对象结构稳定，但操作多变**：如果你有一个由固定类型组成的对象树（就像 BKD 树，节点只有“内部节点”和“叶子节点”），但你需要不断地为这个树增加新功能（比如除了“查询”，还要“遍历”、“统计”、“估算内存”）。使用访问者模式，你可以轻松添加新的 `Visitor` 来实现新功能，而完全不用去修改那些节点的类。

2. **需要对结构复杂的聚合对象执行操作**：当一个操作需要横跨、遍历并处理整个对象结构中不同层级、不同类型的元素时（就像 BKD 树的 `intersect` 方法，它必须自行处理文件读取、节点跳转和分支决策），访问者模式能把“如何遍历这个复杂结构”的逻辑，封装在访问者内部。

3. **操作本身依赖于对象的具体类型**：如果要对一个 `Node` 执行 `export()` 操作，但导出 `InternalNode` 和 `LeafNode` 的细节完全不同，且这种区分逻辑很可能在别处也有用到。访问者模式通过双分派（Double Dispatch）机制，允许你定义多个重载的 `visit(InternalNode)` 和 `visit(LeafNode)` 方法，让对象自己“决定”该调用哪个，从而优雅地解决类型判断问题。

---

### 🆚 什么时候不该用？

了解了“该用”的场景，你也就明白了“不该用”的反面：

- **对象结构本身经常变化**：比如你频繁增加新的 `Node` 子类（如 `RangeNode`），那么每加一个新的 `Node`，你都不得不修改所有 `Visitor` 接口，这会让你和你的同事抓狂。在这种情况下，直接在基类中定义虚方法（如 `doQuery()`）会更方便。
- **功能非常核心且固定**：如果操作是对象最本质的功能（如“支付”对于“订单”），那么它就应该直接是对象行为的一部分，而不是通过访问者模式从外部注入。
- **对性能要求极其严苛且调用频繁**：访问者模式引入了间接层和虚函数调用，虽然通常开销很小，但在极端高频的循环中，一个直接的 `if/else` 或 `switch` 可能会更优。

---

### 🧩 回到 Lucene 的场景验证

现在，我们用这个标准来验证一下 Lucene 的设计：

- **BKD 树**：它的 `InternalNode` 和 `LeafNode` 结构非常固定（这符合“对象结构稳定”）。但对它执行的操作却在不断扩展：不仅有点查询（`intersect`），还有 `estimatePointCount`、`checkIntegrity` 等。BKD 树把**“怎么在磁盘上找到并遍历节点”这个麻烦事**封装在自己内部，而把“拿到这些节点后你想干什么”这个灵活的部分，交给了 `IntersectVisitor`。这完美契合了访问者模式的适用场景。

- **倒排索引 & DocValues**：它们的查询路径是“定位文档列表”或“根据文档ID取值”，操作非常固定，就是查询和获取，并且它们的结构（词项列表、文档值映射）也相对简单。因此，直接提供 `TermsEnum` 或 `get(docId)` 这样的 API 更直接，也更高效。如果强行套用访问者模式，反而是“杀鸡用了牛刀”。

总的来说，当你感觉一个数据结构处理起来很复杂，而未来又可能为它增加各种意想不到的操作时，访问者模式就是一个值得考虑的、非常经典的选择。