我正在尝试将数据存储在关系数据库中的二进制空间分区树中。这个数据结构的棘手部分是它有两种不同类型的节点。第一种类型，我们称为数据节点，只是保存一定数量的项目。我们将能够容纳的最大项目数定义为t。第二种类型，我们称之为容器节点，包含另外两个子节点。当一个项目被添加到树中时，节点会被递归，直到找到一个数据节点。如果数据节点中的项目数小于t，则将该项目插入数据节点。否则，数据节点将拆分为另外两个数据节点，并由其中一个容器节点替换。当一个元素被删除时，必须发生相反的过程。
我有点迷路了。我应该如何使用关系模型来完成这项工作？
为什么没有两张表，一张用于节点，一张用于项目？（请注意，当我写答案时，我在下面使用术语“叶”而不是“数据”节点；“叶”节点包含数据项，非“叶”节点包含其他节点。）
节点表将具有如下列：id primary key, parentid references node, leaf boolean此外还有一些列来描述节点的空间边界以及它将/已如何拆分。（我不知道您是在 2D 还是 3D 中工作，所以我没有提供有关几何的详细信息。）
数据表将包含id primary key, leafid references node任何数据。
您可以通过在每个级别发出SELECT * FROM node WHERE parentid = ?查询并检查要下降到哪个子级来向下遍历树。向叶子添加数据项是一个简单的INSERT. 拆分节点需要取消设置叶子标志，插入两个新的叶子节点，并通过更改它们的叶子值来更新节点中的所有数据项以指向适当的子节点。
请注意，SQL 往返可能很昂贵，因此如果您希望将其用于实际应用程序，请考虑t在 DB 中使用相对较大的树，在您拥有数据项。