基於樹形數據結構節點的插入的方法和存儲裝置的製作方法

2023-10-09 06:15:09 1

專利名稱：基於樹形數據結構節點的插入的方法和存儲裝置的製作方法
技術領域：
本發明涉及存儲技術領域，特別涉及基於樹形數據結構節點的插入的方 法和存儲裝置。
背景技術：
樹形數據結構中的樹由自然數個節點(Node )基於一定的關係結合構成。 在任意一棵非空的樹中每個節點都具有用於唯一識別節點的關鍵碼值。在二 叉樹中上述關鍵碼值一般會用鍵(Key)來表示。
二叉樹是構成樹的每個節點最多只能有兩個子節點的一種樹形數據結 構；在二叉樹中任取一個節點作為父節點，為了區分當前節點的兩個子節點， 兩個子節點可以分別稱為父節點的左子節點和右子節點，在二叉樹中所有的 節點與其子節點基於的關係可以是左子節點大於父節點，父節點大於右子節點。
在二叉樹中插入節點的方法可以是將待插節點的關鍵碼值與二叉樹的 根節點的關鍵碼值比較，若待插節點的關鍵碼值小於根節點的關鍵碼值，則
進入左子樹，否則進入右子樹。在左子樹或右子樹裡再將待插節點的關鍵:碼
值與子樹的根節點的關鍵碼值比較，如此進行下去，直到把待插入點插入到 二叉樹裡作為一個新的葉子節點。如果上述二叉樹的形狀是固定的(有時也 稱為樹的高度固定)，上述4巴待插入點插入到二叉樹裡作為一個新的葉子節點
可以理解為將待插節點插入到了一個虛擬的位置，然後對已經存在的節點 和上述待插節點按照左子節點大於父節點，父節點大於右子節點的關係進行 搬移。
發明人在實現本發明的過程中發現在形狀固定的樹裡，插入新的節點 需要對已經存在的節點進行搬移，需要搬移的節點的數量會隨著樹的高度成 指數增長，從而導致節點的插入時間迅速增加；現有樹形數據結構中節點插 入的速度慢。

發明內容
本發明實施例要解決的技術問題是提供基於樹形數據結構節點的插入的方法和存儲裝置，提高節點插入的速度。
為解決上述技術問題，本發明所提供的基於樹形數據結構節點的插入方
法實施例可以通過以下技術方案實現
根據待插節點的關鍵碼值在主樹中查找最近主樹節點，所述最近主樹節 點的關鍵碼值小於且最接近待插節點的關鍵碼值；所述主樹的根節點初始化 為具有最小的關鍵碼值；其中，所述主樹包括父節點、所述父節點的左子節 點和所述父節點的右子節點，且所述左子節點大於所述父節點，所述父節點 大於所述右子節點；
以最近主樹節點的外部指針指向的從樹作為當前從樹，判斷當前從樹是 否已滿，
若是，則在當前從樹中任意選擇一個節點作為拆分節點，將拆分節點插 入到主樹中作為新建主樹節點，為新建主樹節點分配新建從樹，並將新建主 樹節點的外部指針指向新建從樹，將當前從樹中位於拆分節點左側的全部節 點搬移到新建從樹中，然後執行查找最近主樹節點，
若否，則將待插節點插入到當前從樹中。
本發明實施例還提供了另 一種基於樹形數據結構節點的插入方法，包括 根據待插節點的關鍵碼值在主樹中查找最近主樹節點，所述最近主樹節
點的關鍵碼值大於且最接近待插節點的關鍵碼值；所述主樹的根節點初始化 為具有最大的關鍵碼值；所述主樹中的左子節點大於父節點，父節點大於右 子節點；
以最近主樹節點的外部指針指向的從樹作為當前從樹，判斷當前從樹是 否已滿，
若是，則在當前從樹中任意選擇一個節點作為拆分節點，將拆分節點插 入到主樹中作為新建主樹節點，為新建主樹節點分配新建從樹，並將新建主 樹節點的外部指針指向新建從樹，將當前從樹中位於拆分節點右側的全部節 點搬移到新建從樹中，然後執行查找最近主樹節點；
若否，則將待插節點插入到當前從樹中。
本發明實施例還提供了 一種存儲裝置，包括
從樹存儲單元，用於存儲從樹；主樹存儲單元，用於存儲主樹，主樹中的節點具有指向從樹的外部指針。
本發明實施例還提供了一種通信設備，包括上述存儲裝置。 上述技術方案具有如下有益效果將樹形數據結構的樹分成主樹和從樹
降低了樹的高度，減少了節點插入的時間，提高了節點的插入速度。


圖l為本發明實施例中樹形數據結構示意圖； 圖2為現有技術中的多叉樹示意圖； 圖3為本發明實施例一節點插入的方法流程示意圖； 圖4為本發明實施例 一查找最近主樹節點的方法流程示意圖； 圖5為本發明實施例二節點查找的方法流程示意圖； 圖6為本發明實施例二查找最近主樹節點的方法流程示意圖； 圖7為本發明實施例三刪節點的方法流程示意圖； 圖8為本發明實施例四節點插入的方法流程示意圖； 圖9為本發明實施例四查找最近主樹節點的方法流程示意圖； 圖IO為本發明實施例五存儲裝置結構示意圖； 圖11為本發明實施例六插入裝置的裝置結構示意圖； 圖12為本發明實施例六的插入裝置加入平衡單元後的結構示意圖； 圖13為本發明實施例七查找裝置結構示意圖； 圖14為本發明實施例八刪除裝置結構示意圖； 圖15為本發明實施例九合併裝置結構示意圖； 圖16為本發明實施例十插入裝置結構示意圖； 圖17為本發明實施例十二應用環境的結構示意圖； 圖18為本發明實施例十二現場可編程門陣列和存4諸器的結構示意圖； 圖19為本發明實施例十二查找數據的方法流程示意圖； 圖20為本發明實施例十二更新數據的方法流程示意圖； 圖21為本發明實施例十二另 一更新數據的方法流程示意圖。
具體實施例方式
本發明實施例要解決的技術問題是提供一種基於樹形數據結構節點的插 入的方法和存儲裝置，提高節點的插入的速度。在對本發明實施例進行前對本發明實施例中，樹形數據結構所使用的名 稱進行一個說明，以二叉樹為例，如圖l所示，其中，圓可以表示為節點，圓中的數字可以表示為節點的關鍵碼值；可以看到深度為BranchO、 Branch 1、 Branch 2的三層節點基於一定的關係(用實線示意)結合構成一棵樹，稱為主 樹；深度為Branch3、 Branch 4的兩層節點基於一定的關係(用虛線示意)結 合構成了7棵樹，每顆樹都可以稱為從樹；主樹中的節點具有指向與本節點對 應的從樹的外部指針(用帶箭頭的線表示)。可以理解的是，上述主樹的高度、 從樹的高度、主樹中每個節點外部指針的數量、從樹的數量都是可以根據需 要存儲的數據規模等條件來設定，圖l不應理解為對本發明實施例的限定。另 外，在後續實施例的說明中無特別說明，稱節點大或小均指關鍵碼值大或小； 在本發明實施例中，主樹和從樹的高度設定後，數據的插入刪除等操作不改 變主樹和從樹能夠具有的最大高度；本發明實施例中的樹形數據結構是有序樹形數據結構，為方便說明在本 發明實施例中將左定義為大的一側，右定義為小的一側，可以理解的是左和 右是一個相對的概念，左和右僅表示大小關係不應理解為對本發明實施例的 限定，可以從主樹中看到根據這樣的大小關係建立的樹形結構中，任選一個 節點其左側的節點都大於該節點，右側的節點都小於該節點；另外對樹形數據結構中的一些概念進行簡單的介紹，如圖l所示，以主樹為例節點16在主樹中沒有上層節點，節點30在從樹中沒有上層節點，可以稱 節點16為主樹的根節點，節點30為節點30所在從樹的根節點；與節點24有直接聯繫的上層節點(節點16)為節點24的父節點，節點24 則為節點16的子節點，可以看到節點8也是節點16的子節點，為了區分節點24 和節點8，可以稱節點24為節點16的左子節點，節點8為節點16的右子節點； 另外，具有父子關係的節點在邏輯上是相鄰的，稱為相鄰節點；可以看到左子節點、右子節點還可以有自己的子節點，所有的子節點 可以稱為節點16的子孫；節點16的左子節點(節點24)和節點24的子孫，也 是樹形的結構，可以稱為節點16的左子樹，同理右子節點(節點8)和節點8 的子孫，可以稱為節點16的右子樹；節點28、節點20等節點在主樹中沒有子節點，可以稱為主樹的葉子節點。 如圖2所示，為一4果多叉樹，可以看到深度為BranchO、 Branch l的兩層節 點基於一定的關係(用實線示意)構成多叉樹，與二叉樹類似，不同點在於 多叉樹中每個節點可以有多個子節點；在多叉樹中取一個節點(節點16)作 為當前節點，參考二叉樹，可以將當前節點的子節點分為左子節點(虛線的 左邊)和右子節點(虛線右邊)；與二叉樹不同的是這時左子節點和右子節 點都可以有多個，當前節點與其子節點的關係依然可以參考二叉樹左子節 點大於當前節點，當前節點大於右子節點；另外，在多個左子節點和多個右 子節點也可以按照一定的順序進行排序，圖2中從左到右排序依據從大到小的 原則進行(圖2中左子節點排序依次為節點32、節點31、節點29、節點27,右 子節點排序依次為節點23、節點21、節點19、節點8),當然也可以從小到大 排序。可以理解的是在多叉樹節點的插入、查找、刪除都是可以參考二叉樹 進行的，在本發明實施例的說明中均以二叉樹為例，可以理解的是，二叉樹 不應理解為對本發明實施例的限定，本發明實施例中所述的樹也可以是多叉 樹。實施例一，如圖3所示，本發明實施例提供了一種基於樹形數據結構節點 的插入方法，包括以下步驟步驟301:根據待插節點的關4t碼值在主樹中查找最近主樹節點，上述最 近主樹節點的關鍵碼值小於且最接近於待插節點的關鍵碼值；上述主樹的根 節點初始化為具有最小的關鍵碼值；其中，上述主樹包括父節點、上述父節 點的左子節點和上述父節點的右子節點，且上述左子節點大於上述父節點， 上述父節點大於上述右子節點在一棵樹中，插入的節點的關鍵碼值會在一個數域內取值，上述最小關 鍵碼值可以是上述數域中最小的數，也可以是小於上述數域中的所有數的任 意值；上述查找最近主樹節點的方法是在主樹中查找關鍵碼值小於且最接近 於待插節點的關鍵碼值的節點；後續實施例中將給出一種查找最近主樹節點 的實現方式；步驟302:以最近主樹節點的外部指針指向的從樹作為當前從樹；步驟303:判斷當前從樹是否已滿，若是，則進入步驟304,若否則進入 步驟305;上述當前從樹是否已滿，可以是上述當前從樹的使用率是否達到設定 的使用率，若是，則確定上述當前從樹已滿，若否，則確定上述當前從樹未 滿；也可以是上述當前從樹是否已經沒有空節點了，若是，則確定當前從 樹已滿，若否，則確定當前從樹未滿。步驟304:在當前從樹中任意選擇一個節點作為拆分節點，將拆分節點插 入到主樹中作為新建主樹節點，為新建主樹節點分配新建從樹，並將新建主 樹節點的外部指針指向新建從樹，將當前從樹中位於拆分節點左側的全部節 點搬移到新建從樹中，然後進入步驟301;步驟305:將待插節點插入到當前從樹中。本發明實施例所述的插入方法保證了從樹的高度不會隨著數據的插入過 度增長，從而減少了後續節點插入的時間，提高了節點的插入速度。具體地，如圖4所示，本發明實施例給出了上述根據待插節點的關鍵碼值 在主樹中查找最近主樹節點，以最近主樹節點的外部指針指向的從樹作為當 前從樹的一種實現方式，以二叉樹為例，包括讀取主樹根節點的外部指針，設置變量為上述主樹根節點的外部指針， 將上述根節點作為當前節點；判斷待插節點關鍵碼值是否大於上述主樹節點的關鍵碼值，設置上述變 量為上述主樹節點的左子節點的外部指針，將上述左子節點作為當前節點， 若否，將上述當前節點的右子節點作為當前節點；判斷當前節點是否為葉子節點，若是，以上述變量指向的從樹作為當前 從樹。上述實施方式，還還可以包括判斷當前節點是否為空或無效，若是，以上述變量指向的從樹作為當前 從樹。具體還可以包括以下步驟步驟401:讀取主樹根節點的外部指針，設置變量為上述主樹根節點的外 部指針，將上述主樹根節點作為當前主樹節點；假設上述變量用Pointer表示，則可以為Pointer =主樹根節點的外部指針； 步驟402:判斷當前主樹節點是否為空或無效，若是，進入步驟403,若 否，進入步驟404;步驟403:以上述變量指向的從樹作為當前從樹；步驟404:判斷待插節點關鍵碼值是否大於上述當前主樹節點的關鍵碼 值，若是，進入步驟405,若否，進入步驟406;步驟405:設置上述變量為上述當前主樹節點的左子節點的外部指針(可 以表示為PointeF左子節點的外部指針)，將上述左子節點作為當前主樹節 點，進入步驟407;若這裡的樹為多叉樹，那麼上述設置上述變量為上述當前主樹節點的左 子節點的外部指針之前還包括查找當前主樹節點的左子節點中小於且最接 近於待查節點的節點，然後設置上述變量為上述查找到的主樹節點的左子節 點。 -步驟406:將上述當前主樹節點的右子節點作為當前主樹節點(此時Pointer 沒有改變)，進入步驟407。若這裡的樹為多叉樹，那麼上述將當前主樹節點的右子節點作為當前主 樹節點之前還包括查找上述當前主樹節點的右子節點鐘小於且最接近於待 查節點的節點，然後將上述查找到的當前主樹節點的右子節點作為當前主樹 節點。步驟407:判斷上述當前主樹節點是否為上述當前主樹節點所在的主樹的 葉子節點；若是，進入步驟403;若否，進入步驟402;上述實施方式提供了根據待插節點的關鍵碼值在主樹中查找最近主樹節 點，以最近主樹節點的外部指針指向的從樹作為當前從樹的一種實現方式， 可以理解的是實現的方案還有很多，上述舉例不應理解為實現方案的窮舉， 故上述實施方式不應理解為對本發明實施例的限定。進一步地，還可以對主樹進行平衡才喿作；經平tf操作後主樹的有效節點 在主樹中具有最小的深度。具體地，觸發對主樹進行平衡操作的條件可以是在上述主樹的某一深 度的節點處於未滿狀態，且上述某一深度非上述主樹的最下層時，執行對主樹進行平衡操作；或在最下層節點以上的各深度節點中，為空的數量達到設定值時，執行對 主樹進行平衡操作。可以理解的是觸發對主樹進行平衡的條件還可以有很多，例如還可以 是在存儲系統處於閒置狀態時對主樹進行平衡操作；故上述兩種舉例不應理 解為對本發明實施例的限定。上述實施方式通過對主樹進行平衡操作可以降低主樹的高度，從而進一 步提高插入速度。實施例二，如圖5所示，本發明實施例還提供了一種基於樹形數據結構節 點的查找方法，可以包括以下步驟步驟501:根據待查節點的關鍵碼值在主樹中查找待查找節點；若主樹中 不存在上述待查節點，則查找最近主樹節點；上述最近主樹節點的關鍵碼值 'J 、於且最接近待插節點的關鍵碼值；若主樹中存在節點與待查節點具有相同的關鍵碼值，這時就已經找到了 待查找節點，查找流程可以結束；步驟502:以上述最近主樹節點的外部指針指向的從樹作為當前從樹；步驟503:在上述當前從樹中查找上述待查找節點。上述查找的實現方式中，由於降低了樹的高度，節點的查找速度也會決。具體地，如圖6所示，本發明實施例給出了上述才艮據待查節點的關4定碼值 在主樹中查找最近主樹節點，以最近主樹節點的外部指針指向的從樹作為當 前從樹的一種實現方式，以二叉樹為例，包括以下步驟步驟601:讀取主樹根節點的外部指針，設置變量為上述主樹根節點的外 部指針，將上述主樹根節點作為當前主樹節點；假設上述變量用Pointer表示，則可以為Pointer =主樹根節點的外部指針；步驟602:判斷當前主樹節點是否為空或無效，若是，進入步驟603,若 否，進入步驟604;步驟603:以當前變量指向的從樹作為當前從樹；步驟604:判斷待查節點關鍵碼值是否大於上述當前主樹節點的關鍵碼 值，若是，進入步驟605，若否，進入步驟606;步驟605:設置上述變量為上述當前主樹節點的左子節點的外部指針(可 以表示為Pointe產左子節點的外部指針)，將上述左子節點作為當前主樹節 點，進入步驟607;步驟606:將上述當前主樹節點的右子節點作為當前主樹節點(此時Pointer 沒有改變)，進入步驟607。步驟607:判斷上述當前主樹節點是否為上述當前主樹節點所在的主樹的 葉子節點；若是，進入步驟603;若否，進入步驟602;上述實施方式提供了才艮據待查節點的關鍵碼值在主樹中查找最近主樹節 點，以最近主樹節點的外部指針指向的從樹作為當前從樹的一種實現方式， 可以理解的是實現的方案還有很多，上述舉例不應理解為實現方案的窮舉， 故上述實施方式不應理解為對本發明實施例的限定。實施例三，如圖7所示，本發明實施例還提供了一種基於樹形數據結構節 點的刪除方法，可以包括以下步驟步驟701:根據待刪節點的關鍵碼值在主樹中查找待刪節點，若主樹中不 存在上述待刪節點，則查找最近主樹節點；上述最近主樹節點的關4定碼值小 於且最接近待刪節點的關鍵碼值；若主樹中存在節點與待刪節點具有相同的關鍵碼值，這時就已經找到了 待刪節點，可以直接進入步驟704;步驟702:以最近主樹節點的外部指針指向的從樹作為當前從樹；步驟703:在上述當前從樹中查找上述待刪節點；步驟704:刪除上述查找到的待刪節點。可以看到，本實施例的實現方法可以在實施例二的基礎上進行，首先查 找待刪節點，然後刪除待刪節點。若刪除的節點為主樹節點時，可以對主樹 節點指向的從樹節點和下層節點進行重新排序，排序的過程可以是將這些節 點重新插入；若刪除的節點為從樹的節點，則可以對該乂人樹的節點進行排序。上述實施例中，由於樹的高度降低了，能夠更快地查找到待刪節點，從 而加快了刪除節點的速度。進一步地，樹中的節點被刪除後會出現一些未滿的樹，還可以進行樹的 合併操作，具體可以為主樹中的第一正整數個相鄰的節點指向的從樹中的有效節點數，小於第
二正整數個從樹能夠容納的節點數時(上述第一正整數大於第二正整數)
將上述主樹中的第一正整數個相鄰節點，及上述第一正整數個節點分別
指向的從樹，合併為第二正整數個主樹節點，以及與上述第二正整數個主 樹節點指向的從樹。
舉例說明，假設上述第一正整數為2，上述第二正整數為l則
當主樹中兩個相鄰的節點指向的從樹中的有效節點數，小於一個從樹能 夠容納的節點數時；
將上述主樹中，兩個相鄰節點中較大的主樹節點，及其指向的從樹中的 有效節點，插入上述兩個相鄰節點中較'』、的主樹節點指向的從樹中。
可以理解的是，上述對樹的合併過程是可以為將需要合併的主樹節點， 以及上述主樹節點指向的從樹的有效節點，再次插入本發明實施例的樹形數 據結構中的過程。另外觸發進行樹的合併的條件可以有很多種，例如還可以 是在存儲系統處於閒置狀態時進行，可以理解的是上述觸發進行樹的合併的 條件的舉例不應理解為對本發明實施例的限定。
上述實施例中通過合併處於未滿狀態的從樹可以釋放出一些存儲資源， 可以^提高存儲空間的利用率。
實施例四，如圖8所示，本發明實施例還提供了另一種樹形數據結構節點 插入的方法，可以包括以下步驟
步驟801:才艮據待插節點的關鍵:碼值在主樹中查找最近的主樹節點，上述 最近的主樹節點的關鍵碼值大於且最接近於待插節點的關鍵碼值；上述主樹 的根節點初始化為具有最大的關鍵碼值；其中，上述主樹包括父節點、上述 父節點的左子節點和上述父節點的右子節點，且上述左子節點大於上述父節 點，上述父節點大於上述右子節點
在一棵樹中，插入的節點的關鍵碼值會在一個數域內取值，上述最大關 鍵碼值可以是上述數域中最大的數，也可以是大於上述數域中的所有數的任 意值；
步驟802:以最近主樹節點的外部指針指向的從樹作為當前從樹； 步驟803:判斷當前從樹是否已滿，若是，則進入步驟804，若否，則進入步驟805;
步驟804:在當前從樹中任意選擇一個節點作為拆分節點，將拆分節點插 入到主樹中作為新建主樹節點，為新建主樹節點分配新建從樹，並將新建主 樹節點的外部指針指向新建從樹，將當前從樹中位於拆分節點右側的全部節 點搬移到新建從樹中，然後進入步驟801;
步驟805:將待插節點插入到當前從樹中。
上述實施例中，將樹形數據結構的樹分成主樹和從樹降低了樹的高度， 減少了數據插入的時間，提高了節點的插入速度。
具體地，如圖9所示，本發明實施例給出了上述根據待插節點的關4走碼值 在主樹中查找最近主樹節點，以最近主樹節點的外部指針指向的從樹作為當 前從樹的一種實現方式，以二叉樹為例，包括以下步驟
步驟901:讀取主樹根節點的外部指針，設置變量為上述主樹根節點的外 部指針，將上述^f艮節點作為當前節點；
假設上述變量用Pointer表示，則可以為Pointer =根節點的外部指針；
步驟902:判斷當前節點是否為空或無效，若是，進入步驟903,若否， 進入步驟904;
步驟903:以上述變量指向的從樹作為當前從樹；
步驟904:判斷待插節點關鍵碼值是否大於上述主樹節點的關鍵碼值，若 是，進入步驟906，若否，進入步驟905;
步驟905:設置上述變量為上述主樹節點的右子節點的外部指針(可以表 示為Pointer二左子節點的外部指針)，將上述右子節點作為當前節點，進入 步驟907;
步驟906:將上述當前節點的左子節點作為當前節點(此時Pointer沒有改 變)，進入步驟907。
步驟907:判斷上述當前節點是否為上述主樹的葉子節點；若是，進入步 驟903;若否，進入步驟902;
上述實施方式提供了根據待插節點的關鍵碼值在主樹中查找最近主樹節 點，以最近主樹節點的外部指針指向的從樹作為當前從樹的一種實現方式， 可以理解的是實現的方案還有很多，上述舉例不應理解為實現方案的窮舉，故上述實施方式不應理解為對本發明實施例的限定。
上述實施例四與實施一的方案具有的實現思想相同，區別點在於本實 施例中主樹的根節點的關4走碼值在進行初始化時設置為最大值。節點的查找 和刪除的方法與實施例一和實施例二相同，首先在主樹中查找待查/刪節點， 失敗後，查找最近主樹節點，然後在最近主樹節點的外部指針指向的從樹中 查找到待查/刪節點，然後刪除待刪節點。在此不再贅述。另，如果最近主樹 節點的外部指針指向了多棵從樹，可以參考多叉樹的插入、查找和刪除的方 法。
實施例五，如圖10所示，本發明實施例還提供了一種存儲裝置，包括 從樹存儲單元IOOI，用於存儲從樹；
主樹存儲單元1002,用於存儲主樹，主樹中的節點具有指向從樹的外部 指針；上述主樹的根節點初始化為具有最小的關鍵碼值，上述主樹中的左子 節點大於父節點，父節點大於右子節點。
可選地，上述從樹存儲單元和上述主樹存儲單元均為隨機存取存儲器。 當然採用其它類型的存儲器來存儲主樹或從樹也是可以的，本發明實施例對 此不作限定。
實施例六，如圖ll所示，本發明實施例還提供了一種插入裝置IIOO,上 述插入裝置包括
查找單元1101,用於根據待插節點的關鍵碼值在主樹中查找最近主樹節 點，在搬移單元1103將當前從樹中位於拆分節點右側的全部節點搬移到新建 從樹中後執行查找最近主樹節點，上述最近主樹節點的關鍵碼值d、於且最接 近待插節點的關鍵碼值；上述主樹的根節點初始化為具有最小的關鍵碼值； 上述主樹中的左子節點大於父節點，父節點大於右子節點；
判斷單元1102,用於以最近主樹節點的外部指針指向的從樹作為當前從 樹，判斷當前從樹是否已滿；
^:移單元1103,用於在當前從樹已滿時，在當前/人樹中任意選擇一個節 點作為拆分節點，將拆分節點插入到主樹中作為新建主樹節點，為新建主樹 節點分配新建從樹，並將新建主樹節點的外部指針指向新建從樹，將當前從 樹中位於拆分節點左側的全部節點搬移到新建從樹中；插入單元1104,用於在當前從樹未滿時，將待插節點插入到當前從樹中。
如圖12所示，上述插入裝置還可以包括'.
平衡單元1201，用於對主樹進行平衡處理。經平衡操作後主樹的有效節 點在主樹中具有最小的深度。
實施例七，如圖13所示，本發明實施例還^是供了一種查找裝置1300,包 括第一查找單元1301,用於根據待查節點的關鍵碼值在主樹中查找待查節 點，若主樹中不存在上述待查節點，則查找最近主樹節點；上述最近主樹節 點的關鍵碼值小於且最接近待插節點的關鍵碼值；若主樹中存在上述待查節 點，則在主樹中已經查找到需要查找的節點，查找流程結束；
待查節點查找單元1302，用於以上述最近主樹節點的外部指針指向的從 樹作為當前從樹；在上述當前/人樹中查找上述待查找節點。
上述查找裝置可以為現場可編程門陣列或專用集成電路；當然採用其 它類型的物理實體來實現上述查找裝置1300的功能也是可以的，對此本發明 實施例不作限定。
實施例八，如圖14所示，本發明實施例還^是供了一種刪除裝置1400包括
第二查找單元1401 ，用於根據待刪節點的關鍵碼值在主樹中查找待刪節 點，若主樹中不存在上述待刪節點，則查找最近主樹節點；上述最近主樹節 點的關鍵碼值'J 、於且最接近待刪節點的關鍵碼值；
待刪節點查找單元1402,用於以最近主樹節點的外部指針指向的從樹作 為當前從樹；在上述當前從樹中查找上述待刪節點；
刪除單元1403,刪除上述查找到的待刪節點。
實施例九，如圖15所示，本發明實施例還提供了一種合併裝置1500,包
括
檢測單元1501，用於檢測上述主樹中的第一正整數個相鄰的節點指向的 從樹中的有效節點數，小於第二正整數個從樹能夠容納的節點數，且上述第 一正整數大於第二正整數
合併單元1502:在檢測單元1501檢測結果為是時，用於將上述主樹中的 第一正整數個相鄰節點，及上述第一正整數個節點分別指向的從樹，合併為 第二正整數個主樹節點，以及與上述第二正整數個主樹節點指向的從樹。
1實施例十，如圖16所示，本發明實施例還提供了另一種插入裝置1600, 包括
查找單元1601，用於根據待插節點的關鍵碼值在主樹中查找最近的主樹 節點，在搬移單元1603將當前從樹中位於拆分節點右側的全部節點搬移到新 建從樹中後執行查找最近主樹節點，上述最近主樹節點的關鍵碼值大於且最 接近待插節點的關鍵碼值；上述主樹的根節點初始化為具有最大的關鍵碼值； 上述主樹中的左子節點大於父節點，父節點大於右子節點；
判斷單元1602,用於以最近主樹節點的外部指針指向的從樹作為當前從 樹，判斷當前從樹是否已滿，
搬移單元1603，若判斷單元1602判斷結果為是，則用於在當前從樹中任 意選擇一個節點作為拆分節點，將拆分節點插入到主樹中作為新建主樹節點， 為新建主樹節點分配新建從樹，並將新建主樹節點的外部指針指向新建從樹， 將當前從樹中位於拆分節點右側的全部節點搬移到新建從樹中；
插入單元1604，若判斷單元1602判斷結果為是否，則用於將待插節點插 入到當前從樹中。
實施例十一，本發明實施例還提供了一種通信設備，包括
實施例五所述的存儲裝置，和實施例六到實施例九所述的至少一個裝置； 或者，實施例五所述的存儲裝置，和實施例六到實施例九、實施例十所述的 至少一個裝置。
實施例十二，本發明實施例還提供了上述實施例一到實施例十一的方法 或裝置一個應用場景，如圖17所示，可以一併參考圖18，包括
現場可編程門陣列1703 ( Field-programmable gate array, FPGA ),上述現 場可編程門陣列1703也可以為專用集成電路(Application Specific Intergrated Circuits , ASIC);
現場可編程門陣列1703可以具有兩個接口 與中央處理器1701連接的管 理接口和與查找控制裝置1702連接的查找接口 ；上述查找控制裝置1702可以 為路由器的網絡處理器；
晶片內建隨機存取存儲器1704 ( Onchip RAM)可以集成於現場可編程門 陣列1703內部，在現場可編程門陣列1703的外部還可以有隨機存取存儲器1705 (Random-access memory ， RAM);晶片內建隨才踏取存儲器1704和隨機 存取存儲器1705，共同用於存儲主樹和從樹；在本實施例中，可以只有晶片 內建隨機存取存儲器1704,用於存儲主樹和從樹，也可以只有隨機存取存儲 器1705,用於存儲主樹和從樹；圖18中的虛線三角形為本發明實施例的樹在 晶片內建隨機存取存儲器1704和隨機存取存儲器1705存儲的一個示意，大致 表示了在所述晶片內建隨才錄M儲器1704和隨機存取存儲器1705中存儲的 樹的各部分的位置；
查找控制裝置1702可以通過查找接口向現場可編程門陣列1703發送查找 指令，然後通過查找接口接收查找的結果；上述查找過程的執行主體可以為 現場可編程門陣列1703,具體查找的實現，可以參考前述的方法或裝置實施 例來實現。
中央處理器1701可以通過管理埠向現場可編程門陣列1703發送管理樹 的命令，上述管理樹的命令可以為插入、或者刪除等命令；現場可編程門陣 列1703接收到管理樹的命令後，對樹進行管理；對樹管理的具體實現可以參 考前述的方法或裝置實施例插入、刪除等的實現。
本實施例中，中央處理器1701、現場可編程門陣列1703、晶片內建隨機 存取存儲器]704和隨機存取存儲器1705可以處於同一個通信設備中；查找控 制裝置1702可以與上述通信設備通過查找接口連接，處於上述通信設備的外 部。
本實施例中，現場可編程門陣列1703可以只有管理接口，此時，圖17中 的查找控制裝置1702是不必要的；現場可編程門陣列1703也可以只有查找接 口，此時，圖17中的中央處理器1701是不必要的。
在本實施例中，關鍵碼值可以是介質訪問控制(Media Access Control ， MAC)地址的值，也可是MAC地址與其它信息的組合；上述其它信息可以為 虛擬區域網(Virtual Local Area Network, VLAN)地址等，本實施例對上述 其它信息不作限定，可以理解的是，上述MAC地址、VLAN地址、MAC地址 與其它信息的組合的舉例不是關鍵碼值的類型的窮舉，不應理解為對本發明 實施例的限定。
本發明實施例還給出了 ，在路由器中使用實施例一到實施例十一中任意一種方法或裝置思想的實施例
如圖19所示，為一種從本發明實施例的樹形數據結構中查找數據的方法 實施例，可以包括以下步驟
步驟1901:路由器接收數據報文；
上述數據報文可以為在路由器的任意物理輸入埠輸入的數據4艮文；
步驟1902:路由器根據上述數據報文攜帶的需要查找的數據的關鍵碼值， 在主樹/從樹中查找與上述關4走碼值相同的節點；上述主樹和從樹可以存儲在 路由器的存儲器中；
上述步驟1902具體查找方法可以參考實施例二的方法；上述才艮文可以為 二層轉發數據報文，上述關鍵碼可以表示為MAC地址、也可以表示為MAC 地址和VLAN信息；
步驟1903:路由器讀取查找到的節點的數據信息，並將上述數據信息更 新到上述數據報文；
步驟1904:路由器將上述更新後的數據報文從上述查找到的節點的數據 信息指示的埠輸出。
如圖20所示，為一種更新本發明實施例的樹形數據結構中的數據的方法 實施例，可以包括以下步驟
步驟2001:路由器的埠接收協議報文，並將上述協議報文發送給CPU;
步驟2002: CPU獲得所述報文的關鍵碼值；獲得的方式可以是對協議報 文進行解析，得到關鍵碼值；
步驟2003: CPU發送插入命令給FPGA,命令將上述關鍵碼值的協議報文 插入到主樹/從樹中。具體的插入方法可以參考實施例一的方法。
上述協議報文可以是地址解析協議(Address Resolution Protocol, ARP ) 表項；當然上述協議報文也可以是其它類型的協議報文，本發明實施例對此 不作限定；
如圖21所示，為更新本發明實施例的樹形數據結構中的數據的另 一種方 法實施例，可以包括以下步驟
步驟2101:路由器的埠接收數據報文；步驟2102:根據上述數據報文的指示或上述數據報文的輸入埠信息， 發送插入消息給CPU;上述插入消息包含關鍵碼值；上述關鍵碼值為上述數 據報文的關鍵碼值；
步驟2103: CPU解析上述插入消息得到關鍵碼值，然後發送插入命令給 FPGA，命令將上述關鍵碼值的數據報文插入到主樹/從樹中。具體的插入方法 可以參考實施例 一 的方法。
上述數據報文可以是MAC表項；當然協議報文也可以是其它類型的數據 報文，本發明實施例對此不作限定。所述插入消息用於指示要在主樹/從樹中 插入數據。
在上述實施例中路由器採用樹形數據結構來實現大容量表項的插入，由 於本發明實施例中的樹形數據結構降低了樹的高度，可以提高表項的插入速率。
上述實施例中，將樹形數據結構的樹分成主樹和從樹降低了樹的高度， 減少了節點插入的時間，提高了節點的插入速度。由於樹的高度降低了，可 以更快的查找到待查節點、待刪節點，從而提高了查找節點和刪除節點的速 度。通過平衡主樹可以降低主樹的高度，從而進一步降低整棵樹的高度，提 高插入、查找、刪除節點的速度。另外通過對從樹的合併釋放存儲資源達到 了提高存儲空間利用率的效果。
本領域普通技術人員可以理解實現上述實施例方法中的全部或部分步驟 是可以通過程序來指令相關的硬體完成，所述的程序可以存儲於一種計算機 可讀存儲介質中，上述提到的存儲介質可以是存儲器(RAM)、內存、只讀存 儲器(ROM)、電可編程ROM、電可擦除可編程ROM、寄存器、硬碟、可移 動磁碟、CD-ROM、或技術領域內所公知的任意其它形式的存儲介質中。
以上對本發明實施例所提供的基於樹形數據結構節點的插入的方法和存
進行了闡述，以上實施例的說明只是用於幫助理解本發明的方法及其核心思 想；同時，對於本領域的一般技術人員，依據本發明的思想，在具體實施方 式及應用範圍上均會有改變之處，綜上所述，本說明書內容不應理解為對本 發明的限制。
權利要求
1、一種基於樹形數據結構節點的插入方法，其特徵在於，包括根據待插節點的關鍵碼值在主樹中查找最近主樹節點，所述最近主樹節點的關鍵碼值小於且最接近待插節點的關鍵碼值；所述主樹的根節點初始化為具有最小的關鍵碼值；其中，所述主樹包括父節點、所述父節點的左子節點和所述父節點的右子節點，且所述左子節點大於所述父節點，所述父節點大於所述右子節點；以最近主樹節點的外部指針指向的從樹作為當前從樹，判斷當前從樹是否已滿，若是，則在當前從樹中任意選擇一個節點作為拆分節點，將拆分節點插入到主樹中作為新建主樹節點，為新建主樹節點分配新建從樹，並將新建主樹節點的外部指針指向新建從樹，將當前從樹中位於拆分節點左側的全部節點搬移到新建從樹中，然後執行查找最近主樹節點，若否，則將待插節點插入到當前從樹中。
2、 根據權利要求l所述方法，其特徵在於，所述根據待插節點的關鍵碼 值在主樹中查找最近主樹節點，以最近主樹節點的外部指針指向的從樹作為 當前/人樹具體為讀取主樹根節點的外部指針，設置變量為所述主樹根節點的外部指針， 將所述^f艮節點作為當前節點；判斷待插節點關鍵碼值是否大於所述主樹節點的關鍵碼值，設置所述變 量為所述主樹節點的左子節點的外部指針，將所述左子節點作為當前節點， 若否，將所述當前節點的右子節點作為當前節點；判斷當前節點是否為葉子節點，若是，以所述變量指向的從樹作為當前 從樹。.
3、 根據權利要求2所述方法，其特徵在於，還包括 判斷當前節點是否為空或無效，若是，以所述變量指向的從樹作為當前從樹。
4、 根據權利要求l所述方法，其特徵在於，還包括對主樹進行平衡操作， 所述對主樹進行平衡操作包括在所述主樹的某一深度的節點處於未滿狀態，且所述某一深度非所述主樹的最下層時，執行對主樹進行平衡操作；或在最下層節點以上的各深度節點的為空的數量達到設定值時，執行對主 樹進行平衡操作。
5、 根據權利要求1至4任意一項所述方法，其特徵在於，所述當前從樹是 否已滿包括所述當前從樹的使用率是否達到設定的使用率，若是，則確定所述當前 從樹已滿，若否，則確定所述當前從樹未滿。
6、 根據權利要求1至4任意一項所述方法，其特徵在於，所述根據待插節 點的關鍵碼值在主樹中查找最近主樹節點之前還包括通過路由器的輸入埠接收報文，並獲得所述報文的關鍵碼值； 所述將待插節點插入到當前從樹中包括 將所述關鍵碼值的協議々艮文插入當前從樹中。
7、 根據權利要求1至4任意一項所述方法，其特徵在於，還包括 根據待查節點的關鍵碼值在主樹中查找待查節點，若主樹中不存在上述待查節點，則查找最近主樹節點；所述最近主樹節點的關鍵碼值小於且最接 近待插節點的關鍵碼值；以所述最近主樹節點的外部指針指向的從樹作為當前/人樹；在所述當前從樹中查找所述待查找節點；或還包括根據待刪節點的關鍵碼值在主樹中查找待刪節點，若主樹中不存在上述 待刪節點，則查找最近主樹節點；所述最近主樹節點的關鍵碼值小於且最接 近待刪節點的關鍵碼值；以最近主樹節點的外部指針指向的從樹作為當前從樹；在所述當前從樹中查找所述待刪節點；刪除所述查找到的待刪節點。
8、 根據權利要求7所述方法，其特徵在於，所述根據待查節點的關鍵碼 值在主樹中查找待查節點之前還包括通過路由器的輸入埠接收數據報文，並得到所述數據報文需要查找的 數據的關鍵碼值即為待查節點的關鍵碼值；所述在當前從樹中查找待查找節點之後還包括讀取查找到的節點的數據信息，並請上述數據信息更新到所述數據才艮文； 然後將所述更新後的數據報文從所述查找到的節點的數據信息指示的埠輸 出；和/或所述刪除所述查找到的待刪節點之後還包括當所述主樹中的第一正整數個相鄰的節點指向的從樹中的有效節點數， 小於第二正整數個從樹能夠容納的節點數，且所述第一正整數大於第二正整 數時將所述主樹中的第 一正整數個相鄰節點，及所述第一正整數個節點分別 指向的從樹，合併為第二正整數個主樹節點，以及與所述第二正整數個主 樹節點指向的從樹。
9、 根據權利要求8所述方法，其特徵在於，所述主樹中的第一正整數個 相鄰的節點指向的從樹中的有效節點數，小於第二正整數個從樹能夠容納的 節點數包括主樹中兩個相鄰的節點指向的從樹中的有效節點數，小於一個從樹能夠 容納的節點數；所述將主樹中的第一正整數個相鄰節點，及所述笫一正整數個節點分別 指向的從樹，合併為第二正整數個主樹節點，以及與所述第二正整數個主 樹節點指向的從樹具體為將所述主樹中，兩個相鄰節點中較大的主樹節點，及其指向的從樹中的 有效節點，插入所述兩個相鄰節點中較小的主樹節點指向的從樹中。
10、 一種基於樹形數據結構節點的插入方法，其特徵在於，包括 才艮據待插節點的關鍵碼值在主樹中查找最近主樹節點，所述最近主樹節點的關鍵碼值大於且最接近待插節點的關鍵碼值；所述主樹的根節點初始化 為具有最大的關鍵碼值；所述主樹中的左子節點大於父節點，父節點大於右 子節點；以最近主樹節點的外部指針指向的從樹作為當前從樹，判斷當前從樹是 否已滿，若是，則在當前從樹中任意選擇一個節點作為拆分節點，將拆分節點插 入到主樹中作為新建主樹節點，為新建主樹節點分配新建從樹，並將新建主樹節點的外部指針指向新建從樹，將當前從樹中位於拆分節點右側的全部節點搬移到新建從樹中，然後執行查找最近主樹節點； 若否，則將待插節點插入到當前從樹中。
11、 一種存儲裝置，其特徵在於，包括 從樹存儲單元，用於存儲從樹；主樹存儲單元，用於存儲主樹，主樹中的節點具有指向從樹的外部指針。
12、 如權利要求ll所述的存儲裝置，其特徵在於，所述存儲裝置還包括 查找單元，用於根據待插節點的關鍵碼值在主樹中查找最近主樹節點，所述最近主樹節點的關鍵碼值小於且最接近待插節點的關鍵碼值；所述主樹 的才艮節點初始化為具有最小的關鍵碼值；其中，所述主樹包括父節點、所述 父節點的左子節點和所述父節點的右子節點，且所述左子節點大於所述父節 點，所述父節點大於所述右子節點，判斷單元，用於以最近主樹節點的外部指針指向的從樹作為當前從樹， 判斷當前從樹是否已滿，搬移單元，若判斷單元判斷結果為是，則用於在當前從樹中任意選擇一 個節點作為拆分節點，將拆分節點插入到主樹中作為新建主樹節點，為新建 主樹節點分配新建從樹，並將新建主樹節點的外部指針指向新建從樹，將當 前從樹中位於拆分節點左側的全部節點搬移到新建從樹中，插入單元，若判斷單元判斷結果為是否，則用於將待插節點插入到當前 從樹中；或者， 所述存儲裝置還包括第一查找單元，根據待查節點的關鍵碼值在主樹中查找待查節點，若主 樹中不存在上述待查節點，則查找最近主樹節點；所述最近主樹節點的關4建 碼值、於且最接近待插節點的關鍵碼值，待查節點查找單元，用於以所述最近主樹節點的外部指針指向的從樹作 為當前從樹；在所述當前從樹中查找所述待查找節點；或者，所述存儲裝置還包括第二查找單元，用於根據待刪節點的關鍵碼值在主樹中查找待刪節點，若主樹中不存在上述待刪節點，則查找最近主樹節點；所述最近主樹節點的 關鍵碼值'J 、於且最接近待刪節點的關鍵碼值，待刪節點查找單元，用於以最近主樹節點的外部指針指向的從樹作為當 前從樹；在所述當前從樹中查找所述待刪節點，刪除單元，刪除所述查找到的待刪節點；或者，所述存儲裝置還包括檢測單元，用於檢測所述主樹中是否存在主樹中的第 一正整數個相鄰的 節點指向的從樹中的有效節點數，小於第二正整數個從樹能夠容納的節點數， 且所述第一正整數大於第二正整數，合併單元用於在檢測單元檢測結果為是時，將所述主樹中的第一正整 數個相鄰節點，及所述第一正整數個節點分別指向的從樹，合併為第二正 整數個主樹節點，以及與所述第二正整數個主樹節點指向的從樹。
13、 根據權利要求ll所述存儲裝置，其特徵在於，還包括 查找單元，用於才艮據待插節點的關^l碼值在主樹中查找最近主樹節點，在搬移單元將當前從樹中位於拆分節點右側的全部節點搬移到新建從樹中後 執行查找最近主樹節點，所述最近主樹節點的關鍵碼值大於且最接近待插節 點的關鍵碼值；所述主樹的根節點初始化為具有最大的關鍵碼值，其中，所 述主樹包括父節點、所述父節點的左子節點和所述父節點的右子節點，且所 述左子節點大於所述父節點，所述父節點大於所述右子節點；判斷單元，用於以最近主樹節點的外部指針指向的從樹作為當前,人樹， 判斷當前從樹是否已滿，搬移單元，若判斷單元判斷結果為是，則用於在當前從樹中任意選擇一 個節點作為拆分節點，將拆分節點插入到主樹中作為新建主樹節點，為新建 主樹節點分配新建從樹，並將新建主樹節點的外部指針指向新建從樹，將當 前從樹中位於拆分節點右側的全部節點搬移到新建從樹中；插入單元，若判斷單元判斷結果為是否，則用於將待插節點插入到當前 從樹中。
14、 一種通信設備，其特徵在於，包括 權利要求11至13所述的存儲裝置中的任意一個。
全文摘要
本發明實施例公開了一種基於樹形數據結構節點的插入的方法和存儲裝置。根據待插節點的關鍵碼值在主樹中查找最近主樹節點，所述最近主樹節點的關鍵碼值小於且最接近待插節點的關鍵碼值；以最近主樹節點的外部指針指向的從樹作為當前從樹，判斷當前從樹是否已滿，若是，則在當前從樹中任意選擇一個節點作為拆分節點，將拆分節點插入到主樹中作為新建主樹節點，為新建主樹節點分配新建從樹，並將新建主樹節點的外部指針指向新建從樹，將當前從樹中位於拆分節點左側的全部節點搬移到新建從樹中，然後執行查找最近主樹節點，若否，則將待插節點插入到當前從樹中。將樹形數據結構的樹分成主樹和從樹降低了樹的高度，減少了節點插入的時間。
文檔編號G06F17/30GK101515298SQ20091013265
公開日2009年8月26日 申請日期2009年3月30日 優先權日2009年3月30日
發明者毅 易, 杜文華, 洪榮峰 申請人:華為技術有限公司