朱迪矩阵

朱迪矩阵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

外部链接