标签: nested-sets

我一直在考虑修改前序树遍历算法,用于在平面表(例如SQL)中存储树.

我不喜欢标准方法的一个属性是插入一个节点,你必须触摸(平均)N/2个节点(左边或右边高于插入点的所有东西).

我见过的实现依赖于顺序编号的值.这没有留下更新的余地.

这对于并发和扩展似乎很糟糕.想象一下,你有一棵植根于世界的树,它包含大型系统中每个帐户的用户组,它非常大,你必须将树的子集存储在不同的服务器上.触摸所有节点的一半以将节点添加到树的底部是不好的.

这是我正在考虑的想法.基本上通过划分键空间并在每个级别划分来为插入留出空间.

这是N _max = 64 的示例(这通常是数据库的MAX_INT)

                     0:64
              ________|________
             /                 \
         1:31                   32:63
        /    \                 /     \
    2:14    15-30         33:47       48:62

这里,节点被添加到树的左半部分.

                     0:64  
              ________|________
             /                 \
         1:31                  32:63
      /   |   \               /     \
  2:11  11:20  21:30     33:47       48:62

必须扩展alogorithm以进行插入和删除过程,以递归重新编号为子树的左/右索引.由于查询节点的直接子节点很复杂,我认为将父节点ID存储在表中也是有意义的.然后,算法可以选择子树(使用left> p.left && right <p.right),然后使用node.id和node.parent来处理列表,细分索引.

这比仅增加所有索引以便为插入腾出空间(或递减删除)更复杂,但它有可能影响更少的节点(仅插入/删除节点的父节点的后果).

我的问题基本上是:

1. 这个想法是否已正式化或实施？

2. 这与嵌套间隔相同吗？

我在嵌套集模型中有分层数据(表:项目):

我的表(项目):

id, lft, rgt
1, 1, 6
2, 2, 3
3, 4, 5
4, 7, 10
5, 8, 9
6, 11, 12
7, 13, 14
...

漂亮印刷:

 1
  2
  3
 4
  5
 6
 7

为了找到最近的节点3的超节点(知道它的lft值),我能做到

explain
SELECT projects.*
FROM projects
WHERE 4 BETWEEN projects.lft AND projects.rgt

这给了我一个到节点3的路径中的项目列表.然后通过分组并找到结果的MAX(projects.lft),我得到最近的超级节点.但是,我似乎无法让这个查询快速运行,它不会使用我已经定义的索引.EXPLAIN说:

+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+
| id | select_type | table    | type  | possible_keys  | key      | key_len | ref  | rows | Extra                    |
+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+
|  1 | SIMPLE      | projects | index | …

基于将修改后的预订树遍历模型(嵌套集)转换为<ul>

其中一个答案给出了正确的代码来显示完整的树.我需要的是始终显示第一级(深度= 0)和兄弟姐妹+孩子的活动列表项.目标是当用户选择列表项时扩展树的可见部分,该列表项是更多列表项的父项.

所以,如果我有这个清单:

1. item
2. item
  2.1. item
  2.2. item
    2.2.1. item
    2.2.2. item
    2.2.3. item
  2.3. item
  2.4. item
    2.4.1. item
    2.4.2. item
3. item
4. item
  4.1. item
  4.2. item
    4.2.1. item
    4.2.2. item
5. item

如果当前列表项为"2",则列表应如下所示:

1. item
2. item // this needs class .selected
  2.1. item
  2.2. item
  2.3. item
  2.4. item
3. item
4. item
5. item

如果当前列表项是"2.2.",列表应如下所示:

1. item
2. item // this needs class .selected
  2.1. item
  2.2. item // …

我正在使用awesome_nested_set我的Rails项目中的插件.我有两个看起来像这样的模型(简化):

class Customer < ActiveRecord::Base
  has_many :categories
end

class Category < ActiveRecord::Base
  belongs_to :customer

  # Columns in the categories table: lft, rgt and parent_id
  acts_as_nested_set :scope => :customer_id

  validates_presence_of :name
  # Further validations...
end

数据库中的树按预期构造.的所有值parent_id,lft以及rgt是否正确.树有多个根节点(当然允许进入awesome_nested_set).

现在,我想在一个正确排序的树中呈现给定客户的所有类别,例如结构:例如嵌套<ul>标签.这不会太难,但我需要它才能有效(sql查询越少越好).

更新:想出可以在没有进一步SQL查询的情况下计算树中任何给定节点的子节点数:number_of_children = (node.rgt - node.lft - 1)/2.这并不能解决问题,但可能会有所帮助.

我有一张桌子,其中包含世界上所有地理位置的位置及其关系.

以下是显示层次结构的示例.您将看到数据实际存储为全部三个

• 枚举路径
• 邻接清单
• 嵌套集

数据显然也从未改变过.下面是英格兰布莱顿位置的直接祖先的例子,其中有一个13911的寂寞.

表:( geoplanet_places有560万行) 大图:http://tinyurl.com/68q4ndx

然后,我有一个名为的表entities.此表存储我想要映射到地理位置的项目.我存储了一些基本信息,但最重要的是我存储了woeid哪个是外键geoplanet_places.

最终该entities表将包含数千个实体.我想要一种能够返回包含实体的所有节点的完整树的方法.

我计划创建一些东西,以便根据实体的地理位置过滤和搜索实体,并能够发现在该特定节点上可以找到多少个实体.

所以如果我的表中只有一个实体entities,我可能会有这样的东西

`地球(1)

英国(1)

英格兰(1)

东萨塞克斯郡(1)

布莱顿 - 霍夫市(1)

布莱顿(1)`

让我们说我有另一个位于德文郡的实体,那么它会显示如下:

地球(2)

联合王国(2)

英格兰(2)

德文(1)

东萨塞克斯(1)......等

(计数)将说明每个地理位置"内部"有多少实体不需要是活的.我可以忍受每小时生成我的对象并缓存它.

目标是,能够创建一个界面,可能开始只显示有实体的国家.

所以喜欢

Argentina (1021),Chile (291),...,United States (32,103),United Kingdom (12,338)

然后,用户将点击某个位置,例如United Kindom,然后将获得作为英国后代的所有直接子节点,并且其中包含实体.

如果United Kindgdom中有32个县,但最终只有23个当你向下钻取时存储了实体,那么我不想显示其他9.它只是位置.

本网站恰如其分地表明,我希望实现的功能: http://www.homeaway.com/vacation-rentals/europe/r5

您如何建议我管理这样的数据结构？

我正在使用的东西.

• PHP
• MySQL的
• Solr的

我计划尽可能快地完成钻孔.我想创建一个无缝的AJAX界面进行搜索.

我也有兴趣知道你建议索引哪些列.

正在开发一个正在开发的电子商务应用程序我试图解决以下问题:我通过awesome_nested_set插件实现了我的类别.如果我通过选择一个类别列出我的文章一切正常,但对于某些链接,我想显示一个类别的所有产品和其子类别的产品.

这里是控制器代码只适用于一个类别:

   # products_controller.rb
   def index
    if params[:category]
      @category = Category.find(params[:category])
      #@products = @category.product_list
      @products = @category.products
    else
      @category = false
      @products = Product.scoped
    end
    @products = @products.where("title like ?", "%" + params[:title] + "%") if params[:title]
    @products = @products.order("created_at).page(params[:page]).per( params[:per_page] ? params[:per_page] : 25)
    @categories = Category.all
  end

我注释掉的一行是我在类别模型中自己编写的辅助方法,它返回类别中所有产品及其子类别的数组.

它的定义如下:

# app/models/category.rb
def product_list
  self_and_ancestors.to_a.collect! { |x| x.products }
end

现在当我取消注释这一行并尝试选择一个类别时,我的产品控制器代码会出现错误,例如

undefined method `order' for #<Array:0x1887c2c>

要么

undefined method `page' for #<Array:0x1887c2c>

因为我正在使用订购和分页,它不能再订购.

有什么想法如何在我的控制器中的ActiveRecord Relation元素中获取所有产品？谢谢

UPDATE

所以,当我使用以下内容时:

class Category …

我想做铁饼/ reddit /喜欢评论系统,我的评论数据库中有一个"id_answer"(由defaut设置为0)字段,当用户回答另一个评论时,该字段是父评论的"id".

我有一个数组中的线程的注释,但我不知道如何过滤每个循环过滤器得到这样的东西:

comment lvl 1($ array [id_answer]为0)

-------评论lvl 2($ array [id_answer]是id_of_level_one_comment)

---------------评论lvl 3 ...

我正在为我的CMS使用嵌套集,但是从MySQL 5.5起我无法移动节点.
抛出以下错误:

重新排序文档时出错:MySQL-DB出错:SQL无效:

 SELECT baum2.id AS id,
 COUNT(*) AS level
 FROM elisabeth_tree AS baum1,
 elisabeth_tree AS baum2
 WHERE baum2.lft BETWEEN baum1.lft AND baum1.rgt
 GROUP BY baum2.lft
 ORDER BY ABS(baum2.id - 6);

错误:BIGINT UNSIGNED值超出范围在'( ..lektoren - 6)' 的错误编号:1690baum2id

有没有人解决过这个问题？我已经尝试过铸造一些零件但是没有成功.

我有一个分层数据.最常见的查询将是"获取节点的父分支"和"获取节点的子树".更新和插入不太可能经常发生.我在嵌套集和hierarchyid之间进行选择.就我而言,在索引列上搜索嵌套集应该非常快,但是,我不了解hierarchyid的内部实现.为了获得最高性能,我应该使用什么？

我正在处理分层数据，如树结构。我想知道将它们存储在数据库中的最佳方式是什么。

我从 MySQL 中的邻接表开始。但随着数据的增加，性能似乎会下降。我有大约 20,000 行存储在具有父子关系的 MySQL 表中，并且将来还会增加。获取数据需要很长时间，因为我必须根据树的深度编写许多自连接。

所以我正在寻找存储此类数据的最佳方法。在一次地方，我发现嵌套集比邻接列表更好。然后我被建议考虑 NoSQL，如果这能解决我的问题。所以我现在很困惑是继续使用 SQL 还是进入 No SQL，或者是否有其他最好的方法来处理此类数据。

那么有人可以建议我什么是最好的方法吗？