截至 DuckDB v1.1.0 版本，spatial 扩展通过 R-tree 扩展索引类型提供了对空间索引的基本支持。
为什么我应该使用R-Tree索引？
在处理地理空间数据集时，通常需要根据它们与特定感兴趣区域的空间关系来过滤行。不幸的是，尽管DuckDB的向量化执行引擎相当快，但这种操作在大数据集上扩展性不佳，因为它总是需要全表扫描来检查表中的每一行。然而，通过使用R树对表进行索引，可以显著加速这类查询。
R树索引是如何工作的？
R树是一种平衡树数据结构，它在叶节点中存储每个几何图形的近似最小边界矩形（以及相应行的内部ID），并在每个内部节点中存储包含所有子节点的边界矩形。
几何体的最小边界矩形（MBR）是完全包围该几何体的最小矩形。通常当我们谈论几何体的边界矩形（或在2D几何体上下文中的边界“框”）时，我们指的是最小边界矩形。此外，我们倾向于假设边界框/矩形是轴对齐的，即矩形不旋转 - 边总是与坐标轴平行。点的MBR就是点本身。
通过从顶部到底部遍历R树，可以非常快速地搜索R树索引表，仅查找那些索引几何列与特定感兴趣区域相交的行，因为如果父节点的边界矩形与查询区域完全不相交，则可以跳过整个子树的搜索。一旦到达叶节点，只需从磁盘中获取几何与查询区域相交的特定行，并且通常更昂贵的精确空间谓词检查（以及任何其他过滤器）只需对这些行执行。
R-Tree 索引在 DuckDB 中的限制是什么？
在开始使用R-tree索引之前，有一些限制需要注意：
- R-tree 索引仅支持
GEOMETRY数据类型。 - R-tree索引仅在表使用以下空间谓词函数之一进行过滤（使用
WHERE子句）时用于执行“索引扫描”（因为它们都暗示交集）：ST_Equals,ST_Intersects,ST_Touches,ST_Crosses,ST_Within,ST_Contains,ST_Overlaps,ST_Covers,ST_CoveredBy,ST_ContainsProperly。 - 空间谓词函数的其中一个参数必须是一个“常量”（即在查询规划时结果已知的表达式）。这是因为查询规划器需要在查询本身执行之前知道查询区域的边界框，以便使用R-tree索引扫描。
未来我们希望启用R树索引，以加速额外的谓词函数和更复杂的查询，如空间连接。
如何在DuckDB中使用R-Tree索引
要创建R树索引，只需使用CREATE INDEX语句和USING RTREE子句，将几何列传递给括号内的索引。例如：
-- Create a table with a geometry column
CREATE TABLE my_table (geom GEOMETRY);
-- Create an R-tree index on the geometry column
CREATE INDEX my_idx ON my_table USING RTREE (geom);
在使用WITH子句创建R树索引时，您还可以传入额外的选项来控制R树索引的行为。例如，要指定R树中每个节点的最大条目数，您可以使用max_node_capacity选项：
CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (max_node_capacity = 16);
调整这些选项对性能的影响高度依赖于DuckDB运行的系统设置、数据集的空间分布以及特定工作负载的查询模式。默认设置应该足够好，但如果你想尝试不同的参数，请参阅这里的完整选项列表。
Example
这里有一个示例，展示了如何在几何列上创建R树索引，并且我们可以看到当表使用空间谓词进行过滤时，使用了RTREE_INDEX_SCAN操作符：
INSTALL spatial;
LOAD spatial;
-- Create a table with 10_000_000 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 10_000, 1337);
-- Create an index on the table.
CREATE INDEX my_idx ON t1 USING RTREE (geom);
-- Perform a query with a "spatial predicate" on the indexed geometry column
-- Note how the second argument in this case, the ST_MakeEnvelope call is a "constant"
SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));
390
我们可以通过使用EXPLAIN语句来检查是否使用了R树索引扫描：
EXPLAIN SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));
┌───────────────────────────┐
│ UNGROUPED_AGGREGATE │
│ ──────────────────── │
│ Aggregates: │
│ count_star() │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ FILTER │
│ ──────────────────── │
│ ST_Within(geom, '...') │
│ │
│ ~2000 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ RTREE_INDEX_SCAN │
│ ──────────────────── │
│ t1 (RTREE INDEX SCAN : │
│ my_idx) │
│ │
│ Projections: geom │
│ │
│ ~10000 Rows │
└───────────────────────────┘
性能考虑
批量加载与维护
在已经填充数据的表上创建R树比先创建索引再插入数据要快得多。这是因为R树在插入数据后，当节点达到最大容量时，必须定期重新平衡自己并执行一些代价较高的分裂操作，这可能会导致额外的分裂在树中向上级联。然而，当在已经填充数据的表上创建R树索引时，使用了一种特殊的自下而上的“批量加载算法”（Sort-Tile-Recursive），该算法将所有条目划分为一个已经平衡的树，因为所需节点的总数可以从一开始就计算出来。
此外，使用批量加载算法往往会创建一个结构更好的R树（边界框之间的重叠较少），这通常会导致更好的查询性能。如果您发现R树的查询性能在大量更新或删除后开始下降，删除并重新创建索引可能会产生更高质量的R树。
内存使用
与DuckDB内置的ART索引类似，所有包含R树的关联缓冲区将从磁盘延迟加载（当DuckDB在磁盘支持模式下运行时），但它们目前除非索引被删除，否则不会被卸载。这意味着如果你最终扫描整个索引，整个索引将被加载到内存中，并在数据库连接期间保留在那里。然而，R树索引使用的所有内存（即使在批量加载期间）都由DuckDB跟踪，并将计入由memory_limit配置参数设置的内存限制。
调优
根据你的具体工作负载，你可能想要尝试使用max_node_capacity和min_node_capacity选项来改变R树的结构以及它如何响应插入和删除操作，请参阅此处完整的选项列表。一般来说，具有更高总节点数的树（即较低的max_node_capacity）可能会导致更细粒度的结构，从而在查询执行期间能够更积极地修剪子树，但它也需要更多的内存来存储树本身，并且在查询较大区域时会更加耗时，因为需要遍历更多的内部节点。
选项
在创建R树索引时，可以将以下选项传递给WITH子句：（例如，CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (⟨option⟩ = ⟨value⟩);）
| 选项 | 描述 | 默认值 |
|---|---|---|
max_node_capacity |
R树中每个节点的最大条目数。 | 128 |
min_node_capacity |
R树中每个节点的最小条目数。 | 0.4 * max_node_capacity |
*如果删除后某个节点的条目数低于最小值，该节点将被解散，所有条目将从树的顶部重新插入。这是R树实现中的常见操作，以防止树变得过于不平衡。
R-Tree 表函数
rtree_index_dump(VARCHAR) 表函数可用于返回 R-tree 索引中的所有节点，这在调试、性能分析或检查索引结构时可能会派上用场。该函数以 R-tree 索引的名称作为参数，并返回一个包含以下列的表：
| 列名 | 类型 | 描述 |
|---|---|---|
level |
INTEGER |
节点在R树中的层级。根节点的层级为0。 |
bounds |
BOX_2DF |
节点的边界框。 |
row_id |
ROW_TYPE |
如果这是一个叶节点，则为表中行的rowid，否则为NULL。 |
示例：
-- Create a table with 64 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 64, 1337);
-- Create an R-tree index on the geometry column (with a low max_node_capacity for demonstration purposes)
CREATE INDEX my_idx ON t1 USING RTREE (geom) WITH (max_node_capacity = 4);
-- Inspect the R-tree index. Notice how the area of the bounding boxes of the branch nodes
-- decreases as we go deeper into the tree.
SELECT
level,
bounds::GEOMETRY AS geom,
CASE WHEN row_id IS NULL THEN st_area(geom) ELSE NULL END AS area,
row_id,
CASE WHEN row_id IS NULL THEN 'branch' ELSE 'leaf' END AS kind
FROM rtree_index_dump('my_idx')
ORDER BY area DESC;
┌───────┬──────────────────────────────┬────────────────────┬────────┬─────────┐
│ level │ geom │ area │ row_id │ kind │
│ int32 │ geometry │ double │ int64 │ varchar │
├───────┼──────────────────────────────┼────────────────────┼────────┼─────────┤
│ 0 │ POLYGON ((2.17285037040710… │ 3286.396482226409 │ │ branch │
│ 0 │ POLYGON ((6.00962591171264… │ 3193.725100864862 │ │ branch │
│ 0 │ POLYGON ((0.74995160102844… │ 3099.921458393704 │ │ branch │
│ 0 │ POLYGON ((14.6168870925903… │ 2322.2760491675654 │ │ branch │
│ 1 │ POLYGON ((2.17285037040710… │ 604.1520104388514 │ │ branch │
│ 1 │ POLYGON ((26.6022186279296… │ 569.1665467030252 │ │ branch │
│ 1 │ POLYGON ((35.7942314147949… │ 435.24662436250037 │ │ branch │
│ 1 │ POLYGON ((62.2643051147460… │ 396.39027683023596 │ │ branch │
│ 1 │ POLYGON ((59.5225715637207… │ 386.09153403820187 │ │ branch │
│ 1 │ POLYGON ((82.3060836791992… │ 369.15115640929434 │ │ branch │
│ · │ · │ · │ · │ · │
│ · │ · │ · │ · │ · │
│ · │ · │ · │ · │ · │
│ 2 │ POLYGON ((20.5411434173584… │ │ 35 │ leaf │
│ 2 │ POLYGON ((14.6168870925903… │ │ 36 │ leaf │
│ 2 │ POLYGON ((43.7271652221679… │ │ 39 │ leaf │
│ 2 │ POLYGON ((53.4629211425781… │ │ 44 │ leaf │
│ 2 │ POLYGON ((26.6022186279296… │ │ 62 │ leaf │
│ 2 │ POLYGON ((53.1732063293457… │ │ 63 │ leaf │
│ 2 │ POLYGON ((78.1427154541015… │ │ 10 │ leaf │
│ 2 │ POLYGON ((75.1728591918945… │ │ 15 │ leaf │
│ 2 │ POLYGON ((62.2643051147460… │ │ 42 │ leaf │
│ 2 │ POLYGON ((80.5032577514648… │ │ 49 │ leaf │
├───────┴──────────────────────────────┴────────────────────┴────────┴─────────┤
│ 84 rows (20 shown) 5 columns │
└──────────────────────────────────────────────────────────────────────────────┘