MySQL多層級結(jié)構(gòu)-樹搜索介紹

更新時間：2016年07月08日 21:44:10 投稿：mdxy-dxy

這篇文章主要介紹了MySQL多層級結(jié)構(gòu)-樹搜索,需要的朋友可以參考下

基本上在每個系統(tǒng)中都有那么幾張表是自關聯(lián)父子關系的結(jié)構(gòu)。往往有很多人都是使用pid來做關聯(lián)。在剛進入IT行業(yè)時使用CAKEPHP框架編寫WEB的時候，使用它里面的一個ACL plugin實現(xiàn)權(quán)限管理的時候。發(fā)現(xiàn)一個表結(jié)構(gòu)硬是不明白是怎么回事。具體表結(jié)構(gòu)如下：

CREATE TABLE acos (
 id INTEGER(10) UNSIGNED NOT NULL AUTO_INCREMENT,
 parent_id INTEGER(10) DEFAULT NULL,
 model VARCHAR(255) DEFAULT '',
 foreign_key INTEGER(10) UNSIGNED DEFAULT NULL,
 alias VARCHAR(255) DEFAULT '',
 lft INTEGER(10) DEFAULT NULL,
 rght INTEGER(10) DEFAULT NULL,
 PRIMARY KEY (id)
);

我們可以看到上面 acos 表用有l(wèi)ft、rght這兩個字段。起初我根本就不明白這兩個是做什么用的，幾次直接修改數(shù)據(jù)導致數(shù)據(jù)錯亂。

1.2. 原理解釋

其實這就是樹的后續(xù)遍歷的每個節(jié)點的左值、右值。如下圖表示:

1.3. 樹的使用（引用上圖樹結(jié)構(gòu)）

構(gòu)造數(shù)據(jù)

DROP TABLE IF EXISTS comment;
CREATE TABLE `comment` (
 `comment_id` int(11) DEFAULT NULL,
 `left_num` int(11) DEFAULT NULL,
 `right_num` int(11) DEFAULT NULL
);

INSERT INTO `comment` VALUES 
 (1,1,14),
 (2,2,5),
 (3,3,4),
 (4,6,13),
 (5,7,8),
 (6,9,12),
 (7,10,11);
 
CREATE INDEX idx$comment$left_num$right_num ON `comment` (`left_num`, `right_num`);

查找 '節(jié)點4' 的所有子節(jié)點

思路:我們只要查找出節(jié)點左值在 '節(jié)點4' 左值和右值之間的節(jié)點
通俗說法:能被 '節(jié)點4' 包住的節(jié)點,通過左節(jié)點和右節(jié)點來判斷是否被 '節(jié)點4' 包住。

-- 獲得 '節(jié)點4' 孩子
SELECT c.*
FROM comment AS p, comment AS c
WHERE c.left_num BETWEEN p.left_num AND p.right_num
 AND p.comment_id = 4;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     4 |    6 |    13 |
|     5 |    7 |     8 |
|     6 |    9 |    12 |
|     7 |    10 |    11 |
+------------+----------+-----------+

查找 '節(jié)點6' 的所有父節(jié)點
思路: 找出左值小于 '節(jié)點6' 并且右值大于 '節(jié)點6' 的節(jié)點。
通俗說法: 找出那個節(jié)點能將 '節(jié)點6' 給包住。

-- 獲得 '節(jié)點6' 父親
SELECT p.* 
FROM comment AS p, comment AS c
WHERE c.left_num BETWEEN p.left_num AND p.right_num
 AND c.comment_id = 6;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     1 |    1 |    14 |
|     4 |    6 |    13 |
|     6 |    9 |    12 |
+------------+----------+-----------+

計算 '節(jié)點4' 的深度
如果是MySQL5.7 需要修改sql_mode

SET SESSION sql_mode = 'STRICT_TRANS_TABLES,NO_ZERO_IN_DATE,NO_ZERO_DATE,ERROR_FOR_DIVISION_BY_ZERO,NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION';
SELECT c.*,
 COUNT(c.comment_id) AS depth
FROM comment AS p, comment AS c
WHERE c.left_num BETWEEN p.left_num AND p.right_num
 AND c.comment_id = 4
GROUP BY c.comment_id;
+------------+----------+-----------+-------+
| comment_id | left_num | right_num | depth |
+------------+----------+-----------+-------+
|     4 |    6 |    13 |   2 |
+------------+----------+-----------+-------+

獲取 '節(jié)點4' 的所有子節(jié)點, 和相關深度

SELECT sub_child.*,
 (COUNT(sub_parent.comment_id) - 1) AS depth
FROM (
 SELECT child.*
 FROM comment AS parent, comment AS child
 WHERE child.left_num BETWEEN parent.left_num AND parent.right_num
  AND parent.comment_id = 4
) AS sub_child, (
 SELECT child.*
 FROM comment AS parent, comment AS child
 WHERE child.left_num BETWEEN parent.left_num AND parent.right_num
  AND parent.comment_id = 4
) AS sub_parent
WHERE sub_child.left_num BETWEEN sub_parent.left_num AND sub_parent.right_num
GROUP BY sub_child.comment_id
ORDER BY sub_child.left_num;
+------------+----------+-----------+-------+
| comment_id | left_num | right_num | depth |
+------------+----------+-----------+-------+
|     4 |    6 |    13 |   0 |
|     5 |    7 |     8 |   1 |
|     6 |    9 |    12 |   1 |
|     7 |    10 |    11 |   2 |
+------------+----------+-----------+-------+

插入數(shù)據(jù)
數(shù)據(jù)的插入是一件相當麻煩的事，需要更新節(jié)點的所有父節(jié)點的右值和和所有孩子節(jié)點的 '左值、右值'
如上圖，如果我們想為 '節(jié)點4' 添加一個孩子 '節(jié)點44'(為了不給自己挖坑，我們將添加的孩子放在父節(jié)點的最左邊)，就是將 '節(jié)點44' 放在 '節(jié)點5' 的左邊。如下圖：

最終我們獲得的結(jié)果，如下圖：

上圖 '紫色' 的是節(jié)點需要變更的左值和右值，'綠色' 的是新增節(jié)點的值。
更新思路：
1、將左值大于 '節(jié)點4' 的左值的節(jié)點的左值加2。
2、將右值大于 '節(jié)點4' 的左值的節(jié)點的右值加2。

-- 獲得 '節(jié)點4' 和 '節(jié)點4'的第一個孩子的(節(jié)點5)的左右值
SELECT c.*
FROM comment AS p, comment AS c
WHERE c.left_num BETWEEN p.left_num AND p.right_num
 AND p.comment_id = 4;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     4 |    6 |    13 |
|     5 |    7 |     8 |
... omit ...
-- 通過上面獲得的信息更新 '節(jié)點4' 的父子幾點的左右值
UPDATE comment SET left_num = left_num + 2 WHERE left_num > 6;
UPDATE comment SET right_num = right_num + 2 WHERE right_num > 6;

插入思路
1、將 '節(jié)點44' 的左值設置為 '節(jié)點4' 的左值加1
2、將 '節(jié)點44' 的右值設置為 '節(jié)點4' 的左值加2

INSERT INTO comment 
SELECT 44, left_num + 1, left_num + 2
FROM comment WHERE comment_id = 4;

驗證

-- 獲得 '節(jié)點4' 孩子
SELECT c.*
FROM comment AS p, comment AS c
WHERE c.left_num BETWEEN p.left_num AND p.right_num
 AND p.comment_id = 4;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     4 |    6 |    15 |
|     5 |    9 |    10 |
|     6 |    11 |    14 |
|     7 |    12 |    13 |
|     44 |    7 |     8 |
+------------+----------+-----------+
-- 獲得 '節(jié)點44' 父親
SELECT p.* 
FROM comment AS p, comment AS c
WHERE c.left_num BETWEEN p.left_num AND p.right_num
 AND c.comment_id = 44;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     1 |    1 |    16 |
|     4 |    6 |    15 |
|     44 |    7 |     8 |
+------------+----------+-----------+

1.4. 總結(jié)

這種樹結(jié)構(gòu)一般會用在查詢多增加修改少的場景中（比如地區(qū)表，類別表之類的）。
在現(xiàn)實中其實還有些表的數(shù)據(jù)字段很多，并且具有層級關系。但是他們層級關系并不需要實時的那么準確(最終能達到數(shù)據(jù)數(shù)據(jù)一直就行)，這是我們會將這種層級關系的字段和主表分開放在另外一個表。這樣為了加快更新。如果實時更新影響到了性能，這是我們會考慮使用kafka(我們還沒有發(fā)現(xiàn)性能很差)。

您可能感興趣的文章:

樹搜索

MySQL 數(shù)據(jù)庫的監(jiān)控方式小結(jié)
本文主要介紹了MySQL 數(shù)據(jù)庫的監(jiān)控方式小結(jié)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2023-04-04
MySQL是如何保證數(shù)據(jù)的完整性
這篇文章主要介紹了MySQL是如何保證數(shù)據(jù)的完整性，幫助大家更好的理解和學習MySQL，感興趣的朋友可以了解下
2020-08-08
mysql中如何根據(jù)經(jīng)緯度計算距離
這篇文章主要給大家介紹了關于mysql中如何根據(jù)經(jīng)緯度計算距離的相關資料,經(jīng)緯度距離計算方法是一種用來計算地球上兩個點之間距離的方法,它可以在MySQL數(shù)據(jù)庫中輕松實現(xiàn),非常適用于需要進行地理定位的應用程序,需要的朋友可以參考下
2023-08-08
MySQL的加密解密的幾種方式(小結(jié))
這篇文章主要介紹了MySQL的加密解密的幾種方式(小結(jié))，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2021-03-03
MySQL中空值Null和空字符‘‘的具體使用
本文主要介紹了MySQL中空值Null和空字符''的具體使用,文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-05-05
MySQL中?LBCC?和?MVCC?的理解及常見問題示例
這篇文章主要介紹了MySQL中LBCC和MVCC的理解及常見問題示例，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，感興趣的朋友可以參考一下
2022-09-09
Navicat無法連接MySQL報錯1251的解決方案
這篇文章主要為大家詳細介紹了Navicat無法連接MySQL報錯1251的解決方案,文中解決方法介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
2023-12-12
MySQL數(shù)據(jù)庫定時任務舉例講解
最近項目里面的后臺需要用到定時任務,而MySQL從5.0開始自帶了定時事件操作,所以學習下并做下記錄,下面這篇文章主要給大家介紹了關于MySQL數(shù)據(jù)庫定時任務的相關資料,需要的朋友可以參考下
2023-06-06
mysql中鎖機制的最全面講解
大概幾個月之前項目中用到事務,需要保證數(shù)據(jù)的強一致性,期間也用到了mysql的鎖,所以本文打算總結(jié)一下mysql的鎖機制,這篇文章主要給大家介紹了關于mysql中鎖機制的相關資料,需要的朋友可以參考下
2021-09-09
Linux下MySQL安裝配置 MySQL配置參數(shù)詳解
Linux下MySQL安裝配置 MySQL配置參數(shù)詳解，在linux下配置mysql的朋友可以參考下。
2011-07-07