一、为什么需要空间索引
假设地图有 100 万个点。
如果用户点击地图，需要找：
text
离鼠标最近的点最简单方式：
text
遍历所有点
O(n)如果：
text
n = 1000000每次点击都遍历：
text
1000000 次计算地图就会卡顿。
所以需要：
text
空间索引（Spatial Index）目标：
text
O(n) → O(log n)二、空间索引核心思想
普通数据库索引：
text
B-Tree是 一维数据。
但 GIS 数据是：
text
二维 / 三维例如：
text
(x, y)所以需要：
text
多维索引常见结构：
| 索引 | 用途 |
|---|---|
| R-Tree | GIS 最常见 |
| QuadTree | 地图瓦片 |
| KD-Tree | 最近邻搜索 |
三、R-Tree（GIS最常见）
R-Tree 是 矩形树。
核心思想：
text
用矩形包裹对象例如：
Root
/ \
NodeA NodeB每个节点是：
text
MBR
Minimum Bounding Rectangle例如：
+--------+
| 点集合 |
+--------+插入流程
假设插入一个点：
text
P(10,20)步骤：
1 找最合适节点
选择 扩展面积最小 的矩形。
例如：
text
Area increase 最小2 插入叶子节点
Leaf
├ Point1
├ Point2
└ Point33 节点溢出
如果：
text
node > maxEntries就：
text
split拆分节点。
四、查询流程（核心）
例如查询：
text
鼠标附近的点步骤：
1 从 root 开始
检查：
text
query bbox是否和节点矩形相交。
2 如果不相交
直接：
text
skip3 如果相交
进入子节点。
4 到达 leaf
返回数据。
查询复杂度：
text
O(log n)而不是：
text
O(n)五、QuadTree（地图常用）
地图系统很常见：
text
QuadTree原理：
text
空间递归四分示意：
+--------+
| |
| +----+----+
| | | |
|---+----+----|
| | | |
| +----+----+每个节点分成：
text
4 个象限优点：
text
实现简单很多地图：
text
tile本质就是：
text
QuadTree六、KD-Tree（最近邻搜索）
如果问题是：
text
找最近的点通常使用：
text
KD-Tree原理：
text
交替按 x / y 分割示例：
x < 50
\
y < 30适合：
text
Nearest Neighbor七、前端如何实现空间索引
前端一般不会自己写 R-Tree。
常见库：
rbush
非常流行。
javascript
import RBush from "rbush"
const tree = new RBush()
tree.insert({
minX: 10,
minY: 20,
maxX: 10,
maxY: 20,
id: "point1"
})查询：
javascript
tree.search({
minX: 0,
minY: 0,
maxX: 50,
maxY: 50
})复杂度：
text
O(log n)八、GIS 系统真实架构
大型地图系统通常：
text
前端
↓
VectorTile
↓
TileServer
↓
PostGIS数据库层：
text
GIST Index例如：
sql
CREATE INDEX idx_geom
ON points
USING GIST(geom)查询：
sql
ST_Intersects九、前端真实应用场景
空间索引常见用途：
1 点击地图选点
text
click → nearest point2 框选查询
text
bbox search3 聚合算法
text
cluster4 碰撞检测
例如：
text
label collision十、空间索引怎么实现？
空间索引主要用于优化 GIS 数据查询，因为空间数据是二维或三维的，普通 B-Tree 只能处理一维数据，所以 GIS 通常使用多维索引结构，比如 R-Tree、QuadTree 或 KD-Tree。
其中 R-Tree 是最常见的，它通过 Minimum Bounding Rectangle 对空间对象进行分组，形成层级树结构。查询时只需要遍历与查询范围相交的节点，从而将复杂度从 O(n) 降低到 O(log n)。
在地图系统中，QuadTree 常用于瓦片地图划分，而 KD-Tree 更适合最近邻搜索。
在前端实现中，一般会使用 rbush 这样的库构建 R-Tree 索引，用于快速实现点击选点、框选查询或点位聚合等功能。