基數(shù)樹

對(duì)于長整型數(shù)據(jù)的映射。怎樣解決Hash沖突和Hash表大小的設(shè)計(jì)是一個(gè)非常頭疼的問題。
radix樹就是針對(duì)這樣的稀疏的長整型數(shù)據(jù)查找，能高速且節(jié)省空間地完畢映射。借助于Radix樹，我們能夠?qū)崿F(xiàn)對(duì)于長整型數(shù)據(jù)類型的路由。

利用radix樹能夠依據(jù)一個(gè)長整型（比方一個(gè)長ID）高速查找到其相應(yīng)的對(duì)象指針。這比用hash映射來的簡(jiǎn)單，也更節(jié)省空間，使用hash映射hash函數(shù)難以設(shè)計(jì)，不恰當(dāng)?shù)膆ash函數(shù)可能增大沖突，或浪費(fèi)空間。

radix tree是一種多叉搜索樹。樹的葉子結(jié)點(diǎn)是實(shí)際的數(shù)據(jù)條目。每一個(gè)結(jié)點(diǎn)有一個(gè)固定的、2^n指針指向子結(jié)點(diǎn)（每一個(gè)指針稱為槽slot，n為劃分的基的大小）

插入、刪除

radix Tree(基數(shù)樹) 事實(shí)上就幾乎相同是傳統(tǒng)的二叉樹。僅僅是在尋找方式上。利用比方一個(gè)unsigned int的類型的每個(gè)比特位作為樹節(jié)點(diǎn)的推斷。

能夠這樣說，比方一個(gè)數(shù)1000101010101010010101010010101010，那么依照Radix 樹的插入就是在根節(jié)點(diǎn)，假設(shè)遇到0。就指向左節(jié)點(diǎn)。假設(shè)遇到1就指向右節(jié)點(diǎn)，在插入過程中構(gòu)造樹節(jié)點(diǎn)，在刪除過程中刪除樹節(jié)點(diǎn)。假設(shè)認(rèn)為太多的調(diào)用Malloc的話，能夠採用池化技術(shù)。預(yù)先分配多個(gè)節(jié)點(diǎn)。
（使用一個(gè)比特位推斷。會(huì)使樹的高度過高，非葉節(jié)點(diǎn)過多。故在實(shí)際應(yīng)用中，我們通常是使用多個(gè)比特位作為樹節(jié)點(diǎn)的推斷，但多比特位會(huì)使節(jié)點(diǎn)的子節(jié)點(diǎn)槽變多。增大節(jié)點(diǎn)的體積，一般選用2個(gè)或4個(gè)比特位作為樹節(jié)點(diǎn)就可以）

如圖：

插入：

我們?cè)诓迦胍粋€(gè)新節(jié)點(diǎn)時(shí)，我們依據(jù)數(shù)據(jù)的比特位，在樹中向下查找，若沒有對(duì)應(yīng)結(jié)點(diǎn)，則生成對(duì)應(yīng)結(jié)點(diǎn)，直到數(shù)據(jù)的比特位訪問完，則建立葉節(jié)點(diǎn)映射對(duì)應(yīng)的對(duì)象。

刪除：

我們能夠“惰性刪除”，即沿著路徑查找到葉節(jié)點(diǎn)后，直接刪除葉節(jié)點(diǎn)，中間的非葉節(jié)點(diǎn)不刪除。

應(yīng)用

Radix樹在Linux中的應(yīng)用：

Linux基數(shù)樹（radix tree）是將long整數(shù)鍵值與指針相關(guān)聯(lián)的機(jī)制，它存儲(chǔ)有效率。而且可高速查詢，用于整數(shù)值與指針的映射（如：IDR機(jī)制）、內(nèi)存管理等。
IDR（ID Radix）機(jī)制是將對(duì)象的身份鑒別號(hào)整數(shù)值ID與對(duì)象指針建立關(guān)聯(lián)表。完畢從ID與指針之間的相互轉(zhuǎn)換。

IDR機(jī)制使用radix樹狀結(jié)構(gòu)作為由id進(jìn)行索引獲取指針的稀疏數(shù)組，通過使用位圖能夠高速分配新的ID，IDR機(jī)制避免了使用固定尺寸的數(shù)組存放指針。IDR機(jī)制的API函數(shù)在lib/idr.c中實(shí)現(xiàn)。

Linux radix樹最廣泛的用途是用于內(nèi)存管理。結(jié)構(gòu)address_space通過radix樹跟蹤綁定到地址映射上的核心頁，該radix樹同意內(nèi)存管理代碼高速查找標(biāo)識(shí)為dirty或writeback的頁。

其使用的是數(shù)據(jù)類型unsigned
long的固定長度輸入的版本號(hào)。每級(jí)代表了輸入空間固定位數(shù)。Linux radix樹的API函數(shù)在lib/radix-tree.c中實(shí)現(xiàn)。（把頁指針和描寫敘述頁狀態(tài)的結(jié)構(gòu)映射起來。使能高速查詢一個(gè)頁的信息。）

Linux內(nèi)核利用radix樹在文件內(nèi)偏移高速定位文件緩存頁。
Linux(2.6.7) 內(nèi)核中的分叉為 64(2^6)。樹高為 6(64位系統(tǒng))或者 11(32位系統(tǒng))，用來高速定位 32 位或者 64 位偏移，radix tree 中的每個(gè)葉子節(jié)點(diǎn)指向文件內(nèi)相應(yīng)偏移所相應(yīng)的Cache項(xiàng)。

【radix樹為稀疏樹提供了有效的存儲(chǔ)，取代固定尺寸數(shù)組提供了鍵值到指針的高速查找。】

后記

Radix樹與Trie樹的思想有點(diǎn)類似。甚至能夠把Trie樹看為一個(gè)基為26的Radix樹。

（也能夠把Radix樹看做是Tire樹的變異）
Trie樹一般用于字符串到對(duì)象的映射。Radix樹一般用于長整數(shù)到對(duì)象的映射。

trie樹主要問題是樹的層高。假設(shè)要索引的字的拼音非常長非常變態(tài)，我們也要建一個(gè)非常高非常變態(tài)的樹么？
radix樹能固定層高（對(duì)于較長的字符串，能夠用數(shù)學(xué)公式計(jì)算出其特征值，再用radix樹存儲(chǔ)這些特征值）

【相關(guān)代碼能夠參考】

http://www.cnblogs.com/Bozh/archive/2012/04/15/radix.html

----------------------------------
感謝您的訪問。希望對(duì)您有所幫助。 歡迎大家關(guān)注、收藏以及評(píng)論。

----------------------------------

總結(jié)

以上是生活随笔為你收集整理的查找——图文翔解RadixTree（基数树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。