在實際的項目開發中，我們經常會碰到存儲多級數據結構（樹狀）的問題。下面，我們來介紹一下層次結構存儲的兩種設計方法：
1：鄰接表模式（adjacency list model）
2：先根遍曆樹算法（modified preorder tree traversal algorithm）
參考數據結構：
中國
|
|---陝西
| |
| |---渭南
| |
| |--- 西安
| |
| |--鍾樓
| | |
| | |--大雁塔
|
|---雲南
| |
| |---麗江
1：鄰接目錄模式：
一般情況下，我們在數據庫中增加一個parent字段表示這個節點的父節點，從而將整個樹狀描述出來
如：
parent name
中國
中國 陝西
中國 雲南
陝西 渭南
陝西 西安
雲南 麗江
西安 鍾樓
西安 大雁塔
等這樣我們就能夠通過數據庫保存整個樹狀結構啦。
通過這種方法需要得到一個多級結構時候需要進行一個遞歸， 通過遞歸的方法我們可以得到任意節點的路徑。
這種方法的優點是簡單，容易理解。缺點是運行速度很慢。尤其是數據量很大的時候需要進行很多查詢時候才能完成一個樹， 效率很低。
2:先根遍曆樹算法
將多級數據按照下面的格式劃出來
1 中國 16
|
+------------------------+
2 陝西 11 12 雲南 15
| |
+-------------+ 13 麗江 14
3 渭南 4 5 西安 10
|
+-----------+
6 鍾樓 7 8 大雁塔 9
我們給根節點“中國”左側標上1， 然後沿著這個樹向下在“陝西”左側標上2， 然後繼續前進， 向下在“渭南”左側標上3， 渭南沒有子節點，所以在“渭南”右側標上4， 然後繼續“渭南”的右側節點。。。沿著整個樹的給每個節點的左側和右側標上數字。最後一個數組標在“中國”右側爲16。 你只要用手指從1指到16就知道怎麽回事啦。
這些數字表明了各個節點之間的關系。我們可以看到， 所有左側大于2， 右側小于11的節點，都是“陝西”的子節點。
這樣我們可以在數據庫中用left, right表示左右數字。如：
我們給根節點“中國”左側標上1， 然後沿著這個樹向下在“陝西”左側標上2， 然後繼續前進， 向下在“渭南”左側標上3， 渭南沒有子節點，所以在“渭南”右側標上4， 然後繼續“渭南”的右側節點。。。沿著整個樹的給每個節點的左側和右側標上數字。最後一個數組標在“中國”右側爲16。 你只要用手指從1指到16就知道怎麽回事啦。
這些數字表明了各個節點之間的關系。我們可以看到， 所有左側大于2， 右側小于11的節點，都是“陝西”的子節點。
這樣我們可以在數據庫中用left, right表示左右數字。如：
name left right
中國 1 16
陝西 2 11
雲南 12 15
渭南 3 4
西安 5 10
鍾樓 6 7
大雁塔 8 9
麗江 13 14
這樣我們如果想得到 "陝西"下的所有節點。只需要執行：
select * from table where left between 2 and 11;
要想知道“西安”的路徑只需要執行：
select * from table where left < 5 and right > 10;
計算某個節點有多少子孫節點： 子孫節點數＝（右值－左值－1）/2;
要算出所有節點的左右值， 數據庫中需要parent字段，然後編寫一個計算左右值遞歸函數執行。（這裏略去不談）。
主要考慮如何進行一個子節點的增加，刪除。
◆方法1： 在數據庫中保留parent字段， 增加節點後，調用計算左右值遞歸函數重新計算左右值。 該方法不推薦用
◆方法2： 改變所有位于新節點右側的左右值。
比如：想添加“華清池”作爲“西安”的最後一個節點，我們給它挪出一個空間，“西安”的右值改爲12， “陝西”的右值改爲13， “雲南”及其子節點的左右值從“12－15”改爲 “14－17”， “中國”的右值改爲18。即給左右值大于9的所有節點加2 （9爲西安最後一個子節點的右值）
update table set right=right+2 where right > 9;
update table set left=left+2 where left > 9;
這樣就給新節點騰出空間，它的左右值分別爲 9+1, 9+2;
insert into table set left=10, right=11, name='華清池';
當然，刪除一個節點時候給左右值大于該節點右值的所有節點減2。
注釋：以上兩種方法的采用根據我們可以針對具體情況來酌情考慮，假如查詢量小但頻繁添加，刪除則建議采用第一種。假如查詢量偏大，我們可以考慮使用第二種方法。
