朱迪矩陣

朱迪矩陣Judy array)是一個電腦科學和軟件工程學中的名詞,是一種高效能、低主記憶體消耗的數據結構,實現了關聯陣列的功能。與普通陣列不同,Judy array可以是稀疏的,這一點更像是雜湊表,而非陣列。Judy array可以用整形或字串作為鍵值來儲存、查詢數據,它最大的優勢是可動態自動擴充,高效能,節省主記憶體並且易於使用。

由於Judy array在操作速度和主記憶體使用上都非常高效,同時並不需要特殊組態或初始化,使得它可以用來替換掉多種常見數據結構,例如跳躍列表,鏈結串列,二叉樹,B樹,雜湊表,而且judy array在海量數據集上的表現比那些數據結構更好。

粗略地講,Judy array像是一個高度最佳化了的256叉樹,為了節省主記憶體,它使用了超過20種不同的壓縮技術來壓縮樹節點。.[1]

Judy array 是Douglas Baskins發明的,他用自己妹妹的名字命名了這種數據結構。[2]

術語

容量、用量、密度 這三個概念是傳統樹形結構中很少使用,但在Judy array中反覆使用的。 這個的概念的定義如下:

  1. 容量 可以理解為Judy Array在不擴充主記憶體使用的情況下所能維護的數據量,也可以是某個節點的,視乎上下文。
  2. 用量 已經儲存的數據量,既可以描述整個Judy Array的數據量,也可以是某個節點下的。
  3. 密度 用來描述數據儲存的密集程度, 密度 = 用量/容量

優勢

主記憶體分配

Judy array是沒有容量限制的,所以也不用事先分配好儲存空間,它可以根據用量動態決定生長或收縮主記憶體使用,來支撐海量數據儲存。其儲存能力僅受到電腦主記憶體容量的限制。[3] Judy array的主記憶體用量與其儲存的數據用量基本呈線性關係。

速度

Judy array在設計上就力爭保持儘可能高的CPU快取命中率,為了達到這個目標,其內部演算法十分複雜。由於有了這些針對性的最佳化,使得Judy array在執行速度上十分高效,有時甚至超過雜湊表,尤其是在處理大數據集的時候。由於Judy array是依託樹 (數據結構)形結構設計的,其主記憶體消耗比雜湊表小很多,同樣是拜樹形結構所賜,使得它可以完成鍵值的順序遍歷,這一點在雜湊表中是不可能的。

演算法

從Judy array的發明者所撰寫的簡介以及其他一些相關的中文論文中看,設計中使用了多種的壓縮思想與壓縮演算法,根據不同的密度情況,選擇不同的壓縮方式,以期儘可能節省主記憶體,降低實際儲存中的稀疏情況,我猜測,這能夠在快取命中率上帶來不少提升,進而提升效率。

看到的演算法思路包括:

  • 對於密度很高,空洞很少的節點,使用點陣圖(bitmap)來儲存。
  • 對於密度很低的情況,只儲存出現的鍵值
  • 對於密度極低的情況,使用類似於字典樹的結構,跨層壓縮數據。

參考文獻

  1. ^ Alan Silverstein, "Judy IV Shop Manual頁面存檔備份,存於互聯網檔案館)", 2002
  2. ^ 存档副本. [2013-01-07]. (原始內容存檔於2013-01-06). 
  3. ^ Advances in databases: concepts, systems and applications : By Kotagiri Ramamohanarao

外部連結