java - 关系数据库中BFS的实现

标签 java mysql sql nosql

我需要使用三叉树结构,它必须存储在某个地方(我选择了关系数据库,但我仍然可以更改它)。

我的数据库树看起来像:

Tree example

例如,我的关系包含列 - Idchild1Idchild2Idchild3Idis_active

问题是我必须通过 boolean 参数提供 BFS 的能力。例如,在图片上应该可以找到 Node#35。 当然,我知道如何用java中的现成数据实现BFS,但是要做到这一点,我需要从数据库接收整个树。 是否可以通过 SQL 查询来完成? 或者也许任何人都可以提出比将其存储在关系数据库上更好的解决方案?

最佳答案

可能的解决方案之一是使用图形数据库而不是关系数据库,正如评论中所建议的那样。 但是,如果可以仅使用关系数据库,方法之一是向带有节点的表添加附加字段 - 深度position_in_layerdepth = 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/

相关文章:

java - 使用 jena 在 java 中构建维基百科查询表单

java "this"关键字正确使用

java - position() 函数给我带来了错误的数据

mysql - mysql中的列不明确?

php多表更改

java - 如何使用 ceylon 命令行工具构建 ceylon?

c++ - 如何使用 Boost 在 C++ 中通过上下文切换执行两个任务

Java网络编程

java - 从数据库中删除一行

mysql - SQL GROUPBY 和 SUM OF A COLUMN