代码之家 › 专栏 › 技术社区 › Daniel Vandersluis

搜索嵌套集

nested-sets search algorithm mysql

Daniel Vandersluis · 技术社区 · 15 年前

我有一个mysql表,它就像一个嵌套集,以包含一个类别层次结构。表架构如下:

CREATE TABLE IF NOT EXISTS `categories` (
  `id` int(11) NOT NULL auto_increment,
  `name` varchar(200) NOT NULL,
  `parent_id` int(11) default NULL,
  `lft` int(11) default NULL,
  `rgt` int(11) default NULL,
  PRIMARY KEY  (`id`),
  UNIQUE KEY `index_categories_on_parent_id_and_name` (`parent_id`,`name`)
)

lft 和 rgt 定义节点的左边界和右边界(嵌套集的工作方式是每个节点的ID都在其父节点的边界内),以及 parent_id 指定父节点。唯一索引允许有多个具有相同名称的类别,只要它们没有相同的父类别。

我正试图找到一种基于层次结构的在集合中查找特定节点的正确方法。例如,如果我查找foo/bar/baz,我想检索名为baz的节点,其父节点名为bar,其父节点名为foo。显然,我不能只按名称搜索,因为可能有多个类别具有相同的名称。

我认为这样做的方法是找到最前面的类别,然后找到具有给定名称的每个后续类别,其父ID是以前找到的类别的父ID,但这对我来说似乎不是很有效。有没有更好的方法来搜索嵌套集?

3 回复 | 直到 15 年前

Michael 15 年前

我不相信有一种完全干净和有效的方法可以用嵌套集来实现这一点。将节点的祖先列表存储在非规范化列中可以有效地提供这一点,但我不建议实现它。

不过,还有一个不错的方法,即1个查询,可以方便地访问已有的索引。对于目标节点的每个深度级别,您将看到一个连接。

例如foo bar baz


   
    选择C3**
    

    来自类别C1
    

    c2.parent_id=c1.id和c2.name='bar'上的内部联接类别c2
    

    c3.parent_id=c2.id和c2.name='baz'上的内部联接类别c3
    

    其中c1.name='foo'
    

   
   
   
   
   
   
    它不是最好的,但它可能是你最好的选择,除非你想去努力存储一堆非规范化的信息。在代码中生成SQL也是相当直接的。

A. I. Breveleri 15 年前

TopVar = 'foo'
MidVar = 'bar'
BotVar = 'baz'

SELECT D0.*
FROM categories D0, categories D1, categories D2
WHERE D0.name = :BotVar
  AND D0.lft > D1.lft
  AND D0.rgt < D1.rgt
  AND D1.name = :MidVar
  AND D1.lft > D2.lft
  AND D1.rgt < D2.rgt
  AND D2.name = :TopVar;

- Al。

jessehanson1981 15 年前

我以前在一个交付给我的PHP项目中看到过,呃,这很糟糕。如果可以,请将其分为至少2个表;类别至少有1个表,项目至少有1个表,这样您就可以加入。不管怎样,恐怕你都需要多问几句

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前