[科普中國(guó)]-朱迪矩陣

朱迪矩陣是一個(gè)計(jì)算機(jī)科學(xué)和軟件工程學(xué)中的名詞，是一種高性能、低內(nèi)存消耗的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了關(guān)聯(lián)數(shù)組的功能。與普通數(shù)組不同，Judy array可以是稀疏的，這一點(diǎn)更像是散列表，而非數(shù)組。Judy array可以用整形或字符串作為鍵值來存儲(chǔ)、查詢數(shù)據(jù)，它最大的優(yōu)勢(shì)是可動(dòng)態(tài)自動(dòng)擴(kuò)展，高性能，節(jié)省內(nèi)存并且易于使用。

由于Judy array在操作速度和內(nèi)存使用上都非常高效，同時(shí)并不需要特殊配置或初始化，使得它可以用來替換掉多種常見數(shù)據(jù)結(jié)構(gòu)，例如跳躍列表,鏈表,二叉樹,B樹,散列表，而且judy array在海量數(shù)據(jù)集上的表現(xiàn)比那些數(shù)據(jù)結(jié)構(gòu)更好。

粗略地講，Judy array像是一個(gè)高度優(yōu)化了的256叉樹，為了節(jié)省內(nèi)存，它使用了超過20種不同的壓縮技術(shù)來壓縮樹節(jié)點(diǎn)。

Judy array 是Douglas Baskins發(fā)明的，他用自己妹妹的名字命名了這種數(shù)據(jù)結(jié)構(gòu)。

術(shù)語容量、用量、密度 這三個(gè)概念是傳統(tǒng)樹形結(jié)構(gòu)中很少使用，但在Judy array中反復(fù)使用的1。 這個(gè)的概念的定義如下：

容量可以理解為Judy Array在不擴(kuò)展內(nèi)存使用的情況下所能維護(hù)的數(shù)據(jù)量，也可以是某個(gè)節(jié)點(diǎn)的，視乎上下文。

用量已經(jīng)存儲(chǔ)的數(shù)據(jù)量，既可以描述整個(gè)Judy Array的數(shù)據(jù)量，也可以是某個(gè)節(jié)點(diǎn)下的。

密度用來描述數(shù)據(jù)存儲(chǔ)的密集程度， 密度 = 用量/容量。

內(nèi)存分配Judy array是沒有容量限制的，所以也不用事先分配好存儲(chǔ)空間，它可以根據(jù)用量動(dòng)態(tài)決定生長(zhǎng)或收縮內(nèi)存使用，來支撐海量數(shù)據(jù)存儲(chǔ)。其存儲(chǔ)能力僅受到計(jì)算機(jī)內(nèi)存容量的限制。Judy array的內(nèi)存用量與其存儲(chǔ)的數(shù)據(jù)用量基本呈線性關(guān)系。

速度Judy array在設(shè)計(jì)上就力爭(zhēng)保持盡可能高的CPU緩存命中率，為了達(dá)到這個(gè)目標(biāo)，其內(nèi)部算法十分復(fù)雜。由于有了這些針對(duì)性的優(yōu)化，使得Judy array在運(yùn)行速度上十分高效，有時(shí)甚至超過散列表，尤其是在處理大數(shù)據(jù)集的時(shí)候。由于Judy array是依托樹 (數(shù)據(jù)結(jié)構(gòu))形結(jié)構(gòu)設(shè)計(jì)的，其內(nèi)存消耗比散列表小很多，同樣是拜樹形結(jié)構(gòu)所賜，使得它可以完成鍵值的順序遍歷，這一點(diǎn)在散列表中是不可能的。

算法從Judy array的發(fā)明者所撰寫的簡(jiǎn)介以及其他一些相關(guān)的中文論文中看，設(shè)計(jì)中使用了多種的壓縮思想與壓縮算法，根據(jù)不同的密度情況，選擇不同的壓縮方式，以期盡可能節(jié)省內(nèi)存，降低實(shí)際存儲(chǔ)中的稀疏情況，我猜測(cè)，這能夠在緩存命中率上帶來不少提升，進(jìn)而提升效率。

看到的算法思路包括：

對(duì)于密度很高，空洞很少的節(jié)點(diǎn)，使用位圖（bitmap）來存儲(chǔ)。

對(duì)于密度很低的情況，只存儲(chǔ)出現(xiàn)的鍵值

對(duì)于密度極低的情況，使用類似于字典樹的結(jié)構(gòu)，跨層壓縮數(shù)據(jù)。

本詞條內(nèi)容貢獻(xiàn)者為:

王慧維 - 副研究員 - 西南大學(xué)