這個題目有點大，而且我要嚴格控制字數，不能像《命題作文：在一棵IPv4位址樹中徹底了解IP路由表的各種查找過程》那樣扯得那麼開了。事實上，這篇作文是上 一篇作文中關于區間查找小節的擴充。
根據IP資料包協定頭的若幹字段，也叫比對域，将資料包劃分到某個類别，這就是IP資料包分類的核心。
事實上，IP路由查找的過程就是IP資料包分類的一個特例，一個極其簡單的特例，此時的比對域就是目标IP位址，而類别就是路由項或者說更簡單一點，下一 跳。此時考慮一下源位址Policy routing，随即又增加了一個比對域，即源IP位址，這時整個過程應該怎麼做呢？本文關注一種多元區間比對方案，不談其它的比如HASH比對，也不談 硬體算法。
在HiPAC一般算法中，雖然在執行效率上講是非常好的，但是卻可能浪費大量的記憶體。可能需要采用Grid of Tries資料結構的優化方式對其存儲空間進行優化，去除備援資料。
雖然我要說的關于IP資料包分類的核心算法到此應該就結束了，但是資料包分類背後的理論，才剛剛開始。後面我會用一個執行個體來做盡可能明晰的圖解，而不是用一個統一的數學推導來說明問題，目的在于提供一個感性的畫面。
往往隻知道如何在多元連續區間集合裡讓一個IP資料包是遠遠不夠的，其實不懂這些也沒關系。如果确實懂這個，那麼就要知其然亦知其是以然。
現在，我假設通過上面提到的兩篇關于nf-HiPAC的文章，你已經知道了多元區間比對的過程，那麼我們可以脫離具體場景了，将其抽象成一個一般問題，先 看一下抽象後的示意圖，在這個圖中，我忽略了區間的大小，忽略了Rule的排列問題(最終我将會回到這個問題)：
<a href="http://s3.51cto.com/wyfs02/M00/5B/94/wKioL1UNWMfyUrmJAAKUDFdIH98560.jpg" target="_blank"></a>
在這個圖中，我們看到了很多的“?”号，意思是說，我們此時并不知道和該區間相關的Ruleset是什麼？這是為什麼呢？
我們來看第二層，也就是Dimension 2的那一層，該層中有4個節點，對應Dimension 1分裂出來的4個區間，如果想讓比對繼續下去，即繼續比對Dimension 3那一層的節點，對應的Ruleset中必須要有交集才可以，是以我們得到了下面這個更加清晰的圖示，雖然，它有點亂。。。。在寫這個文章時，我不知怎麼 想起了哈爾濱，想哭...：
<a href="http://s3.51cto.com/wyfs02/M01/5B/94/wKioL1UNWNqi_UHuAAMg8uowYVA613.jpg" target="_blank"></a>
我們依照這個圖，發現了下面重要的三個關鍵點：
當 前區間的Ruleset與下一個次元的各個區間的Ruleset并集取交集，該結果集合不為空時才會擴充該分支成一個孩子節點。我加入了一些與場景相關的 限制，比如每一個區間起碼要有一個Default Rule，是以所有的取交集的結果均不會為空，是以上面的這句話應該是，如果結果集合的元素個數為1，且該元素為Default Rule的話，則該目前區間對應的下一個比對次元孩子擴充為葉子節點。這意味着，下下一個次元将不會再擴充該子樹，也就是說比對沒有必要繼續下去了，直接 取Default Rule即可。
如關鍵操作所示，隻要比對會繼續進行下去，即相關的目前 區間剩餘的Ruleset中Rule數量不為1或者為1但是不是Default Rule，那麼我們就不能确定最終結果，是以，這意味着快速成功是不可能的。但是我們卻可以很快确定什麼情況下會失敗，即目前區間的Ruleset中隻剩 下了1個Default Rule。這就是快速失敗。
通過上面的圖示可以看出，由于 Ruleset是取交集，Dimension 1/2/3誰在前誰在後其實最終并不影響結果，但是這個排序的不同卻可以影響空間的占用，從上圖可以看出，隻要Ruleset有交集，就要在下層建立一個 孩子節點，其實就是建立一個區間查找樹，而我們在快速失敗中知道，所有的子樹可能由于Ruleset布局的不同而導緻其高度并不相同。問題是，我們如何來 排列次元的查找順序？
不要指望在上面的那棵樹上作什麼平衡操作，因為影響其子樹高度以及寬度的因素是互相關聯的，它們是Rule的數量，每一個次元的區間數量，Ruleset的内部布局等。這棵樹的任意“旋轉”将會導緻其稱為一團亂麻，它不是三角架。
由于根本就沒有好的辦法去計算如何最優化排列這些次元比對順序，倒不如按照統計的意義，尋找一種“讓這棵樹”更加平衡的方式。
到 此為止，我們一直覺得所謂的多元區間比對就是一個M叉樹，其中M是每層由該層，即該次元所被劃分的區間數量。通過以上的分析，我們發現在一個如此胖的且每 個分支的高度還不确定的樹中尋找一種最佳的建構方式是一件困難的事情，因為變量太多了，Ruleset中Rule的數量是一個變參，區間數量也是一個變 參，各個次元的每一個區間的Ruleset都要取并集，這涉及到一個笛卡爾積的問題。這裡面涉及太多的數學計算，又沒有一個簡單的公式。
難道多元區間比對樹一開始就必須如此構造成M叉樹嗎？
在繼續之前，我來用一種更加直覺的方式展示上述的多元比對問題，然後從0開始，直到我們遇到KD樹為止，剩下的内容，資料結構，算法相關的書上就都有了。
幸虧我以三維域比對為例，要不然我真不知道四維立方體怎麼畫出來。
我把上面的三維域比對問題以一個立方體來描述：
<a href="http://s3.51cto.com/wyfs02/M01/5B/9A/wKiom1UNV8qTTcUSAAJfj45ihrs960.jpg" target="_blank"></a>
注 意到，每一個黑色的點沿着坐标軸連接配接成的線段進而由這些線段形成的面将這個立方體分割成了4*3*2個子立方體，我們的問題就是，最終比對完成後，我們會 落入一個子立方體中，而這個子立方體裡面目前的Ruleset就是結果集，我們取優先級最大的，就是最終結果，值得注意的是，這些子立方體中的 Ruleset是在構造這個立方體的時候放進去的，和那篇講路由查找的命題作文一樣，我并不考慮相對稀有的資料結構構造事件的時間複雜度。是以，我将 Ruleset示意圖放入子立方體，如下圖所示：
<a href="http://s3.51cto.com/wyfs02/M02/5B/94/wKioL1UNWQvg7gVUAAMthfnau4Q485.jpg" target="_blank"></a>
那麼現在問題來了。我要怎麼切割這個立方體，然後最後得到那個期望的子立方體呢？第一刀怎麼切？沿着D1軸？D2軸？D3軸？如果确定了D1軸，那麼第二刀呢？繼續D1軸？還是換一個方向切？...
這不禁讓人想到切西瓜，但是事實上卻完全不同，這個和你用一大塊木頭塊取中心的小塊比較類似。你有兩種方式，先把它削成片，再把它削成棍，最後把棍剁成小塊；還有一種方式比較類似機床銑床那般，始終不斷變換方向切割。對于多元比對問題，我們面臨了同樣的選擇。
這種方式類似片-棍-塊的方式，如下圖所示：
<a href="http://s3.51cto.com/wyfs02/M02/5B/9A/wKiom1UNV_Gj5FZgAAXftW7eXQc423.jpg" target="_blank"></a>
這個比較類似機器加工的方式，如下圖所示：
<a href="http://s3.51cto.com/wyfs02/M00/5B/94/wKioL1UNWWPSdrD5AAfApy3hPMk431.jpg" target="_blank"></a>
那麼，是時候給出資料結構了。我在講路由查找的作文中的區間查找小節給出了區間二叉查找樹的結構以及構造方式，本文中對此前提作了基本假設。
深度優先的查找樹結構如下：
<a href="http://s3.51cto.com/wyfs02/M00/5B/9A/wKiom1UNWErTlpH8AAKLu92Vfq0135.jpg" target="_blank"></a>
可見，這是一種直接的方式，特别适合精确比對。以下我提到Dimension Tree或者Dimtree的時候，指的就是這棵樹。
廣度優先的查找樹結構如下：
<a href="http://s3.51cto.com/wyfs02/M01/5B/94/wKioL1UNWYvBl56HAAQo_M7Hvuw079.jpg" target="_blank"></a>
可 見，這是一種碰運氣的方式，在各個次元上逐漸(以盡可能細的粒度，小心翼翼地)接近最終要落到的子立方體空間。當然這種方式其實就是Dimension Tree的逐層旋轉後展開的結果，最終也可以得到答案，碰到某個次元的葉子節點後，将其中的Ruleset壓入一個棧中，最終在這棵樹遊曆結束後，将棧裡 面的Ruleset取出後求交集，然後取最佳的即可。當然，也可以用快速失敗來剪掉枝幹，比如到達了一個隻包含Default Rule的葉子節點。但是，第一次發現葉子節點的時刻要等多久呢？如果第一個次元的查找樹有3層，第二次元有2層，第三次元有2層，那麼廣度優先樹的層則 為：第一次元-第二次元-第三次元-第一次元-第二次元(首次碰到葉子)-第三次元(葉子節點)-第一次元....不管怎麼說，即便從第二次元開始切割， 也不可能在第二層碰到葉子...這就說明，即便是快速失敗的檢測，也要比深度優先延後。
對于資料包精确比對分類來 講，深度優先的方式好于廣度優先的方式，這不僅僅是在說如果沒有精确區間比對，那麼再接近的比對也不算(比如精确比對192.168.1.18，那麼 192.168.1.19顯然是不符合要求的，雖然它很接近)，還包括這種方式可以最大限度的利用系統Cache。
注意，不要認為資料包的掩碼比對就不是精确比對，本文是嚴格基于區間來比對的，掩碼将一個域劃分成了多個精确的區間，而最終的目的是定位一個資料包的某個域精确落到了哪個區間中，注意，這是一種精确比對。
KD樹，即k-dimension樹就采用了上述逐次元廣度優先的比對方式。然而它的次元排序思想可以被借鑒，進而用于深度優先比對，最終目标是建構一棵“若不比對則快速失敗”的樹！
看起來，這像極了一棵B-樹，但它不是！
KD樹的資料網上實在太多。我要說的是它的遞歸建構中是如何使用方差的。現在讓我們回答第一刀從哪裡切割的問題。
我将區間長度作為基準，那麼每個次元均可以計算出一個區間長度的方差數值，即：
取這個值最大的次元為第一次元，然後使用樸素的二分建構，取該次元區間全集中最接近中點的那個點作為根，開始遞歸建構二叉樹。每一層都要計算該子域的方差，進而根據這個最大方差原則選出子樹的二分根。通過上面的廣度優先比對可以看出，那個圖應該就是一棵樸素的KD樹。
采用最小方差的思想的目的是，讓這棵樹平衡一些，方差比較大說明這個次元上的區間分布比較均勻，标示點并沒有集中在平均值附近，這樣切割的時候就不會一下 子切掉一大塊，進而錯過了可能比較接近最終答案的那些區域(最終結果的逼近原則：切割粒度盡可能小，一定要小心翼翼，類似削梨或者削鉛筆那樣的)。注 意，KD樹的目标并不是精确比對，而是模糊最佳比對，比如經典的尋找K個最接近的點。
由 于深度優先比對并不是遞歸建構的，是以不需要每一步都去計算方差進而确定切割的次元，對于深度優先比對而言，隻要确定了某個次元，那麼将在這個次元上直接 切割完畢，對于三維情況而言，就是直接切成一個片，對于二維而言就是切成一根棍...對于接下來的切割就不需要再考慮這個次元了，因為在這個次元，它已經 精确到達它的區間了。是以，我們隻需要找出一個次元序列就可以了。
還是像KD樹一樣基于方差嗎？不一定。此時我們希望的是，讓Rule在各個區間分布最不平均的次元作為第一維，依次類推。這是因為，Rule分布不平均在 和下一維的Ruleset并集取交集的時候，對應區間在經過取交集計算後，出現唯一Default Rule進而導緻快速失敗的可能性比較大，這就會減少孩子節點的數量，對于一棵M叉樹而言，越是剪掉靠近根的節點的孩子，越能抑制下層節點的瘋長。我們判 斷是否擴充該孩子的公式為：
目前次元區間Ruleset & (next次元各個Ruleset的并集)
我們不好控制next 次元的各個區間Ruleset的并集，我們甚至不知道next次元是哪個，但是我們可以找到目前次元的Ruleset分布情況。舉一個最簡單的例子，有一 個次元劃分了4個區間，第一個區間的Ruleset中有10條，後三個區間中均是2條，那麼僅有2條Rule的區間和别人取交集時很可能是空，這就為我們 找到了一個計算的依據，很顯然，我們這次不用KD樹的方差，而是将權值表示成一個區間數量，區間Rule的分布情況(這個變量可以用方差也可以不用)的函 數，進而算出最終的排序。最樸素的計算還是使用方差，計算每個次元區間中Rule數量的方差，取最小值為最高權值，這說明Rule在某個區間的分布比其它 區間更加集中，進而有更高的可能切掉孩子的臍帶導緻“快速失敗”！
這是個問題嗎？不是問題。
本文中，我們以區間為基準，是以就可以把Ruleset進行拆分。舉一個最簡單的例子，設定Rule1，2的區間192.168.1.0/24被設定Rule1，3區間192.168.0.0/16覆寫，但是這不是問題，解決如下圖所示：
<a href="http://s3.51cto.com/wyfs02/M01/5B/9A/wKiom1UNWHPi2hkRAACSQ4zTbhQ882.jpg" target="_blank"></a>
不要在一棵樹上吊死！
我們非要将整個比對資料結構塞到一棵樹中嗎？如果非要這麼做，我們就失去了并行操作的可能性，因為一棵樹的從根到葉子的路徑隻有一條路徑，鑒于下層分支巨 量，瞎猜隻是掰扯，你幾乎不可能猜對分支。那麼怎麼辦呢？由于最終的結果是N個次元(在我們的例子中，N為3)的比對區間Ruleset取交集，那麼就好 辦了，N個次元分别建構N棵樹，N個處理程序同時運算，最終取交集。讓我們回到最初的那幅圖，點一下題：
<a href="http://s3.51cto.com/wyfs02/M02/5B/94/wKioL1UNWbOggOwRAAEG0Z404_Y871.jpg" target="_blank"></a>
本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1622852
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)