Mysql實現樹型結構，數據庫上常見有2種方式：領接表、預排序遍歷樹（MPTT）。
領接表方式——
主要依賴於一個 parent 字段，用於指向上級節點，將相鄰的上下級節點連接起來，id 為自動遞增自動，parent_id 為上級節點的 id。
領接表方式的優點在於容易理解，代碼也比較簡單明了。缺點則是遞歸中的 SQL 查詢會導致負載變大，特別是需要處理比較大型的樹狀結構的時候，查詢語句會隨著層級的增加而增加，WEB 應用的瓶頸基本都在數據庫方面，所以這是一個比較致命的缺點，直接導致樹結構的擴展困難重重。
排序遍歷樹方式
現在我們來聊聊第二種方式─預排序遍歷樹方式（即通常所說的 MPTT，Modified Preorder Tree Traversal）。此算法是在第一種方式的基礎之上，給每個節點增加一個左、右數字，用於標識節點的遍歷順序，如下圖所示：
vcq9yrXA/Q==" src="http://www.bkjia.com/uploads/allimg/150703/04231513a-0.gif" title="PHP+Mysql樹型結構（無限分類）數據庫設計的2種方式實例" />
從根節點開始左邊為 1，然後下一個節點的左邊為 2，以此類推，到最低層節點之後，最低層節點的右邊為其左邊的數字加 1。順著這些節點，我們可以很容易地遍歷完整個樹。根據上圖，我們對數據表做一些改變，增加兩個字段，lft 和 rgt 用於存儲左右數字（ left 和 right 是 MySQL 的保留字，所以改用簡寫）。
可以看出，由於MPTT方式存儲不僅包含隸屬關系，還包括了順序，因此在讀取子樹時不需遞歸，效率大大提高。
下面面討論下如何在這兩著間轉換.
MPTT轉領接表比較容易，只要尋找層級比當前節點小1，且lft<當前節點lft，rgt>當前節點rgt的節點，即為父節點。
領接表轉MPTT，一般直觀想到的是遞歸生成。但是這個不是尾遞歸，遞歸層數有限制， mysql沒有數組自建堆棧要用表，效率很低，怎麼辦？
筆者設計了一個近似遞推的算法，分享一下：
首先確定問題：領接表結構（id，pid），目標MPTT表結構（id，lvl，lft，rgt）。
為處理需要，MPTT表增加cnt、seq字段，用於記錄節點及其子節點的個數、在MPTT中遍歷的序號。
處理過程算法如下：
1】根節點，轉入MPTT表，令lvl=1，lft=1，rgt=null,cnt=null,seq=1；
2】逐層處理p的子節點，lvl+1；
3】從最底層（lvl最大）向上（lvl遞減）處理各層的節點，cnt=子節點的cnt數+1
4】從最上曾（lvl=1）向下（lvl遞增）處理各層的節點，seq=父節點seq+ sum（id小於本節點的兄弟節點的cnt）+1
5】對每一個節點，lft=seq*2-lvl，rgt = lft +cnt *2 -1
處理結束；
此算法已在項目中應用，代碼是有版權的，就不貼了。
