# 架构

[English](../en/ARCHITECTURE.md) | [中文](ARCHITECTURE.md)

## 分层与依赖

浏览器桥接直接依赖核心几何与索引，不再维护独立 JS STR 算法。React 负责控件与画布，Worker 负责构建、查询和竞品计时。矩形节点边界审计由 MoonBit 遍历真实树，在计时区域外区分保留和排除；它不冒充查询遍历遥测。其他几何模式显示静态拓扑。

| 层 | 职责 | 依赖 |
| --- | --- | --- |
| 根入口 | 转导出公开名称 | `src/api` |
| `src/api` | 规范几何类型转导出与不透明索引适配 | 核心、扩展、数据生成器 |
| `src/core/geometry` | 几何坐标运算与包围盒谓词 | 运行时基础操作 |
| `src/core/packing` | STR 分区选择、切片排序、整数打包算术 | 几何 |
| `src/core/index` | 存储、查询、近邻、连接、中心点分析 | 几何与打包 |
| `src/core/stats` | 二维结构诊断 | 几何与索引 |
| `src/extensions` | 围栏、多边形、轨迹 | 几何与索引 |
| `src/support/generator` | 有种子的合成数据 | 几何 |

依赖从应用与公开适配层指向算法层。核心索引不依赖扩展。MoonBit 要求方法由接收类型所属包定义，所以索引存储与查询处于同一个 `core/index` 包，以文件区分职责，而不是将方法随意移到其他包。

浏览器现已通过编译后的 MoonBit 桥接调用核心库，原独立 JS STR 实现已移除。

## 构建与存储

二维缓存中心坐标，仅在 STR 切片及页边界做分区选择，不对页内元素完整排序。输出数组预先确定大小并直接填充分列存储，不再先生成临时对象树。最后按深度优先顺序排列叶对象，使每个子树对应连续叶区间。三维仍按 X/Y/Z 排序，四维增加时间；它们的直接构建优化属于后续工作。四维临时节点保存明确存储索引和层级，不再依赖相同坐标或编号反查子节点，并以标准 O(n log n) 排序替代平方复杂度循环。旧打包工具使用可变视图减少切片复制，整数打包算术避免正 Int 上限溢出。

坐标分别存放于数组，子节点由 `child_offset`、`child_count`、`child_indices` 表示 CSR 式邻接关系，叶节点由 `item_ids` 标识。这种布局不等同于构建和查询零分配。

载荷估算为二维每节点 44 字节、三维 64 字节、四维 80 字节，另加每边 4 字节；不包含数组头、运行时对象、结果与临时空间，JavaScript 运行时也可能使用不同表示。填充率为已占用分支槽数除以分支数乘容量；无分支时为 1。

## 查询、分析与所有权

范围和点查询使用迭代 DFS，包含接触边界。二维和三维近邻各共享一个分支限界实现：最小堆决定待访问节点顺序，有界最大堆保留至多 k 个候选，堆顶为最远候选。候选插入及替换为 O(log k)，结束时对结果原地排序一次，成本为 O(k log k)。带过滤的查询在接受候选前执行谓词；距离接口按升序返回平方距离，等距编号顺序不保证稳定。

打包二维查询直接复制完全包含的叶区间，并将部分命中的叶扫描分离。恢复时验证私有布局提示，索引存储与适配器内部字段设为私有。JS 仅针对整数结果追加/复制使用专用宿主操作，遍历仍由 MoonBit 实现；其他目标使用普通 MoonBit 数组。`query` 分配结果和遍历数组；`query_into` 清空并复用两个独立的调用者数组，调用者不能让两个参数引用同一个数组，也不能并发共享临时缓冲。计数查询没有结果数组，但仍有遍历栈。查询至少需要与结果数量成比例的工作，高重叠输入可能退化为 O(N)。

DBSCAN 针对包围盒中心。统一的扩展算法避免同一对象反复入队，临时中心索引使用连续内部编号，支持用户 ID 重复。`dbscan_compact` 的 `item_ids` 与 `labels` 一一对应，结果空间 O(N)；旧 `dbscan` 以用户 ID 索引标签，稀疏 ID 可能需要 O(max_id) 空间。

轨迹窗口与多边形窗口返回包围盒候选，精确相交需要额外几何判断。空间拓扑谓词针对包围盒，不代表任意 GIS 几何的完整拓扑运算。

## 恢复与兼容性

打包点查询直接使用坐标，避免临时矩形、范围归一化及通用覆盖判断，不增加索引字段。正向包含比较保留接触边界语义，并排除 NaN 查询／根坐标。布局提示还验证分支／叶子页同类及完整深度优先叶子顺序；合法但混合子节点深度的恢复树使用通用遍历，仅有叶子前缀不足以证明打包布局。

导入/导出数组都会复制，保证独立所有权。`from_flat_buffers` 用于可信数据；`from_flat_buffers_checked` 校验长度、偏移、根连通性、无环性、叶数量、树高、有限坐标和父子包围关系，损坏数据返回 `None`。

原有根包公开声明继续可用，规范几何类型归属 `src/core/geometry`，不透明索引适配归属 `src/api`，内部字段不再提供直接修改入口，生成接口会体现迁移。旧内部路径已改变，直接导入内部包的调用者需要更新路径。

## 浏览器多维功能

独立 Worker 构建真实三维/四维 MoonBit 索引，XY 与 XZ 视图展示同一批合成包围盒。调整高度范围或四维时间片会改变完整命中集合，全部编号与独立扫描核对。导出保留全部编号及完整包围盒，页面表格只预览前十项；这一功能演示不宣称多维性能排名。