纯python中的可插入r-tree实现。
rtreelib的Python项目详细描述
rtreelib
纯python中的可插入r-tree实现。
概述
自从最初的r树数据结构在1984年被提出以来，已经有了 多年来引入的许多变体针对各种用例进行了优化[1]。但是，当 在python（最流行的空间数据处理语言之一）中工作时，有 很难快速比较这些不同的实现在真实数据上的表现。
这个库的目的是提供一个"可插入"的r树实现，允许交换 输出插入、节点删除和其他行为的各种策略，以便 可以很容易地比较影响（不必安装单独的库，也不必 进行代码更改以适应API差异）。几种比较常见的r-树 变体很快将作为现成的实现提供（请参见状态部分 下面）
此外，该库还提供用于检查r树结构的实用程序。它 允许创建显示R树节点和 条目（包括所有中间节点、非叶节点）及其绘图 相应的边界框。它还允许将r树导出到postgis，这样它就可以 使用像qgis这样的gis查看器进行检查。
状态
这个图书馆目前处于早期开发阶段。此时，只有原来的古特曼 实现了策略（仅插入，不删除），尽管交换的框架 战略已经到位。请注意，随着附加策略的实施， 预计这一框架将需要扩展，从而带来突破性的变化。
欢迎为执行其他战略作出贡献。请参阅 延伸下面。
有用于创建图表的现有功能（如下所述），以及 将r树结构导出到postgis也正在进行中。
设置
此软件包在pypi上提供，可以使用pip安装：
pip install rtreelib
这个包需要python 3.6+。
如果您希望能够 创建图表或将r树数据导出到postgis。见相应章节 下面是其他设置信息。
用法
要实例化默认实现并插入条目：
fromrtreelibimportRTree,Rectt=RTree()t.insert('foo',Rect(0,0,5,5))
insert方法的第一个参数表示数据，并且可以是任何数据类型
（尽管您希望坚持使用字符串、数字和其他基本数据类型，这些数据类型可以是
如果您想创建图表，可以简单而简洁地表示为字符串）。第二
参数表示相关数据元素的最小边界矩形（MBR）。
默认实现使用guttman的原始策略进行插入、节点拆分，
以及删除，如他1984年的论文[2]所述。但是，可以自定义行为
通过实例化或继承rtreebase并提供自己的实现
为了这些行为。（最终，这个库也将附带几个现成的
实现。）有关详细信息，请参阅以下部分。
延伸
如上所述，这个库的目的是提供一个可插入的r树实现 其中，可以交换和自定义各种行为，以便进行比较。到那个 最后，此库提供了实现此目标的框架。
作为一个例子，rtreeguttman
类（别名为rtree）只继承rtreebase，提供一个实现
对于选择叶，调整树，以及拆分节点行为，如下所示：
classRTreeGuttman(RTreeBase[T]):"""R-Tree implementation that uses Guttman's strategies for insertion, splitting, and deletion."""def__init__(self,max_entries:int=DEFAULT_MAX_ENTRIES,min_entries:int=None):""" Initializes the R-Tree using Guttman's strategies for insertion, splitting, and deletion. :param max_entries: Maximum number of entries per node. :param min_entries: Minimum number of entries per node. Defaults to ceil(max_entries/2). """super().__init__(choose_leaf=least_enlargement,adjust_tree=adjust_tree_strategy,split_node=quadratic_split,max_entries=max_entries,min_entries=min_entries)
每个行为都应该是at实现特定签名并执行给定的 任务。以下是当前需要指定的行为：
选择叶：用于在插入新条目时选择叶节点的策略。- 签名：
（tree:rtreebase[t]，entry:rtreeentry[t]）→rtreecode[t] - 参数：
树：rtreebase[t]：r树实例。条目：rtreeentry[t]：正在插入条目。
- 返回：
rtreenode[t]- 此函数应返回应在其中插入新条目的叶节点。这个
节点可能有也可能没有新条目的容量。如果插入新节点
导致节点溢出，将根据
拆分节点
- 此函数应返回应在其中插入新条目的叶节点。这个
节点可能有也可能没有新条目的容量。如果插入新节点
导致节点溢出，将根据
- 签名：
调整树：用于平衡树的策略，包括传播节点拆分， 根据需要更新所有节点和条目上的边界框，并通过 必要时创建新根。此策略在插入或删除 条目。- 签名：
（tree:rtreebase[t]，node:rtreenode[t]，split\u node:rtreenode[t]）→none- 参数：
树：rtreebase[t]：r树实例。节点：rtreenode[t]：刚添加新插入项的节点。拆分节点：rtreenode[t]：如果插入新条目导致节点 拆分，这是新创建的拆分节点。否则，将为none
- 返回：
无 - 参数：
- 签名：
拆分节点：用于拆分包含超过最大值的节点的策略 条目数。此函数应将节点的条目分成两组， 将其中一个组分配给原始节点的条目，另一个分配给 新创建的邻居节点（此函数应返回）。- 签名：
（tree:rtreebase[t]，node:rtreenode[t]）→rtreenode[t] - 参数：
树：rtreebase[t]：r树实例。节点：rtreenode[t]：需要拆分的溢出节点。
- 返回：
rtreenode[t]- 此函数应返回新创建的拆分节点，其条目是一个子集 原始节点的条目。
- 签名：
创建R树关系图
此库提供一组实用函数，可用于创建 整个R树结构，包括根和所有中间和叶级节点 条目.
这些功能是可选的，并且所需的依赖项不是自动安装的 安装此库时。因此，必须手动安装它们。这包括 以下是可以使用pip安装的python依赖项：
pip install matplotlib pydot tqdm
这还包括以下系统级依赖项：
- Tkinter
- 图形
在ubuntu上，可以使用：
sudo apt install python3-tk graphviz
安装上述依赖项后，您可以按如下方式创建R树关系图：
fromrtreelibimportRTree,Rectfromrtreelib.util.diagramimportcreate_rtree_diagram# Create an RTree instance with some sample datat=RTree(max_entries=4)t.insert('a',Rect(0,0,3,3))t.insert('b',Rect(2,2,4,4))t.insert('c',Rect(1,1,2,4))t.insert('d',Rect(8,8,10,10))t.insert('e',Rect(7,7,9,9))# Create a diagram of the R-tree structurecreate_rtree_diagram(t)
这将创建如下图表：
该关系图是作为postscript文件在temp目录中创建的，并且是默认的查看器 为了方便自动启动。主图中的每个框表示一个节点 （叶级除外，其中它表示叶条目），并且包含 从空间上描述所有数据。每个节点的边界框使用 棕褐色矩形虚线轮廓当前节点对应的边界框 以粉红色突出显示。
原始数据项本身的边界框用蓝色表示，并且
使用传入insert的值标记。在叶级，对应的
数据元素以粉红色突出显示。
每个节点中包含的条目沿着节点框的底部进行描述，并且 指向子节点（对于非叶节点）或数据项（对于叶节点）。
如上面的截图所示，该图描述了整个树结构，其中 可能很大，具体取决于节点和条目的数量。可能还需要一段时间 生成，因为它启动matplotlib以空间方式打印每个节点和条目的数据，并且 然后用graphviz生成整体图。给定所需的大小和执行时间 生成这些图，它只适用于包含相对较小的 数据量（例如，总共不超过十几个条目）。分析结果 当处理大量数据时，建议导出 将数据发送到postgis并使用类似qgis的查看器（如下一节所述）。
导出到Postgis
除了创建图表之外，这个库还允许将r树导出到 postgis数据库。
为此，首先需要安装psycopg2驱动程序。
这是可选的依赖项，因此在安装时不会自动安装
这个包裹。参考
psycopg2的安装说明
确保已安装所有必需的系统范围先决条件（C编译器，
python头文件等）。然后，使用以下命令（通过
--no binary标志，以确保它是从源代码构建的，并避免使用控制台
使用psycopg2时的警告：
pip install psycopg2 --no-binary psycopg2
一旦安装了psycopg2，就可以从
rtreelib.pg模块：
fromrtreelib.pgimportinit_db_pool,create_rtree_tables,export_to_postgis
下面的小节将指导您如何使用此库将r树导出到 数据库。您首先需要决定连接到 数据库，以及创建必要的表来存储r树数据。一旦这些 满足前提条件后，可以使用简单的函数调用导出r树。 最后，本指南展示了如何使用qgis（一种流行的 以及免费提供的地理信息系统查看器。
初始化连接池
当使用rtreelib.pg模块时，有三种方法可以传递数据库
连接信息：
- 通过调用init db_pool初始化连接池。这允许使用另一个 此模块中的功能无需传递连接信息。
- 自己手动打开连接，并将连接对象传递给 功能。
- 传入可用于建立数据库连接的关键字参数。 < > >
r tree：此表只包含导出的每个r树的id。 这个库允许您一次导出多个r树，它们是 按id区分（还可以使用清除树表）。r tree_node：包含有关r树中每个节点的信息，包括 它的边界框（作为postgis几何列），指向父项的指针 包含此节点，以及此节点的级别（从根节点的0开始）。 该节点还包含对它所属的rtree的引用。r tree_entry：包含有关r树中每个项的信息，包括 它的边界框（作为postgis几何列）和指向节点的指针 包含此条目。对于叶条目，它还包含 数据元素。- 转到图层→添加图层→添加Postgis图层
- 连接到导出数据的数据库
- 选择
rtree_节点或rtree_条目表，具体取决于 你想想象的结构。在本例中，我们将查看 节点，因此选择rtree\u node - 也可以设置L仅包含属于
特定树（如果导出了多个r树）。为此，请单击
设置筛选器按钮，然后输入筛选器表达式（例如
rtree_id=1）。 - 单击"添加"
第一种方法通常是最简单的——只需调用一次，而不是 必须担心将连接信息传递给其他函数。这个 第节解释此方法，以下各节假设您正在使用 它。但是，本指南后面还将介绍其他方法。
init_db_pool接受与
psycopg2.connect函数。
例如，可以传入连接字符串：
init_db_pool("dbname=mydb user=postgres password=temp123!")
或者，使用url语法：
pip install rtreelib
或关键字参数：
pip install rtreelib
接下来，在导出r树之前，首先需要创建几个数据库 标签存储数据。下一节介绍如何实现这一点。
创建表以存储r树数据
使用此库导出r树时，数据将填充在三个 表：
可以使用create_rtree_tables函数创建这些表。这是
你只需要做一次。
如果已建立
连接池，并且数据不使用空间引用系统（srid）。
但是，通常在处理空间数据时，您将具有
您的数据所在的srid，在这种情况下，您应该将其传入以确保
所有几何列都使用正确的srid:
pip install rtreelib
您还可以选择在不同的模式（而不是public）中创建表：
pip install rtreelib
但是，在这种情况下，请确保将同一架构传递给 此模块。
您还可以传入一个数据类型，它指示存储在叶中的数据类型
条目（即，传递到rtree的insert方法的数据类型）。
这可以是包含PostgreSQL列类型的字符串：
pip install rtreelib
或python类型，在这种情况下，将推断出适当的postgresql数据类型：
pip install rtreelib
如果您没有传入任何内容，或者适当的postgresql数据类型不能是
根据python类型确定，列类型默认为text，这允许
存储任意长度的字符串。
当传递包含PostgreSQL列类型的字符串时，您还可以选择
添加修饰符，例如not null，甚至外键约束：
pip install rtreelib
导出r树
要在创建表后导出r树，只需调用
export_to_postgis函数，传入r-tree实例（以及可选的srid）：
pip install rtreelib
此函数使用
来自r树的数据，并返回
rtree表格。
请注意，如果在调用
创建树表，调用时需要传入相同的架构
导出到postgis：
pip install rtreelib
使用qgis查看数据
qgis是一个受欢迎且免费提供的gis查看器。 可用于可视化导出的R树数据。为此，启动qgis并创建 一个新项目。然后，按照以下步骤将导出的r树数据添加为层：
此时，层将显示树的每个级别上的所有节点， 如果你有大量的数据，这可能有点难以破译。调整后 图层样式使其部分透明，下面是一个r树的示例 如果有几百个leaf条目，可能看起来像（3个级别上有38个节点）：
为了更容易理解结构，可以查看每个 独立于树的级别。为此，双击图层中的图层 面板，切换到"样式"选项卡，然后从 "单一符号"（默认）设置为"分类"。然后在列下拉列表中，选择 "级别"栏。可以选择指定颜色渐变或使用随机颜色，以便 每一层都有不同的颜色。然后单击"分类"自动 为每个图层创建单独的样式：
现在在Layers面板中，每个级别将显示为一个单独的条目，并且可以 打开和关闭，使探索r树结构成为可能 每次：
现在，只查看级别1（根节点正下方的级别）的节点， 这样可以更容易地看到边界矩形的外观：
显然，在这个特定的数据集上使用默认的guttman实现是 非最优（取决于用例），因为它导致了很多重叠。这个 例如，这意味着一个典型的查询可以找到给定 位置需要访问许多子树。
也许一个不同的r树变体在这个数据集上更有效？这就是 此库要回答的问题类型。
清理
如上所述，当您调用export_to_postgis时，
表格未清除。这允许您一次导出多个r树，并且
并排比较。
但是，为了简单起见，您可能希望在
正在导出新数据。为此，请调用清除树表：
pip install rtreelib
这将对所有r树表执行sqltruncate。
注意，如果您在不同的模式（而不是public）中创建表，
您需要将相同的架构传递给此函数：
fromrtreelibimportRTree,Rectt=RTree()t.insert('foo',Rect(0,0,5,5))0
您可能还希望完全删除由
创建树表。要执行此操作，请调用drop_rtree_tables：
fromrtreelibimportRTree,Rectt=RTree()t.insert('foo',Rect(0,0,5,5))1
同样，如果schema不是public，则可能需要传入它：
fromrtreelibimportRTree,Rectt=RTree()t.insert('foo',Rect(0,0,5,5))2
备用数据库连接处理方法
如本指南前面所述，不是初始化连接池， 当 使用这个库。您可以选择打开和关闭连接 您自己并传入连接对象；或者，您可以传入 连接信息作为关键字参数。
为了自己建立数据库连接，典型的使用场景可能 如下所示：
fromrtreelibimportRTree,Rectt=RTree()t.insert('foo',Rect(0,0,5,5))3
您还可以将数据库连接信息作为 关键字参数。这些关键字参数应与 psycopg2.connect函数：
fromrtreelibimportRTree,Rectt=RTree()t.insert('foo',Rect(0,0,5,5))4
参考文献
[1]：Nanopoulos，Alexandros和Papadopoulos，Apostolos（2003年）： "到处都长满了R树"
[2]：Guttman，A.（1984年）： "r-trees：用于空间搜索的动态索引结构" （pdf），1984年ACM SIGMOD数据管理国际会议记录-SIGMOD '84.第47页。
欢迎加入QQ群-->： 979659372
