我需要使用三叉树结构,它必须存储在某个地方(我选择了关系数据库,但我仍然可以更改它)。
我的数据库树看起来像:
例如,我的关系包含列 - Id
、child1Id
、child2Id
、child3Id
和 is_active
问题是我必须通过 boolean 参数提供 BFS 的能力。例如,在图片上应该可以找到 Node#35。 当然,我知道如何用java中的现成数据实现BFS,但是要做到这一点,我需要从数据库接收整个树。 是否可以通过 SQL 查询来完成? 或者也许任何人都可以提出比将其存储在关系数据库上更好的解决方案?
最佳答案
可能的解决方案之一是使用图形数据库而不是关系数据库,正如评论中所建议的那样。
但是,如果可以仅使用关系数据库,方法之一是向带有节点的表添加附加字段 - 深度
和position_in_layer
。
depth = Parent.depth+1
, positionInLayer = (parent.positionInLayer - 1) * 3 + childNum
,其中 3 表示三叉树(对于二叉树则为 2), childnum - 当前节点是哪个子节点。
例如,当我们将第二个子节点添加到第 5 层中的节点 5 时,它将具有深度 6 和位置 4*3+2 = 14。它将是第 6 层中的第 14 个元素。
有了这些字段,二分搜索就可以通过像这样的查询逐层实现
从节点中选择*,其中深度 = i 且 is_active = 0 按position_in_layer asc limit 1 排序
,其中 i - 层数(从 1 到SELECT MAX(深度) FROM 节点
)。
结果还不错 - 通过 BFS 在具有 ~9800 个节点的树中搜索最后一个元素仅花费了 22 毫秒(添加了索引)
关于java - 关系数据库中BFS的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50907401/