- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
假设您有一个存储有序树层次结构的平面表:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 20
4 'Node 1.1.1' 2 10
5 'Node 2.1' 3 10
6 'Node 1.2' 1 20
这是一个图表,其中我们有[id] Name
。根节点 0 是虚构的。
[0] ROOT / \ [1] Node 1 [3] Node 2 / \ \ [2] Node 1.1 [6] Node 1.2 [5] Node 2.1 / [4] Node 1.1.1
您将使用哪种简约方法将其作为正确排序、正确缩进的树输出到 HTML(或文本,就此而言)?
进一步假设您只有基本的数据结构(数组和 HashMap ),没有带有父/子引用的奇特对象,没有 ORM,没有框架,只有您的两只手。该表表示为一个结果集,可以随机访问。
伪代码或者简单的英文都行,这纯粹是个概念题。
红利问题:有没有更好的方法来在 RDBMS 中存储这样的树结构?
编辑和添加
回答一位评论者(Mark Bessey 的)问题:根节点不是必需的,因为它永远不会显示。 ParentId = 0 是表达“这些是顶级”的约定。 Order 列定义了如何对具有相同父节点的节点进行排序。
我所说的“结果集”可以被描绘成 HashMap 数组(保留在该术语中)。因为我的例子本来就已经存在了。有些答案更进一步并首先构建它,但这没关系。
树可以任意深。每个节点可以有 N 个 child 。不过,我并没有完全想到“数百万条目”树。
不要将我选择的节点命名(“节点 1.1.1”)误认为是可以依赖的东西。这些节点同样可以称为“Frank”或“Bob”,没有暗示命名结构,这只是为了使其可读。
我已经发布了我自己的解决方案,所以你们可以把它分解成碎片。
最佳答案
现在MySQL 8.0 supports recursive queries ,我们可以说 all popular SQL databases support recursive queries在标准语法中。
WITH RECURSIVE MyTree AS (
SELECT * FROM MyTable WHERE ParentId IS NULL
UNION ALL
SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;
我在演示文稿中测试了 MySQL 8.0 中的递归查询 Recursive Query Throwdown 2017 年。
以下是我 2008 年的原始回答:
有几种方法可以在关系数据库中存储树结构数据。您在示例中显示的内容使用两种方法:
另一种解决方案称为嵌套集,它也可以存储在同一个表中。阅读 Joe Celko 的“Trees and Hierarchies in SQL for Smarties”,了解有关这些设计的更多信息。
我通常更喜欢一种称为闭包表(又名“邻接关系”)的设计来存储树结构数据。它需要另一个表,但是查询树非常容易。
我在演示文稿中介绍了闭包表 Models for Hierarchical Data with SQL and PHP在我的书中 SQL Antipatterns Volume 1: Avoiding the Pitfalls of Database Programming .
CREATE TABLE ClosureTable (
ancestor_id INT NOT NULL REFERENCES FlatTable(id),
descendant_id INT NOT NULL REFERENCES FlatTable(id),
PRIMARY KEY (ancestor_id, descendant_id)
);
将所有路径存储在闭包表中,其中存在从一个节点到另一个节点的直接祖先。为每个节点包含一行以引用自身。例如,使用您在问题中显示的数据集:
INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
(1,1), (1,2), (1,4), (1,6),
(2,2), (2,4),
(3,3), (3,5),
(4,4),
(5,5),
(6,6);
现在你可以像这样得到一棵从节点 1 开始的树:
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;
输出(在 MySQL 客户端中)如下所示:
+----+
| id |
+----+
| 1 |
| 2 |
| 4 |
| 6 |
+----+
换句话说,节点 3 和 5 被排除在外,因为它们是单独层次结构的一部分,而不是从节点 1 下降。
回复:来自 e-satis 关于直系子女(或直系 parent )的评论。您可以向 ClosureTable
添加“path_length
”列,以便更轻松地专门查询直系子级或父级(或任何其他距离)。
INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
(1,1,0), (1,2,1), (1,4,2), (1,6,1),
(2,2,0), (2,4,1),
(3,3,0), (3,5,1),
(4,4,0),
(5,5,0),
(6,6,0);
然后您可以在搜索中添加一个术语以查询给定节点的直接子节点。这些是 path_length
为 1 的后代。
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
AND path_length = 1;
+----+
| id |
+----+
| 2 |
| 6 |
+----+
来自@ashraf 的评论:“[按名称] 对整棵树进行排序怎么样?”
这是一个示例查询,用于返回节点 1 的所有后代节点,将它们连接到包含其他节点属性(例如 name
)的 FlatTable,并按名称排序。
SELECT f.name
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;
来自@Nate 的评论:
SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id)
WHERE a.ancestor_id = 1
GROUP BY a.descendant_id
ORDER BY f.name
+------------+-------------+
| name | breadcrumbs |
+------------+-------------+
| Node 1 | 1 |
| Node 1.1 | 1,2 |
| Node 1.1.1 | 1,2,4 |
| Node 1.2 | 1,6 |
+------------+-------------+
今天有用户建议修改。所以版主批准了编辑,但我正在撤销它。
编辑建议上面最后一个查询中的 ORDER BY 应该是 ORDER BY b.path_length, f.name
,大概是为了确保顺序与层次结构匹配。但这不起作用,因为它会在“节点 1.2”之后排序“节点 1.1.1”。
如果您希望排序以合理的方式匹配层次结构,那是可能的,但不能简单地按路径长度排序。例如,请参阅我对 MySQL Closure Table hierarchical database - How to pull information out in the correct order 的回答.
关于sql - 将平面表解析为树的最有效/优雅的方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48369346/
我一直在使用 AJAX 从我正在创建的网络服务中解析 JSON 数组时遇到问题。我的前端是一个简单的 ajax 和 jquery 组合,用于显示从我正在创建的网络服务返回的结果。 尽管知道我的数据库查
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
我在尝试运行 Android 应用程序时遇到问题并收到以下错误 java.lang.NoClassDefFoundError: com.parse.Parse 当我尝试运行该应用时。 最佳答案 在这
有什么办法可以防止etree在解析HTML内容时解析HTML实体吗? html = etree.HTML('&') html.find('.//body').text 这给了我 '&' 但我想
我有一个有点疯狂的例子,但对于那些 JavaScript 函数作用域专家来说,它看起来是一个很好的练习: (function (global) { // our module number one
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗?通过 editing this post 添加详细信息并澄清问题. 已关闭 8 年前。 Improve th
我需要编写一个脚本来获取链接并解析链接页面的 HTML 以提取标题和其他一些数据,例如可能是简短的描述,就像您链接到 Facebook 上的内容一样。 当用户向站点添加链接时将调用它,因此在客户端启动
在 VS Code 中本地开发时,包解析为 C:/Users//AppData/Local/Microsoft/TypeScript/3.5/node_modules/@types//index而不是
我在将 json 从 php 解析为 javascript 时遇到问题 这是我的示例代码: //function MethodAjax = function (wsFile, param) {
我在将 json 从 php 解析为 javascript 时遇到问题 这是我的示例代码: //function MethodAjax = function (wsFile, param) {
我被赋予了将一种语言“翻译”成另一种语言的工作。对于使用正则表达式的简单逐行方法来说,源代码过于灵活(复杂)。我在哪里可以了解更多关于词法分析和解析器的信息? 最佳答案 如果你想对这个主题产生“情绪化
您好,我在解析此文本时遇到问题 { { { {[system1];1;1;0.612509325}; {[system2];1;
我正在为 adobe after effects 在 extendscript 中编写一些代码,最终变成了 javascript。 我有一个数组,我想只搜索单词“assemble”并返回整个 jc3_
我有这段代码: $(document).ready(function() { // }); 问题:FB_RequireFeatures block 外部的代码先于其内部的代码执行。因此 who
背景: netcore项目中有些服务是在通过中间件来通信的,比如orleans组件。它里面服务和客户端会指定网关和端口,我们只需要开放客户端给外界,服务端关闭端口。相当于去掉host,这样省掉了些
1.首先贴上我试验成功的代码 复制代码 代码如下: protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec)
什么是 XML? XML 指可扩展标记语言(eXtensible Markup Language),标准通用标记语言的子集,是一种用于标记电子文件使其具有结构性的标记语言。 你可以通过本站学习 X
【PHP代码】 复制代码 代码如下: $stmt = mssql_init('P__Global_Test', $conn) or die("initialize sto
在SQL查询分析器执行以下代码就可以了。 复制代码代码如下: declare @t varchar(255),@c varchar(255) declare table_cursor curs
前言 最近练习了一些前端算法题,现在做个总结,以下题目都是个人写法,并不是标准答案,如有错误欢迎指出,有对某道题有新的想法的友友也可以在评论区发表想法,互相学习🤭 题目 题目一: 二维数组中的
我是一名优秀的程序员,十分优秀!