标签: hierarchical-data

我有一个具有这种结构的MySQL数据库表:

table
    id INT NOT NULL PRIMARY KEY
    data ..
    next_id INT NULL

我需要按链表顺序获取数据.例如,给定这些数据:

 id | next_id
----+---------
  1 |       2
  2 |       4
  3 |       9
  4 |       3
  9 |    NULL

我需要按顺序获取id = 1,2,4,3,9的行.如何使用数据库查询执行此操作？(我可以在客户端完成.我很好奇是否可以在数据库端完成.因此,说这是不可能的(没有足够的证明)).

有一个终止点也是很好的(例如,在10次提取后停止,或者当行上的某些条件变为真时),但这不是必需的(可以在客户端完成).我(希望我)不需要检查循环引用.

我正在尝试使用PHP和SQLite表设置创建一个分层列表,如下所示:

    |   itemid  |   parentid    |   name    |
    -----------------------------------------
    |   1       |   null        |   Item1   |
    |   2       |   null        |   Item2   |
    |   3       |   1           |   Item3   |
    |   4       |   1           |   Item4   |
    |   5       |   2           |   Item5   |
    |   6       |   5           |   Item6   |

这些列表将使用无序列表构建,并允许这种类型的树结构:

Item1
    |_Item3
    |_Item4
Item2
    |_Item5
        |_Item6

我已经看到这对目录和平面数组完成了,但我似乎无法使其正常使用此结构并且没有深度限制.

我最难将列表(Of Folder)转换为层次结构.

Public Class Folder

Public Property FolderID() As Integer
Public Property Name() As String
Public Property ParentFolderID() As Integer
Public Property Children() as IEnumerable(Of Folder)

End Class

我需要返回填充了Children的List(Of Folder).

我从数据库中的数据构建一个List(Of Folder).

{1,"文件夹1",没有} {2,"文件夹2",1} {3,"文件夹3",2} {4,"文件夹4",3} {5,"文件夹5",没什么}

我无法弄清楚如何以递归方式将子文件夹移动到其父级的Children属性中.

我想用LINQ做这个.

任何帮助是极大的赞赏.

更新

谢谢你的回答,但不是那里.根据你的答案,我想出了几乎可行的.

Dim list = (From folder in folderList Select New Folder() With {
    .FolderID = folder.FolderID, 
    .Name = folder.Name, 
    .ParentFolderID = folder.ParentFolderID, 
    .Children = (From child in folderList 
                 Where child.ParentFolderID = item.FolderID).ToList()}).ToList()

{1, "Root", Nothing}
{2, "Child", 1}
{3, …

我有两个带有hierarchyid字段的表,其中一个是具有需要合并到另一个的新数据的临时表(即,需要添加到主树的一组节点,其中一些可能已经是那里).

除了定义树结构(父/子关系)的hierarchyid列之外.每个表都有一个单独的列,其中包含唯一标识每个节点的节点标识符.也就是说,判断登台表中的节点是否已经在主表中的方法是通过节点ID,而不是通过hierarchyid列.

当然,需要执行的处理看起来像这样:

For each row, RS, in the staging table:
    If there is not already a row with the same Id as RS in the main table:
         Find the parent, PS, of the staging row
         Find the row, PM, in the main table that has the same node ID as PS
         Create a new child, RM of row PM
         Set PM's ID equal to the ID of RS

重要的是,这种方法只有在登台表中的树以广度优先顺序排序/遍历时才有效 - 这样当遇到RS时,可以保证其父PS在主表中已经有相应的行.

到目前为止,我在SQL服务器中看到实现此目的的唯一方法是在登台表(已经排序)上使用游标,并为每一行调用一个存储过程,基本上完全按照上面描述的那样完成,并使用SELECT完成MAX()用于查找已作为PM的子项存在的最高hierarchyid,以便可以唯一地添加子项.

然而,这是一种非常低效的方法,并且对于我的目的来说太慢了.有没有更好的方法？

对于背景,这是我正在进行的一种可行性检查.我需要弄清楚我是否可以在SQL Server中快速执行此操作.如果事实证明我不能在数据库之外以另一种方式做到这一点.树的合并是固有的(实际上,在某种意义上一种是)的问题域,所以结构化数据不同或采取更广泛的看法,并试图以某种方式完全避免执行此操作是不是一种选择.

更新

根据要求,这是一个具体的例子. …

我的情况是,我目前正在SQL数据库中存储层次结构,该数据库快速接近15000个节点(5000个边缘).此层次结构根据树中的用户位置定义我的安全模型,授予对下面项目的访问权限.因此,当用户请求所有安全项目的列表时,我正在使用CTE将其递归到数据库中(并展平所有项目),这将开始显示其年龄(慢).

层次结构不经常更改,所以我试图将其移动到RAM(redis)中.请记住,我有许多需要这个安全调用的子系统,以及用于为CRUD操作构建树的UI.

第一次尝试

我的第一次尝试是将关系存储为键值对(这是它存储在数据库中的方式)

       E
     /   \
    F     G
   / \   /  \
  H  I  J    K

mapped to:
    E - [F, G]
    F - [H, I]
    G - [J, K]

因此,当我想要E及其所有的死者时,我递归地让它的孩子和他们的孩子使用钥匙,它允许我从任何节点开始向下移动.这个解决方案提供了很好的速度提升但是有15,000个节点,在代码中重建我的树大约有5000个缓存命中(更糟糕的情况......从E开始.性能基于起始节点位置,导致超级用户看到最糟糕的表现).这仍然很快,但似乎很健谈.我喜欢这样一个事实,即我可以通过将其从键列表中弹出而无需重建我的整个缓存来随时删除节点.这也可以快速点亮,在UI上直观地构建树.

第二次尝试

我的另一个想法是从数据库中获取层次结构,构建树并将其存储在RAM(redis)中,然后将整个内容拉出内存(大小约为2 MB,序列化).这给了我一个单独的调用(不是很健谈)到redis中拉出整个树,找到用户父节点,然后下降以获取所有子项.这些调用很频繁,在网络层传递2 MB似乎很大.这也意味着我无法轻松添加/删除和项目,而无需拉下树并编辑并将其全部推回.同时根据需要通过HTTP建立树木意味着每个请求必须下拉2MB才能获得直接子项(使用第一个解决方案非常小).

那么您认为哪种解决方案是更好的方法(长期因为它继续增长).两者都更加快速,并从数据库中减轻一些负担.或者他们是一个更好的方法来实现这一点,我没有想过？

谢谢

我正在敲打我的头,我想知道是否有人能够帮助我.

我的目标是创建一个评论线程,该评论线程在评论评分系统中起作用.

首先,我将解释我目前的情况.

假设我们在一篇文章中有一个评论主题,看起来像下面的例子.parenthasis中的数字是该注释的ID.ID由数据库自动分配,并按时间顺序递增,并发布每个附加注释.注释文本前的短划线数量会重新显示注释深度.

(01)"This is a top level comment." 
(02)-"This is a second level comment. A reply to the top level comment above."
(06)-"This is also a second level comment / another reply to comment 01."
(07)--"This is a reply to comment 06."
(03)"This is a different top level comment."
(05)-"This is a reply to the comment above."
(08)--"This is a reply to that comment in turn."
(10)---"This is a deeper comment still."
(04)"This is one more top level …

我在MySQL中有一个分层表:parent每个项的id字段指向其父项的字段.对于每个项目,我可以使用此处描述的查询获取所有父项的列表[无论深度] .随着GROUP_CONCAT我得到的完整路径作为一个字符串:

SELECT GROUP_CONCAT(_id SEPARATOR ' > ') FROM (
SELECT  @r AS _id,
         (
         SELECT  @r := parent
         FROM    t_hierarchy
         WHERE   id = _id
         ) AS parent,
         @l := @l + 1 AS lvl
 FROM    (
         SELECT  @r := 200,
                 @l := 0
         ) vars,
         t_hierarchy h
WHERE    @r <> 0
ORDER BY lvl DESC
) x

只有当id项目的内容得到修复时,我才能完成这项工作[ 200在这种情况下].

我想对所有行执行相同操作:使用一个额外的字段(path)检索整个表,该字段将显示完整路径.我想到的唯一解决方案是将此查询包装在另一个select中,设置一个临时变量@id并在子查询中使用它.但它不起作用.我进入NULL了 …

我有一个树层次结构,它将内置于一个表中,其中parent_id指向前一个根节点.

我正在遍历所有根节点(root1,root2),我正在为root1和child1设置root1或root1/child1的路径.为了找到child1的路径,我将至少进行2次调用以形成路径.是否有一种有效的方法来填充路径,因为我们处理的是非常大量的根节点和子节点,这些节点和子节点的深度为5-7级.

create table foo (id, name, parent_id, path)
insert into foo (1, "root1', null, null)
insert into foo (2, "child1', 1, null)

root1 (path = null)
  child1 (path = root1)
    subchild1 (path = root1/child1)

root2
   child2
     subchild2

这是我的第一个问题; 所以,请温柔.

我有一些数据形式:

library('networkD3')
    Relationships<- data.frame(Parent=c("earth","earth","forest","forest","ocean","ocean","ocean","ocean"),
                  Child=c("ocean","forest","tree","sasquatch","fish","seaweed","mantis shrimp","sea monster"))
> Relationships
  Parent         Child
1  earth         ocean
2  earth        forest
3 forest          tree
4 forest     sasquatch
5  ocean          fish
6  ocean       seaweed
7  ocean mantis shrimp
8  ocean   sea monster

本质上,这是一个可用于制作网络地图的边缘列表:

net <- graph_from_data_frame(d = Relationships,
                             directed = T)
plot(net)

我想将它转换为可以在diagonalNetwork下面的函数中使用的形式.

Hierarchical_list <- list(name = "earth",
                 children = list(list(name = "ocean",
                                      children = list(list(name = "mantis shrimp"),
                                                      list(name = "fish"),
                                                      list(name = "sea monster"),
                                                      list(name = "seaweed")
                                                      )),
                                 list(name …

我正在开展一个奖励人们推荐的项目(MLM)

我已经能够计算左侧和右侧的子节点总数,但现在我需要能够更新用户的等级,当他们有一定数量的用户时,他们两侧的某些等级低于他们.(我将在下面解释得更好:

用户表

 id | name  | parentID| side | rank   |
 4  | Dan   |         |      | starter|
 5  | Chris |   4     | left | starter|
 6  | James |   4     | right| starter|
 7  | Tybe  |   5     | left | starter|
 8  | Rose  |   5     | right| starter|
 9  | Paul  |   6     | left | starter|
10  | Zach  |   6     | right| starter|

树桌

userID | left | right| leftCount | rightCount|
 4 …