寫這篇文章的時候使用的是FreeBSD5.1的代碼，舉例用的是IPv6地址。BSDradixDonaldR.Morrison1968樹PracticalAlgorithmToRetrieveInformationCodedInAlphanumerc。這是一種基于以二進制表示的鍵值的查找樹，尤其適合于處理非常長的、可變長度的鍵值Partricia的基本思想是構建一個二叉樹，在每個節點中都存儲有進行下一次bitbit上的Patriciabitbit測試結果決定查找操作的前進方向BSDPartriciaPartriciaBSD的radixBSD的radixPartricia查找，終結于某個葉子節點節點的重復鍵鏈表中尋找網絡匹配的可能BSDBSDradix_node_headBSDradixradix就都存放在AF_INET6radix_node_head結構體的內存布局如圖1rnh_treetop8還有三個radix_noderadixrn_flags，表示這是radix3根節點組成的數組rnh_treetop指針指向個根節點被初始化為頂部節點的右孩子這實際上已經搭起了一個radix2在圖2子節點。BSDBSDradixbit點時需要判斷是01的bitbitIP內部節點前已述及，內部節點在radix樹中用于表示一個bit測試位置。radix_node通過內部節點來查看一下radix_noderadix33radix_mask結構體鏈表。對于內部節點來說這個鏈表上的掩碼都取自它的子樹中的葉子節點所對應的掩碼AND運算時能夠把這個內部節點的測試bit0的rn_mklist指針就會指向這個掩碼鏈表中對應于它自己的掩碼的那個節點。指向它自己的。路由查找時的回溯過程將沿父指針進行。bitIP地址的socket-10的bitsocket:這是一個1bit為1。在實際的路由查找中，為了加快查bitbit點，這個字段為0。rn_flags:這個字段的可能取值一共有3個，RNF_NORMAL，表示這是一個含有常規路由的葉子節點；RNF_ROOT，表示這是一個位于radix_node_head結構體中的節點，即路由表中的三個根節點；RNF_ACTIVE，表示這條路由的狀態是好的。socketrn_bmaskrn_L:這是內部節點獨有的字段，指向這個內部節點的左孩子。rn_R:這是內部節點獨有的字段，指向這個內部節點的右孩子。葉子節點葉子節點和內部節點的大部分字段都是一樣的義已在前面的內部節點部分進行了描述，最后三個字段的定義如下。rn_Off子節點鍵值（即IP）的socketrn_Pfxlen:這個字段就內存位置而言相當于內部節點中的rn_L字段。這個字段用于存儲前綴長度。rn_Dupedkey:rn_R況出現的時候，即有多個葉子節點的鍵值IP地址）相同，這些葉子節點是以鏈表的形式掛接在樹在radix根節點radix233RNF_ROOT志，以表示它們是根節點。中間的那個根節點是radixbit64，socketBSD際的BSDbit64，整個radixbit64bit此，第64bit1000。另外的兩個根節點分列于樹的最左端和最右端。我們可以看到，它們rn_bit01在路由查找操作中，任何時刻都不能返回根節點本身。如果查找操作定位到了根節點，將代之以返回空指針。重復鍵節點BSD路由表中的重復鍵節點是指路由樹中鍵值IP地址）完全相同的葉子節點。rn_Dupedkey這串重復鍵節點，就可以保證掩碼最長的路由最先匹配。BSDBSDrtentry到的內部節點和外部節點實際上都是存放在這個結構體中的rtentry4我們可以看到，在rtentryradix_nodeIPrtentryrtentry結構體，并對應著各自的葉子節點。在rtentry結構體的剩余部分中存儲的是這條路由的接口、接口地址以及網關路由等關鍵信息。BSDBSDPatriciaBSDradix樹。在這種樹bitbit邏輯AND成0第一步：尋葉這一步實際上就是Patriciabitbit0還是1止。當radix_node結構體作為內部節點的時候bitrn_bitbitIP位這個bitbitrn_Offrn_bmaskbit對于socket8bitbit1bitBSD564的那個內部節點就是radix樹的頂端根節點，即在初始化路由表時生成的三個根節點中的中間一個64這個數字是IPv6地址的第一個bit在socketIPv6bitradix樹中查找FE80::210:5CFF:FEC2:38E7這條路由。從樹的頂端開bit64bit1，向右。第65bit1，繼續向右。第71bit，向左。第128bit0，繼續向左。第160bit1到一個rn_bit0第一步的查找路徑在圖5中用紅色曲線進行了標識。第二步：辨重如果在第一步中找到的葉子節點與查找鍵不滿足匹配的條件IP地址）是完全相同665各自掩碼的長短，可以看出，掩碼是呈逐漸變短趨勢的。bitradix_node0的bitbit際的掩碼操作。如果在重復鍵鏈表中有某個葉子節點滿足網絡匹配條件了。第二步的查找路徑在圖65鍵鏈表中。第三步：回溯IPradixbitradix樹中還存在有其它可能滿足網絡匹配條件的葉子節點7回溯過程在圖7rn_parent即它的rn_mklist7這里首先就遇到了一個問題radix為什么要回溯？在第一步“尋葉”中，我們根據查找鍵的一系bit.它和我們在第一步中找到的葉子節點有共同部分；.它的掩碼短于或等于它和第一步中的葉子節點的共同部分；.它的掩碼短于或等于查找鍵和第一步中的葉子節點的共同部分。為什么可以回溯？如果radix樹中存在滿足上述條件的葉子節點，那我們通過回溯算法就一定可以找到它，這是由radixbit為nIPbitn-1