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

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

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。

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

MySQL兩種表存儲結構性能比較測試過程
  MySQL支持的兩種主要表存儲格式MyISAM,InnoDB,上個月做個項目時,先使用了InnoDB,結果速度特別慢,1秒鍾只能插入10幾條。後來換成MyISAM格式,一秒鍾插入上萬條。當時覺的這兩個表的性能也差別太大了吧。後來...查看完整版>>MySQL兩種表存儲結構性能比較測試過程
 
MySQL兩種表存儲結構性能比較測試過程
MySQL支持的兩種主要表存儲格式MyISAM,InnoDB,上個月做個項目時,先使用了InnoDB,結果速度特別慢,1秒鍾只能插入10幾條。後來換成MyISAM格式,一秒鍾插入上萬條。當時覺的這兩個表的性能也差別太大了吧。後來自己...查看完整版>>MySQL兩種表存儲結構性能比較測試過程
 
PHP面向對象編程開發大型PHP項目方法
這篇文章介紹了在PHP中的面向對象編程(OOP,Object Oriented Programming)。我將向你演示如何通過使用一些OOP的概念和PHP的技巧來減少編碼和提高質量。祝你好運!面向對象編程的概念:不同的作者之間說法可能不一樣,...查看完整版>>PHP面向對象編程開發大型PHP項目方法
 
JXTA技術的設計目標和層次結構
  P2P即Peer to Peer,稱爲對等連接或對等網絡,P2P技術主要指由硬件形成連接後的信息控制技術,其代表形式是軟件;P2P並不是一個新的概念,因特網上的許多核心協議本身就是P2P的應用程序,因特網的發展過程也說明了...查看完整版>>JXTA技術的設計目標和層次結構
 
菲議存儲:實現 iSCSI Initiator 的兩種方法
菲議存儲:實現 iSCSI Initiator 的兩種方法
首先我們要了解iSCSI 架構中的角色與專詞,iSCSI 的儲存設備稱爲iSCSITarget(或稱iSCSI Target Device),例如iSCSI 磁盤陣列櫃、iSCSI 磁帶櫃等,而iSCSI 卡稱爲iSCSI HBA(Host Bus Adapter),與FC 卡稱呼相同,...查看完整版>>菲議存儲:實現 iSCSI Initiator 的兩種方法
 
菲議存儲:實現 iSCSI Target的兩種方法
菲議存儲:實現 iSCSI Target的兩種方法
如何實現一個iSCSI Target(軟件法) iSCSI Initiator 可用軟件方式實現,同樣的iSCSI Target 也行,不過優劣特點也相近,即是偏成本取向且不易達到專屬硬件的效能。且要更注重的是,iSCSI Initiator 軟件確實多半采...查看完整版>>菲議存儲:實現 iSCSI Target的兩種方法
 
項目叠代開發手記--文件分割存儲用例的實現過程(3)
項目叠代開發手記--文件分割存儲用例的實現過程(3) 上午的叠代2完成後,我們獲得了一個有完整壓縮流功能的實現代碼,這次叠代完成的代碼是可用的,我們在叠代2中完成了我們既定的任務。在下午的小組討論中,...查看完整版>>項目叠代開發手記--文件分割存儲用例的實現過程(3)
 
項目叠代開發手記--文件分割存儲用例的實現過程(2)
項目叠代開發手記--文件分割存儲用例的實現過程(2) 在第二天早上的開發中我們擴展了第一天叠代開發的用例,我們考慮增加了壓縮流的功能,減少數據的存儲負擔。叠代2:用例:對向數據庫提交的二進制流進行壓縮;那...查看完整版>>項目叠代開發手記--文件分割存儲用例的實現過程(2)
 
項目叠代開發手記--文件分割存儲用例的實現過程(1)
摘 要 本文詳細描述了在嘗試使用極限編程在軟件開發中的一個實現例子,在小步叠代開發中逐步的實現用例需要的功能,同時每個叠代都能集成實現的功能。關鍵字 極限編程 在一次項目開發中我們開發組遇到了一個需求,該...查看完整版>>項目叠代開發手記--文件分割存儲用例的實現過程(1)
 
 
回到王朝網路移動版首頁