寫這篇文章的時候使用的是FreeBSD5.1的代碼，舉例用的是IPv6地址。
BSD路由表使用的是radix樹，這種樹的設計思想來自Donald R.Morrison於1968年提出的Patricia樹（Practical Algorithm To Retrieve Information Coded In Alphanumeric）。這是一種基於以二進制表示的鍵值的查找樹，尤其適合於處理非常長的、可變長度的鍵值。Partricia的基本思想是構建一個二叉樹，在每個節點中都存儲有進行下一次的bit測試之前需要跳過的bit數目，以此來避免單路分支（即避免二叉樹的某一段呈現只往左或者只往右生長的趨勢）。因此，一般意義上的Patricia樹由內部節點和外部節點組成，內部節點用於指示需要進行bit測試的位置，並依據bit測試結果決定查找操作的前進方向，而外部節點則用於存儲鍵值，查找操作將於外部節點處終止。
BSD正是借用了Partricia樹的思想來組織路由表，但考慮到路由表的特殊性，即需要存儲掩碼並實現最長匹配路由查找，於是對Partricia樹進行了改造，形成了BSD的radix樹。在BSD的radix樹中的路由查找操作將分為三個步驟，第一個步驟即是Partricia查找，終結於某個葉子節點，判斷該葉子節點是否與查找鍵相同。第二個步驟，如果找到的葉子節點與查找鍵無法匹配，則在這個葉子節點的重復鍵鏈表中尋找網絡匹配的可能。第三個步驟，如果找到的葉子節點及其重復鍵與查找鍵不滿足網絡匹配條件，則向樹頂回溯，繼續尋找網絡匹配的可能。
BSD路由表的頭指針存放在rt_tables[]數組中，這是一個radix_node_head結構體類型的指針數組。在BSD的協議棧中，所有協議的路由表都是用radix樹進行組織的，而這些radix樹的頭指針就都存放在rt_tables[]數組中，IPv6路由表的頭指針只是其中之一，即下標為AF_INET6的數組元素。
radix_node_head結構體的內存布局如圖1所示。rnh_treetop是指向路由表頂部節點的指針。在這個結構體中還定義了8個函數指針，分別指向路由表提供的8個操作函數。在這個結構體的尾部還有三個radix_node結構體，這就是radix樹的初始三節點，它們的rn_flags字段將被設置成RNF_ROOT，表示這是radix樹的根節點。這三個節點是在路由表跏薊時生成的？
路由表初始化完成後，這三個根節點的鏈接關系如圖3所示。從這個圖中我們可以看出，在三個根節點組成的數組rnh_nodes[3]中，第二個根節點作為路由表的頂部節點，由rnh_treetop指針指向，它將是對路由表的所有操作的開始處。此外，第一個根節點被初始化為頂部節點的左孩子，第三個根節點被初始化為頂部節點的右孩子，而這三個初始根節點的父指針都指向了中間的那個頂部節點。這實際上已經搭起了一個radix樹的基本框架。如圖2所示。
在圖2中，我們將中間的作為路由樹頂的根節點用圓圈表示，因為它屬於內部節點。而另外的兩個根節點我們用方框表示，它們屬於葉子節點。在本文檔中將始終按照這一約定來圖示內部節點和葉子節點。
BSD路由表的radix樹實際上就是由一系列的內部節點和葉子節點組成的。內部節點位於樹的中間位置，每個內部節點都會指定一個bit測試位置，即當從樹的頂端開始向下查找，遇到這個內部節點時需要判斷是0還是1的bit位置，接下來的查找將根據bit測試的結果來決定是向左走還是向右走。葉子節點位於樹的邊緣，用於存儲路由表鍵值，即IP地址。
2.1 內部節點
前已述及，內部節點在radix樹中用於表示一個bit測試位置。
內部節點和葉子節點使用的都是radix_node結構體，只是少數字段的定義有所不同。我們首先通過內部節點來查看一下radix_node結構體中的各個字段。在radix樹中的3個根節點中，位於中間的那個頂端節點就是內部節點，因此我們的描述就以圖3為例。
rn_mklist:這個指針指向的是一個radix_mask結構體鏈表。對於內部節點來說這個鏈表上的掩碼都取自它的子樹中的葉子節點所對應的掩碼，但只有那些在做邏輯AND運算時能夠把這個內部節點的測試bit變成0的掩碼才能夠加入到這個鏈表中，這類掩碼的作用將在路由查找時的回溯過程中體現出來。對於葉子節點，如果它的掩碼滿足上述條件而被選入它的某一級父節點的掩碼鏈表的話，那麼它的rn_mklist指針就會指向這個掩碼鏈表中對應於它自己的掩碼的那個節點。
rn_parent:這是節點的父指針，從葉子節點一直向上指到樹的頂端節點，而樹的頂端節點的父指針是指向它自己的。路由查找時的回溯過程將沿父指針進行。
rn_bit:對於內部節點，這個值大於等於0，用於指示在這個內部節點處需要進行測試的bit位置。這個位置是從用於存儲IP地址的socket地址結構體的起始位置開始計算的。對於葉子節點，這個值是一個負數，具體數值就是-1減去這個葉子節點所對應的掩碼的索引值。而所謂掩碼的索引值就是指這個掩碼中第一次出現0的bit位置，這個位置也是從socket地址結構體的起始位置開始計算的。
rn_bmask:這是一個1字節的掩碼，其中只有一個bit為1。在實際的路由查找中，為了加快查找速度，就是使用這個字段直接對指定的字節進行bit測試，而不是指定bit進行測試。對於葉子節點，這個字段為0。
rn_flags:這個字段的可能取值一共有3個，RNF_NORMAL，表示這是一個含有常規路由的葉子節點；RNF_ROOT，表示這是一個位於radix_node_head結構體中的節點，即路由表中的三個根節點；RNF_ACTIVE，表示這條路由的狀態是好的。
rn_Off:這是內部節點獨有的字段，表示一個從socket地址結構體的起始位置開始計算的字節偏移量，用於指定在這個內部節點處需用rn_bmask進行單字節比較的字節偏移量。
rn_L:這是內部節點獨有的字段，指向這個內部節點的左孩子。
rn_R:這是內部節點獨有的字段，指向這個內部節點的右孩子。
2.2 葉子節點
葉子節點和內部節點的大部分字段都是一樣的，只是最後三個字段的定義不一樣。相同字段的定義已在前面的內部節點部分進行了描述，最後三個字段的定義如下。
rn_Key:這個字段就內存位置而言相當於內部節點中的rn_Off字段。這個字段用於指向存儲著葉子節點鍵值（即IP地址）的socket地址結構體。
rn_Pfxlen: 這個字段就內存位置而言相當於內部節點中的rn_L字段。這個字段用於存儲前綴長度。
rn_Dupedkey: 這個字段就內存位置而言相當於內部節點中的rn_R字段。當路由表中有重復鍵情況出現的時候，即有多個葉子節點的鍵值（IP地址）相同，這些葉子節點是以鏈表的形式掛接在樹中的某個葉子節點下的，rn_Dupedkey即指向重復鍵鏈表中的下一個葉子節點。
在radix樹中，左右兩個根節點即屬於葉子節點。
2.3 根節點
radix樹中的根節點即是在圖2和圖3中給出的3個節點。這三個節點都被設置了RNF_ROOT標志，以表示它們是根節點。
中間的那個根節點是radix樹的頂部節點，所有的路由查找操作都是從它開始的。我們可以看到，這個根節點的bit測試位置是64，也就是說，對於存儲在socket地址結構體中的BSD地址而言，實際的BSD地址開始的第一個bit在結構體中的偏移量是64，整個radix樹的bit比較算法就是從這第64 bit開始。前已述及，為了加快查找速度，實際的查找操作中使用的是字節偏移和字節掩碼。因此，第64 bit對應的字節偏移就是8，而字節掩碼就是二進制的1000 0000。
另外的兩個根節點分列於樹的最左端和最右端。我們可以看到，它們的rn_bit字段都小於0，表明這兩個根節點屬於葉子節點。事實上，它們一個對應的是全0鍵值，一個對應的是全1鍵值。
在路由查找操作中，任何時刻都不能返回根節點本身。如果查找操作定位到了根節點，將代之以返回空指針。
2.4 重復鍵節點
BSD路由表中的重復鍵節點是指路由樹中鍵值（IP地址）完全相同的葉子節點。
這些重復鍵節點由各自的rn_Dupedkey指針串成一個鏈表，通過位於鏈表頭部的葉子節點掛在路由樹中。位於鏈表中的重復鍵節點是按照掩碼的精確程度從高到低排列的，即位於鏈表頭部的葉子節點的掩碼最精確，對於掩碼連續的情況而言也就是它的掩碼最長。這樣在路由查找的時候如果找到了這串重復鍵節點，就可以保證掩碼最長的路由最先匹配。
如前所述，BSD路由表是由一系列的內部節點和葉子節點組織起來的，這是BSD路由表的邏輯結構。如果從內存布局來講，BSD路由表中的路由條目則是通過rtentry結構體來存放的，我們前面提到的內部節點和外部節點實際上都是存放在這個結構體中的。rtentry結構體的組成如圖4所示。
我們可以看到，在rtentry結構體的頭部就是由兩個radix_node結構體組成的數組rt_nodes[2]。在這個數組中，第一個元素是葉子節點，負責存儲路由表鍵值，即IP地址，第二個元素是內部節點，負責完成樹的連接。因此，就一般情況而言，每當往路由樹中添加一條路由的時候，我們實際上添加的是兩個節點，一個葉子節點和一個內部節點，只不過這兩個節點的存儲空間是我們事先用rtentry結構體分配好了的。雖然這兩個節點在物理上是緊挨著的，但是由於後續路由條目的加入，它們之間就可能會插入一系列的內部節點，而這些內部節點又分別屬於各自的rtentry結構體，並對應著各自的葉子節點。
在rtentry結構體的剩余部分中存儲的是這條路由的接口、接口地址以及網關路由等關鍵信息。
前已述及，BSD路由表使用的是經BSD修改之後的Patricia樹，也就是BSD radix樹。在這種樹中，內部節點用於指定需要對查找鍵進行測試的一系列bit位置，而外部節點則用於存儲鍵值。為了適合路由表的需求，每個葉子節點都會有一個與之對應的掩碼。內部節點可能有也可能沒有對應的掩碼，這取決於在它的子樹中是否存在能夠將它的測試bit邏輯AND成0的掩碼。於是，根據這些特性，BSD路由表中的路由查找就分成了三個步驟，即找到葉子節點進行精確匹配、在重復鍵鏈表中進行網絡匹配和通過回溯過程進行網絡匹配。
4.1 第一步：尋葉
這一步實際上就是Patricia查找，即從路由表的頂部節點開始，根據所遇內部節點中指示的bit測試位置進行測試，根據該bit是0還是1來決定繼續往右走還是往左走，直至到達一個葉子節點為止。
當radix_node結構體作為內部節點的時候，它的bit測試位置是由rn_bit字段來給出的。但是，僅僅是這樣一個bit測試位置對於有多個字節的IP地址來說顯然是不合適的，在查找的時候再去定位這個bit會影響查找效率，所以在添加這個內部節點的時候就會根據bit測試位置計算一個字節偏移量和相應的字節掩碼，即rn_Off和rn_bmask字段。字節偏移量用於指定bit測試位置所在字節相對於socket地址結構體起始處的偏移量，而字節掩碼則是一個8 bit的掩碼，其中只有一個bit為1，在通過字節偏移量定位了字節之後，即可由字節掩碼進行bit測試操作。
舉例而言，BSD路由表的局部如圖5所示。圖中位於最上方的標記有64的那個內部節點就是radix樹的頂端根節點，即在初始化路由表時生成的三個根節點中的中間一個，64這個數字是IPv6地址的第一個bit在socket地址結構體中的偏移量。由於所有的路由查找操作都要從樹的頂端開始向下進行，所以不管查找哪條路由，都會從IPv6地址的第一個bit開始進行比較。
假設我們現在需要在這個radix樹中查找FE80::210:5CFF:FEC2:38E7這條路由。從樹的頂端開始，根據沿途內部節點指定的bit進行測試。這條路由的第64 bit為1，向右。第65 bit為1，繼續向右。第71 bit為0，向左。第128 bit為0，繼續向左。第160 bit為1，向右。這時，將會遇到一個rn_bit字段為負值的節點，即葉子節點，於是查找操作將停止在此處。
接下來的操作就是比較找到的這個葉子節點與我們的查找鍵是否匹配。比較操作是以字節為單位進行的，參與比較的字節數將以葉子節點掩碼的最後一個非0字節為限，即若在此范圍內葉子節點與查找鍵相同則認為匹配，查找操作成功結束，否則認為不匹配，並記錄下查找鍵與葉子節點鍵值第一次出現不同的字節位置。在返回查找結果時有一點需要注意，即在任何時候都不能返回根節點自身，如果在這一步找到的葉子節點是一個根節點，那麼就必須返回它的重復鍵指針rn_dupedkey，而不是它自己。
第一步的查找路徑在圖5中用紅色曲線進行了標識。
4.2 第二步：辨重
如果在第一步中找到的葉子節點與查找鍵不滿足匹配的條件，則需要遍歷這個葉子節點的重復鍵鏈表。由於重復鍵鏈表中的葉子節點與第一步中找到的葉子節點的鍵值（也就是IP地址）是完全相同的，只是掩碼呈逐漸縮短的趨勢，因此可能在重復鍵鏈表中存在網絡匹配的可能。重復鍵處理的過程如圖6所示。
圖6是在圖5的基礎上繪制的。對於圖中所示的三個重復鍵節點，我們用綠色的長短表示了它們各自掩碼的長短，可以看出，掩碼是呈逐漸變短趨勢的。
由於在第一步中我們已經確定了查找鍵和葉子節點鍵值第一次出現不同的字節位置，因此可以方便地換算出查找鍵和葉子節點鍵值第一次出現不同的bit位置。前已述及，在葉子節點的radix_node結構體中，rn_bit字段就是由葉子節點的掩碼中第一次出現0的bit位置換算出來的。因此，在接下來的重復鍵處理中，我們只需要把查找鍵和葉子鍵值第一次出現不同的bit位置跟葉子節點的rn_bit字段進行比較就可以方便地確定某個重復鍵節點是否滿足網絡匹配的條件，而不需要進行實際的掩碼操作。
如果在重復鍵鏈表中有某個葉子節點滿足網絡匹配條件，則向調用者返回這個葉子節點。否則查找操作將回到最初找到的那個葉子節點（也就是重復鍵鏈表上的第一個節點），准備開始向樹頂回溯了。
第二步的查找路徑在圖6中依然用紅色曲線進行標識，實際上是將圖5中的紅色曲線延伸至重復鍵鏈表中。
4.3 第三步：回溯
到目前為止，我們只是使用作為查找鍵的IP地址在radix樹中根據內部節點指示的bit測試位置找到了某個葉子節點，並進行了重復鍵處理，仍然沒有找到匹配的葉子節點。這並不能排除在radix樹中還存在有其它可能滿足網絡匹配條件的葉子節點，因此就需要沿著來時的內部節點路徑向樹頂回溯，尋求網絡匹配的可能。回溯過程如圖7所示。
回溯過程在圖7中用藍色曲線標識，方向從下到上。我們可以看出，回溯過程是從第一步中找到的那個葉子節點處開始，沿著每個節點的父指針rn_parent向樹頂前進，這實際上就是我們在第一步中從樹頂找到葉子節點所經由的路徑，因此才把這一步稱為回溯。
回溯途中經過的是一系列的內部節點，對於每一個內部節點，將會判斷它是否掛的有掩碼鏈表，即它的rn_mklist字段是否為空。掩碼鏈表在圖7中用粉紅色表示。沒有掩碼鏈表的內部節點將不予考慮，直接通過。如果某個內部節點掛的有掩碼鏈表，那說明在它的子樹中可能存在著網絡匹配的可能，需要停下來做一下判斷再決定是否繼續回溯。
這裡首先就遇到了一個問題，究竟什麼樣的內部節點才掛有掩碼鏈表？這實際上就是要回答回溯的必要性和可行性，這和radix樹的組織方式即路由添加時的設計方法有關。首先需要明確下面兩個問題。
為什麼要回溯？
在第一步“尋葉”中，我們根據查找鍵的一系列bit測試結果找到了一個葉子節點，具體找到哪個葉子節點完全取決於radix樹當時的組織形態，但有一點是可以確定的，那就是這個葉子節點的鍵值在其起點之後的某個長度之內一定和我們的查找鍵是相同的。如果這個長度就是葉子鍵值的長度，那我們在第一步中就匹配成功了，否則我們就要在樹中尋找滿足以下三個條件的葉子節點：
.它和我們在第一步中找到的葉子節點有共同部分；
.它的掩碼短於或等於它和第一步中的葉子節點的共同部分；
.它的掩碼短於或等於查找鍵和第一步中的葉子節點的共同部分。
為什麼可以回溯？
如果radix樹中存在滿足上述條件的葉子節點，那我們通過回溯算法就一定可以找到它，這是由radix樹的路由添加算法決定的。在這裡我們只需要明確一個事實，那就是對於一個測試bit為n的內部節點的子樹中的所有子孫葉子節點的鍵值而言，從實際IP地址的開始bit到第n-1 bit都是相同的。舉例而言，如果一個內部節點的測試bit是71，那麼它的子樹中的所有子孫葉子節點的鍵值的第64到70共 7個bit的內容都是相同的。因此，如果這個內部節點的子樹中有某個葉子節點的掩碼短於或等於7的話，那它的鍵值事實上就是這個子樹中所有路由的公共部分，而它本身也就成了這個子樹中所有路由的普適路由。正是radix樹中的這些普適路由組成了回溯查找時的候選路由的集合。
一個內部節點的掩碼鏈表正是它的子樹中所有普適路由的記錄鏈表，而對於一條普適路由來說，則會將其掛在它所能作為普適路由的最大可能的子樹的頂端內部節點的掩碼鏈表中。