Mysql：优化查找嵌套集树中的超级节点

Question

我有一些层次结构的数据，采用嵌套集模型存储（表名：projects）：

我的表结构如下（表名：projects）：

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 | lft,rgt,lftRgt | idLftRgt | 12      | NULL |   10 | Using where; Using index | 
+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+

虽然Mysql知道要使用哪个索引，但仍需要循环遍历所有10行（或实际表中的100k行）。

我如何让MySql正确优化此查询？ 我在下面附上一个测试脚本。

DROP TABLE IF EXISTS projects; 
CREATE TABLE projects (
    id INT NOT NULL ,
    lft INT NOT NULL ,
    rgt INT NOT NULL ,
    PRIMARY KEY ( id )
) ENGINE = MYISAM ;
ALTER TABLE projects ADD INDEX lft (lft);
ALTER TABLE projects ADD INDEX rgt (rgt);
ALTER TABLE projects ADD INDEX lftRgt (lft, rgt);
ALTER TABLE projects ADD INDEX idLftRgt (id, lft, rgt);

INSERT INTO projects (id,lft,rgt) VALUES (1,1,6);
INSERT INTO projects (id,lft,rgt) VALUES (2,2,3);
INSERT INTO projects (id,lft,rgt) VALUES (3,4,5);
INSERT INTO projects (id,lft,rgt) VALUES (4,7,10);
INSERT INTO projects (id,lft,rgt) VALUES (5,8,9);
INSERT INTO projects (id,lft,rgt) VALUES (6,11,12);
INSERT INTO projects (id,lft,rgt) VALUES (7,13,14);
INSERT INTO projects (id,lft,rgt) VALUES (8,15,16);
INSERT INTO projects (id,lft,rgt) VALUES (9,17,18);
INSERT INTO projects (id,lft,rgt) VALUES (10,19,20);

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

- Joernsn

Answer 1

为了优化 MySQL 中的嵌套集查询，您应该在集合框上创建一个 SPATIAL (R-Tree)索引：

ALTER TABLE projects ADD sets LINESTRING;

UPDATE  projects
SET     sets = LineString(Point(-1, lft), Point(1, rgt));

ALTER TABLE projects MODIFY sets LINESTRING NOT NULL;

CREATE SPATIAL INDEX sx_projects_sets ON projects (sets);

SELECT  hp.*
FROM    projects hp
WHERE   MBRWithin(Point(0, 4), hp.sets)
ORDER BY
        lft;

详细内容请参见我的博客文章：

• 邻接表 vs 嵌套集：MySQL

- Quassnoi

---

你，我的朋友，是一个天才！你刚刚拯救了我们的数据库服务器，让它不再早日退役。当我们制作贡献名单（yast.com）时，你会被列入其中 :) - Joernsn

Answer 2

如果您无法使用空间索引，则可以使用这两个索引：

ALTER TABLE projects ADD INDEX lftRgt (lft, rgt);
ALTER TABLE projects ADD INDEX idLftRgt (id, lft, rgt);

应该是唯一的。这将极大地帮助数据库。

ALTER TABLE projects ADD INDEX lft (lft);

不必要 - 这是 lftRgt 的重复。

- Ariel

Answer 3

在尝试寻找嵌套集索引帮助时偶然发现了这个。

我最终采用了不同的解决方案，它很庞大，但可以轻松地完全索引化。但是，它会使更新变得更慢。然而，我将其发布在这里，因为它可能会帮助到其他人。

我们有一个产品类别表，可以有子类别等。这些数据相当静态。

我设置了一个表来缓存包含类别及其每个父类别（包括此特定类别）之间关系和深度差异的行。

当实际类别表进行更改时，我只需触发过程以重建缓存表。

然后，任何检查父/子关系的内容都可以使用缓存直接链接类别与其所有子项（或子项与其所有父项）。

实际类别表。

CREATE TABLE `category` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(128) NOT NULL,
  `depth` int(11) NOT NULL,
  `left_index` int(4) NOT NULL,
  `right_index` int(4) NOT NULL,
  `mmg_code` varchar(30) NOT NULL
  PRIMARY KEY (`id`),
  UNIQUE KEY `mmg_code` (`mmg_code`),
  UNIQUE KEY `left_index_right_index` (`left_index`,`right_index`),
  UNIQUE KEY `depth_left_index_right_index` (`depth`,`left_index`,`right_index`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;


DELIMITER ;;

CREATE TRIGGER `category_ai` AFTER INSERT ON `category` FOR EACH ROW
CALL `proc_rebuild_category_parents_cache`();;

CREATE TRIGGER `category_au` AFTER UPDATE ON `category` FOR EACH ROW
CALL `proc_rebuild_category_parents_cache`();;

DELIMITER ;

简单的缓存表：

CREATE TABLE `category_parents_cache` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `category_id` int(11) NOT NULL,
  `parent_category_id` int(11) NOT NULL,
  `depth_difference` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `category_id` (`category_id`),
  KEY `parent_category_id` (`parent_category_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

步骤如下：

BEGIN
    TRUNCATE category_parents_cache;

    INSERT INTO category_parents_cache (id, category_id, parent_category_id, depth_difference)
    SELECT NULL, 
            child_category.id AS category_id, 
            category.id AS parent_category_id, 
            child_category.depth - category.depth AS depth_difference 
    FROM category
    INNER JOIN category child_category ON child_category.left_index BETWEEN category.left_index AND category.right_index
    ORDER BY category.id, child_category.id;
END

如果表格很大且经常更新，这可能会有所改善。

- Kickstart