从 DuckDB v1.1.0 版本开始，spatial 扩展通过 R-tree 扩展索引类型提供了对空间索引的基本支持。
为什么要使用 R-Tree 索引？
在处理地理空间数据集时，通常需要根据行与特定关注区域的空间关系来过滤数据。遗憾的是，尽管 DuckDB 的向量化执行引擎速度很快，但这种操作在大型数据集上的扩展性并不好，因为它总是需要进行全表扫描来检查表中的每一行。然而，通过使用 R-tree 对表建立索引，可以显著加速此类查询。
R-Tree 索引是如何工作的？
R-tree 是一种平衡树数据结构，它在叶子节点中存储每个几何对象的近似最小外接矩形（以及相应行的内部 ID），并在每个内部节点中存储包围所有子节点的矩形。
几何对象的最小外接矩形 (MBR) 是完全包围该几何对象的最小矩形。通常当我们谈论几何对象的外接矩形（在二维几何上下文中也称为外接“盒子”）时，指的就是最小外接矩形。此外，我们通常假设外接盒子/矩形是轴对齐的，即矩形不会旋转——其各边始终平行于坐标轴。点的 MBR 就是点本身。
通过从上到下遍历 R-tree，可以非常快速地在建立了 R-tree 索引的表中搜索那些索引几何列与特定关注区域相交的行。因为如果父节点的边界矩形与查询区域完全不相交，你就可以跳过对整个子树的搜索。一旦到达叶子节点，只有那些几何图形与查询区域相交的特定行才需要从磁盘读取，而通常代价更高昂的精确空间谓词检查（以及任何其他过滤器）只需对这些行执行即可。
DuckDB 中 R-Tree 索引的局限性是什么？
在开始使用 R-tree 索引之前，有一些局限性需要注意：
- R-tree 索引仅支持
GEOMETRY数据类型。 - 只有当表使用以下空间谓词函数之一进行过滤（使用
WHERE子句）时，才会使用 R-tree 索引来执行“索引扫描”（因为它们都隐含了相交关系）：ST_Equals、ST_Intersects、ST_Touches、ST_Crosses、ST_Within、ST_Contains、ST_Overlaps、ST_Covers、ST_CoveredBy、ST_ContainsProperly。 - 空间谓词函数的参数之一必须是“常量”（即在查询规划时结果已知的表达式）。这是因为查询规划器需要在执行查询本身之前就知道查询区域的边界框，以便使用 R-tree 索引扫描。
未来我们希望能够让 R-tree 索引用于加速更多的谓词函数以及更复杂的查询，例如空间连接 (spatial joins)。
如何在 DuckDB 中使用 R-Tree 索引
要创建 R-tree 索引，只需使用带有 USING RTREE 子句的 CREATE INDEX 语句，并在括号内传入要索引的几何列。例如：
-- 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-tree 索引时，还可以传入额外的选项来控制其行为。例如，要指定 R-tree 中每个节点的最大条目数，可以使用 max_node_capacity 选项：
CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (max_node_capacity = 16);
调整这些选项对性能的影响在很大程度上取决于 DuckDB 运行的系统设置、数据集的空间分布以及特定工作负载的查询模式。默认设置通常已经足够好，但如果你想尝试不同的参数，请参阅此处的完整选项列表。
示例
以下是一个示例，展示了如何在几何列上创建 R-tree 索引，以及当我们用空间谓词过滤表时，可以看到使用了 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-tree 索引扫描：
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-tree 比先创建索引再插入数据要快得多。这是因为 R-tree 在插入后当节点达到最大容量时，必须周期性地进行自我平衡并执行代价高昂的拆分操作，这可能会导致额外的拆分级联到树的上方。然而，当在已填充的表上创建 R-tree 索引时，会使用一种特殊的自底向上“批量加载算法”（Sort-Tile-Recursive），它将所有条目划分为一个已经平衡的树，因为所需的节点总数可以从一开始就计算出来。
此外，使用批量加载算法往往能创建结构更好的 R-tree（边界框之间的重叠更少），这通常会带来更好的查询性能。如果你发现 R-tree 的查询性能在大量更新或删除后开始下降，删除并重新创建索引可能会产生质量更高的 R-tree。
内存使用
与 DuckDB 内置的 ART 索引一样，所有包含 R-tree 的关联缓冲区都会从磁盘延迟加载（在磁盘备份模式下运行 DuckDB 时），但除非索引被删除，否则它们目前永远不会被卸载。这意味着如果你最终扫描了整个索引，整个索引将被加载到内存中，并在数据库连接期间一直保留在那里。不过，R-tree 索引使用的所有内存（即使在批量加载期间）都会由 DuckDB 跟踪，并计入 memory_limit 配置参数设置的内存限制内。
调优
根据你的特定工作负载，你可能需要试验 max_node_capacity 和 min_node_capacity 选项，以改变 R-tree 的结构及其对插入和删除的响应方式，请参阅此处的完整选项列表。通常情况下，节点总数较多的树（即较低的 max_node_capacity）可能会产生更细粒度的结构，从而在查询执行期间实现对子树更积极的剪枝，但它也需要更多的内存来存储树本身，并且在查询较大区域时因为必须遍历更多的内部节点，性能会受到更多影响。
选项
创建 R-tree 索引时，可以将以下选项传递给 WITH 子句：（例如：CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (option = value);）
| 选项 | 描述 | 默认值 |
|---|---|---|
max_node_capacity |
R-tree 中每个节点的最大条目数 | 128 |
min_node_capacity |
R-tree 中每个节点的最小条目数 | 0.4 * max_node_capacity |
*如果删除后节点的条目数低于最小值，该节点将被解散，所有条目将从树的顶端重新插入。这是 R-tree 实现中防止树变得过于不平衡的常见操作。
R-Tree 表函数
rtree_index_dump(VARCHAR) 表函数可用于返回 R-tree 索引中的所有节点，这在调试、分析或仅仅是检查索引结构时非常有用。该函数接受 R-tree 索引的名称作为参数，并返回一个包含以下列的表：
| 列名 | 类型 | 描述 |
|---|---|---|
level |
INTEGER |
节点在 R-tree 中的层级。根节点的层级为 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 │
└──────────────────────────────────────────────────────────────────────────────┘