在實際的項目開發中,我們經常會碰到存儲多級數據結構(樹狀)的問題。下面,我們來介紹一下層次結構存儲的兩種設計方法:
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。
注釋:以上兩種方法的采用根據我們可以針對具體情況來酌情考慮,假如查詢量小但頻繁添加,刪除則建議采用第一種。假如查詢量偏大,我們可以考慮使用第二種方法。