一種用二維表實現的樹的存儲、訪問的方法
2023-05-28 07:05:46 1
專利名稱：一種用二維表實現的樹的存儲、訪問的方法
技術領域：
本發明涉及一種樹狀數據結構的配置、存儲方法，尤其涉及通訊領域的協議棧數據配置、存儲和管理。包括對現有的路由數據配置和在3G產品中採用的IP承載配置，象WCDMA的RNC，MSC-S，MGW，SGSN，GGSN等，CDMA2000中PCF，PDSN等網元的基於IP協議棧承載的配置。
背景技術：
現有的關於協議承載配置的數據一般有兩種主要的存儲方式1.基於鍊表的樹狀結構+連續緩衝區的實現方式請參照中國專利文獻CN 00125204.6號本方式由樹形索引結構(如圖1)和單一的緩衝區組成。樹節點指示該節點的配置類型、數據長度、數據緩衝區地址等屬性。其中數據緩衝區地址指示了該配置參數在緩衝區的位置，數據長度指示該參數在緩衝區中佔用的連續空間大小。這樣有幾個缺點(1)對配置參數表使用現有的面向對象的資料庫的各種約束機制以及操作非常困難；(2)在較長時間內，如果對配置表進行增、刪操作過多，會造成緩衝區的碎片。(3)對於樹結構節點數目和數據緩衝區的容量和大小不可以靈活配置。不可以實現容量的動態升級。
2.純粹用關係表實現方式這種方式只適合一些具有很少的協議數據配置的系統，並且由於在表設計時要關心到具體的數據屬性，協議數據配置的可擴充性較差，因為協議數據分布包括多個層次，屬於應用的協議數據配置需求變化(屬於關係表的設計變化)較快，所以使用的也不是很好。
發明內容
本發明要解決的技術問題是克服現有技術中的協議配置數據管理的局限性，提出了一種結合二維表實現樹結構的快速存儲、訪問和管理的方法。
本發明中的二維表包括容量表、容量表索引、樹形結構索引表、多個二維緩衝數據表以及各種狀態表(這些狀態表描述了各種表當前的佔用和空閒狀態)。
本發明用二維表實現的樹的存儲、訪問的方法，包括以下步驟(1)創建二維表，包括容量配置表，用於描述系統中表的容量；樹結構關係表，用於描述樹結構的關係；數個數據存儲區表，用於記錄樹結構中的節點屬性值；(2)加載數據並對數據進行維護，包括增加、刪除、修改和查找數據，以及由此引起的相關操作；(3)對數據進行管理，包括數據的加載、同步、數據更改通知和觀察部分。
所述的容量配置表欄位屬性如下表所示
所述的樹結構關係表欄位屬性如下表所示
所述的數據存儲區表欄位屬性如下表所示
所述的用二維表實現的樹的存儲、訪問的方法，還包括創建容量表，創建容量索引數據；加載容量數據，加載索引。
所述的用二維表實現的樹的存儲、訪問的方法，還包括創建樹結構表，創建樹結構節點索引數據；創建數據存儲區表，為各個數據存儲區創建索引欄位；加載樹結構和數據存儲區的數據，加載各個索引欄位。
所述的增加的步驟包括(1)同步或異步發送增加請求消息；(2)接收進程根據請求消息中的參數查找父節點記錄標誌；如果不存在父節點，在系統中自動增加一個虛的父節點記錄；(3)查看要增加的節點記錄是否已經存在；已經存在，返回錯誤；(4)在樹結構的二維表中增加一個記錄，在記錄中描述其父節點記錄或兄弟節點記錄的相關信息，同時更改相關的表項；(5)根據要增加的節點記錄的節點屬性值的類型和長度，選擇不同的數據緩衝區，在選中的數據緩衝區表中申請一個空閒的記錄空間存放當前的數據；(6)同步返回操作結果。
所述的刪除的步驟包括(1)同步或異步發送刪除請求消息；(2)接收進程根據請求消息中的參數查找節點記錄標誌；(3)查看要刪除的節點記錄是否存在；不存在，返回錯誤；(4)刪除找到的節點，釋放節點對應的數據緩衝區資源；(5)在關係表中查詢該節點是否有孩子節點記錄，循環刪除所有的孩子及其下的節點記錄；(6)循環判斷當前節點的父節點記錄有沒有存在的必要，沒有的話刪除該節點記錄。
(7)同步返回操作結果；所述的修改的步驟包括
(1)同步或異步發送修改數據請求消息；(2)接收進程根據請求消息中的參數查找父節點記錄標誌；(3)查看要修改的節點記錄是否已經存在；已經存在，修改相應的屬性值，主要是數據緩衝區表的數據維護，可能的操作包括修改原來的數據緩衝區中的內容(以前的數據和新的數據在同一個緩衝區中時)；從原來的數據緩衝區中刪除記錄項(新的數據不再需要在緩衝區中存放，釋放以前的記錄緩衝區數據)；新申請一個數據緩衝區增加屬性(以前的數據沒有存放在緩衝區表中，現在需要存放在緩衝區表中)；刪除原來的數據表項，增加新的數據表項(以前的數據和新的數據長度要求在不同的緩衝區中)四種操作；(4)同步返回結果所述的查找包括簡單查找和插入查找，簡單查找是按照樹結構關係在表中一層一層記錄地查找，直接返回查找的結果；插入查找是從根節點開始查找，遇到不存在的節點，插入記錄，一直到最終的記錄節點位置。
所述數據的加載採用二維表記錄加載方式；數據的同步同樣採用表記錄的增加和刪除來實現，在數據的加載和同步的過程中，樹結構數據和緩衝區中的數據相對獨立，同樣在加載、同步數據緩衝區中的數據時，只負責標誌出本數據緩衝區的標誌欄位。
所述數據的更改通知是以一個完整的事務應用為單位進行數據的更改通知，該事務定義就是一次協議數據的修改，事務完成後再進行相關數據的更改通知。
所述數據的觀察採用兩種方式(1)類似於二維表的記錄顯示方式；(2)採用樹型的結構顯示協議數據，將存儲在內模式中的數據轉化成數據的邏輯模式顯示給應用用戶查看。
採用本發明所述方法，與現有技術相比，在配置數據靈活性、緩存機制簡化等方面取得了進步，達到了靈活配置數據並可以最大化使用面向對象資料庫原有機制的效果，提高了處理效率和處理的靈活性和穩定性。體現在以下幾個方面(1)結合了關係表和樹結構的優點；一方面配置參數使用了現有的面向對象的資料庫的各種約束機制，可以按記錄來進行控制，包括表記錄的預刪除、預增加、刪除、增加等觸發器的編寫，使得應用場合更加廣泛，操作容易；另一方面擺脫了關係表和應用的相關性，方便了應用數據配置的可擴充性。
(2)對配置表的操作，不會造成緩衝區的碎片。系統在啟動時會根據容量表中分配的數據計算出各個數據緩衝區表的大小(在系統啟動後，這是一個定值)，在每一個數據緩衝區表中存放的數據長度是固定大小，基於表的操作就是基於表中記錄的操作，一個節點記錄的數據只會保存在一個緩衝表記錄中，釋放節點記錄也會釋放該緩衝表中對應的記錄，記錄和記錄之間是緊湊的，不會產生碎片。這是一個犧牲內存(靜態分配內存)來實現避免內存碎片的方法。採用了該方法，可以很好地提高系統長期運行的穩定性。
(3)容量和大小可以靈活配置，可以做到版本不升級實現容量的升級，很好的提高了系統的可維護性。由於在3G產品中，運用到IP承載設計的網元很多，如果容量不能靈活配置，各個網元的配置勢必有很大差別，這些差別體現在代碼中對系統的穩定性和可維護性都有一定的影響。採用容量表來配置網元容量將這種網元的差別屏蔽在用戶配置上，系統比較靈活；另外，對於一個固定網元，根據用戶需要可能會要求容量的升級，採用了該方法後，可以做到用戶配置增加容量而不用更換軟體版本。
圖1是一個現有樹狀結構示意圖；圖2是圖1的樹狀結構轉換後對應的二叉樹示意圖；圖3是該樹狀結構在關係表中的存儲方式及其對應的數據存儲位置示意圖；圖4是在關係表中增加一個節點數據的流程；圖5是在關係表中刪除一個節點及其相關的節點的流程；圖6是在關係表中刪除一個節點數據的流程；圖7是在關係表中修改一個節點數據的流程；圖8是在關係表中查詢一個節點和節點值的流程；圖9是在關係表中查詢一個節點的流程；圖10是在關係表中查詢並追加節點的流程。
具體實施例方式
在附圖中，各英文單詞的含義如下DWORD表示一個數據是整數數據類型；STREAM表示一個字符串碼流格式的數據類型；Fathercode表示當前要查找的起始節點位置；Lplocate表示從起始節點位置到要操作節點的全路徑。
另外，說明書中縮略語意義如下GPRSGeneral Packet Radio System，無線分組系統RNCRadio NetWork Controller，無線網絡控制MSC-SMobile Switching Center -SERVER，移動交換中心-服務端MGWMedia Gateway，媒體網關SGSNServing GPRS Support Node，GPRS支持服務節點GGSNGateway GPRS Support Node，GPRS支持網關節點PCFPacket Control Function，分組控制功能PDSNPacket Data Service Node，分組數據服務節點本發明所述協議數據配置的方法如下一.數據結構描述按功能在系統中創建了三種二維表一個容量配置表描述了系統中表的容量；一個樹結構關係表描述了樹結構的關係；數個數據存儲區表記錄樹結構中的節點屬性值。
1.容量配置表欄位屬性如表一所示表一.描述了系統中容量表中的各個欄位及其意義
表一中各個欄位的說明
前三個欄位wModule，dwNetype，dwModuletype是通用的欄位，可以用來區分多模塊的容量配置ucInfoType＝0時表示該記錄描述的是樹結構節點容量配置關係，緊跟著wTreeNodeNum欄位描述了系統中樹結構節點的總的個數(容量)；其它欄位無效ucInfoType＞0時表示該記錄描述的是相應的數據緩衝區的容量配置關係，wTreeNodeNum欄位無效，wBufferSize描述了該數據緩衝區每一個記錄的大小，wBufferNum描述了該數據緩衝區記錄的個數；2.樹結構欄位屬性如表二所示表二.描述了系統中樹狀關係表中的各個欄位及其記錄間的相互關係
結構說明本發明針對圖1所示現有的樹形索引結構，通過演化轉變成圖2所示二叉樹索引結構，然後進一步的處理變成圖3所示關係表索引結構，圖2隻是這個完整過程中的一個演進階段，是為了的系統的完整性而增加，增加該圖便於對整個過程的認識，在本發明中不做贅述。
從圖3中可以看到，NODEINDEX(節點標誌)欄位在表中的值是唯一的，用該欄位可以做為該表的唯一主索引。
3.數據存儲區表欄位屬性如表三所示
表三.描述了系統中各個數據緩衝區的存儲方式
結構說明Nodeindex標誌了該數據緩衝區位置；從圖3中可以看到，該欄位在表中的值是唯一的，用該欄位可以做為該表的唯一主索引。
Nodevalue一個可變數組，長度由R_CONST表中的記錄來確定；可以實現一個可變長度和可變容量的數據緩衝區。
二.系統的運行第一步二維表的創建，數據加載本步驟又可以包括下列步驟1.創建容量表，創建容量索引數據；2.加載容量數據，加載索引；根據容量表中的數據進行如下的操作創建樹結構表，創建樹結構節點索引數據；創建數據存儲區表，為各個數據存儲區創建索引欄位；加載樹結構和數據存儲區的數據，加載各個索引欄位。
至此，整個內存數據表創建，加載完畢；可以進行以下的操作。
第二步.樹節點的維護加載完數據，可以對表中的樹結構進行維護，包括對表中記錄的增、刪、改、查，以及由此引起的相關的一系列操作，比如刪除一個表中的樹的記錄節點引起相應的孩子節點記錄項的刪除，同時會刪除數據存儲區中的內容。
增加一個數據節點的過程參考附圖4中的步驟1.同步(或異步)發送增加請求消息；2.接收進程根據請求消息中的參數查找父節點記錄標誌(如果不存在父節點，在系統中自動增加一個虛的父節點記錄。)3.查看要增加的節點記錄是否已經存在(已經存在，返回錯誤)；4.在樹結構的二維表中增加一個記錄，在記錄中描述其父節點記錄或兄弟節點記錄的相關信息，同時更改相關的表項，(如果是父節點的第一個子孩子，要修改當前記錄的父節點欄位和父節點記錄的左孩子節點欄位；否則的話只要修改當前記錄前一個兄弟記錄的右孩子欄位)；5.根據要增加的節點記錄的節點屬性值的類型和長度，選擇不同的數據緩衝區，在選中的數據緩衝區表中申請一個記錄空間存放當前的數據。
6.同步返回操作結果；刪除一個數據節點的過程參考附圖5，附圖6中的步驟1.同步(或異步)發送刪除請求消息；2.接收進程根據請求消息中的參數查找節點記錄標誌；3.查看要刪除的節點記錄是否存在(不存在，返回錯誤)；4.刪除找到的節點，刪除節點對應的數據緩衝區中的數據；5.在關係表中查詢該節點是否有孩子節點記錄，循環刪除所有的孩子及其下的節點記錄；6.循環判斷當前節點的父節點記錄有沒有存在的必要，沒有的話刪除該節點記錄。(節點是虛節點記錄類型並且沒有孩子記錄表示當前的記錄沒有存在的必要，可以刪除之，但第一層根節點除外)7.同步返回操作結果；修改一個數據節點的過程參考附圖7中的步驟1.同步(或異步)發送修改數據請求消息；2.接收進程根據請求消息中的參數查找父節點記錄標誌(如果不存在父節點記錄，返回操作失敗及失敗原因。)3.查看要修改的節點記錄是否已經存在(已經存在，修改相應的屬性值，主要是數據緩衝區表的數據維護，可能的操作包括修改原來的數據緩衝區中的內容；從原來的數據緩衝區中刪除記錄項；新申請一個數據緩衝區增加屬性；刪除原來的數據表項，增加新的數據表項等四種操作。如果該節點記錄不存在，按照增加節點記錄的方式在當前的節點下新生成一個節點記錄)；4.同步返回結果查看一個表數據節點值的過程參考圖8中的步驟1.同步(或異步)發送查詢數據請求消息；2.接收進程根據請求消息中的參數查找節點記錄標誌(如果不存在節點記錄，返回操作失敗及失敗原因。)
3.根據得到的節點記錄數據項中的存儲數據屬性和長度判斷該節點數據存放的數據緩衝區及其在緩衝區中的位置，然後到相應的緩衝區中取出數據。
4.同步返回結果在上面的描述中，每一個操作都需要對表中的記錄定位，所以查詢操作的效率比較重要，系統中為每一個表創建了HASH索引，採用HASH和名字比較的方法，提高了查找效率。根據系統中的需求不同，我們提供了兩種方式的查找簡單查找和插入查找。
簡單查找用戶的操作都會引發簡單查找的動作，其目的是為了得到要操作對象的節點記錄。
簡單查找一個數據節點的過程參考附圖9中的步驟1.根據輸入路徑第一個欄位在表中記錄的根節點下查找匹配的記錄；2.如果沒有找到記錄則返回失敗，否則路徑去掉第一個欄位，如果路徑為空，則返回找到的表記錄的節點標誌；3.循環1，2操作；插入查找用戶的增加一個節點操作可能會引起插入查找的過程，其目的是為了在簡單查找的基礎上，如果一個對象不存在，不再返回失敗，而是增加一個虛路徑。
插入查找一個數據節點的過程參考附圖10中的步驟1.根據輸入路徑第一個欄位在表中記錄的根節點下查找匹配的記錄；2.如果沒有找到記錄則跳到4執行，否則路徑去掉第一個欄位，如果路徑為空，則返回找到的表記錄的節點標誌；3.循環1，2操作；4.根據路徑中第一個欄位在表中增加相應的虛節點；路徑去掉第一個欄位5.循環執行4，一直到路徑為空；第三步.數據的管理數據的管理包括數據的加載、同步、數據更改通知和觀察部分。
在通訊領域中，由於採用了分布處理，並且為了提高系統的穩定性，很多單板採用1+1熱備份方式，因此數據的加載、同步的處理顯得更加複雜、重要。
協議數據物理存儲結構以表方式組織，因此數據的加載採用二維表記錄加載方式；數據的同步同樣採用表記錄的增加和刪除來實現，在行數據的加載和同步的過程，不關心具體的記錄數據的相互依賴關係。樹結構數據和緩衝區中的數據相對獨立，比如在加載、同步如附圖1所示的數據時，可以按照附圖3所示的記錄位置來存放數據，也可以按實際運行中雜亂的位置存放數據，此時不關心具體的數據存放的數據緩衝區中的位置，只在表中記錄好緩衝區中的標誌欄位DATAHANDLE和DATAMARK，同樣在加載、同步數據緩衝區中的數據時也不用關心其對應的樹結構中的節點位置，只負責標誌出本數據緩衝區的標誌欄位Nodeindex，這兩種表的關係只在系統運行時通過上面的三個欄位和緩衝區在系統中的句柄來對應起來。
協議的數據更改通知主要是指協議數據成功修改後需要通知其他的應用；由於在協議數據中增加一個節點，其存儲的二維表中可能會增加或刪除多條記錄，因此不能以傳統的二維表記錄的增加和刪除觸發數據的通知，而以一個完整的事務應用為單位進行數據的更改通知，該事務定義就是一次協議數據的修改，事務完成後再進行相關數據的更改通知。
協議數據的觀察可以採用兩種方式(1)類似於二維表的記錄顯示方式，該方式對具體的協議數據含義觀察不直觀，但對於資料庫專業人員可以直觀的查看協議數據內模式的存儲結構，便於表容量的調整，以及一些索引的組織。(2)採用樹型的結構顯示協議數據，將存儲在內模式中的數據轉化成數據的邏輯模式顯示給應用用戶查看。
權利要求
1.一種用二維表實現的樹的存儲、訪問的方法，其特徵在於，包括步驟一創建二維表，包括容量配置表，用於描述系統中表的容量；樹結構關係表，用於描述樹結構的關係；數個數據存儲區表，用於記錄樹結構中的節點屬性值；步驟二加載數據並對數據進行維護，包括增加、刪除、修改和查找數據，以及由此引起的相關操作；步驟三對數據進行管理，包括數據的加載、同步、數據更改通知和觀察部分。
2.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，所述的容量配置表欄位屬性如表所示
3.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，所述的樹結構欄位屬性如表所示
4.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，所述的數據存儲區表欄位屬性如表所示
5.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟一還包括創建容量表，創建容量索引數據；加載容量數據，加載索引。
6.如權利要求1或5所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟一還包括創建樹結構表，創建樹結構節點索引數據；創建數據存儲區表，為各個數據存儲區創建索引欄位；加載樹結構和數據存儲區的數據，加載各個索引欄位。
7.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟二中所述的增加的步驟包括(1)同步或異步發送增加請求消息；(2)接收進程根據請求消息中的參數查找父節點記錄標誌；如果不存在父節點，在系統中自動增加一個虛的父節點記錄；(3)查看要增加的節點記錄是否已經存在；已經存在，返回錯誤；(4)在樹結構的二維表中增加一個記錄，在記錄中描述其父節點記錄或兄弟節點記錄的相關信息，同時更改相關的表項；(5)根據要增加的節點記錄的節點屬性值的類型和長度，選擇不同的數據緩衝區，在選中的數據緩衝區表中申請一個記錄空間存放當前的數據；(6)同步返回操作結果。
8.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟二中所述的刪除的步驟包括(1)同步或異步發送刪除請求消息；(2)接收進程根據請求消息中的參數查找節點記錄標誌；(3)查看要刪除的節點記錄是否存在；不存在，返回錯誤；(4)刪除找到的節點，刪除節點對應的數據緩衝區中的數據；(5)在關係表中查詢該節點是否有孩子節點記錄，循環刪除所有的孩子及其下的節點記錄；(6)循環判斷當前節點的父節點記錄有沒有存在的必要，沒有的話刪除該節點記錄。(7)同步返回操作結果；
9.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟二中所述的修改的步驟包括(1)同步或異步發送修改數據請求消息；(2)接收進程根據請求消息中的參數查找父節點記錄標誌；(3)查看要修改的節點記錄是否已經存在；已經存在，修改相應的屬性值，主要是數據緩衝區表的數據維護，可能的操作包括修改原來的數據緩衝區中的內容；從原來的數據緩衝區中刪除記錄項；新申請一個數據緩衝區增加屬性；刪除原來的數據表項，增加新的數據表項四種操作；(4)同步返回結果
10.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟二中所述的查找包括簡單查找和插入查找，簡單查找是按照樹結構關係在表中一層一層記錄地查找，直接返回查找的結果；插入查找是從根節點開始查找，遇到不存在的節點，插入記錄，一直到最終的記錄節點位置。
11.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟三中所述數據的加載採用二維表記錄加載方式；所述數據的同步同樣採用表記錄的增加和刪除來實現，在數據的加載和同步的過程，樹結構數據和緩衝區中的數據相對獨立，同樣在加載、同步數據緩衝區中的數據時，只負責標誌出本數據緩衝區的標誌欄位。
12.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟三中所述數據的更改通知是以一個完整的事務應用為單位進行數據的更改通知，該事務定義就是一次協議數據的修改，事務完成後再進行相關數據的更改通知。
13.如權利要求1所述的用二維表實現的樹的存儲、訪問的方法，其特徵在於，步驟三中所述數據的觀察採用兩種方式(1)類似於二維表的記錄顯示方式；(2)採用樹型的結構顯示協議數據，將存儲在內模式中的數據轉化成數據的邏輯模式顯示給應用用戶查看。
全文摘要
本發明涉及一種用二維表實現的樹的存儲、訪問的方法，包括(1)創建二維表，包括容量配置表，用於描述系統中表的容量；樹結構關係表，用於描述樹結構的關係；數個數據存儲區表，用於記錄樹結構中的節點屬性值；(2)加載數據並對數據進行維護，包括增加、刪除、修改和查找數據，以及由此引起的相關操作；(3)對數據進行管理，包括數據的加載、同步、數據更改通知和觀察部分。本發明應用於通訊領域，在配置數據靈活性、緩存機制簡化等方面取得了進步，達到了靈活配置數據並可以最大化使用面向對象資料庫原有機制的效果，提高了處理效率和處理的靈活性和穩定性。
文檔編號G06F17/30GK1545048SQ200310113660
公開日2004年11月10日 申請日期2003年11月17日 優先權日2003年11月17日
發明者鄭宇 , 蔡輝, 業緒進, 鄭 宇 申請人:中興通訊股份有限公司