基樹（Radix tree），是一種基於二進製表示鍵值的二叉查找樹，正是由於其鍵值的這個特點，所以隻有在特定的情況下才會使用，典型的應用場景有文件係統、路由表等。關於基樹的理論知識，在一些數據結構或算法書籍上有詳細描述，所以這裏直接來看Nginx基樹的具體實現。
按慣例，從其初始函數ngx_radix_tree_create()開始分析，代碼首先分配了基樹描述結構ngx_radix_tree_t的內存，然後創建了一個隻有根節點的基樹，如圖4-11所示。
圖4-11 隻包含有根節點的基樹
在ngx_radix_tree_t結構體中，除root以外的幾個字段都是為了對該基樹所使用的內存進行管理所做的設計，free字段下掛載的是當前空閑的樹節點（即從樹裏刪除出來而沒被使用的廢棄節點，這個節點所占內存空間既沒有返還給內存池，也沒有返還給係統）。這些節點以單鏈表的形式組織起來（把節點描述結構ngx_radix_node_t的right字段當鏈表的next字段使用），所以在節點申請函數ngx_radix_alloc()裏，會先去這個空閑鏈表查找是否有廢棄節點可用。如果有的話，就直接取鏈頭節點返回；否則就要申請（如果之前沒申請過頁內存或者上次剩餘內存不足一個基樹節點）一頁內存（ngx_pagesize大小，有對齊處理），然後先從中分出一個待分配的基樹節點，剩下內存的起始地址和大小分布記錄在tree->start和tree->size字段裏，以便下次分配基樹節點時，可從該剩餘內存裏直接獲取。讀者會有個疑問，對於申請的頁內存，基樹相關代碼裏怎麼沒有釋放，並且如果申請第二塊內存頁則第一塊內存頁的起始地址都搞丟了，這會不會導致內存泄露？當然不會，這些基樹內存的最終回收會在Nginx內存池裏處理，所以不用擔心。
關於基樹對內存的管理與使用，上麵就介紹完了，下麵再來專心看基樹本身的相關邏輯。在函數ngx_radix_tree_create()創建完隻有根節點的基樹後，還會根據參數preallocate進行樹節點的創建。如果該值指定為0，表示不需預創建而直接返回；如果preallocate為正數n，則表示要預創建的基樹（預創建的是一顆滿二叉樹，即，除了葉子節點，其他節點的子節點都有左右兩個子節點）深度（假定根節點的層次為0，樹深度定義為最大的葉結點層次，也就是說如果preallocate值為1，那麼樹深度為1，接下來將創建2個樹節點；如果preallocate指定為2，那麼樹深度為2，那麼接下來將一共創建6個樹節點）；如果preallocate為?1，則表示要選擇一個默認深度，這根據平台的不同而不同。如果為其他負數，那這就是一個未被函數ngx_radix_tree_create()所處理的異常輸入，比如如果為?2，那麼將幾乎創建無數多個樹節點而必定由於內存不足而失敗，所以調用函數ngx_radix_tree_create()時需特別小心。
根據平台的不同選擇默認深度的代碼也有bug
[]
，不過這是一個“筆誤”，在計算一頁內存可以存放多少樹節點時用錯了結構體。
代碼第63行的代碼sizeof(ngx_radix_tree_t)應該為sizeof(ngx_radix_node_t)，這個bug不算嚴重，僅影響默認預創建的節點個數，所以會稍微影響一下性能（或者說沒有其原本的期望目標性能那麼好）。如何選擇默認深度是從性能上來考慮的，認為默認預分配的節點所占內存總大小為一頁即為最佳（這隻是Nginx代碼作者的一種經驗看法），這樣認識是否恰當我們不做評論，按此計算，在x86 32位平台上，一個節點大小為16字節，所以一頁4KB內存可以創建256個節點，那麼代表樹的深度的preallocate值也就是7（即總節點數 = 2^(樹深度 + 1) – 1，因為這裏預創建的是一顆滿二叉樹）。其他的平台情況類似計算即可。