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

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

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

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

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