PHP與Mysql樹型結構設計的兩種方式

本篇文章為大家展示了PHP與Mysql樹型結構設計的兩種方式，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

常用的方法有兩種：

1. 領接表的方式；

2. 預排序遍歷樹方式；

假設樹狀結構如下圖：

領接表方式

主要依賴于一個 parent 字段，用于指向上級節點，將相鄰的上下級節點連接起來，id 為自動遞增自動，parent_id 為上級節點的 id。一目了然，“Java”是“Language”的子節點。

我們要顯示樹，PHP 代碼也可以很直觀，代碼如下：

復制代碼 代碼如下:

<?php
/**
 * 獲取父節點下的所有子節點
 *
 * @since 2011-05-18
 *
 * @param $parent_id 父節點 id，0 則顯示整個樹結構。
 * @param $level 當前節點所處的層級，用于縮進顯示節點。
 * @return void
 */
function show_children ($parent_id = 0, $level = 0)
{
    // 獲取父節點下的所有子節點
    $result = mysql_query('SELECT id, name FROM tree WHERE parent_id=' . intval($parent_id));
    // 顯示每個子節點
    while ($row = mysql_fetch_array($result)) {
        // 縮進顯示
        echo '<div >' . $row['name'] . '</div>';
        // 遞歸調用當前函數，顯示再下一級的子節點
        show_children($row['id'], $level + 1);
    }
}
?>

想要顯示整個樹結構，調用 show_children()。想要顯示“Database”子樹，則調用 show_children(2)，因為“Database”的 id 是 2。

還有一個經常用到的功能是獲取節點路徑，即給出一個節點，返回從根節點到當前節點的路徑。用函數實現如下：

復制代碼 代碼如下:

<?php
/**
 * @param $id 需要獲取路徑的當前節點的 id。
 * @return array
 */
function get_path($id)
{
    // 獲取當前節點的父節點 id 和當前節點名
    $result = mysql_query('SELECT parent_id, name FROM tree WHERE id='.intval($id));
    $row = mysql_fetch_array($result);
    // 使用此數組保存路徑
    $path = array();
    // 將當前節點名保存進路徑數組中
    $path[] = $row['name'];
    // 如果父節點非 0，即非根節點，則進行遞歸調用獲取父節點的路徑
    if ($row['parent_id']) {
        // 遞歸調用，獲取父節點的路徑，并且合并到當前路徑數組的其它元素前邊
        $path = array_merge(get_path($row['parent_id']), $path);
    }
    return $path;
}
?>

想要獲取“MySQL 5.0”的路徑，調用 get_path(4)，4 即是這個節點的 id。

領接表方式的優點在于容易理解，代碼也比較簡單明了。缺點則是遞歸中的 SQL 查詢會導致負載變大，特別是需要處理比較大型的樹狀結構的時候，查詢語句會隨著層級的增加而增加，WEB 應用的瓶頸基本都在數據庫方面，所以這是一個比較致命的缺點，直接導致樹結構的擴展困難重重。

排序遍歷樹方式

現在我們來聊聊第二種方式─預排序遍歷樹方式（即通常所說的 MPTT，Modified Preorder Tree Traversal）。此算法是在第一種方式的基礎之上，給每個節點增加一個左、右數字，用于標識節點的遍歷順序，如下圖所示：

從根節點開始左邊為 1，然后下一個節點的左邊為 2，以此類推，到最低層節點之后，最低層節點的右邊為其左邊的數字加 1。順著這些節點，我們可以很容易地遍歷完整個樹。根據上圖，我們對數據表做一些改變，增加兩個字段，lft 和 rgt 用于存儲左右數字（由于 left 和 right 是 MySQL 的保留字，所以我們改用簡寫）。表中各行的內容也就變成了：

接下來看看顯示樹/子樹是多么簡單，只需要一條 SQL 語句即可，比如顯示“Database”子樹，則需要獲取到“Database”的左右數字，左為 2，右為 11，那么 SQL 語句是：

復制代碼 代碼如下:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

SQL 語句是簡單了，但我們所希望的縮進顯示卻是個問題。什么時候應該顯示縮進？縮進多少單位？解決這個問題，需要使用堆棧，即后進先出（LIFO），每到一個節點，將其右邊的數字壓入堆棧中。我們知道，所有節點右邊的值都比其父節點右邊的值小，那么將當前節點右邊的值和堆棧最上邊的右邊值進行比較，如果當前節點比堆棧最上邊的值小，表示當前堆棧里邊剩下的都是父節點了，這時可以顯示縮進，堆棧的元素數量即是縮進深度。PHP 代碼實現如下：

復制代碼 代碼如下:

<?php
/**
 * @param $root_id 需要顯示的樹/子樹根節點 id。
 */
function show_tree($root_id = 1)
{
    // 獲取當前根節點的左右數值
    $result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($root_id));
    $row = mysql_fetch_array($result);
    // 堆棧，存儲節點右邊的值，用于顯示縮進
    $stack = array();
    // 獲取 $root_id 節點的所有子孫節點
    $result = mysql_query('SELECT name, lft, rgt FROM tree WHERE lft BETWEEN '.$row['lft'].' AND '.$row['rgt'].' ORDER BY lft ASC');
    // 顯示樹的每個節點
    while ($row = mysql_fetch_array($result)) {
        if (count($stack)>0) { //僅當堆棧非空的時候檢測
            // 如果當前節點右邊的值比堆棧最上邊的值大，則移除堆棧最上邊的值，因為這個值對應的節點不是當前節點的父節點
            while ($row['rgt'] > $stack[count($stack)-1]) {
                array_pop($stack);
            } //while 循環結束之后，堆棧里邊只剩下當前節點的父節點了
        }
        // 現在可以顯示縮進了
        echo '<div >'.$row['name'].'</div>';
        // 將當前的節點壓入堆棧里邊，為循環后邊的節點縮進顯示做好準備
        array_push($stack, $row['rgt']);
    }
}
?>

獲取整個樹調用 show_tree()，獲取“Database”子樹調用show_tree(2)。在這個函數中，我們總算不需要用到遞歸了，呵呵。

接下來是顯示從根節點到某節點的路徑，這比起領接表方式來說也簡單了很多，只需要一句 SQL 就行，不用遞歸  比如獲取“ORACLE”這個節點的路徑，其左右值分別是 7 和 10，則 SQL 語句為：

復制代碼 代碼如下:

SELECT name FROM tree WHERE lft <= 7 AND rgt >= 10 ORDER BY lft ASC;

PHP 函數實現如下：

復制代碼 代碼如下:

<?php
/**
 * @param $node_id 需要獲取路徑的節點 id
 */
function get_path3($node_id) {
    // 獲取當前節點的左右值
    $result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($node_id));
    $row = mysql_fetch_array($result);
    // 獲取路徑中的所有節點
    $result = mysql_query('SELECT name FROM tree WHERE lft <= '.$row['lft'].' AND rgt >= '.$row['rgt'].' ORDER BY lft ASC');
    $path = array();
    while ($row = mysql_fetch_array($result)) {
        $path[] = $row['name'];
    }
    return $path;
}
?>

顯示樹和路徑都沒問題了，現在需要了解一下如何插入一個節點。插入新節點之前，首先要給這個節點騰出空位來，假設我們現在要在“ORACLE 9i”這個節點右邊增加一個“ORACLE 10”，則騰位的 SQL 語句如下（“ORACLE 9i”的右邊值為 9）：

復制代碼 代碼如下:

UPDATE tree SET rgt=rgt+2 WHERE rgt>9;
UPDATE tree SET lft=lft+2 WHERE lft>9;

位置空出來了，開始插入新節點吧：

復制代碼 代碼如下:

INSERT INTO tree SET lft=10, rgt=11, name='ORACLE 10';

調用 show_tree() 看看結果對不對  具體的 PHP 實現代碼這里就不寫了。

上述內容就是PHP與Mysql樹型結構設計的兩種方式，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。