标签: hierarchical-data

好的概述

一般来说,您要在快速读取时间(例如,嵌套集)或快速写入时间(邻接列表)之间做出决定.通常,您最终会得到最适合您需求的以下选项组合.以下提供了一些深入阅读:

• 还有一个嵌套间隔与邻接列表比较:我发现的邻接列表,物化路径,嵌套集和嵌套间隔的最佳比较.
• 分层数据的模型:幻灯片,有很好的权衡解释和示例用法
• 代表MySQL中的层次结构:特别是对嵌套集的非常好的概述
• RDBMS中的分层数据:我见过的最全面,组织良好的链接集,但解释方式不多

选项

我知道和一般的功能:

1. 邻接清单:
   • 列:ID,ParentID
   • 易于实施.
   • 便宜节点移动,插入和删除.
   • 昂贵的找到水平,血统和后代,路径
   • 在支持它们的数据库中通过公用表表达式避免使用N + 1
2. 嵌套集(又名修改的预订树遍历)
   • 列:左,右
   • 便宜的血统,后代
   • 非常昂贵的O(n/2)移动,插入,由于易失性编码而删除
3. 桥表(又名闭包表/ w触发器)
   • 使用单独的连接表:祖先,后代,深度(可选)
   • 廉价的血统和后代
   • 写入O(log n)插入,更新,删除的成本(子树的大小)
   • 规范化编码:适用于连接中的RDBMS统计信息和查询规划器
   • 每个节点需要多行
4. 谱系列(又名物化路径,路径枚举)
   • 专栏:血统(例如/父母/孩子/孙子/等......)
   • 廉价后代通过前缀查询(例如LEFT(lineage, #) = '/enumerated/path')
   • 写入O(log n)插入,更新,删除的成本(子树的大小)
   • 非关系型:依赖于Array数据类型或序列化字符串格式
5. 嵌套间隔
   • 像嵌套集一样,但是使用实数/浮点数/小数,这样编码就不易变(廉价的移动/插入/删除)
   • 有实/浮/十进制表示/精度问题
   • 矩阵编码变体为"自由"添加了祖先编码(物化路径),但增加了线性代数的诡计.
6. 平表
   • 修改的Adjacency List,为每条记录添加Level和Rank(例如排序)列.
   • 便宜迭代/分页
   • 昂贵的移动和删除
   • 好用:线程讨论 - 论坛/博客评论
7. 多个谱系列
   • 列:每个谱系级别一个,指向根目录的所有父级,从项目级别向下的级别设置为NULL
   • 便宜的祖先,后代,水平
   • 便宜的插入,删除,移动的叶子 …

假设您有一个存储有序树层次结构的平面表:

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(或文本,就此而言)作为正确排序,正确缩进的树？

进一步假设你只有基本的数据结构(数组和散列图),没有带有父/子引用的花哨对象,没有ORM,没有框架,只有你的双手.该表表示为结果集,可以随机访问.

伪代码或普通英语是可以的,这纯粹是一个概念性的问题.

额外问题:在RDBMS中存储这样的树结构是否有根本更好的方法？

编辑和补充

回答一个评论者(Mark Bessey的)问题:根节点不是必需的,因为它永远不会被显示.ParentId = 0是表示"这些是顶级"的惯例.Order列定义了如何对具有相同父节点的节点进行排序.

我所谈到的"结果集"可以被描绘成一组哈希图(保留在该术语中).因为我的例子意味着已经存在.有些答案会加倍努力并首先构建它,但那没关系.

树可以任意深.每个节点可以有N个子节点.不过,我并没有考虑到"数百万条目".

不要将我选择的节点命名('Node 1.1.1')误认为是依赖的东西.节点同样可以称为"Frank"或"Bob",不暗示命名结构,这只是为了使其可读. …

我有一个MySQL表,如下所示:

id | name        | parent_id
19 | category1   | 0
20 | category2   | 19
21 | category3   | 20
22 | category4   | 21
......

现在,我想要一个MySQL查询,我只提供id [例如说'id = 19']然后我应该得到它的所有子id [即结果应该有id',21,22']. ...而且,孩子们的等级不知道它可以变化....

另外,我已经有了使用for循环的解决方案.....如果可能的话,让我知道如何使用单个MySQL查询来实现相同的功能.

在SQL Server中执行递归自联接的最简单方法是什么？我有这样一张桌子:

PersonID | Initials | ParentID
1          CJ         NULL
2          EB         1
3          MB         1
4          SW         2
5          YT         NULL
6          IS         5

而且我希望能够获得仅与特定人员开始的层次结构相关的记录.所以,如果我通过PersonID = 1请求CJ的层次结构,我会得到:

PersonID | Initials | ParentID
1          CJ         NULL
2          EB         1
3          MB         1
4          SW         2

对于EB,我会得到:

PersonID | Initials | ParentID
2          EB         1
4          SW         2

我有点卡住这个可以想不出怎么做除了基于一堆连接的固定深度响应.这会发生,因为我们不会有很多级别,但我想做得恰到好处.

谢谢!克里斯.

什么类型的NoSQL数据库最适合存储分层数据？

比方说,我想存储具有树结构的论坛的帖子:

original post
 + re: original post
 + re: original post
   + re2: original post
     + re3: original post
   + re2: original post

我认为答案是否定的,但是我很喜欢它,任何人都可以深入了解如何在SQL(MySQL)中将树结构爬行到任何深度,但只需一个查询

更具体地说,给定树结构表(id,data,data,parent_id)和表中的一行,是否可以获得所有后代(子/孙/等),或者就此而言所有祖先(父/祖父母)/etc)使用单个查询而不知道它将向下或向上移动多远？

或者正在使用某种递归需求,我不断深入查询,直到没有新的结果？

具体来说,我正在使用Ruby和Rails,但我猜这不是很相关.

我正在评估Backbone javascript框架,用于在树视图小部件中显示分层模型的项目(想想Windows文件浏览器).

我喜欢 Backbone对世界的看法.然而,在我获得概念验证之前,涉及到许多编码,其中Backbone实际上从服务器接收分层模型并更新树窗口小部件.我已经看到用Backbone表示深度数据结构的各种解决方案,但我想知道......有没有人真正做过这个？

只知道它可能会有所帮助.实际上,命名树视图UI组件和指针使Backbone中的数据分层将更好.一些示例代码将非常棒.

就数据大小而言,树将运行100个节点(文件夹),其中包含1000个叶子项(文档),并且逐渐加载数据(例如,用户点击时一次一个文件夹)会很好,虽然这可能不是一个表明.

谢谢!

我将使用许多类似的项目(数百万)创建一个应用程序,我想将它们存储在MySQL数据库中,因为我想做大量的统计信息并搜索特定列的特定值.

但与此同时,我将存储所有项目之间的关系,这些项目在许多连接的二叉树结构(传递闭包)中相关,而关系数据库并不擅长这种结构,所以我想存储Neo4j中的所有关系都具有良好的性能.

我的计划是将所有数据除了MySQL数据库中的关系以及item_id存储在Neo4j数据库中的所有关系.当我想查找树时,我首先在Neo4j中搜索树中的所有item_id:s,然后在MySQL数据库中搜索查询中的所有指定项,如下所示:

SELECT * FROM items WHERE item_id = 45 OR item_id = 345435 OR item_id = 343 OR item_id = 78 OR item_id = 4522 OR item_id = 676 OR item_id = 443 OR item_id = 4255 OR item_id = 4345

这是个好主意,还是我错了？我之前没有使用过图形数据库.有没有更好的方法解决我的问题？在这种情况下,MySQL查询将如何执行？

我正在编写一个由Tree和TreeNode组合而成的数据树结构.树将包含数据的根和顶级操作.我正在使用UI库以窗体形式呈现树,我可以将树绑定到TreeView.

我需要在DB中保存这个树和节点.保存树并获得以下功能的最佳方法是什么:

1. 直观的实施.
2. 轻松绑定.很容易从树移动到DB结构并返回(如果有的话)

我有两个想法.第一种是将数据序列化为表格中的单行.第二种是保存在表中,但是当移动到数据实体时,我将在更改的节点上松开表上的行状态.

有任何想法吗？

我有一些分层数据,最终到时间序列数据,看起来像这样:

df = pandas.DataFrame(
    {'value_a': values_a, 'value_b': values_b},
    index=[states, cities, dates])
df.index.names = ['State', 'City', 'Date']
df

                               value_a  value_b
State   City       Date                        
Georgia Atlanta    2012-01-01        0       10
                   2012-01-02        1       11
                   2012-01-03        2       12
                   2012-01-04        3       13
        Savanna    2012-01-01        4       14
                   2012-01-02        5       15
                   2012-01-03        6       16
                   2012-01-04        7       17
Alabama Mobile     2012-01-01        8       18
                   2012-01-02        9       19
                   2012-01-03       10       20
                   2012-01-04       11       21
        Montgomery 2012-01-01       12       22
                   2012-01-02       13       23
                   2012-01-03       14       24
                   2012-01-04       15       25

我想对每个城市进行时间重新采样,所以就像这样

df.resample("2D", how="sum")

会输出 …