Learning spatial index

空间索引是数据库系统的核心组件。传统方法（R-tree, Hilbert 曲线）在高偏态分布和动态更新场景下面临秩值簇化和长尾延迟的挑战。本文提出三阶段的学习型空间索引方案。

1. DLHM：密度感知的 Hilbert 降维映射

1.1 问题定义

给定 $d$ 维空间数据集 $\mathcal{D} = \{\mathbf{p}_1, \dots, \mathbf{p}_N\}$，其中 $\mathbf{p}_i \in \mathbb{R}^d$（地理空间场景下通常 $d = 2$）。目标是将 $\mathcal{D}$ 映射到一维有序序列 $\pi: \mathcal{D} \to [0, M-1]$，使得空间邻近性在一维序列中得以保持：

1.2 密度分布形式化模型

定义空间密度函数 $\rho(\mathbf{x})$ 为位置 $\mathbf{x}$ 处的局部数据密度。采用核密度估计（KDE）：

其中 $K(\cdot)$ 为 Epanechnikov 核函数，$h$ 为带宽参数，按 Silverman 规则 $h = 1.06 \cdot \hat{\sigma} \cdot N^{-1/5}$ 确定。

在每个空间区域 $R_k$ 内，定义局部密度 $D_k^{\text{local}}$ 与全局平均密度 $\bar{D}$ 的比值：

1.3 自适应四叉树分裂策略

DLHM 采用自顶向下的四叉树分割。分裂判据基于密度比值 $\lambda_k$：

其中 $\lambda_{\text{high}} = 2.0$（过密触发分裂），$\lambda_{\text{low}} = 0.3$（过疏停止），$d_{\max} = 12$（最大深度限制）。

分裂后的叶节点集合 $\mathcal{L} = \{L_1, \dots, L_m\}$ 满足空间互斥且完备覆盖。

1.4 局部 Hilbert 编码

在叶节点 $L_k$ 内部，独立执行 Hilbert 编码。对点 $\mathbf{p} = (x, y)$，首先归一化到 $[0, 2^r - 1]^2$ 的整数网格：

Hilbert 编码 $H(x_g, y_g)$ 通过位交错和 Gray 码转换计算。定义阶数为 $r$，编码空间大小为 $2^{2r}$。

1.5 跨网格偏移注入机制

定义全局偏移量 $\Delta_k$ 为前 $k-1$ 个叶节点的编码容量之和：

每个叶节点按密度比值 $\lambda_j$ 分配编码容量。最终全局映射：

保证了 $\pi$ 的全局单调递增性：若 $a < b$（按四叉树深度优先遍历顺序），则 $\forall \mathbf{p}_a \in L_a, \forall \mathbf{p}_b \in L_b$，有 $\pi(\mathbf{p}_a) < \pi(\mathbf{p}_b)$。

1.6 映射质量度量

间隙方差（Gap Variance）：衡量一维序列中点间距离的不均匀程度。

记 $\delta_i = \pi_{(i+1)} - \pi_{(i)}$ 为相邻秩值差（其中 $\pi_{(i)}$ 为有序排列），则：

映射平滑度（Smoothness）：衡量空间邻近点在一维序列中保持邻近的程度。

记 $\mathcal{N}_{\epsilon}(\mathbf{p}_i)$ 为 $\mathbf{p}_i$ 的 $\epsilon$-邻域，定义：

其中 $|\cdot|_{\text{span}}$ 为最大秩差，$|\cdot|$ 为邻域内点数。

1.7 实验结论

2. ETSQ：误差受控的两阶段空间查询

2.1 查询代价形式化

对于空间范围查询 $Q(\mathbf{q}, r) = \{\mathbf{p} \in \mathcal{D} \mid \|\mathbf{p} - \mathbf{q}\|_2 \leq r\}$，查询代价由推理开销和扫描开销组成：

其中：

• $C_{\text{inf}}$：索引推理的常数开销（MLP 前向传播时间）
• $C_{\text{scan}}(r) = \alpha \cdot \pi r^2 \cdot \beta$：扫描开销，与查询面积成正比
• $t_{\text{inf}}$ 和 $t_{\text{scan}}$ 为对应操作次数

核心权衡：增大候选区间 → 减少推理次数但增加扫描量；缩小候选区间 → 反之。

2.2 异构两阶段架构

Phase 1: 轻量级 MLP 路由层

路由函数 $f_{\theta}: \mathbb{R}^d \to \mathbb{R}$ 以亚线性开销将查询点映射到粗粒度区间：

其中 MLP 结构为 $d \to 64 \to 32 \to 1$（GELU 激活），参数量精确控制在 $\Theta = 64d + 64 + 32 \cdot 64 + 32 + 32 + 1$。

训练目标为最小化区间覆盖误差：

Phase 2: $\varepsilon$-有界分段线性回归定位层

在候选区间 $\hat{I}$ 内，使用分段线性函数 $g_{\phi}$ 精确定位：

关键约束：预测误差有界。定义 $\varepsilon$ 边界保证：

训练时通过双目标优化强制满足：

其中 $\lambda = 10.0$ 为约束违反惩罚系数，$\varepsilon = 16$（容许误差 16 个秩值位）。

2.3 查询执行流程

输入：查询点 q，半径 r
阶段 1 — MLP 路由：
    pid_hat = f_θ(q);
    候选区间 = [pid_hat - Δ_L - ε, pid_hat + Δ_R + ε]
    候选点集 = 区间内所有点
阶段 2 — 精确过滤：
    对候选集中每个点 p：
        if ||p - q|| ≤ r → 加入结果集
返回结果

2.4 实验结论

硬件：Intel Xeon 8358P × 2（64 核），数据集规模 $10^7$ 条

在各选择度下（$10^{-6}$ ~ $10^{-1}$），ETSQ 的延迟保持稳定，长尾受控。

3. DLSM：动态更新下的索引维护

3.1 预测偏移代价模型

动态更新场景下，插入/删除操作导致数据分布漂移，模型预测误差逐渐增大。定义时刻 $t$ 的结构化漂移指标：

其中 $\pi_t$ 为理想秩值，$\hat{\pi}_t$ 为当前模型预测值。

局部重构触发条件：

3.2 Gapped Array 存储结构

每个叶节点的数据以 Gapped Array 组织。定义填充因子 $\phi_k$（已占用比例）和空闲率 $\gamma_k = 1 - \phi_k$：

自适应空闲率分配策略根据节点密度比值 $\lambda_k$ 动态调整：

其中 $\gamma_{\min} = 0.05$，$\gamma_{\max} = 0.50$，$\lambda_{\max}$ 为所有叶节点最大密度比值。

该策略保证高密度区域留有充足空位吸收插入，低密度区域避免空间浪费。

3.3 写时复制快照隔离（CoW-SI）

DLSM 采用写时复制快照隔离机制：读操作访问当前快照 $S_{\text{cur}}$，写操作在影子副本 $S_{\text{shadow}}$ 上进行。

快照状态机：

异步重构与原子替换流程：

1. 创建当前四叉树 T_cur 的影子副本 T_shadow
2. 在 T_shadow 上批量执行写操作（插入/删除/更新）
3. 检查 Ψ_t 是否超过 τ_reorg
   → 若超过：对受影响的叶节点集 L_dirty 执行局部重构
   → 重新训练 MLP 路由层（增量 SGD，5 epochs）
4. 更新 T_shadow 中的 Gapped Array 布局
5. 原子 CAS 切换：T_cur ← T_shadow（通常在微秒级完成）

3.4 增量训练策略

MLP 路由层的更新采用增量 SGD，仅对受影响样本训练：

其中 $\mathcal{D}_{\text{delta}}$ 为增量数据（新增 + 删除影响的邻居），$\eta = 0.001$。

3.5 实验结论

硬件：Intel Xeon 8358P × 2（64 核），OS：Ubuntu 22.04

72 小时持续运行稳定性：$\Psi_t < \tau_{\text{reorg}}$ 的时间占比 99.97%，最大漂移 $\Psi_{\max} = 28.7 < 32$（重构阈值）。

3.6 与对比方法的读写平衡性

定义读写平衡性指标 $B$：

4. 总结

DLHM、ETSQ 与 DLSM 构成了学习型空间索引的完整方案：

• DLHM 解决了高偏态分布下的秩值簇化，间隙方差降低 74%
• ETSQ 实现了亚微秒级查询延迟（P50 1.35 μs），长尾受控
• DLSM 在动态更新场景下实现 10⁵ Ops/sec 吞吐，读写平衡性 0.78

核心设计原则：密度感知的自适应分区、异构两阶段的误差受控查询、写时复制快照隔离的异步维护。三者协同，从静态降维、高效查询到动态维护，完整覆盖了空间索引的全生命周期。