對無分類編址的路由表的最簡單的查找算法就是對所有可能的前綴進(jìn)行循環(huán)查找。例如，NAT-10DC-2.5A給定一個(gè)目的地址D。對每一個(gè)可能的網(wǎng)絡(luò)前綴長度M，路由器從D中提取前M個(gè)位成一個(gè)網(wǎng)絡(luò)前綴，然后查找路由表中的網(wǎng)絡(luò)前綴。所找到的最長匹配就對應(yīng)于要查找的路由。

   這種最簡單的算法的明顯缺點(diǎn)就是查找的次數(shù)太多。最壞的情況是路由表中沒有這個(gè)路由。在這種情況下，算法仍要進(jìn)行32次（具有32位的網(wǎng)絡(luò)前綴是一個(gè)特定主機(jī)路由）。就是要找到一個(gè)傳統(tǒng)的B類地址（即/16），也要查找16次。對于經(jīng)常使用的默認(rèn)路由，這種算法都要經(jīng)歷31次的不必要的查找。

  為了進(jìn)行更加有效的查找，通常是把無分類編址的路由表存放在一種層次的數(shù)據(jù)結(jié)構(gòu)中，然后自上而下地按層次進(jìn)行查找。這里最常用的就是二叉線索(binary trie)①，它是一種特殊結(jié)構(gòu)的樹。IP地址中從左到右的比特值決定了從根節(jié)點(diǎn)逐層向下層延伸的路徑，而二叉線索中的各個(gè)路徑就代表路由表中存放的各個(gè)地址。

  用一個(gè)例子來說明二叉線索的結(jié)構(gòu)。圖中給出了5個(gè)lP地址。為了簡化二叉線索的結(jié)構(gòu)，可以先找出對應(yīng)于每一個(gè)lP地址的唯一前綴(unique prefix)。所謂唯一前綴就是在表中所有的IP地址中，該前綴是唯一的。這樣就可以用這些唯一前綴來構(gòu)造二叉線索。在進(jìn)行查找時(shí)，只要能夠和唯一前綴相匹配就行了。

   從二叉線索的根節(jié)點(diǎn)自項(xiàng)向下的深度最多有32層，每一層對應(yīng)于lP地址中的一位。一個(gè)lP地址存入二叉線索的規(guī)則很簡單。先檢查lP地址左邊的第一位，如為0，則第一層的節(jié)點(diǎn)就在根節(jié)點(diǎn)的左下方；如為1，則在右下方。然后再檢查地址的第二位，構(gòu)造出第二層的節(jié)點(diǎn)。依此類推，直到唯一前綴的最后一位。由于唯一前綴一般都小于32位，因此用唯一前綴構(gòu)造的-叉線索的深度往往不到32層。圖中較粗的折線就是前綴0101在這個(gè)二叉線索中的路徑。二叉線索中的小圓圈是中間節(jié)點(diǎn)，而在路徑終點(diǎn)的小方框是葉節(jié)點(diǎn)（也叫作外部節(jié)點(diǎn)）。每個(gè)葉節(jié)點(diǎn)代表一個(gè)唯一前綴。節(jié)點(diǎn)之間的連線旁邊的數(shù)字表示這條邊在唯一前綴中對應(yīng)的比特是0或1。