微软 开源 Firefox centos Python 编程 Ubuntu mysql apache Windows wordpress Android shell php google linux java 程序员 云计算 nginx

基於樹型結構數據的關系數據庫存儲與網頁顯示的研究

Research of storage in Relational Database and display on web based data of tree structure

Abstract:A thinking about data of tree structure how to stored in relational database and a method of how about these data is displayed on web is discussed in this paper. When data of tree structure is stored in database ,it is easy to observer modifications of each data node .Display of plane data note stored in relational [1]database on web needs cooperation of recursive calculational function provided by DBMS and skill of usage about HTML.

Key words: tree structure     nesting label    plane relation

引言:樹型結構是很熟悉的一種模型。它的應用十分廣泛,比如組織結構,物料清單,資料檔案管理,資產管理等等都是以樹型結構為基礎。在現實生活中,有許多事物可以抽象為樹狀結構。這種結構可以簡化對某些事物的理解,使概念清晰。樹型結構在數據庫存儲的表結構可以很簡單也可以很復雜。根據不同的需求,表結構不是一成不變的,讀取數據的方法也不盡相同。在B/S架構下直觀的表達樹型結構需要深刻理解HTML標簽的作用和顯示的效果之間的關系,以及利用數據庫提供的遞歸計算功能。

1.樹型結構的特征和數據庫存儲

       樹型結構是數據結構中的一種重要結構,由節點和分支組成。兩個節點由分支連接,一端的節點稱作父節點,另一端的節點稱為子節點,同一個節點的孩子相互之間是兄弟。有兩條規則可以識別節點和分支。第一條規則是每個節點只能有一個父節點,有一個節點沒有父節點。這個沒有父節點的節點稱作樹的根節點(或者稱為根),第二條規則是每棵樹必須有且只有一個根節點。沒有子節點的節點稱為葉子節點。樹有許多不同的形式,一棵樹可以只包含一個節點,樹的節點可以有不同數目的子節點,也可以沒有子節點。

(圖1)簡單二叉樹

二叉樹是每個節點最多由兩個孩子節點組成的樹,它是一種典型的樹型結構。下面以簡單二叉樹為例說明樹結構的存儲。簡單二叉樹僅僅說明了有直接關系的兩個節點的父子關系。在數據庫中,把每個節點看作一個單獨的實體,每個實體有一個標識,稱為鍵。每個節點至少需要存儲一個鍵(node_id),相應的數據(date),當前節點在兄弟節點中的位置 (pos),子節點的個數(node_id_num),和節點的鍵(pNode_id)。由於父節點的鍵(pNode_id)為參照自身表的外鍵,這個表一中遞歸表。相應的E_R(Entity_Relation)圖如圖2所

示:

(圖2)二叉樹的數據庫存儲的概念模型

可以使用這種表存儲樹結構數據,並可以分別的觀察每個節點的變化情況。以二叉樹為例,pos字段可以存儲漢字“左“或者“右”,也可以存儲代表左和右的數字,在二叉樹上進行的操作也可以在數據庫中存儲的二叉樹中進行操作,比如可以查看一個節點的所有孩子節點信息,按照先序遞歸遍歷,按照中序或者後序進行便利,統計節點的個數等等。

存儲在數據庫中的樹結構數據是平面的二維表,包含每個節點實體的數據。這些數據在表達節點之間的關系方面顯得不夠直觀。為了方便表達這些節點之間的關系,需要對這些數據的表示進行改進。以簡單二叉樹在網頁上的顯示為例來說明樹結構數據的顯示。

2.基於網頁的樹型結構數據表示

普通的客戶端瀏覽動態網頁的過程是客戶端發送頁面請求,服務器端按照客戶端的請求,根據腳本動態生成頁面的HTML(超文本標記語言)代碼發送到客戶端,客戶端瀏覽器解析HTML代碼並顯示給客戶。HTML代碼是服務器端生成的重要資源,根據這些代碼,客戶端就可以顯示不同的網頁效果。經研究發現,使用HTML中的<Table>標簽可以模擬生成二叉樹的表示,並且不占用太多的資源。在HTML中,<table>標簽是頁面布局的常用手段,方便定位和控制大小。下面是使用<table>嵌套標簽來表示的簡單二叉樹。

 

A

B

C

E

F

G

H

       

(圖3)網頁的表示

從數據庫中讀取的二叉樹數據,並不像普通的帶有指針的二叉樹數據容易控制。經過研究發現,每個表格<table>中包括多個行<tr>,每一行包括多個單元格<TD>。這些表格同樣是平面的,只包括行和列。在整個樹的表示中,讓根節點A為表中的單獨的一行,並且只有一個單元格,跨兩個列,第二行有兩個單元格,如果根節點A有左孩子B,在第一個單元格中則嵌套一個表,顯示以B為根節點的子樹,如果A有右孩子,則在第二個單元格中新建一個表,在表中顯示以C為根節點的字樹。以此類推,便可以顯示整個樹的結構。由於HTML中的標簽需要封閉,即如果有一個<Table>則必須對應一個</table>,在,服務器端生成動態頁面是流水線形式的,不可能有類似於回退指針的形式。所以必須在合適的時候封閉對應的標簽。按照以上的分析,整個圖的結構需要的HTML標簽應該類似於以下的代碼

<TABLE><TR><TD colspan=2>A</TD></TR> 

<TR><TD><TABLE><TR><TD>B…….</TABLE>   </TD>    ….   </TR>

</TABLE>

3.二叉樹數據存儲與網頁顯示的關鍵技術

在支持存儲過程和遞歸運算的數據庫管理系統中可以使用遞歸算法來解決這個問題,以MSSQL為例,可以寫出如下存儲過程,由於MSSQL支持的自定義字符類型變量最大長度為8000字符,為了顯示更多層的節點,使用以下的字符代替相應的標簽,在網頁程序腳本中按照一定的次序替換這些字符便可以在在8000個字符的以內表示10層以內的節點數據。

--f=<table><TR><TD colspan=2>

--n=</TD></TR></table>

--p=</TD></TR><TR><TD>

--q=</TD><TD>

遞歸讀取樹型結構數據的存儲過程定義如下:

--定義的存儲過程可以第歸調用zgdh2位用戶名,@level參數可以控制顯示多少層。

       --初始化,定義變量

--遞歸出口

if(@level < 1)return 'f'+rtrim(@data)+'n'

..處理當前節點數據

--如果有左孩子,遞歸調用算法

       if exists(select 1 from tree where pnode_id=@node_id and  pos = 1)

       set @str = @str + zgdh2.getGraph(@child_id,@level -1)…

--關閉/開啟標簽

              set @str = @str + 'q'

--如果有右孩子,遞歸調用算法

              if exists(select 1 from tree where pnode_id=@node_id and pos = 2)

       set @str = @str + zgdh2.getGraph(@child_id,@level -1)…

--封閉標簽並返回結果

       set @str = @str + 'n'

       return @str

在asp中假設已經連接到數據庫,並且把結果讀取到變量str中

則可以按照如下的替換調用順序替換字符為標簽,然後輸出

str = replace(str,"n","</TD></TR></table>")

str =replace(str,"p","</div></TD></TR><TR><TD>")

str =replace(str,"q","</TD><TD valign='top'>")

str = replace (str,"f","<table><TR><TD colspan=2>")

4試驗結果: 

              在數據庫中存儲了樹結構關系的人名,如(圖4)所示,張松霞下面是彭清蘭和許惋春,整個圖有5層,經過替換後從數據庫中讀取出來的結果大約有200個字符,替換為HTML表前後大約有3500個字符。

张松霞

彭清兰

李景花

孟凡双

尹建平

    

    

朱雅静

胡俊才

姚爱玲

王瑞莲

    

    

    

许惋春

薛丽娟

王书花

谢永莉

    

    

    

    

(圖4)人名的二叉樹排列

5.結論:

樹型結構的數據存儲在數據庫中需要一定的技巧,把每個節點作為一個實體,相互之間的關系也存儲在數據庫中,以便於依據DBMS的特點進行與樹有關的操作。存儲在關系數據庫中的樹是平面的,把數據庫中存儲的平面關系的樹型結構顯示出來,不僅要有DBMS提供的功能特點,也需要相關特定編程語言提供的功能的配合。樹型圖不僅能顯示二叉樹,也可是顯示3叉樹,n叉樹,這種顯示樹型圖的方法具有通用性和較強的實用性。

參考文獻:

[1]《Database Solutiongs》[M]Thomas M.Connolly Carolyn E.Begg 北京 機械工業出版社 2005

[2]《數據庫系統概論》[M](第三版) 薩師煊 王珊    北京       高等教育出版社    2003

[3]《數據結構 C語言版》[M] 嚴蔚敏,吳偉民              北京       清華大學出版社2002

[4] 《算法分析與設計技術》[M]      賀紅, 馬紹漢編著 科學出版社 2004

[5] 《ASP數據庫系統開發案例精選》[M]      蓋天宇, 孫明麗, 鄒天思編著     人民郵電出版社 2006

[6]《數據庫管理系統原理與設計》[M]    (美) Raghu Ramakrishnan, Johannes Gehrke著 北京-清華大學出版社 2004

[7]《SQL Server 數據庫管理、設計與實現教程》[M]  趙傑,李濤,朱慧編著 北京-清華大學出版社 2004

[8] 《SQL Server高級開發與專業應用》[M]  敬錚主編  北京-國防工業出版社 2002

[9] 《PowerDesigner 系統分析與建模》[M]  趙韶平…[等]編著  北京-清華大學出版社 2004

延伸阅读

    评论