朱迪矩陣是一個計算機科學和軟體工程學中的名詞，是一種高性能、低記憶體消耗的數據結構，實現了關聯數組的功能。與普通數組不同，Judy array可以是稀疏的，這一點更像是散列表，而非數組。Judy array可以用整形或字元串作為鍵值來存儲、查詢數據，它最大的優勢是可動態自動擴展，高性能，節省記憶體並且易於使用。
由於Judy array在操作速度和記憶體使用上都非常高效，同時並不需要特殊配置或初始化，使得它可以用來替換掉多種常見數據結構，例如跳躍列表,鍊表,二叉樹,B樹,散列表，而且judy array在海量數據集上的表現比那些數據結構更好。
粗略地講，Judy array像是一個高度最佳化了的256叉樹，為了節省記憶體，它使用了超過20種不同的壓縮技術來壓縮樹節點。
Judy array 是Douglas Baskins發明的，他用自己妹妹的名字命名了這種數據結構。
基本介紹
- 中文名：朱迪矩陣
- 外文名：Judy array
- 學科：程式語言技術
術語,記憶體分配,速度,算法,
術語
容量、用量、密度 這三個概念是傳統樹形結構中很少使用，但在Judy array中反覆使用的。 這個的概念的定義如下：
- 容量可以理解為Judy Array在不擴展記憶體使用的情況下所能維護的數據量，也可以是某個節點的，視乎上下文。
- 用量已經存儲的數據量，既可以描述整個Judy Array的數據量，也可以是某個節點下的。
- 密度用來描述數據存儲的密集程度， 密度 = 用量/容量。
記憶體分配
Judy array是沒有容量限制的，所以也不用事先分配好存儲空間，它可以根據用量動態決定生長或收縮記憶體使用，來支撐海量數據存儲。其存儲能力僅受到計算機記憶體容量的限制。Judy array的記憶體用量與其存儲的數據用量基本呈線性關係。
速度
Judy array在設計上就力爭保持儘可能高的CPU快取命中率，為了達到這個目標，其內部算法十分複雜。由於有了這些針對性的最佳化，使得Judy array在運行速度上十分高效，有時甚至超過散列表，尤其是在處理大數據集的時候。由於Judy array是依託樹 (數據結構)形結構設計的，其記憶體消耗比散列表小很多，同樣是拜樹形結構所賜，使得它可以完成鍵值的順序遍歷，這一點在散列表中是不可能的。
算法
從Judy array的發明者所撰寫的簡介以及其他一些相關的中文論文中看，設計中使用了多種的壓縮思想與壓縮算法，根據不同的密度情況，選擇不同的壓縮方式，以期儘可能節省記憶體，降低實際存儲中的稀疏情況，我猜測，這能夠在快取命中率上帶來不少提升，進而提升效率。
看到的算法思路包括：
- 對於密度很高，空洞很少的節點，使用點陣圖（bitmap）來存儲。
- 對於密度很低的情況，只存儲出現的鍵值
- 對於密度極低的情況，使用類似於字典樹的結構，跨層壓縮數據。
