假定有一個lP地址是10011011 01111010 00000000 00000000，需要查NAT-15DC-1.5A找該地址是否在此二叉線索中。我們從最左邊查起。很容易發(fā)現(xiàn)，查到第三個字符（即前綴10后面的0）時，在二叉線索中就找不到匹配的，說明這個地址不在這個二叉線索中。

   以上只是給出了二叉線索這種數(shù)據(jù)結(jié)構(gòu)的用法，而并沒有說明“與唯一前綴匹配”和“與網(wǎng)絡(luò)前綴匹配”的關(guān)系。顯然，要將二又線索用于路由表中，還必須使二叉線索中的每一個葉節(jié)點包含所對應(yīng)的網(wǎng)絡(luò)前綴和子網(wǎng)掩碼。當(dāng)搜索到一個葉節(jié)點時，就必須將尋找匹配的目的地址和該葉節(jié)點的子網(wǎng)掩碼進(jìn)行逐位“與”運算，看結(jié)果是否與對應(yīng)的網(wǎng)絡(luò)前綴相匹配。若匹配，就按下一跳的接口轉(zhuǎn)發(fā)該分組。否則，就丟棄該分組。

   總之，二又線索只是提供了一種可以快速在路由表中找到匹配的葉節(jié)點的機制。但這是否和網(wǎng)絡(luò)前綴匹配，還要和子網(wǎng)掩碼進(jìn)行一次邏輯與的運算。

   為了提高二叉線索的查找速度，廣泛使用了各種壓縮技術(shù)。例如，在圖4-26中的最后兩個地址，其最前面的4位都是1011。因此，只要一個地址的前4位是1011，就可以跳過前面4位（即壓縮了4個層次）而直接從第5位開始比較。這樣就可以減少查找的時間。當(dāng)①注：線索(trie)來自retr/eval（檢索），讀音與“try”相同。