IP Lookup 演算法 – Multibits Trie

「Binary Trie」這個演算法非常簡單易懂,而且也相當好實作。但在搜尋的速度上, 仍有許多待改進的空間,最大的問題在於「Binary Trie」這個演算法建立的二元搜尋樹太深了! 1 個位元一層, 32 個位元就可能要往下 32 層,也就是說可能就要比較 32 次才會得到結果, 自然效果不太好。

於是有人問了:「為什麼要這麼麻煩呢?既然一個位元一個位元比較速度不夠快, 那一次比較好幾個位元不就得了?」

Continue reading