如何在关系数据库中存储二元空间分区树？
我试图将数据存储在关系数据库中的二进制空间分区树中。这个数据结构的棘手部分是它有两种不同类型的节点。第一种类型，我们称之为数据节点，只保存一定数量的项目。我们将可容纳的最大物品数量定义为t。第二种类型，我们称为容器节点，包含另外两个子节点。当一个项目被添加到树中时，节点将被递归，直到找到数据节点。如果数据节点中的项目数小于t，则该项目被插入到数据节点中。否则，数据节点将被拆分为另外两个数据节点，并被容器节点之一替换。当删除一个元素时，必须发生相反的过程。
我有点失落。我该如何使用关系模型来完成这项工作？
I'm trying to store the data in a binary space partitioning tree in a relational database. The tricky part about this data structure is it has two different types of nodes. The first type, which we call a data node, simply holds a certain number of items. We define the maximum number of items able to be held as t. The second type, which we refer to as a container node, holds two other child nodes. When an item is added to the tree, the nodes are recursed until a data node is found. If the number of items in the data node are less than t, then the item is inserted into the data node. Otherwise the data node is split into two other data nodes, and is replaced by one of the container nodes. When an element is deleted, a reverse process must happen.
I'm a little bit lost. How am I supposed to make this work using a relational model?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
为什么不有两张表，一张用于节点，一张用于项目？ （请注意，当我编写答案时，我在下面使用术语“叶”而不是“数据”节点；“叶”节点具有数据项，非“叶”节点包含其他节点。）
节点表将包含列像这样：
id 主键、parentid 引用节点、叶子布尔以及一些用于描述节点的空间边界以及它将/已经如何分割的列。 （我不知道您是在 2D 还是 3D 中工作，所以我没有提供有关几何形状的详细信息。）数据表将包含 id 主键、leafid 引用节点和任何数据。
您可以通过在每个级别发出 SELECT * FROM node WHERE Parentid = ? 查询并检查要下降到哪个子级来向下遍历树。向叶子添加数据项是一个简单的
INSERT。拆分节点需要取消设置叶标志，插入两个新的叶节点，并通过更改其 leafid 值来更新节点中的所有数据项以指向适当的子节点。请注意，SQL 往返可能会很昂贵，因此如果您希望将其用于实际应用程序，请考虑在数据库中使用相对较大的
t在叶子内存中构建更细粒度的树获得数据项后您会感兴趣。Why not have two tables, one for nodes and one for items? (Note that I used the term "leaf" instead of "data" nodes below when I wrote my answer; a "leaf" node has data items, a non-"leaf" node contains other nodes.)
The node table would have columns like this:
id primary key, parentid references node, leaf booleanand in addition some columns to describe the spatial bounaries of the node and how it will/has been split. (I don't know if you're working in 2D or 3D so I haven't given details on the geometry.)The data table would have
id primary key, leafid references nodeand whatever data.You can traverse the tree downward by issuing
SELECT * FROM node WHERE parentid = ?queries at each level and checking which child to descend into. Adding a data item to a leaf is a simpleINSERT. Splitting a node requires unsetting the leaf flag, inserting two new leaf nodes, and updating all the data items in the node to point to the appropriate child node by changing their leafid values.Note that SQL round trips can be expensive, so if you're looking to use this for a real application, consider using a relatively large
tin the DB constructing a finer-grained tree in memory of the leaves you are interested in after you have the data items.