一種基於樹形數據結構的最長前綴匹配方法和裝置的製作方法

2023-09-22 02:30:25 5

專利名稱：一種基於樹形數據結構的最長前綴匹配方法和裝置的製作方法
技術領域：
本發明涉及通信和計算機技術領域，尤其涉及一種基於樹形數據結構的最長前綴匹配方法和裝置。
背景技術：
路由器在轉發IP (International Protocol,網際協議)報文時，需要根據IP報文的目的地址查詢路由表。路由表包含多條路由前綴，每個路由前綴通常用一個由0/1構成的字符串表示，例如01*,字符串尾部的符號"*"表示後面的比特可以取任意值。路由表中的每個路由前綴對應一個下一跳信息，路由器在轉發IP報文時，需要根據IP報文的目的地址查找路由表中匹配的前綴，匹配的方式採用最長前綴匹配的方式，找出最長匹配的前綴後，根據該前綴所對應的下一跳信息轉發IPl艮文。所謂最長前綴匹配，舉例說明假如路由器內有兩個路由前綴(10*-〉interface 1 ), ( 1010*->interface 2 ),如果路由器收到一個才艮文，該I艮文的目的IP位址為101001,則這個地址和兩個前綴都匹配，但是，第二個前綴匹配的比特數更多，所以選擇第二個前綴作為最終的匹配結果，根據該前綴所對應的下一跳信息轉發報文。
隨著網絡規模的擴大，IPv6和VPN (Virtual Private Network,虛擬專用網絡)的廣泛應用，路由表所包含的前綴數目越來越多，目前的路由器需要支持數百萬條路由前綴。而且，隨著路由器接口速率的不斷提升，路由器完成最長前綴匹配的速度也需要不斷提高，需要滿足40Gbit/s， 100Gbit/s甚至更高的接口速率要求。
而在現有技術中，通常採用SRAM ( Static Random Access Memory,靜態隨機存儲器)以實現高速的查找性能，但通常不能支持大容量的路由表；或者採用DRAM以支持大容量的路由表，但由於DRAM (Dynamic RandomAccess Memory,動態隨才幾存儲器)的速度不高，無法支持高的查找性能。
為了能夠同時支持大容量的數據表和高的查找性能，現有技術中提出了一種基於Trie (搜索)樹的最長前綴匹配方法。Trie,是一種樹形結構，用於保存大量的字符串，可以利用字符串的公共前綴來節約存儲空間，具有更新速度快，查詢性能只與地址的長度有關，與前綴的數目不相關的特點，所以採用Trie實現最長前綴匹配是一種比較通用的做法，例如，現有技術中採用了一種通過搜索壓縮多比特Trie來查找最長匹配的前綴的方法，但是，在對現有技術的研究和實踐過程中，發明人發現採用壓縮多比特Trie的匹配方式，如果步長為r， 一次只能讀取r比特，其查詢速度無法滿足不斷提高的線路速率要求。

發明內容
本發明實施例提供一種基於樹形數據結構的最長前綴匹配方法和裝置，能夠提高查詢速度。
為解決上述技術問題，本發明所提供的基於樹形數據結構的最長前綴匹配方法和裝置實施例是通過以下技術方案實現的
本發明實施例提供了 一種基於樹形數據結構的最長前綴匹配方法，所述樹形數據結構代表多個前綴，前綴被區分為至少一個步，每個節點表示一步，所述方法包括
A. 讀取所述樹形數據結構中當前級別的一個搜索節點；
B. 確定讀出的所述搜索節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，如果存在匹配的前綴，則將上一級別的節點內指向葉子節點邀:組的指針和所述搜索節點的偏移量域相加，更新當前最佳匹配指針，並執行步驟C;如果不存在匹配的前綴，直接執行步驟C;
C. 當確定所述搜索節點的分支指示域和搜索關鍵字的對應比特匹配時，才艮據子節點位圖確定所述搜索節點是否存在子節點；
D. 當確定所述搜索節點不存在子節點時，讀取所述搜索節點的內部位圖，並根據所述內部位圖和所述搜索節點內指向葉子節點數組的指針，計算所述搜索節點內存在的匹配的長度最長的前綴，用計算結杲更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點的地址。
本發明實施例還提供了 一種搜索裝置，所述裝置用於基於一個樹形數據
8結構搜索匹配的長度最長的前綴，所述樹形數據結構代表多個前綴，前綴被區分為至少一個步，每個節點表示一步，所述搜索裝置從至少一個存儲器中
讀取節點，包括
讀取單元，用於讀取樹形數據結構中的節點；
最佳匹配指針確定單元，用於確定讀取的節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，並在存在匹配的前綴時，將上一級別的節點內指向葉子節點數組的指針和所述節點的偏移量域相加，更新當前最佳匹配
指針；
分支指示域確定單元，用於確定所述節點的分支指示域和搜索關鍵字的對應比特是否匹配，並在匹配時，觸發子節點位圖確定單元；
子節點位圖確定單元，用於根據子節點位圖確定所述節點是否存在子節點，在不存在時，觸發內部節點匹配單元；
內部位圖匹配單元，用於讀耳又所述節點的內部位圖，並才艮據所述內部位圖和所述節點內指向葉子節點數組的指針，計算所述節點內存在的最長匹配的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點的地址。
本發明實施例還提供了一種路由器，該路由器包括
包處理器，用於發送查詢請求，並接收搜尋引擎發送的查詢結果；
至少一個存儲器，用於存儲樹形數據結構中的節點，所述樹形數據結構代表多個前綴，前綴被區分為至少一步，每個節點表示一步；
搜尋引擎，用於在接收到包處理器的查詢請求時，從存儲器中讀取節點，確定讀取到的節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，並在存在匹配的前綴時，將上一級別的節點內指向葉子節點數組的指針和所述節點的偏移量域相加，更新當前最佳匹配指針；在確定所述節點的分支指示域和搜索關鍵字的對應是否匹配，並在匹配時，根據子節點位圖確定所述節點是否存在子節點，並在不存在子節點時，讀取所述節點的內部位圖，並根據所述內部位圖和所述節點內指向葉子節點數組的指針，計算所述節點內存在的最長匹配的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點的地址，並將計算結果返回給包處理器。
從以上技術方案可以看出，能夠根據讀出的搜索節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，並在存在匹配的前綴時，將上一級別的節點內指向葉子節點數組的指針和當前搜索節點的偏移量域相加，更新當
前最佳匹配指針；在所述搜索節點的分支指示域和搜索關^t字的對應比特匹配，且根據子節點位圖確定所述搜索節點不存在子節點時，可以根據所述搜索節點的內部位圖、指向子節點數組的指針以及搜索關鍵字對應比特，計算出所述搜索節點內存在的匹配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點的地址。設所述搜索節點的步長為r,根據上一級別節點的分支指示域可以確定本搜索節點所在延伸出上一級別節點的路徑與搜索關鍵字的1個比特是否匹配，而讀取所述搜索節點的內部位圖可以對應搜索關鍵字的後續r比特，因此，每讀取一個節點，可以處理r+l比特的4叟索關4建字，與多比特Trie或壓縮多比特Trie每讀取一個步長為r的節點，只能處理r比特的搜索關鍵字的最長前綴匹配方法相比，可以提高查詢速度。


圖1A為一組前綴及對應的單比特Trie示意圖IB為圖1A中前綴數據表1A1中所示前綴的多比特Trie示意圖1C為圖IB中所示多比特Trie所對應的壓縮多比特Trie示意圖2A為本發明實施例中採用的樹形數據結構示意圖2B為本發明實施例中搜索節點的類型位圖示意圖2C為本發明實施例中前綴位圖示意圖3A-B為本發明實施例中最長前綴匹配方法實施例一流程圖4為本發明實施例中節點數據結構示意圖5為本發明實施例中一種搜索系統結構示意圖6A-E為本發明實施例中最長前綴匹配方法實施例二流程10圖7為本發明實施例中搜索裝置實施例一結構示意圖；圖8為本發明實施例中搜索裝置實施例二結構示意圖；圖9為本發明實施例中搜索裝置實施例三結構示意圖；圖IO為本發明實施例中搜索裝置實施例四結構示意圖；圖11為本發明實施例中搜索裝置實施例五結構示意圖；圖12為本發明實施例中路由器實施例結構示意圖。
具體實施例方式
本發明實施例提供了一種基於樹形數據結構的最長前綴匹配方法和裝置，用於提高查詢速度。
以下首先參照附圖，介紹幾種採用Trie樹形數據結構進行最長前綴匹配的方法
參照圖1A,為一組前綴及對應的單比特Trie示意圖，其中，前綴數據表1A1給出了 9個前綴，Trie 1A2為這9個前綴的單比特Trie表示。Trie的每個節點最多有左右兩個子節點；實點表示該節點對應一個前綴。例如，P7是一個實點，從根節點到P7的路徑上所遇到的所有比特，即00110就是P7所對
應的前綴。
假設收到一個報文，搜索時從根節點開始，依次使用目的地址的每個比特，如杲對應的比特為0，則繼續搜索當前節點的左子節點，如果對應的比特為1，則繼續搜索當前節點的右子節點，記錄搜索過程中遇到的所有前綴，選出最後遇到的那個前綴作為匹配的結果。布支設目的地址為01110 ，則可以看出，在搜索過程中， 一共遇到了 3個前綴Pl、 P2、 P8，由於P8的長度最長，所以按照最長匹配的原則，選擇P8作為最終的匹配結果。
採用單比特Trie方式，假設搜索關鍵字的長度為W，最差情況下需要讀W次存儲器，這樣的查詢性能無法滿足實際需求，後來又有了多比特Trie，多比特Trie的特點是每讀一次存儲器，使用搜索關鍵字中的多個比特，參照圖IB,為圖1A中前綴lt據表lAl中所示前綴的多比特Trie示意圖，其中，步長為2，即每次讀取兩個比特，長度不是步長整數倍的前綴需要擴展成多個前綴，但如果擴展後的前綴與其他長度更長的前綴衝突，根據最長前綴匹配原則，選取未擴展時對應的長度最長的前綴。例如，對於根節點，前綴P1需
要擴展成00*， 01*， 10*， 11*,前綴P2需要擴展成00*， 01*，這樣對於00*有三個候選的前綴Pl、 P2、 P3,由於P3的前綴最長，所以在00對應的表項中填入P3;依據同樣原則可以看出，P2填入根節點內01所對應的表項，Pl只能填入根節點內10所對應的表項。
在多比特Trie的數據結構中，假設步長為r，則每個Trie節點有2M"表項，每個表項包含2個域，分別表示下一跳信息和指向子節點的指針。以下為描述方便，將Trie節點簡稱為節點。可以看出，使用多比特Trie，假設一個節點所對應的步長為r,則搜索該節點時會使用搜索關鍵字中的r比特，假設這r比特在搜索關鍵字中的位置為從比特i到比特i+r-l (假設在搜索時，搜索關鍵字的最高位記為比特1 )，則通過搜索該節點可以找出從長度i到長度i+r-l的前綴中與搜索關鍵字匹配的長度最長的前綴；對於根節點而言，i為1，通過搜索根節點可以找出從長度0到長度r的前綴中與搜索關鍵字匹配的長度最長的前綴。
可以看出，假設搜索關鍵字的長度為W，步長越長則讀存儲器的次數越少，搜索的速度越高，但步長越長，存儲器空間浪費越嚴重。針對這一問題，技術人員又提出了壓縮多比特Trie,參照圖1C，為圖1B中所示多比特Trie所對應的壓縮多比特Trie示意圖，假設步長為r,則多比特Trie內的每個節點內最多有2f個下一跳信息，2r個指向子節點的指針。為了節省存儲空間，如圖1C所示，在壓縮多比特Trie中，每個節點改成存放兩個位寬為Y比特的位圖(bitmap)加上兩個指針。每個節點存放一個子節點位圖(Child Bitmap )，和一個指向子節點的指針子節點指針(Child Pointer)。假設步長為r,子節點位圖一共有2r比特，每個節點為1則表示對應的路徑還需要繼續向下搜索，為0則表示不需要繼續搜索，每個節點的所有子節點在存儲器內連續存放，每個節點內有一個子節點指針用於指示該節點的第一個子節點在存儲器內存;改的地址。例如，圖1C中的節點1的子節點位圖為1101,表示在該節點中，假設搜索關鍵字搜索到節點1時所使用的索引為00/01/11,則還需要繼續搜索下去，如果所使用的索引為IO,則不需要繼續搜索下去。節點1 一共有三個
12子節點，在存儲器內連續存;^文，分別對應索引OO、 01、 11。
在進行搜索時，首先根據搜索關鍵字從子節點位圖中找出對應的比特，如果對應的比特為1，則需要繼續搜索，然後計算子節點位圖中從最高位開始到所找出的比特為止(不包括所找出的比特)， 一共有多少個1，將計算結果作為偏移量域，將節點中存放的指向子節點的指針作為基地址，將二者相加作為下一次搜索時需要從存儲器中讀出的節點的地址。例如，在搜索圖1C中的節點1時，假如此時搜索關鍵字中對應的索引為11，則根據節點1的子節點位圖1101,可以算出下一個要搜索的節點相對於節點2的起始地址的偏移量為2,下一次訪問的地址是節點1中的子節點指針加2。
每個節點存放一個前綴擴展位圖(Prefix Expansion Bitmap )，和一個指向葉子節點的指針葉子節點指針。前綴擴展位圖一共有2f個比特， 一個比特為1則表示對應的路徑對應一個前綴； 一個比特為0，將該比特的位置記為s，則從比特s開始在前綴擴展位圖中向左搜索，假設找到的第一個為1的比特所對應的前綴為Px,則比特s所對應的路徑所匹配的前綴也是Px。前綴擴展位圖內可能有多個比特為1，將所有為1的比特所對應前綴的下一跳信息在存儲器內連續存放，存放下一跳信息的節點稱為葉子節點，每個節點內存放一個指向葉子節點的指針用於指示該葉子節點內的第一個下一跳信息在存儲器內存放的地址。例如，圖1C中的節點2包含3個節點，其中，第一個節點的前綴擴展位圖為1110,假設搜索到這個節點時，所使用的索引為11,由於11在前綴擴展位圖內對應的比特為0,需要向左3叟索，找到的第一個為1的比特所對應的索引為IO，對應的前綴為P3，則使用索引ll在搜索本節點的過程中，所找到的匹配的前綴也是P3 。
在進行搜索時，首先才艮據搜索關鍵字從前綴擴展位圖中找出對應的比特，如果對應的比特為1,則計算從前綴擴展位圖的最高位開始， 一直到所找出的比特為止(不包括所找出的比特)， 一共有多少個1,將計算的結果作為偏移量域，將節點內指向葉子節點的指針作為基地址，二者相加後的地址作為搜索本節點時在本節點內所找到的匹配的前綴所對應的下一跳信息在存儲器內的存放地址；如果對應的比特為O,將該比特的位置記為s,則從比特s開始在前綴擴展位圖中向左搜索，直到找到第一個為1的比特，將該比特的位置
13記為t，則計算從前綴擴展位圖的最高位開始， 一直到比特t為止(不包括比 特t), 一共有多少個l,將計算的結果作為偏移量，將節點內指向葉子節點的 指針作為基地址，二者相加後的地址作為搜索本節點時在本節點內所找到的 匹配的前綴所對應的下一跳信息在存儲器內的存放地址。例如，在搜索圖1C
中的節點3時，假設此時搜索關鍵字中對應的索引為11,則根據節點3的前 綴擴展位圖1010，可以計算出對應的下一跳信息的地址相對於對應的葉子節 點的起始地址的偏移量為1，則在本節點內找到的匹配的前綴所對應的下一跳 信息在存儲器內的存放地址為本節點的葉子節點指針加1。
與採用多比特Trie的悽t據結構相同，^i殳一個節點所對應的步長為r,則 搜索該節點時會使用搜索關鍵字中的r比特，假設這r比特在搜索關鍵字中的 位置為從比特i到比特i+r-l(假設在搜索時，搜索關鍵字的最高位記為比特1 )， 則通過搜索該節點可以找出從長度i到長度i+r-1的前綴中與搜索關鍵字匹配 的長度最長的前綴；對於根節點而言，i為l,通過搜索根節點可以找出從長 度0到長度r的前綴中與搜索關鍵字匹配的長度最長的前綴。
可見，假設步長為r， 一個節點最多有2T個子節點，在多比特Trie中，需 要為每個子節點存儲一個指針，無論該子節點是否存在，而在壓縮多比特Trie 中，如果一個子節點不存在，則只需要將子節點位圖內對應的比特設為0，不 需要額外的信息，同多比特Trie相比，對存儲器容量的需求要減少很多。
同樣道理，假設步長為r, 一個節點最多對應2f個下一跳信息，在多比特 Trie中，需要在每個節點內存放2f個下一跳信息；而在壓縮多比特Trie中，如 果一個節點內兩個或者多個連續的索引在節點內所匹配的長度最長的前綴相 同，則只需要將前綴擴展位圖內第一個索引所對應的比特設為1，其餘索引所 對應的比特設為O,對應的下一跳信息只需要在存儲器內存放一次即可，同多 比特Trie相比，對存儲器容量的要求也變少了 。
可見，採用壓縮多比特Trie的匹配方式，如果步長為r， 一次仍然只能讀 取r比特，與多比特Trie的匹配方式相比，無法才是高查詢速度，其查詢速度 無法滿足不斷提高的線路速率要求。
另外，壓縮多比特Trie中，採用前綴擴展位圖的方式還存在一個問題，舉例說明在圖1C中的節點3中，前綴擴展位圖為1010,在葉子節點3內 存放了兩個前綴所對應的下一跳信息P7和P3。與圖1B相比，在圖IB中 P3所對應的下一跳信息只存在於根節點中，而在圖1C中，顯然不是這樣。 這是因為，在圖1C的節點3中，索引OO、 Ol所對應的前綴相同，都是P7， 所以前綴擴展位圖的高二位取為10,但是索引10、 ll在前綴擴展位圖內的對 應比特不能也設為00，如果設為00，則根據前面所描述的匹配方法，索引10、 11所對應的前綴在搜索過程中就會被計算成P7，但這顯然是錯誤的，所以必 須將索引10、 11在前綴擴展位圖內對應的比特設為10，對應的在葉子節點3 中需要增加前綴P3所對應的下一跳信息。而同一個前綴所對應的下一跳信息 在根節點所對應的葉子節點中和子節點所對應的葉子節點中重複存儲，會造 成存儲空間的浪費，以及下 一跳信息更新速率的降低。
為便於理解，以下首先介紹本發明實施例中所採用的樹形數據結構，參 照圖2A,為本發明實施例中採用的樹形數據結構示意圖，其具有TNODE( Trie Node,搜索節點)TNODEl、 TNODE2、 TNODE3, INODE (Internal Node, 內部節點)INODEl、 INODE2，子節點數組1、子節點數組2，葉子節點數 組l、葉子節點數組2和對應的LNODE (Leaf Node,葉子節點)，其中，每 個TNODE內有一個指向子節點數組的指針，用於指示子節點數組存放的基地 址，有一個指向葉子節點數組的指針，用於指示葉子節點數組的基地址，每 個TNODE中存放一個偏移量域(Offset )，用於在搜索過程中計算指向葉子節 點的指針，每個節點內的偏移量域指示兩個信息當前節點的父節點內是否 存在一個匹配的前綴；如果當前節點的父節點內存在匹配的前綴，則指出該 前綴所對應的下一跳信息的地址相對於父節點內所存儲的指向葉子節點數組 的指針的偏移量。
INODE內存》文內部位圖，用於指示該INODE所對應的TNODE所包含的 前綴，INODE和該INODE所對應的TNODE的所有子節點即子節點數組連續 存放，每個TNODE內存放一個指針指向這一段連續空間的起始地址，即指向 子節點數組的指針。當然，如果一個TNODE所對應的子Trie中沒有前綴， 則不需要為這個TNODE生成一個INODE。
其中，如果步長為r， TNODE內需要存放一個位寬為2f比特的子節點位圖
15和一個位寬為Y比特的類型位圖(Type Bitmap )，當子節點位圖內的一個比特 為1時，類型位圖內如果對應的比特為1，則表示對應的路徑延伸出本節點後， 有兩個分支，類型位圖內如果對應的比特為0，則表示對應的路徑延伸出本節 點後，有一個分支，或者是左分支，或者是右分支，不區分到底是哪個分支 存在；當子節點位圖內的一個比特為0時，說明沒有路徑延伸出本節點，因 此沒有分支，不需要判斷類型位圖中對應比特的值，類型位圖中對應的比特 無意義，可以設為0，也可以設為1。參照圖2B,為本發明實施例中節點的 類型位圖示意圖，該圖所示的節點，可以看出子節點位圖表示為1101，其 中索引10所對應的路徑沒有子節點，所以子節點位圖內對應的比特設為0。 類型位圖表示為10x0，由於索引OO對應的路徑延伸出本節點後存在兩個分支， 所以類型位圖對應的比特^皮i殳為1;由於索引01和11對應的路徑延伸出本節 點後存在一個分支，索引01所對應的路徑延伸出本節點有右分支，索引11 所對應的路徑延伸出本節點有左分支，所以類型位圖內對應的比特被設為0; 由於索引IO對應的路徑沒有延伸出本節點，即子節點位圖內對應的比特為0, 所以類型位圖內對應的比特^C標識為x,表示可以，可以取為0,也可以取為 1。
可以看出，釆用子節點位圖和類型位圖相結合的表示方法後， 一共需要2 個位寬為Y比特的位圖，同只採用子節點位圖的方式相比，需要的比特數目 從2f比特變為2T"比特，但是可以獲得每條延伸出本節點的路徑在本節點外有 一個分支還是兩個分支的信息。
如前所述，如果對應的路徑延伸出本節點後只有一個分支，根據類型位 圖內的對應比特並不能判斷出該分支是左分支還是右分支，為解決這一問題， 在每個節點內增加1比特的分支指示域，該域為O標識當對應的路徑延伸出 本節點的父節點時，本節點位於路徑的左分支，該域為1標識當對應的路徑 延伸出本節點的父節點時，本節點位於路徑的右分支。
假設節點內存放了一個Y比特的子節點位圖， 一個Y比特的類型位圖。 在搜索過程中，將一個節點從存儲器讀出後，從搜索關鍵字中對應的位置取 出r比特，然後根據這r比特從子節點位圖中選出對應的比特，判斷該比特是否 為l,如果為l，則表明對應的路徑延伸出本節點。將子節點位圖與類型位圖相與，得到的結果記為位圖V,可以看出，如果子節點位圖的一個比特為0,
則位圖V對應比特為0，如果子節點位圖的一個比特為1,則位圖v的對應比
特和類型位圖的對應比特相同。計算子節點位圖中從最高位開始到所找出的
比特為止(不包括所找出的比特)， 一共有多少個l,將計算的結果記為suml; 計算位圖V中從最高位開始到與搜索關鍵字所對應的比特為止(不包括與搜索 關鍵字所對應的比特)， 一共有多少個l，將計算的結果記為sum2。根據從搜 索關鍵字中取出的r比特從類型位圖中選出對應的比特，判斷該比特是否為1， 如果為1,則表明對應的路徑延伸出本節點，且有兩個分支，此時再從搜索關 鍵字中取出下一比特，根據該比特為0還是為1判斷應該沿著左分支繼續搜 索還是應該沿著右分支繼續搜索，如果從搜索關鍵字中取出的比特為0,則應 該沿著左分支繼續搜索，以節點中存放的指向子節點數組的指針作為基地址， 以suml+sum2為偏移量，將二者相加作為下一次搜索時需要從存儲器中讀出 的節點的地址；如果從搜索關鍵字中取出的比特為1，則沿著右分支繼續搜索， 以節點中存放的指向子節點數組的指針作為基地址，以suml+sum2+l為偏移 量，將二者相加作為下一次搜索時需要從存儲器中讀出的節點的地址；如果 從類型位圖中選取的比特為0，則表明對應的路徑延伸出本節點，並且只有一 個分支，但是不知道是左分支還是右分支，此時無論從搜索關鍵字中取出的 下一比特是否與該分支匹配，都將下一個子節點讀出繼續搜索，以節點中存 放的指向子節點數組的指針作為基地址，以suml+sum2為偏移量，將二者相 加作為下一次搜索時需要從存儲器中讀出的節點的地址。
如前所述，在壓縮多比特Trie中，同一個前綴所對應的下一跳信息在根 節點所對應的葉子節點中和子節點所對應的葉子節點中重複存儲，會造成存 儲空間的浪費，以及下一跳信息更新速率的降低，為解決這一問題，在INODE 中存放內部位圖，內部位圖用於指示該內部節點所對應的搜索節點內存在的 前綴，通過搜索內部位圖可以找出所述搜索節點內與搜索關鍵字匹配的長度 最長的前綴，以下介紹內部位圖的兩種實施方式
第一種內部位圖是在前綴擴展位圖基礎上，增加一個位寬為Z比特的前 綴指示位圖(Prefix Indication Bitmap),前綴指示位圖內的一個比特為1表示 在該節點內存在一個前綴與對應的路徑匹配，如果一個比特為0表示在該節
17點內不存在與對應的路徑相匹配的前綴。舉例而言，圖1C中的節點3的前綴
擴展位圖變為1000,前綴指示位圖為1100。
同樣，每個節點內所包含的所有前綴所對應的下一跳信息在存儲器內連 續存放，組成一個葉子節點數組。在搜索時，首先根據搜索關^t字找出前綴
指示位圖的對應比特，如果為O則表示本節點內沒有匹配的前綴；如果為1, 則繼續判斷前綴擴展位圖內對應的比特是否為1，如果前綴擴展位圖內對應的 比特為1 ，則計算從前綴擴展位圖的最高位開始， 一直到所找出的比特為止(不 包括所找出的比特)， 一共有多少個l，將計算的結果作為偏移量域，將上一 節點，即本內部節點對應的TNODE內指向葉子節點數組的指針作為基地址， 二者相加後的地址作為搜索本節點時在本節點內所找到的匹配的前綴所對應 的下一跳信息在存儲器內的存放地址；如果前綴擴展位圖內對應的比特為0, 將該比特的位置記為s,則從比特s開始在前綴擴展位圖內向左搜索，直到找 到第一個為l的比特，將該比特的位置記為t，計算從前綴擴展位圖的最高位 開始， 一直到比特t為止(不包括比特t)， 一共有多少個l,將計算的結果作 為偏移量域，將上一節點，即本節點對應的TNODE內指向葉子節點數組的指 針作為基地址，二者相加後的地址作為搜索本節點時在本節點內所找到的匹 配的前綴所對應的下一跳信息在存儲器內的存放地址。
可以看出，採用上述表示方式後，圖1C中的葉子節點3中不需要存放前 綴P3所對應的下 一跳信息。
第二種內部位圖所採用的方式參照圖2C，為本發明實施例中前綴位圖示 意圖，用一個位寬為2^-l比特的前綴位圖(Prefix Bitmap )來代替壓縮多比 特Trie中的前綴擴展位圖。對一個步長為r的節點而言，該節點實際上最多對 應了單比特Trie上的r+l級節點，這些節點在單比特Trie上組成一個子Trie 2C1。 首先將單比特Trie上對應的子Trie 2C1擴展成完全二叉樹2C2, 二叉樹上的每 個點對應一個比特，如果該點對應一個前綴，則對應的比特為1，否則對應的 比特為0。按照從上到下，從左到右的順序遍歷二叉樹，形成一個位圖2C3， 將這個位圖稱為前綴位圖。圖2C中，按照上面描述的方法，最終生成的前綴 位圖為1001001 (2C3)。同樣，每個節點內所包含的所有前綴所對應的下一跳信息在存儲器內連
續存放，組成一個葉子節點數組。在搜索時，假設節點的步長為r，則讀出節 點的前綴位圖後，首先分別計算對應的r+l級是否有匹配的前綴，如果有，則 從中選出一個長度最長的前綴作為匹配的前綴。選出匹配的前綴後，計算從 前綴位圖的最高位開始， 一直到該前綴所對應的比特為止(不包括該比特)， 一共有多少個l，將計算的結果作為偏移量域，將上一節點，即本INODE所 對應的TNODE內指向葉子節點數組的指針作為基地址，二者相加後的地址作 為搜索本節點時在本節點內所找到的匹配的前綴所對應的下一跳信息在存儲 器內的存放地址。
可見，採用前綴位圖的方式不會帶來在壓縮多比特Trie中所出現的同 一個 前綴所對應的下 一跳信息在根節點所對應的葉子節點中和子節點所對應的葉 子節點中重複存儲的問題，代價是前綴位圖需要21+1-1比特。
總之，採用前綴擴展位圖加上前綴指示位圖的方式可以避免在壓縮多比 特Trie中只採用前綴擴展位圖所帶來的問題，代價是需要的比特數目從Y比特 變為2^比特；採用前綴位圖的方式也可以避免只採用前綴擴展位圖所帶來的 問題，代價是需要的比特數目從2f比特變為2f+1-l比特。後文統一將這兩種位 圖表示稱為內部位圖。
可以理解的是，所述內部位圖也可以不作為獨立節點存力文，而與對應的 TNODE的其他域的信息存放在一起。
在本發明實施例中，採用樹形數據結構查找與搜索關鍵字匹配的長度最 長的前綴，為描述方便，將與搜索關鍵字匹配的長度最長的前綴稱為最長匹 配前綴，樹形數據結構代表多個前綴，前綴可以被區分為至少一個級別，即 被區分為至少一個步，每個節點表示一步，搜索並維護一個在搜索過程中遇 到的匹配的長度最長的前綴所對應的下一跳信息的地址，將這個地址記作當 前最佳匹配指針，讀取一個搜索節點並確定所述搜索節點中與搜索關鍵字最 長匹配的前綴的過程如下
讀取到樹形數據結構中當前級別的一個搜索節點，確定所述搜索節點的 偏移量域是否指示上一級別的節點內存在匹配的前綴，並在上一級別的節點內存在匹配的前綴時，將上一級別的節點內指向葉子節點數組的指針和當前
搜索節點的偏移量域相加，更新當前最佳匹配指針；在確定所述搜索節點的
分支指示域和搜索關鍵字的對應比特匹配，且根據子節點位圖確定所述4叟索 節點不存在子節點時，讀取所述搜索節點的內部位圖，並根據所述內部位圖 和所述搜索節點內指向葉子節點數組的指針，計算所述搜索節點內存在的匹 配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前 最佳匹配指針所對應的葉子節點的地址。
設所述搜索節點的步長為r,可以看出，根據上一級別節點的分支指示域 可以確定本節點所在延伸出上一級節點的路徑與搜索關鍵字的1個比特是否 匹配，而讀取所述搜索節點的內部位圖可以確定與搜索關鍵字後續對應的r 比特是否匹配，因此，每讀取一個節點，可以處理r+l比特的搜索關鍵字，與 多比特Trie或壓縮多比特Trie每讀取一個步長為r的節點，只能處理r比特 的搜索關鍵字的最長前綴匹配方法相比，可以提高查詢速度。
參照圖3A-B，為本發明實施例中最長前綴匹配方法實施例一流程圖，以 下詳細描述從存儲器內讀出 一個TNODE後的搜索過程，以及樹形數據結構中 定義的各個域在搜索過程中如何使用，其中，內部位圖作為獨立的節點INODE 與該INODE對應的TNODE的子節點連續存;^。搜索並維護一個在搜索過程 中遇到的匹配的長度最長的前綴所對應的下一跳信息的地址，將這個地址記 作當前最佳匹配指針。
301、 判斷讀出的TNODE的偏移量域是否指示上一節點內存在匹配的前 綴，如果上一節點內不存在匹配的前綴，則執行步驟303;如果上一節點內存 在匹配的前綴，則執行步驟302;
302、 將上一節點內指向葉子節點數組的指針和本節點的偏移量域相加， 用得到的結果更新當前最佳匹配指針，然後執行步驟303;
其中，每個節點內的偏移量域指示兩個信息當前節點的父節點內是否 存在一個匹配的前綴；如果當前節點的父節點內存在匹配的前綴，則指出該 前綴所對應的下一跳信息的地址相對於父節點內所存儲的指向葉子節點it組 的指針的偏移量。
20303、判斷TNODE的分支指示域和搜索關鍵字的對應比特是否匹配，如 果是，則執行步驟305;如果否，則執行步驟304;
在本實施例中，如果TNODE的分支指示域和搜索關鍵字的對應比特不匹 配，說明出現了查錯路徑的情況。
304 、將當前最佳匹配指針作為最終的查詢結果返回；
305、 在本實施例中，假設TNODE內包含一個位寬為2*"比特的子節點位圖， 一個位寬為^比特的類型位圖；從搜索關鍵字中對應的位置取出r比特，然後 根據這r比特從子節點位圖中選出一個比特並執行步驟306;
306、 判斷該比特是否為O,如果是，則執行步驟307;否則執行步驟310;
307、 子節點位圖內所選出的比特為0表明對應的路徑沒有延伸出本節點， 根據TNODE內指向子節點數組的指針將對應的INODE從存儲器中讀出，並 執行步驟308;
308、 由於在TNODE中存有指向葉子節點數組的指針，才艮據INODE內 存放的內部位圖和TNODE內存放的指向葉子節點數組的指針，計算出INODE 內是否有匹配的前綴，如果是，則執行步驟309;如果否，則執行步驟304;
在本實施例中，內部位圖可以採用前綴擴展位圖和前綴指示位圖相結合 的方式表示，可以理解的是，內部位圖也可以採用前面介紹的前綴位圖來表 示。
309、 找出一個長度最長的匹配的前綴，將該前綴所對應的當前最佳匹配 指針，即下一跳信息的地址作為最終的查詢結果；
310、 如果子節點位圖中對應的比特為1，則表明對應的路徑延伸出本節 點，此時根據從搜索關鍵字中取出的r比特從類型位圖中選出一個比特，並執 行步驟311;
311、 判斷該比特是否為1,如果為l，則執行步驟312;否則經由連接塊 3B執行圖3B中的步驟317;
312、 類型位圖的對應比特為1表明對應的路徑延伸出本節點，而且有2 個分支，此時從搜索關鍵字中取出下一個比特，並執行步驟313;
21313、 根據該比特為0還是為1判斷應該沿著左分支繼續搜索還是應該沿
著右分支繼續搜索，如果為0，則執行步驟314，否則執行步驟315;
314、 應該沿著左分支繼續搜索，並執行步驟316;
315、 應該沿著右分支繼續搜索，並執行步驟316;
316、 根據搜索關鍵字的對應比特，類型位圖和子節點位圖，以及TNODE 內指向子節點數組的指針計算出下一個需要讀出的節點的地址，然後記錄當
前節點內指向葉子節點數組的指針，將下一個節點讀出後執行步驟301;
317、 類型位圖的對應比特為O表明對應的路徑延伸出本節點，而且有1 個分支，但是不知道是左分支還是右分支，記錄搜索關鍵字的下一比特，將 該比特記為s,並執行步驟318;
318、 目前無法判斷比特s和存在的分支是否匹配，根據搜索關鍵字的對 應比特、類型位圖和子節點位圖，以及TNODE內指向子節點的指針計算出下 一個需要讀出的節點的地址，然後記錄當前節點內指向葉子節點數組的指針， 將下一個節點讀出後執行步驟319;
319、 讀出下一個比特後，判斷讀出的節點的偏移量域是否指示上一節點 內存在匹配的前綴，如果上一節點內不存在匹配的前綴，則執行步驟321;如 果上一節點內存在匹配的前綴，則執行步驟320;
320、 將上一節點內指向葉子節點數組的指針和本節點的偏移量域相加， 用得到的結果更新當前最佳匹配指針，並執行步驟321;
321、 如果當前節點的分支指示域指示是左分支且比特s=0,或者當前節 點的分支指示域指示是右分支且比特s=l，則經由連接塊3A返回困3A中的 步驟305繼續對當前節點進行判斷；如果當前節點的分支指示域指示是左分 支且比特s^，或者，當前節點的分支指示比特指示是右分支且比特s二O，則 執行步驟322;
322、 將當前最佳匹配指針作為最終的查詢結果，查詢過程到此結束。
在本實施例中，當子節點位圖內的對應比特為1且類型位圖的對應比特 為0時，雖然不知道搜索關鍵字與存在的分支是否匹配，但是仍然將該分支所對應的子節點讀出，即使讀錯，子節點內所存儲的偏移量域仍然是正確的， 仍然可以根據子節點內存儲的偏移量域和父節點內存儲的指向葉子節點^t組 的指針去更新當前最佳匹配指針。然後只需要根據分支指示域判斷是否查4昔， 如果查錯則搜索過程結束，否則繼續進行搜索。
從以上步驟可以看出，在搜索過程中，如果讀出的TNODE的子節點位圖 對應的比特為1，則不需要讀出對應的INODE。因為，如果子節點位圖的對 應比特為1,則會繼續讀出下一個節點，而根據上一個節點內所存放的指向葉 子節點數組的指針和下一個節點內存放的偏移量域就可以計算出上一個節點 內存在的長度最長的匹配的前綴所對應的下一跳信息，不需要讀出對應的 INODE;而如果搜索時讀出的TNODE的子節點位圖對應的比特為0,則需要 將INODE讀出來計算當前節點內最長匹配的前綴。而由於INODE和當前節 點的所有子節點是連續存放的，在硬體實現時，假設當前節點放在存儲器p, INODE和當前節點的所有子節點放在存儲器q,無論哪一種情況都會讀一次 存儲器p， 一次存儲器q，而不會出現某個存儲器被讀2次的情況，因此可以 進一步提高查詢效率，所以採用這種將內部位圖從節點中分離出來單獨存放
在INODE中並將INODE和對應的TNODE的子節點連續存》文的方式，利於 硬體上採用流水線方式實現。
假設步長為r，在壓縮多比特Trie中，每個節點存放了兩個位寬為2、匕特 的位圖(bitmap)(前綴擴展位圖和子節點位圖)以及兩個指4十，每處理一個 節點會使用搜索關鍵字中的r比特，而在上述實施例中，每個TNODE中也存放 了兩個位寬為2、匕特的位圖(子節點位圖和類型位圖，內部位圖作為獨立的 INODE單獨存放)加上兩個指針，但是在處理一個TNODE時會使用搜索關鍵 字的r+l比特，在沒有增大節點大小的情況下，每次處理的比特數目同壓縮多 比特Trie相比，可以增加1比特，因此相應地可以提高查詢速度。
參照圖4，為本發明實施例中節點數據結構示意圖，其中，節點數據結構 41為TNODE示意圖，以下對TNODE中各個域進行詳細介紹
設步長為r，則子節點位圖位寬為^比特，子節點位圖用於表示對應的路 徑是否延伸出本節點，例如，可以定義如果子節點位圖中對應的比特為1,表示對應的路徑延伸出本節點，需要繼續向下搜索；如果子節點位圖中對應 的比特為o，表示對應的路徑沒有延伸出本節點，不需要繼續向下搜索。
類型位圖位寬也為Y比特，類型位圖用於表示對應的路徑延伸出本節點
後的分支數，例如，可以定義類型位圖的對應比特為1，表示對應的路徑延 伸出本節點後，有兩個分支；類型位圖的對應比特為0，表示對應的路徑延伸 出本節點後，有一個分支，或者是左分支，或者是右分支。
偏移量域用於在搜索過程中計算指向葉子節點的指針，每個節點內的偏 移量域指示兩個信息當前節點的父節點內是否存在一個匹配的前綴；如果 當前節點的父節點內存在匹配的前綴，則指出該前綴所對應的下一跳信息的 地址相對於父節點內所存儲的指向葉子節點數組的指針的偏移量。
而分支指示域用於指示當前路徑延伸出本節點的父節點時，本節點位於 路徑的左分支還是右分支，例如，可以定義，所述分支指示域為0，表示本節 點位於路徑的左分支；所述分支指示域為l,表示本節點位於路徑的右分支。
指向葉子節點的指針用於表示指向本節點葉子節點數組的指針。
指向子節點的指針用於表示指向本節點子節點數組的指針。
而內部節點是否存在指示域用於指示內部節點是否存在，例如，可以定 義如果內部節點是否存在指示域為1,表示內部節點存在；如果內部節點是 否存在指示域為0，表示內部節點不存在。該域可以避免在內部節點不存在時 不必要的搜索過程。
節點數據結構42、 43為兩種不同形式的INODE示意圖，節點數據結構 42通過前綴擴展位圖加前綴指示位圖的方法指示每個節點內所包含的匹配的 前綴，節點數據結構43採用前綴位圖的方法表示每個節點內所包含的前綴。 節點數據結構44為LNODE示意圖，其中，關聯數據域用於存放前綴所對應 的下一跳信息。
除了 TNODE和INODE,在搜索樹形數據結構查找最長匹配前綴時，還 可以根據具體情況定義不同類型的節點，以進一步加快查詢速度。例如，當 一個節點沒有子節點時，不需要再存放該節點的子節點位圖和類型位圖，可 以將內部位圖放在節點內，這樣會少讀一次存儲器，從而提高查詢性能，這
24種節點可稱為ENODE (End Node,結束節點)，根據內部位圖的兩種表示方 法，ENODE可以採用節點數據結構45、 46兩種格式中的任意一種，節點數 據結構45為內部位圖採用前綴擴展位圖加前綴指示位圖的格式，節點數據結 構46為內部位圖採用前綴位圖的格式。當Trie上出現連續的單分支路徑時， 可以採用SNODE ( Skip Node,跳讀節點) 一次比較多個比特，從而加快查詢 速度，節點數據結構47為SNODE示意圖，比較長度表示一次比較的比特數。
SNODE和ENODE中偏移量域、分支指示比特域以及葉子節點指示域中 的定義採用與TNODE中相同的方式，不再贅述。
參照圖5，為本發明實施例中一種搜索系統實施例結構示意圖，用於查找 最長匹配的前綴，該搜索系統中，搜索裝置51從包處理器52接收查詢請求， 將查詢結果返回給包處理器52,從維護處理器53接收各種指令，根據指令的 內容對各個DRAM 54和SRAM 55執行讀、寫操作，並將最終指令的執行結 果返回給維護處理器53。
搜索裝置可以外掛至少一個DRAM,至少一個SRAM, SRAM可以是片 外SRAM，也可以是片內SRAM，各種節點都存放在存儲器內，根據搜索速 率的需要， 一個節點可以存放在單獨的RAM內，也可以存放在多個RAM內。 而一個DRAM可以包含多個單元(Bank )， 一個節點可以存放在一個DRAM 的一個單元內，也可以存i丈在一個DRAM的多個單元內。
下述以在一個Trie樹中查找最長匹配前綴為例，詳細描述本發明實施例 中所採用的最長前綴匹配方法
參照圖6A-E,為本發明實施例中最長前綴匹配方法實施例二流程圖，在 圖4中，描述了實施例一所採用的TNODE、 INODE和LNODE,以及考慮到 節點所在路徑上位置的不同，對TNODE進行優化後所得到的SNODE、 ENODE的結構，以下介紹讀取到圖4中所定義的不同類型的節點時，針對每 種不同的節點所執行的最長前綴匹配過程，與實施例一的不同之處在於，在 搜索過程中，可以首先判斷節點類型，由於節點的類型不同，執行流程有所 不同，例如，當讀取到一個跳讀節點時，如果確定讀取到的所述跳讀節點的 分支指示域和搜索關鍵字的對應比特匹配，且所述跳讀節點的比較數據與搜
25索關鍵字的對應比特相等時，可以根據所述跳讀節點內指向子節點數組的指 針計算下一個要讀取的節點的地址，並讀取下一個節點以繼續l^行搜索過牙呈。 當讀取到 一個結束節點時，需要確定讀取到的所述結束節點的分支指示域和 搜索關鍵字的對應比特是否匹配，如果匹配，可以根據所述結束節點的內部 位圖和結束節點內指向葉子節點數組的指針計算出所述結束節點內與搜索關 鍵字匹配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並計算所 述當前最佳匹配指針所對應的葉子節點地址。以下通過具體步驟進行詳細說
明
601、 接收一個查詢請求；
602、 判斷是否需要查詢SRAM;如果是，則執行步驟603;否則執行步 驟604;
603、 向SRAM發送讀請求，得到SRAM返回的結果後，執行步驟605;
604、 根據節點在DRAM內的分布情況，從多個DRAM中選出一個 DRAM,向該DRAM發送讀請求，得到DRAM的返回結果後，執行步驟605;
605、 判斷節點類型是否是SNODE,如果是，則經由連接塊6B繼續執行 圖6B中的步驟610,否則執行步驟606;
606、 判斷節點類型是否是INODE,如果是，則經由連接塊6C繼續執行 圖6C中的步驟617,否則執行步驟607;
607、 判斷節點類型是否是LNODE,如果是，則執行步驟608，否則繼續 執行步驟609;
.608、將LNODE的內容作為查詢結果返回，搜索過程結束；
609、 判斷當前節點類型是否是ENODE,如果是，則經由連接塊6D繼續 執行圖6D中的步驟621 ，否則經由連接塊6E繼續執行圖6E中的步驟627;
610、 判斷讀出的節點的偏移量域是否指示上一節點內存在匹配的前綴， 如果上一節點內不存在匹配的前綴，則執行步驟612;如果上一節點內存在匹 配的前綴，則執行步驟611;
611、 將上一節點內指向葉子節點數組的指針和本節點的偏移量域相加，用得到的結果更新當前最佳匹配指針，然後執行步驟612;
612、 判斷當前節點的分支指示域和搜索關鍵字的對應比特是否匹配，即 是否出現查錯路徑的情況，如果查錯路徑，則執行步驟613,否則執行步驟 615;
613、 判斷當前最佳匹配指針是否有效，如果無效，則查詢失敗，搜索過 程至此結束；如果有效，則執行步驟614;
614、 根據當前最佳匹配指針計算對應的LNODE的地址，才艮據計算出來 的地址以及節點在DRAM內的分布，計算出需要訪問哪個DRAM或者 SRAM,向對應的RAM發出讀請求，得到讀回的結果後，經由連接塊6A返 回圖6A中並繼續執行步驟605;
615、 判斷搜索關鍵字內相應的比特是否和SNODE內的比較數據相等， 如果相等，則執行步驟616,否則執行步驟613;
其中SNODE內進行比較的比特數目可以由SNODE內的比較長度域指定。
616、 根據本節點內的指向子節點數組的指針計算下一個要讀取的節點的 地址，根據計算出的地址以及節點在DRAM內的分布，計算出需要訪問哪個 DRAM或者SRAM,向對應的RAM發送讀請求，得到讀回的結果後，經由 連接塊6A返回圖6A中並繼續扭j行步驟605;
617、 根據搜索關鍵字和內部位圖判斷當前節點內是否存在匹配的前綴， 如果不存在，則執行步驟618,否則執行步驟620;
618、 判斷當前最佳匹配指針是否有效，如果無效，則查詢失敗，搜索過 程至此結束；如果有效，則執行步驟619;
619、 根據當前最佳匹配指針計算對應的LNODE的地址，根據計算出來 的地址以及節點在DRAM內的分布，計算出需要訪問哪個DRAM或者 SRAM ，向對應的RAM發出讀請求，得到讀回的結果後，經由連接塊6A返 回圖6A中並繼續執行步驟605;
620、 根據內部位圖和上一節點的指向葉子節點數組的指針計算當前節點
27內與搜索關鍵字匹配的長度最長的前綴，用計算的結果更新當前最佳匹配指
針，根據當前最佳匹配指針計算對應的LNODE的地址，根據計算出來的地址 以及節點在DRAM內的分布，計算需要訪問哪個DRAM或者SRAM。向對 應的RAM發送讀請求，得到讀回的結果後，經由連接塊6A返回圖6A中繼 續執行步驟605;
621 、判斷讀出的節點的偏移量域是否指示上一節點內存在匹配的前綴， 如果上一節點內不存在匹配的前綴，則執行步驟623;如果上一節點內存在匹 配的前綴，則執行步驟622;
622、 將上一節點內指向葉子節點數組的指針和本節點的偏移量域相加， 用得到的結果更新當前最佳匹配指針，並執行步驟623;
623、 判斷當前節點的分支指示域和搜索關鍵字的對應比特是否匹配，如 果是，則執行步驟626;如果否，則執行步驟624;
624、 判斷當前最佳匹配指針是否有效，如果無效，則查詢失敗，搜索過 程至此結束；如果有效，則執行步驟625;
625 、根據當前最佳匹配指針計算對應的LNODE的地址，根據計算出來 的地址以及節點在DRAM內的分布，計算出需要訪問哪個DRAM或者 SRAM，向對應的RAM發出讀請求，得到讀回的結果後，經由連接塊6A返 回圖6A中繼續4丸行步驟605;
626、 根據內部位圖和當前節點的指向葉子節點數組的指針計算出當前節 點內與搜索關鍵字匹配的長度最長的前綴，用計算的結果更新當前最佳匹配 指針，根據當前最佳匹配指針計算對應的LNODE的地址，根據計算出來的地 址以及節點在DRAM內的分布，計算出需要訪問哪個DRAM或者SRAM, 向對應的RAM發送讀請求，得到讀回的結果後，經由連接塊6A返回圖6A 中繼續執行步驟605;
627、 判斷讀出的節點的偏移量域是否指示上一節點內存在匹配的前綴， 如果上一節點內不存在匹配的前綴，則執行步驟629;如果上一節點內存在匹 配的前綴，則執行步驟628;
628 、將上一節點內指向葉子節點數組的指針和本節點的偏移量域相加，用得到的結果更新當前最佳匹配指針，並執行步驟629;
629、 判斷當前節點的分支指示域和搜索關鍵字的對應比特是否匹配，即 是否出現查錯路徑的情況，如果查錯路徑，則執行步驟630;如果沒有查錯路 徑，則執行步驟632;
630、 判斷當前最佳匹配指針是否有效，如果無效，則查詢失敗，搜索過 程至此結束；如果有效，則執行步驟631;
631、 根據當前最佳匹配指針計算對應的LNODE的地址，才艮據計算出來 的地址以及節點在DRAM內的分布，計算出需要訪問哪個DRAM或者 SRAM,向對應的RAM發出讀請求，得到讀回的結果後，經由連接塊6A返 回圖6A中繼續執行步驟605;
632、 根據搜索關鍵字判斷當前節點的子節點位圖內對應的比特是否為0, 如果是O，則執行步驟633;如果為1,則執行步驟635;
633 、判斷當前節點內的內部節點是否存在指示域(INODE Exist Flag ) 是否為1，如果為1,則執行步驟634;如果為0,則執行步驟630;
634、 根據本節點內指向子節點數組的指針計算下一個要讀取的節點的地 址，根據計算出來的地址以及節點在DRAM內的分布，計算出需要訪問哪個 DRAM或者SRAM，向對應的RAM發送讀請求，得到讀回的結果後，經由 連4妄塊6A返回圖6A中繼續執行步驟605;
635、 根據搜索關鍵字判斷當前節點的類型位圖內對應的比特是否為0, 如果為O，則執行步驟636,否則，執行步驟637;
636、 確定對應的路徑延伸出本節點後有1個分支，並.執行步驟638;
637、 確定對應的路徑延伸出本節點後有2個分支，並執行步驟638;
638、 根據當前節點的子節點位圖、類型位圖、指向子節點數組的指針以 及搜索關鍵字的對應比特，計算出下一個需要讀取的節點的地址，根據計算 出來的地點以及節點在DRAM中的分布，計算出需要訪問哪個DRAM或者 SRAM，向對應的RAM發送讀請求，得到讀回的結果後，經由連接塊6A返 回圖6A中繼續執行步驟605;
29以上對搜索Trie樹進行最長前綴匹配的過程進行了詳細的描述，可以理 解的是，實施例中所述的執行順序並不是唯一的，例如，可以先判斷所讀取 的節點的分支指示比特是否與搜索關鍵字的對應比特匹配，並在匹配時，再 判斷節點類型。並且，判斷節點類型的順序沒有一定的限制，例如，可以先 判斷是否為TNODE，也可以最先判斷是否為LNODE等等。
以下對本發明實施例中所採用的搜索裝置進行對應描述
參照圖7，為本發明實施例中搜索裝置實施例一結構示意圖，該裝置用於 基於一個樹形數據結構搜索匹配的長度最長的前綴，所述樹形數據結構代表 多個前綴，前綴被區分為至少一個步，每個節點表示一步，所述搜索裝置從 至少一個存儲器中讀取節點，該裝置包括
讀取單元71,用於讀取樹形數據結構中的節點；
最佳匹配指針確定單元72，用於確定讀取的節點的偏移量域是否指示上 一級別的節點內存在匹配的前綴，並在存在匹配的前綴時，將上一級別的節 點內指向葉子節點數組的指針和所述節點的偏移量域相加，更新當前最佳匹 配指針；
分支指示域確定單元73，用於確定所述節點的分支指示域和搜索關鍵字 的對應比特是否匹配，並在匹配時，觸發子節點位圖確定單元74;
子節點位圖確定單元74,用於根據子節點位圖確定所述節點是否存在子 節點，在不存在子節點時，觸發內部節點匹配單元75;
內部位圖匹配單元75,用於讀取所述節點的內部位圖，並根據所述內部 位圖和所述節點內指向葉子節點數組的指針，計算所述節點內存在的最長匹 配的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指 針所對應的葉子節點的地址。
本實施例中通過最佳匹配指針確定單元72確定當前最佳匹配指針，通過 分支指示域確定單元確定節點的分支指示域和搜索關鍵字的對應比特是否匹 配，並在匹配時觸發子節點位圖確定單元、並由子節點位圖確定單元74確定 所述節點是否存在子節點，在所述節點不存在子節點時，觸發內部位圖匹配 單元75根據所述內部位圖和所述搜索節點內指向葉子節點數組的指針，計算所述搜索節點內存在的最長匹配的前綴，用計算結果更新當前最佳匹配指針， 並計算所述當前最佳匹配指針所對應的葉子節點的地址。設讀取的節點的步
長為r，採用本實施例中的搜索裝置搜索， 一次可以確定搜索關鍵字的r+l比 特是否匹配，因此，可以提高查詢速度。
可以對上述實施例作進一步的優化，以下通過幾個具體實施例進行詳細 說明
參照圖8，為本發明實施例中搜索裝置實施例二結構示意圖，所述搜索裝 置中，所述子節點位圖確定單元還用於在存在子節點時，觸發下一節點地址 計算單元81;
下一節點地址計算單元81,用於在子節點位圖確定單元74確定所述節點 存在子節點時，根據所述節點的類型位圖判斷所述節點的分支數，並根據所 述節點的子節點位圖、類型位圖、指向子節點數組的指針以及搜索關鍵字的 對應比特，計算出下一個需要讀取的節點的地址，並觸發讀耳又單元71,以讀 取要搜索的節點。
該搜索裝置可以對一個存在子節點的節點進行搜索，以查找最長匹配的前綴。
在上述實施例中，為提高查詢速度，可以設置多個存儲器，每個存儲器 用於存儲一級節點。
並且，所述節點的內部位圖作為獨立的內部節點與所述節點的子節點數 組連續存放，這樣，如果存在匹配的下一級節點，則不需要讀取所述內部節 點，如果不存在匹配的下一級節點，則讀取內部位圖，這樣可以保證一次只 讀取一個存儲器，可以進一步提高查詢速度。
還可以對實施例二作進一步優化，以下通過具體的實施例進4亍i兌明
參照圖9，為本發明實施例中搜索裝置實施例三結構示意圖，該搜索裝置 在實施例一基礎上，還可包括跳讀節點匹配單元91，用於當分支指示域確 定單元73確定讀取到的跳讀節點的分支指示域和搜索關鍵字的對應比特匹配 時，確定所讀取的跳讀節點的比較數據與搜索關鍵字的對應比特是否相等， 並在相等時，根據所述跳讀節點內指向子節點數組的指針計算下一個要讀取
31的節點的地址，並觸發讀取單元71讀取下一個節點以繼續:溲索。
可見，該搜索裝置中，當樹形數據結構上出現連續的單分支路徑時，通 過跳讀節點匹配單元判斷所述連續的單分支路徑與搜索關鍵字對應比特是否 匹配， 一次可以讀取多個節點，因此可以進一步加快查詢速度。
在實施例二和實施例三所描述的搜索裝置中，還可包括結束節點匹配 單元，為描述方便，以在實施例一的基礎上進行擴展說明，參照圖10,為本 發明實施例中搜索裝置實施例四結構示意圖，該裝置在實施例一基礎上，還
包括結束節點匹配單元101,用於當分支指示域確定單元73確定讀取到的 結束節點的分支指示域和搜索關鍵字的對應比特匹配時，根據所述結束節點 的內部位圖和結束節點內指向葉子節點數組的指針計算出所述結束節點內與 搜索關鍵字匹配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並 計算所述當前最佳匹配指針所對應的葉子節點地址。
所述搜索裝置通過結束節點匹配單元查找結束節點內是否有匹配的長度 最長的前綴，結束節點沒有子節點，因此節點內不需要存放節點的子節點位 圖和類型位圖，而將內部位圖放在節點內，因此可以少讀一次存儲器，從而 提高查詢性能。
在上述實施例中所描述的搜索裝置中，還可以作進一步優化，參照圖11, 為本發明實施例中搜索裝置實施例五結構示意圖，為在搜索裝置實施例一基 礎上進行擴展，所擴展的有效指針對應葉子節點地址計算單元111，用於當所 述分支指示域確定單元73確定當前讀取到的節點的分支指示域和搜索關鍵字 的對應比特不匹配時，判斷當前最佳匹配指針是否有效，並在有效時，根據 當前最佳匹配指針計算對應的葉子節點的地址。
可見，該實施例中通過有效指針對應葉子節點地址計算單元在當前最佳 匹配指針有效時，根據當前最佳匹配指針計算對應的葉子節點的地址，即使 讀取到的節點的分支指示域和搜索關鍵字的對應比特不匹配時，即搜索到錯 誤的路徑上，也可以保證所讀取的葉子節點的地址正確。
本發明實施例中所述的搜索裝置可以應用於多個領域中，例如，可以應 用於計算機或者通信技術領域，以下以在通信領域中所應用的一種裝置進行
32i羊細i兌明
參照圖12,為本發明實施例中路由器實施例結構示意圖，該路由器包括
包處理器121,用於發送查詢請求，並接收搜尋引擎發送的查詢結果；
至少一個存儲器122,用於存儲樹形數據結構中的節點，所述樹形數據結 構代表多個前綴，前綴被區分為至少一步，每個節點表示一步；
搜尋引擎123，用於在接收到包處理器121的查詢請求時，從存儲器122 中讀取節點，確定讀取到的節點的偏移量域是否指示上一級別的節點內存在 匹配的前綴，並在存在匹配的前綴時，將上一級別的節點內指向葉子節點數 組的指針和所述節點的偏移量域相加，更新當前最佳匹配指針；在確定所述 節點的分支指示域和搜索關鍵字的對應是否匹配，並在匹配時，根據子節點 位圖確定所述節點是否存在子節點，並在不存在子節點時，讀取所述節點的 內部位圖，並根據所述內部位圖和所述節點內指向葉子節點數組的指針，計 算所述節點內存在的最長匹配的前綴，用計算結果更新當前最佳匹配指針， 並計算所述當前最佳匹配指針所對應的葉子節點的地址，並將計算結果返回 給包處理器121。
本實施例所介紹的路由器中，由搜尋引擎123確定當前最佳匹配指針， 確定節點的分支指示域和搜索關鍵字的對應比特是否匹配，並在匹配時確定 所述節點是否存在子節點，在所述節點不存在子節點時，根據所述內部位圖 和所述搜索節點內指向葉子節點數組的指針，計算所述搜索節點內存在的最 長匹配的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹 配指針所對應的葉子節點的地址。設讀取的節點的步長為r，採用本實施例中 的路由器搜索， 一次可以確定搜索關鍵字的r+l比特是否匹配，因此，可以提 高查詢速度。
可以對上述路由器實施例作進一步的優化，例如
所述搜尋引擎123還可用於在確定所述節點存在子節點時，才艮據所述節 點的類型位圖判斷所述節點的分支數，並根據所述節點的子節點位圖、類型 位圖、指向子節點數組的指針以及搜索關鍵字的對應比特，計算出下一個需 要讀取的節點的地址，並繼續從存儲器中讀取下一個要搜索的節點。這樣可以對一個存在子節點的節點進行搜索，以查找最長匹配的前綴。
所述搜尋引擎123還可用於在確定讀取到的跳讀節點的分支指示域和搜 索關鍵字的對應比特匹配時，確定所讀取的跳讀節點的比較數據與搜索關鍵 字的對應比特是否相等，並在相等時，根據所述跳讀節點內指向子節點數組 的指針計算下一個要讀取的節點的地址，並讀取下一個節點以繼續搜索。
這樣一來，當樹形數據結構上出現連續的單分支路徑時，通過搜尋引擎 判斷所述連續的單分支路徑與搜索關鍵字對應比特是否匹配， 一次可以讀取 多個節點，因此可以進一步加快查詢速度。
所述搜尋引擎123還可用於在確定讀取到的結束節點的分支指示域和搜
索關鍵字的對應比特匹配時，根據所述結束節點的內部位圖和結束節點內指 向葉子節點數組的指針計算出所述結束節點內與搜索關鍵字匹配的長度最長 的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針 所對應的葉子節點地址。
由搜尋引擎查找結束節點內是否有匹配的長度最長的前綴，結束節點沒 有子節點，因此節點內不需要存放節點的子節點位圖和類型位圖，而將內部 位圖放在節點內，因此可以少讀一次存儲器，從而提高查詢性能。
所述搜尋引擎123還可用於在確定讀取到的節點的分支指示域和搜索關 鍵字的對應比特不匹配時，判斷當前最佳匹配指針是否有效，並在有效時， 才艮據當前最佳匹配指針計算對應的葉子節點的地址。
這樣，根據當前最佳匹配指針計算對應的葉子節點的地址，即使讀取到 的節點的分支指示域和搜索關鍵字的對應比特不匹配時，即搜索到錯誤的路 徑上，也可以保證所讀取的葉子節點的地址正確。
可以理解的是，在以上實施例中所介紹的路由器中，還可包括維護處 理器，用於向所述搜尋引擎發送指令；
所述搜尋引擎還用於根據維護處理器發送的指令對存儲器執行讀或寫操 作，並將指令執行結果返回給維護處理器。
在以上所介紹的路由器實施例中，存儲器可以為SRAM,也可以為DRAM,用戶可以根據需要靈活選擇，並且，為了進一步提高查詢速度，存
儲器可以為多個，每個存儲器可以分別用於存儲一級節點。
而且，所述節點的內部位圖作為獨立的內部節點與所述節點的子節點數 組連續存放。這樣，如果存在匹配的下一級節點，則不需要讀:取所述內部節 點，如果不存在匹配的下一級節點，則讀取內部位圖，這樣可以保證一次只 讀取一個存儲器，可以進一步提高查詢速度。
.貝可。
是可以通過程序來指令相關的硬體完成，所述的程序可以存儲於一種計算機
可讀存儲介質中，該程序在執行時，包括如下步驟
A. 讀取所述樹形數據結構中當前級別的一個搜索節點；
B. 確定讀出的所述搜索節點的偏移量域是否指示上一級別的節點內存在 匹配的前綴，如果存在，則將上一級別的節點內指向葉子節點數組的指針和 當前搜索節點的偏移量域相加，更新當前最佳匹配指針，並執行步驟C，否 則直接執行步驟C;
C. 當確定所述搜索節點的分支指示域和搜索關鍵字的對應比特匹配時， 根據子節點位圖確定所述搜索節點是否存在子節點；
D. 當確定所述搜索節點不存在子節點時，讀取所述搜索節點的內部位圖， 並根據所述內部位圖和所述搜索節點內指向葉子節點數組的指針，計算所述 搜索節點內存在的匹配的長度最長的前綴，用計算結果更新當前最佳匹配指 針，並計算所述當前最佳匹配指針所對應的葉子節點的地址。
上述提到的存儲介質可以是只讀存儲器，磁碟或光碟等。
以上對本發明所提供的 一種基於樹形數據結構的最長前綴匹配的方法和 裝置進行了詳細介紹，對於本領域的一般技術人員，依據本發明實施例的思 想，在具體實施方式
及應用範圍上均會有改變之處，綜上所述，本說明書內 容不應理解為對本發明的限制。
權利要求
1.一種基於樹形數據結構的最長前綴匹配方法，其特徵在於，所述樹形數據結構代表多個前綴，前綴被區分為至少一個步，每個節點表示一步，所述方法包括A.讀取所述樹形數據結構中當前級別的一個搜索節點；B.確定讀出的所述搜索節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，如果存在匹配的前綴，則將上一級別的節點內指向葉子節點數組的指針和所述搜索節點的偏移量域相加，更新當前最佳匹配指針，並執行步驟C；如果不存在匹配的前綴，直接執行步驟C；C.當確定所述搜索節點的分支指示域和搜索關鍵字的對應比特匹配時，根據子節點位圖確定所述搜索節點是否存在子節點；D.當確定所述搜索節點不存在子節點時，讀取所述搜索節點的內部位圖，並根據所述內部位圖和所述搜索節點內指向葉子節點數組的指針，計算所述搜索節點內存在的匹配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點的地址。
2. 如權利要求1所述的基於樹形數據結構的最長前綴匹配方法，其特徵在於，進一步包括當確定所述搜索節點存在子節點時，根據所述搜索節點的類型位圖判斷當前節點的分支數，並根據所述搜索節點的子節點位圖、類型位圖、指向子節點數組的指針以及搜索關鍵字的對應比特，計算出下一個需要讀取的節點的地址，並重複執行步驟A、 B、 C以繼續執行搜索過程。
3. 如權利要求2所述的基於樹形數據結構的最長前綴匹配方法，其特徵在於，進一步包括確定讀取到 一個跳讀節點，所述跳讀節點用於表示連續的單分支路徑；當確定讀取到的所述跳讀節點的分支指示域和搜索關^lt字的對應比特匹配，且所述跳讀節點的比較數據與搜索關鍵字的對應比特相等時，根據所述跳讀節點內指向子節點數組的指針計算下一個要讀取的節點的地址，並讀取下 一個節點以繼續執行搜索過程。
4. 如權利要求2所述的基於樹形數據結構的最長前綴匹配方法，其特徵在於，進一步包括讀取到一個結束節點；當確定讀取到的所述結束節點的分支指示域和搜索關鍵字的對應比特匹配時，根據所述結束節點的內部位圖和結束節點內指向葉子節點數組的指針計算出所述結束節點內與搜索關鍵字匹配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點地址。
5. 如權利要求1或2所述的基於樹形數據結構的最長前綴匹配方法，其特徵在於，所述搜索節點的內部位圖作為獨立的節點與所述當前節點的子節點數組連續存儲。
6. 如權利要求1至4任一項所述的基於樹形數據結構的最長前綴匹配方法，其特徵在於，進一步包括當確定當前讀取到的節點的分支指示域和搜索關鍵字的對應比特不匹配時，判斷當前最佳匹配指針是否有效，如果有，則根據當前最佳匹配指針計算對應的葉子節點的地址。
7. —種搜索裝置，其特徵在於，所述裝置用於基於一個樹形數據結構搜索匹配的長度最長的前綴，所述樹形數據結構代表多個前綴，前綴被區分為至少一個步，每個節點表示一步，所述搜索裝置從至少一個存儲器中讀取節點，包括讀取單元，用於讀取樹形數據結構中的節點；最佳匹配指針確定單元，用於確定讀取的節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，並在存在匹配的前綴時，將上一級別的節點內指向葉子節點數組的指針和所述節點的偏移量域相加，更新當前最佳匹配指針；分支指示域確定單元，用於確定所述節點的分支指示域和搜索關^:字的對應比特是否匹配，並在匹配時，觸發子節點位圖確定單元；子節點位圖確定單元，用於根據子節點位圖確定所述節點是否存在子節點，在不存在時，觸發內部節點匹配單元；內部位圖匹配單元，用於讀取所述節點的內部位圖，並才艮據所述內部位圖和所述節點內指向葉子節點數組的指針，計算所述節點內存在的最長匹配的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點的地址。
8. 如權利要求7所述的搜索裝置，其特徵在於，還包括下一節點地址計算單元，用於當子節點位圖確定單元確定所述節點存在子節點時，；f艮據所述節點的類型位圖判斷所述節點的分支數，並根據所述節點的子節點位圖、類型位圖、指向子節點數組的指針以及搜索關鍵字的對應比特，計算出下一個需要讀取的節點的地址，並觸發讀取單元，以讀取要搜索的節點。
9. 如權利要求8所述的搜索裝置，其特徵在於，所述存儲器為多個，每個存儲器用於存儲一級節點。
10. 如權利要求9所述的搜索裝置，其特徵在於，所述節點的內部位圖作為獨立的內部節點與所述節點的子節點數組連續存放。
11. 如權利要求8所述的搜索裝置，其特徵在於，還包括跳讀節點匹配單元，用於當分支指示域確定單元確定讀取到的跳讀節點的分支指示域和搜索關鍵字的對應比特匹配時，確定所讀取的跳讀節點的比較數據與搜索關鍵字的對應比特是否相等，並在相等時，根據所述跳讀節點內指向子節點數組的指針計算下一個要讀取的節點的地址，並觸發讀取單元讀取下一個節點以繼續搜索。
12. 如權利要求8所述的搜索裝置，其特徵在於，還包括結束節點匹配單元，用於當分支指示域確定單元確定讀取到的結束節點的分支指示域和搜索關鍵字的對應比特匹配時，根據所述結束節點的內部位圖和結束節點內指向葉子節點數組的指針計算出所述結束節點內與搜索關鍵字匹配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點地址。
13. 如權利要求7至12任一項所述的搜索裝置，其特徵在於，還包括有效指針對應葉子節點地址計算單元，用於當所述分支指示域確定單元確定當前讀取到的節點的分支指示域和搜索關鍵字的對應比特不匹配時，判斷當前最佳匹配指針是否有效，並在有效時，根據當前最佳匹配指針計算對應的葉子節點的地址。
14. 一種路由器，其特徵在於，包括包處理器，用於發送查詢請求，並接收搜尋引擎發送的查詢結果；至少一個存儲器，用於存儲樹形數據結構中的節點，所述樹形數據結構代表多個前綴，前綴被區分為至少一步，每個節點表示一步；搜尋引擎，用於在接收到包處理器的查詢請求時，從存儲器中讀取節點，確定讀取到的節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，並在存在匹配的前綴時，將上一級別的節點內指向葉子節點數組的指針和所述節點的偏移量域相加，更新當前最佳匹配指針；在確定所述節點的分支指示域和搜索關鍵字的對應是否匹配，並在匹配時，4艮據子節點位圖確定所述節點是否存在子節點，並在不存在子節點時，讀取所述節點的內部位圖，並根據所述內部位圖和所述節點內指向葉子節點數組的指針，計算所述節點內存在的最長匹配的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點的地址，並將計算結果返回給包處理器。
15. 如權利要求14所述的路由器，其特徵在於，所述搜尋引擎還用於在確定所述節點存在子節點時，根據所述節點的類型位圖判斷所述節點的分支數，並根據所述節點的子節點位圖、類型位圖、指向子節點^t組的指針以及搜索關鍵字的對應比特，計算出下一個需要讀取的節點的地址，並繼續從存儲器中讀取下 一個要搜索的節點。
16. 如權利要求15所述的路由器，其特徵在於，所述搜尋引擎還用於在確定讀取到的跳讀節點的分支指示域和搜索關鍵字的對應比特匹配時，確定所讀取的跳讀節點的比較數據與搜索關鍵字的對應比特是否相等，並在相等時，根據所述跳讀節點內指向子節點數組的指針計算下一個要讀取的節點的地址，並讀取下一個節點以繼續搜索。
17. 如權利要求15所述的路由器，其特徵在於，所述搜尋引擎還用於在確定讀取到的結束節點的分支指示域和搜索關鍵字的對應比特匹配時，根據所述結束節點的內部位圖和結束節點內指向葉子節點數組的指針計算出所述結束節點內與搜索關鍵字匹配的長度最長的前綴，用計算結果更新當前最佳匹配指針，並計算所述當前最佳匹配指針所對應的葉子節點i也址。
18.如權利要求14至17任一項所述的路由器，其特徵在於，所述搜尋引擎還用於在確定當前讀取到的節點的分支指示域和搜索關4建字的對應比特不匹配時，判斷當前最佳匹配指針是否有效，並在有效時，才艮據當前最佳匹配指針計算對應的葉子節點的地址。
全文摘要
本發明公開了最長前綴匹配方法和裝置，該方法包括A.讀取一個搜索節點；B.確定讀出的搜索節點的偏移量域是否指示上一級別的節點內存在匹配的前綴，如果存在，將上一級別的節點內指向葉子節點數組的指針加上該搜索節點的偏移量域，更新當前最佳匹配指針，並執行步驟C；如果不存在，執行步驟C；C.確定該搜索節點的分支指示域和搜索關鍵字的對應比特匹配時，確定該搜索節點是否存在子節點；D.確定該搜索節點不存在子節點時，讀取該搜索節點的內部位圖，根據內部位圖和搜索節點內指向葉子節點數組的指針，計算該搜索節點內存在的最長匹配前綴，更新當前最佳匹配指針，計算當前最佳匹配指針對應的葉子節點的地址。該方法可以提高查詢速度。
文檔編號G06F17/30GK101577662SQ20081009690
公開日2009年11月11日 申請日期2008年5月5日 優先權日2008年5月5日
發明者娟 張, 猛 李, 軍 梁, 沈士軍, 睿 胡, 鈞 龔 申請人:華為技術有限公司