MySQL的：優化找到嵌套集樹超級節點

Question

我有一個嵌套集模型分層數據（表：項目）：

我的表（項目）：

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 

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; 

請參閱本文中我的博客更多的細節：

• Adjacency list vs. nested sets: MySQL

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的副本。

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 

這或許可以，如果表很大，一般更新被有效改善。