Radix樹

引言：總所周知，NoSQL，Memcached等作為Key—Value 存儲的模型的數據路由都採用Hash表來達到目的。如何解決Hash衝突和Hash表大小的設計是一個很頭疼的問題。 藉助於Radix樹，我們同樣可以達到對於uint32_t 的數據類型的路由。這個靈感就來自於Linux核心的IP路由表的設計。

簡介

Radix樹的設計思想來自於DonaldR.Morrison於1968年提出的Patricia樹（Practical Algorithm To Retrieve Information Coded In Alphanumeric），這是一種基於二進制表示的鍵值的查找樹，尤其適合處理非常長的、可變長度的鍵值。

Patricia的基本思想是構建一個二叉樹，在每個節點中都存儲有在進行下一次bit測試之前需要跳過的bit數目，以此來避免單路分支。Patricia樹一般由內部節點和外部節點組成，內部節點指示需要進行bit測試的位置，並根據bit測試結果決定查找操作前進的方向；外部節點用於存儲鍵值，查找操作將於外部節點處終結。

BSD路由表使用的是Radix樹。

操作步驟

BSD的Radix樹中的路由查找操作分為3步：

第一步：Patricia查找，終結於某個葉子節點，判斷該葉子節點是否與查找鍵相同。

第二步：如果找到的葉子節點無法與查找鍵匹配，則在這個葉子節點的重複鍵鍊表中尋找網路匹配的可能。

第三步：如果找到的葉子節點及其重複鍵與查找鍵不滿足網路匹配條件，則向樹頂回溯，繼續尋找網路匹配的可能。