DSU數(shù)據(jù)庫存儲單元在CBTC系統(tǒng)中的計劃

PAGE1PAGE2職業(yè)技術(shù)學(xué)院畢業(yè)設(shè)計(論文）論文題目DSU數(shù)據(jù)庫存儲單元在ＣBTＣ系統(tǒng)中的應(yīng)用方案系別專業(yè)班級學(xué)號姓名指導(dǎo)老師２0１1年月日名目TOC\ｏ"1-３＂＼h＼uHYPERＬＩNK二、數(shù)據(jù)庫技術(shù)進(jìn)展現(xiàn)狀?PAGEREF_Tｏc３１268407４\h1HＹPＥRLIＮＫ\l”_Ｔｏc312６８４075"(一)數(shù)據(jù)庫技術(shù)的進(jìn)展?PAGERＥF＿Ｔoc312684０75\h1HＹPＥRLINＫ\ｌ”_Toc31２６84076"(二）嵌入式數(shù)據(jù)庫?ＰＡＧEREF＿Ｔoc312684０76\h2ＨYPERLINK\ｌ"_Toc３126840７7"(三）實時數(shù)據(jù)庫?ＰAGＥＲEF_Toc３126840７7＼h２HYＰERLＩＮK\l”_Ｔｏc312６８407８”三、系統(tǒng)需求以及設(shè)計問題的提出 PAGERＥF_Tｏｃ31２684078\h3ＨＹPERLＩＮＫ＼ｌ＂_Tｏｃ3126８4０７9”四、DSU數(shù)據(jù)庫在ＣBTC系統(tǒng)中的作用 PＡＧEREF_Toc31２684079＼h3HYＰERLＩNK\l"_Toｃ3１２6８４080”五、基于二叉樹的CＢＴC數(shù)據(jù)庫構(gòu)建與搜尋算法 PＡＧEＲＥF_Toc３１2684０80\ｈ5HYＰERＬINK＼l”_Ｔｏc312684０81”六、結(jié)論 ＰAＧERＥF_Toc３１268４081\ｈ7DＳＵ數(shù)據(jù)庫存儲單元在CBTＣ系統(tǒng)中的應(yīng)用方案內(nèi)容摘要摘要：基于通信的列車運行掌握（CＢTC）系統(tǒng)是目前世界上討論應(yīng)用最為廣泛的列控系統(tǒng)，是利用連續(xù)、大容量的車地雙向通信來實現(xiàn)數(shù)據(jù)傳輸?shù)牧锌叵到y(tǒng)。其中，DSＵ是數(shù)據(jù)庫存儲單元的簡稱,它是CBＴC系統(tǒng)所包含的諸多子系統(tǒng)之一.DSＵ存在的意義在于為ＣBTC系統(tǒng)存儲和供應(yīng)全部的系統(tǒng)數(shù)據(jù)。分析了各種數(shù)據(jù)處理方式的簡略實現(xiàn)方案，對DSU所包含的數(shù)據(jù)存儲處理子系統(tǒng)(DSＭS）進(jìn)行了模塊化構(gòu)建.論文提出了在平安計算機(jī)的環(huán)境中開發(fā)DSU系統(tǒng)的理念，并在嵌入式實時操作系統(tǒng)VxWorｋs的環(huán)境下,此外,論文還對DSU中的數(shù)據(jù)平安以及數(shù)據(jù)庫平安性特點進(jìn)行了的定性討論。最后論文對所作的工作進(jìn)行了總結(jié)，并對今后的實際設(shè)備投入工作進(jìn)行了展望。關(guān)鍵詞：HYPERLINＫ＂http：/／cｄ．ｃｎ/aｒtｉｃle/%09%09％09%0９％09％０９％09％09％０9％０9httｐ:/wikｉ。cnkｉ.com．cn/ｈｏｔｗord／hｏtｗｏｒｄSearｃh。ａshx?q=CBTC"\t＂_bｌanｋ”CBTCＨYPＥRLINK"ｈtｔｐ：//cdmd．cｎki．cｏｍ.cｎ/arｔicle/%0９%0９%09％09%09%０9%09％09%0９%09htｔp:／wｉｋｉ．cｏm．cn/ｈotword/hotwordSeａrch.aｓhx?ｑ=％E6%95%B0％E６％8Ｄ％AE%E5％BA%９3％E5%AD%98％E5%82%Ａ8%Ｅ5％8D％95％E5%85%８3＂＼ｔ"_blａnk”數(shù)據(jù)庫存儲單元HＹPEＲＬINK＂ｈttp://cｄki。cｏm。ｃｎ/article/%09％09％０9％09％09%09％０9%0９%0９%０9hｔtp：/wｉｋkｉ．ｃom。ｃn/hoｔword/hoｔｗordSeaｒch.ashx？ｑ=DSＵ"\t＂＿bｌanｋ"ＤSUHYＰERLＩNK＂ｈｔtp：//cｄki。cｏｍ。ｃn/aｒticlｅ/%09％０9%０９％09％09％09%09％０9％09％0９hｔtp:/ｗiki．/hｏtword/hoｔwｏｒdSearch．a(chǎn)ｓhx?q＝％E6%95％B０%E6％8Ｄ%AE%E5％BA％９3%Ｅ8％AＥ%BE%E8%AＥ%A１"\t"_blank＂數(shù)據(jù)庫設(shè)計HYＰERLINK”hｔtp:/／cdmd．ｃnｋ/ａrtｉclｅ/%09%09％09%09％0９%09％09％09％09%09ｈttp:/wiｋｉ．．cn／ｈotｗord/ｈotwoｒｄSearｃh。ashx？ｑ=％E4%BＡ％8C%E５％８F%8９%E6％A0%91"＼ｔ”_bｌaｎk"二叉樹ＨYPERLINK”http:/／cdmｄ。cnｋi．cｏｍ．ｃn/articｌe/％09％09%0９%09％09％0９%09％0９％09%09http：/ｗiｋｉ．ｃ。cｎ／hotｗorｄ/hｏtｗoｒdSearch．ａshx？q=%E5％8A％A8％E６%80％81%Ｅ５%9Ｂ％BE”\t"＿blanｋ"動態(tài)圖一、引言目前在全世界范圍內(nèi),隨著社會經(jīng)濟(jì)進(jìn)展和城市化進(jìn)程的加快，城市軌道交通(包括地鐵、輕軌、城際快速鐵路等）正以其客運量大、效率高、污染小、受干擾少、平安系數(shù)高的優(yōu)勢,成為很多大城市解決交通問題的首要方案。近年來中國的城市軌道交通建設(shè)有了很大進(jìn)展,到20０7年我國已有1０個城市１８條線路4２5公里的軌道交通系統(tǒng)投入運營，2０07年10月北京地鐵5號線正式開通,而且7個城市的軌道交通項目正在建設(shè),建設(shè)項目總長度為400多公里.到2０10年，我國計劃新建城市軌道交通項目總長度將近1300公里，估計總投資約５0００億元。為了提高城市軌道交通系統(tǒng)運營效率和運行平安,現(xiàn)代的列車掌握系統(tǒng)正朝著自動化、智能化、系統(tǒng)化、網(wǎng)絡(luò)化和信息化的方向進(jìn)展，基于通信的列車掌握（ＣBTＣ：CommuniｃaｔionBaｓedTrａｉnＣoｎtr０1)技術(shù)（以下簡稱CＢＴC）是目前國際最先進(jìn)的列車掌握技術(shù),它代表著當(dāng)今世界范圍內(nèi)掌握領(lǐng)域信號技術(shù)的進(jìn)展趨勢。隨著近年來世界多個城市的CBTＣ線路的成功運行,CBTＣ系統(tǒng)已被證明可以有效地提高城市軌道交通的運輸效率與平安性。一個完善的信號系統(tǒng)離不開數(shù)據(jù)庫的支持,CBTC系統(tǒng)作為一個簡潔的列車自動運行掌握系統(tǒng),需要一個為系統(tǒng)供應(yīng)必須數(shù)據(jù)并進(jìn)行數(shù)據(jù)庫管理的數(shù)據(jù)庫存儲單元（DSＵ：DatabaseStｏrａgeUnit),它包含了CBTC系統(tǒng)中各子系統(tǒng)使用的全部數(shù)據(jù)庫和配置文件。數(shù)據(jù)庫存儲單元是一個平安型設(shè)備,負(fù)責(zé)存儲整個軌道線路的數(shù)據(jù)以及各種掌握信息，它的牢靠性以及平安性直接關(guān)系到ＣBTC系統(tǒng)中的列車運行效率以及行車平安,因此DSU的討論與開發(fā)在CBＴC系統(tǒng)的設(shè)計中扮演著相當(dāng)重要角色，良好的ＤSU設(shè)計對提高整個ＣBTC系統(tǒng)的性能以及平安性都具有十分重要的意義,整個CBＴC系統(tǒng)的設(shè)計對DSU子系統(tǒng)的設(shè)計也提出了很高的要求。面對目前國內(nèi)相關(guān)討論還比較貧乏的現(xiàn)狀，本文對CBＴC系統(tǒng)中數(shù)據(jù)庫存儲單元的設(shè)計進(jìn)行了有益的探究和實踐，對我國具有自主知識產(chǎn)權(quán)的CBTＣ技術(shù)的進(jìn)展具有樂觀意義。二、數(shù)據(jù)庫技術(shù)進(jìn)展現(xiàn)狀（一)數(shù)據(jù)庫技術(shù)的進(jìn)展數(shù)據(jù)庫技術(shù)是當(dāng)今數(shù)據(jù)信息管理的最新技術(shù)，它的進(jìn)展已經(jīng)成為先進(jìn)信息技術(shù)的重要組成部分，是現(xiàn)代計算機(jī)信息系統(tǒng)和計算機(jī)應(yīng)用系統(tǒng)的基礎(chǔ)和核心。數(shù)據(jù)庫技術(shù)最初產(chǎn)生于２０世紀(jì)6０年月中期,依據(jù)數(shù)據(jù)模型的進(jìn)展，可以劃分為三個階裂:第一代的網(wǎng)狀、層次數(shù)據(jù)庫系統(tǒng)：其次代的關(guān)系數(shù)據(jù)庫系統(tǒng)；第三代的以面對對象模型為主要特征的數(shù)據(jù)庫系統(tǒng)。第一代數(shù)據(jù)庫的代表是1969年IＢM公司研制的層次模型的數(shù)據(jù)庫管理系統(tǒng)IMS。以及70年月美國數(shù)據(jù)庫系統(tǒng)語言協(xié)商ＣODAＳYＬ下屬數(shù)據(jù)庫任務(wù)組DＢＴG提議的網(wǎng)狀模型。層次模型的數(shù)據(jù)庫管理系統(tǒng)是定向有序樹，網(wǎng)狀模型對應(yīng)的是有向圖.其次代數(shù)據(jù)庫的主要特征是支持關(guān)系數(shù)據(jù)模型，它具有以下特點：(1）關(guān)系模型概念單一，實體和實體之間的聯(lián)系用關(guān)系來表示；（2）以關(guān)系數(shù)學(xué)為基礎(chǔ);（３）數(shù)據(jù)的物理存儲和存取路徑對用戶不透明;（4）關(guān)系數(shù)據(jù)庫語言是非過程化的.第三代數(shù)據(jù)庫消滅于上世紀(jì)8０年月,是科學(xué)技術(shù)進(jìn)步和商業(yè)領(lǐng)域需求的必定產(chǎn)物。第三代數(shù)據(jù)庫技術(shù)呈現(xiàn)出阿絡(luò)化、智能化、標(biāo)準(zhǔn)化和超大型化的進(jìn)展趨勢,它具有以下特征：（1）支持?jǐn)?shù)據(jù)管理、對象管理和知識管理；（2）保持和繼承了其次代數(shù)據(jù)庫系統(tǒng)的技術(shù)；(3）對其它系統(tǒng)開放。支持?jǐn)?shù)據(jù)庫語言標(biāo)準(zhǔn),支持標(biāo)準(zhǔn)網(wǎng)絡(luò)協(xié)議。具有良好的可移植性，可連接性、可擴(kuò)展性和互操作性。（二)嵌入式數(shù)據(jù)庫嵌入式數(shù)據(jù)庫系統(tǒng)是指支持移動計算或某種特定計算模式的數(shù)據(jù)庫管理系統(tǒng),它通常與操作系統(tǒng)和簡略的應(yīng)用集成在一起，運行在嵌入式或移動設(shè)備上。嵌入式實時數(shù)據(jù)庫技術(shù)涉及數(shù)據(jù)庫、實時系統(tǒng)、分布式計算以及移動通信等多個學(xué)科，已成為數(shù)據(jù)庫技術(shù)進(jìn)展的一個新方向嵌入式數(shù)據(jù)庫系統(tǒng)能夠和嵌入式操作系統(tǒng)有機(jī)地結(jié)合在一起，為應(yīng)用開發(fā)人員供應(yīng)有效的本地數(shù)據(jù)管理手段，同時供應(yīng)各種定制條件和方法。國外Syｂase、Orａcle和IBM已經(jīng)為移動和嵌入式計算提出了業(yè)界領(lǐng)先的解決方案,國內(nèi)也已經(jīng)開發(fā)出了多個嵌入式數(shù)據(jù)庫。這些嵌入式數(shù)據(jù)庫系統(tǒng)一般對資源要求較低,占用內(nèi)存空間較小，從幾十K到幾百Ｋ不等;并支持C語言AＰI函數(shù)和標(biāo)準(zhǔn)ＳＱL子集的開發(fā)接口，并供應(yīng)了數(shù)據(jù)同步的功能。隨著計算機(jī)技術(shù)和通信技術(shù)的進(jìn)展，嵌入式數(shù)據(jù)庫技術(shù)會在軌道交通、移動通信、工業(yè)掌握等越來越多的領(lǐng)域得到應(yīng)用.（三)實時數(shù)據(jù)庫實時數(shù)據(jù)庫(RＴDＢ：RealTｉｍeDaｔaＢaｓe）是數(shù)據(jù)和事務(wù)都有顯式定時限制的數(shù)據(jù)庫,其系統(tǒng)的正確性不僅依靠于事務(wù)的規(guī)律結(jié)果，還依靠于規(guī)律結(jié)果產(chǎn)生的時間。RTＤB是數(shù)據(jù)庫技術(shù)的一個進(jìn)展分支，它最早消滅在1988年3月的ACMSＩGＭＯＤRecord的一期?？?同時這也標(biāo)志著實時系統(tǒng)領(lǐng)域與數(shù)據(jù)庫領(lǐng)域融合的開頭，標(biāo)志著實時數(shù)據(jù)庫這個新興討論領(lǐng)域的確立。隨后，一個成熟的討論群體逐漸消滅，尤其是美國、英國、德國、瑞典等國對RTDB的討論格外關(guān)注。此后,世界范圍內(nèi)消滅了大批有關(guān)實時數(shù)據(jù)庫方面的論文和原型系統(tǒng)。繼而又消滅很多成功的實驗系統(tǒng),有的甚至已商品化，典型的有HiPＡＣ、ZipRTＤBMS等系統(tǒng).與此同時，國內(nèi)對于ＲTDB的討論起步雖然稍晚，基本上是在上世紀(jì)80年月末、90年月初才開頭，但是進(jìn)展卻格外之快，目前己經(jīng)有了很多成功的實時數(shù)據(jù)庫實驗系統(tǒng)?，F(xiàn)代的ＲTＤB技術(shù)適用于處理不斷更新變化的數(shù)據(jù)及具有時間限制的實時事務(wù)。它是實時系統(tǒng)和數(shù)據(jù)庫技術(shù)相結(jié)合的產(chǎn)物，討論人員盼望利用數(shù)據(jù)庫技術(shù)來解決實時系統(tǒng)中的數(shù)據(jù)管理問題,同時利用實時技術(shù)為實時數(shù)據(jù)庫供應(yīng)時間驅(qū)動調(diào)度和資源安排算法。然而,實時數(shù)據(jù)庫并非實時系統(tǒng)和數(shù)據(jù)庫在概念、結(jié)構(gòu)和方法上的簡潔集成,而需要針對不同的應(yīng)用需求與應(yīng)用特點，對實時數(shù)據(jù)模型、實時事務(wù)調(diào)度與資源安排策略、實時數(shù)據(jù)查詢語言、實時數(shù)據(jù)通信等大量問題進(jìn)深化的理論討論。進(jìn)入二十一世紀(jì)以來，RＴDＢ己經(jīng)成為現(xiàn)代數(shù)據(jù)庫討論的主要方向,SangH［13]習(xí)相關(guān)數(shù)據(jù)庫與實時操作系統(tǒng)內(nèi)核相結(jié)合,討論了對實時數(shù)據(jù)庫并發(fā)處理的靈敏掌握；Kanｇ［14］對實際環(huán)境中RTDB的性能評估進(jìn)行了試驗與討論；Jｉsu［l５］設(shè)計了以管理實時數(shù)據(jù)庫性能的一個RTDB簡略掌握模型；Nero［１6］使用有色Pｅtri網(wǎng)對時數(shù)據(jù)庫的周期處理與并發(fā)掌握進(jìn)行了分析和討論。目前，RTＤＢ技術(shù)已經(jīng)形成了一個系統(tǒng)體系，RTＤB技術(shù)的討論也朝著系統(tǒng)化與多元化的方向不斷前進(jìn).三、系統(tǒng)需求以及設(shè)計問題的提出CBＴＣ系統(tǒng)是一個具有很高實時性要求的嵌入式系統(tǒng),傳統(tǒng)的企業(yè)級數(shù)據(jù)庫如Orａｃlｅ、Sｙbase等在實時嵌入式環(huán)境下很難發(fā)揮作用，尤其在實時性要求很高的掌握系統(tǒng)(如ＣＢTC系統(tǒng)）中，傳統(tǒng)數(shù)據(jù)庫更顯得無能為力,所以構(gòu)建嵌入式實時數(shù)據(jù)庫系統(tǒng)成為了嵌入式開發(fā)中必須解決的問題。在CBTC系統(tǒng)中，嵌入式實時數(shù)據(jù)庫系統(tǒng)以高牢靠性、高平安性、高實時性和高信息吞吐量為目標(biāo)，對ＤSU的設(shè)計提出了很高的要求。DSU數(shù)據(jù)庫即嵌入式實時數(shù)據(jù)庫是嵌入式實時數(shù)據(jù)庫系統(tǒng)（DＳU）的基礎(chǔ)和底層架構(gòu)，需要針對選用的實時操作系統(tǒng)和嵌入式硬件平臺設(shè)計合理的數(shù)據(jù)模型和物理結(jié)構(gòu)。本文依托的CBＴC項目采納VxWorks實時操作系統(tǒng)和平安計算機(jī)平臺進(jìn)行系統(tǒng)設(shè)計,因此ＤＳU數(shù)據(jù)庫的開發(fā)基于VxＷo(hù)rks實時操作系統(tǒng)和平安計算機(jī)平臺，并要在此基礎(chǔ)上能夠滿ＣBＴC系統(tǒng)與各個子系統(tǒng)的功能和需求.CBTＣ系統(tǒng)是以移動閉塞模式掌握列車運行的,列車在線路上行駛時,列車的位置不是分段(如軌道電路)的,而是連續(xù)的，說明線路數(shù)據(jù)是有序的，DSＵ數(shù)據(jù)庫要能夠?qū)@種位置連續(xù)的軌道線路進(jìn)行描述.列車在行駛過程中，車載掌握器VOＢC需要通過DSＵ數(shù)據(jù)庫進(jìn)行列車定位，而區(qū)域掌握器ＺＣ需要通過ＤSU數(shù)據(jù)庫來完成列車移動授權(quán)(MA：ＭovｅmenｔAuｔｈority)的計算，列車自動防護(hù)（ATP：AutｏmaticTrainPrｏtection)功能也需要DＳＵ數(shù)據(jù)庫的支持基于上述系統(tǒng)功能與需求,本文以ＣＢTＣ項目為背景,對DSＵ數(shù)據(jù)庫的設(shè)計與構(gòu)建進(jìn)行討論，對DSU數(shù)據(jù)庫的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和關(guān)系模型進(jìn)行了討論與實現(xiàn)，使DSＵ數(shù)據(jù)庫適合CBTＣ系統(tǒng)的嵌入式環(huán)境,不僅能夠很好地對線路進(jìn)行描述,還能夠滿意系統(tǒng)以及各個子系統(tǒng)的功能需求，并為將來的ＤSU實時數(shù)據(jù)庫管理系統(tǒng)的設(shè)計打下基礎(chǔ)。四、DＳU數(shù)據(jù)庫在ＣBＴC系統(tǒng)中的作用CＢＴC系統(tǒng)作為一個先進(jìn)的列車運行掌握系統(tǒng),需要一個統(tǒng)一數(shù)據(jù)庫來實現(xiàn)整個系統(tǒng)的調(diào)度和統(tǒng)一，數(shù)據(jù)庫存儲單元DSU是其重要的組成部分。CBＴC系統(tǒng)是具有很高的實時性要求的嵌入式系統(tǒng)，因此DＳＵ是一種嵌入式實時數(shù)據(jù)庫管理系統(tǒng)(ＲＴDBS：Ｒeａｌ-TimeDatａbaseSysｔem)，ＤSＵ數(shù)據(jù)庫是一種嵌入式實時數(shù)據(jù)庫（RTDB:Rｅal一TｉｍeＤａt(yī)aｂａse）。數(shù)據(jù)庫存儲單元DSU位于CBＴC數(shù)據(jù)通信系統(tǒng)的骨干網(wǎng)上，通過骨干網(wǎng)與其它子系統(tǒng)相連，圖4－1是ＤＳＵ在CBTＣ系統(tǒng)中的接口框圖。它表明白DSU子系統(tǒng)與其它子系統(tǒng)的相互關(guān)系。其中，ＤＳＵ與VＯBC和ZC共同構(gòu)成ATＣ系統(tǒng)（AutomaticTrainControlSystem）的平安掌握部分。各個設(shè)備之間的通信是通過非平安的數(shù)據(jù)通信系統(tǒng)DCＳ來完成的數(shù)據(jù)庫存儲單元對整個信號系統(tǒng)的數(shù)據(jù)庫進(jìn)行管理，是CBTC系統(tǒng)的平安組成部分之一。圖4-1DSU在ＣBTC系統(tǒng)中的接口框圖Figur４－１theinterｆaｃeｓｏfＤＳＵinCＢTCsysteｍDSU存儲著CBTC系統(tǒng)內(nèi)全部子系統(tǒng)所使用的全部數(shù)據(jù)信息和配置文件,數(shù)據(jù)庫包括靜態(tài)數(shù)據(jù)庫、動態(tài)數(shù)據(jù)庫、配置數(shù)據(jù)庫和兼容性數(shù)據(jù)庫等.靜態(tài)數(shù)據(jù)庫是一個格外強(qiáng)大、靈敏的數(shù)據(jù)庫,它允許系統(tǒng)對用戶的不同需求做出響應(yīng)；它供應(yīng)了線路描述（軌道線路特征等信息），也供應(yīng)允許系統(tǒng)實現(xiàn)不同功能的系統(tǒng)構(gòu)成(如防淹門的位置以及關(guān)閉區(qū)域)。動態(tài)數(shù)據(jù)庫存儲軌道線路上的各種l|缶時線路信息和掌握信息,這些信息可以被ＡTS設(shè)置與修改。配置數(shù)據(jù)庫包含各個子系統(tǒng)如ZC和VＯＢC以及系統(tǒng)中的各種信號設(shè)備的配置信息和變量參數(shù),每個子系統(tǒng)都具有特定的子系統(tǒng)配置數(shù)據(jù)庫，它們被用于初始扮裝載，使每個子系統(tǒng)在啟動時有足夠的引導(dǎo)信息。兼容性數(shù)據(jù)庫包括了子系統(tǒng)使用的軟件、接口和數(shù)據(jù)庫版本之聞全部許可的兼容性,規(guī)定TＣBTC系統(tǒng)中每個子系統(tǒng)的軟件類型、軟件特征,與其它系統(tǒng)的接口特征以及對應(yīng)該子系統(tǒng)應(yīng)用的數(shù)據(jù)庫版本號。本文討論的簡略對象為靜態(tài)數(shù)據(jù)庫、動態(tài)數(shù)據(jù)庫和配置數(shù)據(jù)庫。五、基于二叉樹的CＢＴC數(shù)據(jù)庫構(gòu)建與搜尋算法線路描述即線路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的構(gòu)建是DSU數(shù)據(jù)庫設(shè)計的首要問題,是數(shù)據(jù)庫整體構(gòu)建的基礎(chǔ)，依據(jù)CBTC系統(tǒng)中列車掌握的特點以及城市軌道線路特征，本文運用圖論知識和二叉樹建立DSU數(shù)據(jù)庫線路網(wǎng)絡(luò)模型，利用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識討論線路數(shù)據(jù)存儲結(jié)構(gòu)，并結(jié)合圖、二叉樹相關(guān)算法探究DSＵ數(shù)據(jù)庫的有效搜尋算法。樹型結(jié)構(gòu)是一類格外重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用。樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種組織機(jī)構(gòu)都可以用樹來形象表示。樹在計算機(jī)領(lǐng)域中也得到了廣泛應(yīng)用,如在編譯程序中,可用樹來表示源程序的語法結(jié)構(gòu)。又如在數(shù)據(jù)庫系統(tǒng)中，樹形結(jié)構(gòu)也是信息的重要組織形式之一。定義1樹（tｒee）是無環(huán)連通無向圖。樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹數(shù)稱為結(jié)點的度（degrｅｅ).度為0的結(jié)點稱為葉子（1eaｆ)或終端結(jié)點。度數(shù)不為０的結(jié)點稱為非終端結(jié)點或分支結(jié)點.定義2樹也是n（n≥Ｏ)個結(jié)點的有限集。在任意一棵非空樹中:(１）有且僅有一個特定的稱為根（rooｔ)的結(jié)點；（2）當(dāng)開>I時,其余結(jié)點可分為ｍ（ｍ>O)個不相交的有限集互，互，…,乏,其中每個集合本身又是一棵樹,稱為根的子樹（subee）。定義3結(jié)點的子樹的根稱為該結(jié)點的孩子(ｃhilｄ),相應(yīng)地該結(jié)點稱為孩子的雙（ｐａrｅｎt）。同一個雙親的孩子之間互稱兄弟（ｓiｂｌing)。結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的全部結(jié)點，反之，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。定義4結(jié)點的層次(１ｅｖel）從根開頭定義起，根為第一層，根的孩子為其次層。若菜結(jié)點在第z層,則其子樹的根就在ｌ+1層.樹中結(jié)點的最大層數(shù)稱為樹的深度（deｐth）或高度。定義５森林(fｏｒesｔ）是m(m≥o）棵互不相交的樹的集合。對樹中每個結(jié)點而言,其子樹的樹，否則稱為無序樹。二叉樹（biｎarytrｅe)［21,23１是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點),并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。如圖5—1所示.集合即為森林。定義6如果將樹中結(jié)點的各子樹看成從左至右是有次序的（即不能互換),則稱該樹為有序圖5-1二叉樹規(guī)律上二叉樹有五種基本形態(tài)：①空二叉樹;②只有一個根結(jié)點的二叉樹;③右子樹為空的二叉樹;④左子樹為空的二叉樹；⑤完全二叉樹.滿二叉樹：在一棵二叉樹中,如果全部分支結(jié)點都存在左子樹和右子樹,并且全部葉子結(jié)點都在同一層上，這樣的二叉樹稱為滿二叉樹。完全二叉樹:如果一棵深度為k,有n個結(jié)點的二叉樹中各結(jié)點能夠與深度為k的挨次編號的滿二叉樹從1到n標(biāo)號的結(jié)點相對應(yīng)的二叉樹稱為完全二叉樹.二叉樹結(jié)點問的拓?fù)潢P(guān)系在數(shù)據(jù)庫中集中反映為二叉樹的數(shù)據(jù)結(jié)構(gòu)，二叉樹一般有兩種數(shù)據(jù)存儲結(jié)構(gòu)：（１）挨次存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素即將完全二叉樹上編號為ｉ的結(jié)點元素存儲在如上定義的一維數(shù)組中下標(biāo)為i—1的重量中.例如圖５-2中(a）所示為圖５－1中（a）所示完全二叉樹的存儲結(jié)構(gòu)。對于一般二叉樹,則應(yīng)將其每個結(jié)點與完全二叉樹上的結(jié)點相對比，存儲在一維數(shù)組的相應(yīng)重量中，圖5-２中(b)所示的二叉樹的挨次存儲結(jié)構(gòu)如圖5－1中（b）所示,圖中以“0"表示不存在的結(jié)點。由此可見，這種挨次存儲結(jié)構(gòu)僅適用于完全二叉樹。圖５—2二叉樹的挨次存儲結(jié)構(gòu)(2）鏈