| 導購 | 订阅 | 在线投稿
分享
 
 
 

項目開發中層次結構存儲的兩種設計方法

來源:互聯網  2008-06-03 06:17:47  評論

在實際的項目開發中,我們經常會碰到存儲多級數據結構(樹狀)的問題。下面,我們來介紹一下層次結構存儲的兩種設計方法:

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。

注釋:以上兩種方法的采用根據我們可以針對具體情況來酌情考慮,假如查詢量小但頻繁添加,刪除則建議采用第一種。假如查詢量偏大,我們可以考慮使用第二種方法。

在實際的項目開發中,我們經常會碰到存儲多級數據結構(樹狀)的問題。下面,我們來介紹一下層次結構存儲的兩種設計方法: 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。 注釋:以上兩種方法的采用根據我們可以針對具體情況來酌情考慮,假如查詢量小但頻繁添加,刪除則建議采用第一種。假如查詢量偏大,我們可以考慮使用第二種方法。
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有