1. Why is spatial index needed?

Let's say the map has 1 million points.

If the user clicks on the map, they need to find:

离鼠标最近的点

The simplest way:

遍历所有点
O(n)

if:

n = 1000000

Iterate through each click:

1000000 次计算

The map will freeze.

So need:

空间索引（Spatial Index）

Goal:

O(n) → O(log n)

2. Core idea of spatial index

Ordinary database index:

B-Tree

is one-dimensional data.

But GIS data is:

二维 / 三维

For example:

(x, y)

So need:

多维索引

Common structures:

Index	Purpose
R-Tree	GIS most common
QuadTree	Map tiles
KD-Tree	Nearest neighbor search

3. R-Tree (the most common in GIS)

R-Tree is rectangular tree 。

Core idea:

用矩形包裹对象

For example:

        Root
       /    \
    NodeA  NodeB

Each node is:

MBR
Minimum Bounding Rectangle

For example:

+--------+
| 点集合 |
+--------+

Insert process

Suppose you insert a point:

P(10,20)

Steps:

1 Find the most suitable node

Choose Minimum expansion area rectangle.

For example:

Area increase 最小

2 Insert leaf nodes

Leaf
 ├ Point1
 ├ Point2
 └ Point3

3 node overflow

if:

node > maxEntries

Just:

split

Split the node.

4. Query process (core)

For example query:

鼠标附近的点

Steps:

1 Start from root

Check:

query bbox

Whether it intersects with the node rectangle.

2 if they do not intersect

Directly:

skip

3 if intersected

Enter the child node.

4 arrive at leaf

Return data.

Query complexity:

O(log n)

instead of:

O(n)

5. QuadTree (commonly used for maps)

Map systems are common:

QuadTree

Principle:

空间递归四分

Indicate:

+--------+
|        |
|   +----+----+
|   |    |    |
|---+----+----|
|   |    |    |
|   +----+----+

Each node is divided into:

4 个象限

Advantages:

实现简单

Lots of maps:

tile

The essence is:

QuadTree

6. KD-Tree (nearest neighbor search)

If the question is:

找最近的点

Typically used:

KD-Tree

Principle:

交替按 x / y 分割

Example:

x < 50
      \
       y < 30

Suitable for:

Nearest Neighbor

7. How to implement spatial index on the front end

The front end generally does not write R-Tree by itself.

Common libraries:

rbush

Very popular.

import RBush from "rbush"

const tree = new RBush()

tree.insert({
  minX: 10,
  minY: 20,
  maxX: 10,
  maxY: 20,
  id: "point1"
})

Query:

tree.search({
  minX: 0,
  minY: 0,
  maxX: 50,
  maxY: 50
})

Complexity:

O(log n)

8. Real architecture of GIS system

Large map systems typically:

前端
 ↓
VectorTile
 ↓
TileServer
 ↓
PostGIS

Database layer:

GIST Index

For example:

CREATE INDEX idx_geom
ON points
USING GIST(geom)

Query:

ST_Intersects

9. Front-end real application scenarios

Common uses of spatial indexes:

1 Click on the map to select a point

click → nearest point

2 Frame selection query

bbox search

3 Aggregation algorithm

cluster

4 Collision detection

For example:

label collision

10. How to implement spatial index?

Spatial indexes are mainly used to optimize GIS data queries. Because spatial data is two-dimensional or three-dimensional, ordinary B-Tree can only process one-dimensional data, so GIS usually uses multi-dimensional index structures, such as R-Tree, QuadTree or KD-Tree.

Among them, R-Tree is the most common. It groups spatial objects through Minimum Bounding Rectangle to form a hierarchical tree structure.When querying, only the nodes that intersect the query range need to be traversed, thereby reducing the complexity from O(n) to O(log n).

In map systems, QuadTree is often used for tile map partitioning, while KD-Tree is more suitable for nearest neighbor search.

In front-end implementation, libraries such as rbush are generally used to build R-Tree indexes to quickly implement functions such as click point selection, frame selection query, or point aggregation.