[發明專利]數據庫和數據庫處理方法

有效

• 申請號: 200810149667.2
• 申請日: 2008-09-16
• 公開（公告）號: CN101388030A
• 公開（公告）日: 2009-03-18
• 發明（設計）人: 喬納森·理查德·伯杰;高文·博斯沃思;戴維·愛德華·麥沃爾特
• 申請（專利權）人: 數據連接有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京康信知識產權代理有限責任公司
• 代理人: 余 剛;尚志峰

技術領域

本發明涉及數據庫和用于在數據庫樹結構中存儲和搜索數據 的方法。特別地，但不排他地，本發明涉及對存儲在數據庫樹結構 中的數據的處理，供數據包路由應用程序之用。

背景技術

網際協議(IP)網絡包括許多互連路由器實體，其負責作出關 于數據包可以從源流到目的地的那些路徑的決定。路由協議被用于 獲取關于網絡的信息，并確定特定網絡目的地或不同區域或該網絡 的子網絡之間的路由。在每個路由器處，可以將這些路由存儲在被 稱為路由表的數據庫中。創建和維護路由表內容的過程通常被稱作 為IP路由。

路由器還可以存儲執行轉發數據庫中的數據包所必須的信息， 其通常被稱作為轉發表。使用存儲在轉發表中的信息接收數據包并 將該數據包發送到其目的地上的處理通常被稱作為IP轉發。

通常不直接將路由表用在包轉發處理中。而是，包路由處理根 據路由信息和一個或多個路由協議(諸如路由選擇信息協議(RIP) 或邊界網關協議(BGP))將關于所選路由的數據輸出到轉發表。 然后，可以(例如)使用有效的硬件實現方式在包轉發過程期間訪 問轉發表的內容。

被傳輸到IP網絡中的數據包將包括IP目的地址。IPv4地址是 32位長，其給出了超過40億的IP地址的范圍，而IPv6地址更長。 在每個路由器處為這個數目的IP地址交換和更新轉發信息通常是 不切實際的。

代替地，路由器將通常地維護包含許多IP地址前綴條目和對 應于這些前綴條目的每一個的轉發信息的轉發表。當關于網絡目的 地址的信息到達路由器時，可以由該路由器檢查網絡目的地的IP 地址，然后，該路由器可以搜索其路由表，查找對網絡目的地的IP 目的地址的最長的匹配。該最長的匹配按照匹配目的IP地址的最長 前綴的形式出現，即，具有匹配IP網絡地址的最大數目的初始位的 路由。這被稱作為‘最長前綴匹配’。

然后，路由器可以將該信息輸出到轉發表，從而當該目的地址 的數據包到達該路由器時，可以使用包含在轉發表中的轉發信息通 過該路由器中的包轉發功能或模塊轉發這些數據包。可以按照所需 的頻率來重復包轉發處理，可以將數據包從一個路由器轉發到另一 個路由器，直到其到達期望的IP目的地址。

通常地，將IPv4地址表示為通過小數點所分隔的一連串的四 個十進制數。每個十進制數代表32位IPv4地址的八個位，從而每 個十進制數處于從零至255的范圍。

前綴指的是IP地址或其初始部分。使用IPv4，例如“192.168/16” 是“192.168.1.4”、“192.168.200.200”、以及“192.168.26.8”等的 16位前綴。事實上，“192.168/16”是所有地址為“192.168.x.y”的 16位前綴，其中，0≤x≤255，以及0≤y≤255。這樣，路由器處 包含前綴“192.168/16”的路由信息的路由表能夠對范圍在 “192.168.x.y”內的所有IP目的地址的數據包進行路由。然而，路 由器還可以包含諸如“192.168.4.5”的32位IP目的地的更具體的 路由信息。這樣，網絡IP地址可以與路由器的路由表中的所有前綴 進行比較，以提供最長匹配前綴形式的合適的(諸如更具體地)路 由信息，然后可以將該信息輸出到轉發表。

這樣，IP網絡中的路由過程涉及通過大量路由器的路由表的大 量搜索。此外，當添加新路由并且其他路由變為廢棄時，會頻繁地 改變路由表。因此，就較高搜索速度同時所需數據存儲資源保持較 低而言，期望實現這些系統的算法和數據結構是高效的。

樹是廣泛使用的一種具有樹形狀的數據結構，該樹形狀具有一 組基于根節點的鏈接節點。每個節點可以包含值或條件，并具有零 個或多個子節點，其緊接著位于樹中的每個節點之下。具有孩子的 節點被稱為孩子的雙親。節點具有至多一個雙親。葉節點是具有零 個子節點的樹數據結構的節點，其常常離根節點最遠。

節點的祖先是該節點的雙親，或該節點的雙親的雙親等。根是 樹中所有其他節點的祖先。給定節點的一組祖先是從根到該節點通 過該樹的(最短)路徑。節點的后裔是該節點的孩子，或該節點的 孩子的孩子等。當且僅當節點B是節點A的后裔時，節點A是節 點B的祖先。