国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

1. 基數(shù)樹(shù)概述

• 對(duì)于長(zhǎng)整型數(shù)據(jù)的映射，如何解決Hash沖突和Hash表大小的設(shè)計(jì)是一個(gè)很頭疼的問(wèn)題。

• radix樹(shù)就是針對(duì)這種稀疏的長(zhǎng)整型數(shù)據(jù)查找，能快速且節(jié)省空間地完成映射。借助于Radix樹(shù)，我們可以實(shí)現(xiàn)對(duì)于長(zhǎng)整型數(shù)據(jù)類(lèi)型的路由。

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

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

2. 插入、刪除操作

• radix Tree(基數(shù)樹(shù)) 其實(shí)就差不多是傳統(tǒng)的二叉樹(shù)，只是在尋找方式上，利用比如一個(gè)unsigned int的類(lèi)型的每一個(gè)比特位作為樹(shù)節(jié)點(diǎn)的判斷。

• 比如一個(gè)數(shù)1000101010101010010101010010101010，那么按照Radix 樹(shù)的插入就是在根節(jié)點(diǎn)，如果遇到0，就指向左節(jié)點(diǎn)，如果遇到1就指向右節(jié)點(diǎn)，在插入過(guò)程中構(gòu)造樹(shù)節(jié)點(diǎn)，在刪除過(guò)程中刪除樹(shù)節(jié)點(diǎn)。如果覺(jué)得太多的調(diào)用Malloc的話(huà)，可以采用池化技術(shù)，預(yù)先分配多個(gè)節(jié)點(diǎn)。

• 使用一個(gè)比特位判斷，會(huì)使樹(shù)的高度過(guò)高，非葉節(jié)點(diǎn)過(guò)多。故在實(shí)際應(yīng)用中，我們一般是使用多個(gè)比特位作為樹(shù)節(jié)點(diǎn)的判斷，但多比特位會(huì)使節(jié)點(diǎn)的子節(jié)點(diǎn)槽變多，增大節(jié)點(diǎn)的體積，一般選用2個(gè)或4個(gè)比特位作為樹(shù)節(jié)點(diǎn)即可。

• 如圖： 
  

  

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

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

3. RadixTree應(yīng)用

1. Radix樹(shù)在Linux中的應(yīng)用

   Linux基數(shù)樹(shù)（radix tree）是將long整數(shù)鍵值與指針相關(guān)聯(lián)的機(jī)制，它存儲(chǔ)有效率，并且可快速查詢(xún)，用于整數(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樹(shù)狀結(jié)構(gòu)作為由id進(jìn)行索引獲取指針的稀疏數(shù)組，通過(guò)使用位圖可以快速分配新的ID，IDR機(jī)制避免了使用固定尺寸的數(shù)組存放指針。IDR機(jī)制的API函數(shù)在lib/idr.c中實(shí)現(xiàn)。

   Linux radix樹(shù)最廣泛的用途是用于內(nèi)存管理，結(jié)構(gòu)address_space通過(guò)radix樹(shù)跟蹤綁定到地址映射上的核心頁(yè)，該radix樹(shù)允許內(nèi)存管理代碼快速查找標(biāo)識(shí)為dirty或writeback的頁(yè)。其使用的是數(shù)據(jù)類(lèi)型unsigned long的固定長(zhǎng)度輸入的版本。每級(jí)代表了輸入空間固定位數(shù)。Linux radix樹(shù)的API函數(shù)在lib/radix-tree.c中實(shí)現(xiàn)。（把頁(yè)指針和描述頁(yè)狀態(tài)的結(jié)構(gòu)映射起來(lái)，使能快速查詢(xún)一個(gè)頁(yè)的信息。）

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

   【radix樹(shù)為稀疏樹(shù)提供了有效的存儲(chǔ)，代替固定尺寸數(shù)組提供了鍵值到指針的快速查找?！?/p>

2. RadixTree數(shù)據(jù)庫(kù)和Spark RDD中應(yīng)用 
   2013年在ICDE上有一篇《The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases》論文，專(zhuān)門(mén)論述ART是如何用在內(nèi)存數(shù)據(jù)庫(kù)方面的。

   2014年Spark項(xiàng)目組啟動(dòng)indexedRDD設(shè)計(jì)理念，其中用到的主要存儲(chǔ)結(jié)構(gòu)就是ART。

4. 總結(jié)

• Radix樹(shù)與Trie樹(shù)的思想有點(diǎn)類(lèi)似，甚至可以把Trie樹(shù)看為一個(gè)基為26的Radix樹(shù)。（也可以把Radix樹(shù)看做是Tire樹(shù)的變異）

• Trie樹(shù)一般用于字符串到對(duì)象的映射，Radix樹(shù)一般用于長(zhǎng)整數(shù)到對(duì)象的映射。

• trie樹(shù)主要問(wèn)題是樹(shù)的層高，如果要索引的字的拼音很長(zhǎng)很變態(tài)，我們也要建一個(gè)很高很變態(tài)的樹(shù)么？

• radix樹(shù)能固定層高（對(duì)于較長(zhǎng)的字符串，可以用數(shù)學(xué)公式計(jì)算出其特征值，再用radix樹(shù)存儲(chǔ)這些特征值）

  相關(guān)代碼可以參考這里