[發明專利]一種樹形結構中數據的處理方法和系統

無效

• 申請號: 201210350548.X
• 申請日: 2012-09-19
• 公開（公告）號: CN102867059A
• 公開（公告）日: 2013-01-09
• 發明（設計）人: 付正全;劉成平;劉正偉
• 申請（專利權）人: 浪潮（北京）電子信息產業有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 栗若木;曲鵬

技術領域

本發明涉及計算機應用領域，尤其涉及一種樹形結構中數據的處理方法和系統。

背景技術

在各種基于關系數據庫的應用系統開發中，我們往往需要存儲樹型結構的數據，而很多時候我們需要用到多個樹形結構的模型，目前針對單一樹形結構有很多流行的方法，如鄰接列表模型(The?Adjacency?List?Model)、左右值編碼法等，在此基礎上也有很多人針對不同的需求做了相應的改進，但總是在某些方面存在的各種各樣的缺陷，下面分別以這兩種存儲方法為例進行說明。

首先，鄰接列表模型(The?Adjacency?List?Model)在大多數編程語言中，他運行很慢，效率很差。這主要是“遞歸”造成的，每次查詢節點都要訪問數據庫。每次數據庫查詢都要花費一些時間，這讓函數處理龐大的樹時會十分慢；造成這個函數不是太快的第二個原因可能是使用的語言。不像Lisp這類語言，大多數語言不是針對遞歸函數設計的。對于每個節點，函數都要調用他自己，產生新的實例。于一個5層的樹，你可能同時要運行5個函數副本。對于每個函數都要占用一塊內存并且需要一定的時間初始化，這樣處理大樹時遞歸就很慢了。圖1為現有技術中采用鄰接列表管理樹形結構的示意圖。

其次，左右值編碼法按照先序遍歷的次序進行編號，在消除遞歸的前提下實現了無限分級，而且查詢條件是基于整型數字比較的，效率很高。可以進行先序列表，添加，修改，刪除，同層平移等常規操作，基本滿足需求。但是經過仔細研究這種方法也有很大的缺點：由于這種左右值編碼的方式和常見的阿拉伯數字直觀排序不同，再加上節點在樹中的層次，順序不能直觀顯示出來，而必須通過簡單的公式計算后得到，需要花費一定的時間對其數學模型進行深入理解。而且，采用該方案編寫相關存儲過程，新增，刪除，同層平移節點需要對整個樹進行查詢修改，由此導致的代碼復雜度，耦合度較高，修改維護的風險較高。圖2為現有技術中采用左右值編碼法進行樹形結構管理的示意圖。

以上兩種方法都不是針對多個樹形結構的存儲，對多個樹形結構的處理能力相當有限。那么理想中的樹型結構應具備哪些特點呢？數據存儲冗余小、直觀性強；適用于多個樹形結構的情況；方便返回整個樹型結構數據；可以很輕松的返回某一子樹(方便分層加載)；快整獲以某節點的祖譜路徑；插入、刪除、移動節點效率高等等。

發明內容

本發明提供一種樹形結構中數據的處理方法和系統，要解決的技術問題是如何提高數據處理的高效性與可靠性。

為解決上述技術問題，本發明提供了如下技術方案：

一種樹形結構中數據的處理方法，所有樹形結構的根節點以遞增的數字進行編號，其中每個樹形結構的根節點為第一級，深度為i的葉子節點為第i+1級，其中i為大于或等于2的整數，其中同一樹形結構中深度為i的節點中同屬于深度為i-1的節點的多個節點以遞增的數字進行編號，且樹形結構上的每個節點配置有一個序號字段，其中一個節點的序號由該節點的全部父節點在各自深度的編號按照深度從小到大的順序排序而成，其中兩個父節點的編號通過一預先設置的符號隔開，其中：

采用順序存儲的方式將樹形結構的所有節點存儲在數據庫中；

根據節點的編號對樹形結構的所有節點對應的數據進行處理。

優選的，所述方法還具有如下特點：所述預先設置的符號為下劃線。

優選的，所述方法還具有如下特點：根據節點的編號對樹形結構的所有節點對應的數據進行處理，包括：

當對該樹形結構進行增加節點操作時，且該節點為葉子節點，則按照該葉子節點的位置為該節點編號，并按照順序存儲方式存儲到數據庫；如果該節點不是葉子節點，則根據新增節點處的節點序號，依次修改該葉子節點的孩子節點的父節點域；

當對該樹形結構進行增加樹操作時，則新增加一個根節點，并向該新增加的樹中添加節點。

優選的，所述方法還具有如下特點：根據節點的編號對樹形結構的所有節點對應的數據進行處理，包括：

當對該樹形結構進行刪除節點操作時，刪除該節點以及所有編號以節點的編號開頭的節點；

當對該樹形結構進行刪除樹操作時：刪除所有編號以此根節點的編號開頭的節點。

優選的，所述方法還具有如下特點：根據節點的編號對樹形結構的所有節點對應的數據進行處理，包括：

如果是對所有樹的遍歷，樹形結構的所有節點采用順序存儲的方式存儲在數據庫中，僅進行一次查詢，并將查詢結果按照樹形結構上的節點的編號排序輸出；

如果是對某棵樹的遍歷，查詢以根節點的編號開頭的所有數據記錄；