朱迪树(judy trie/array/tree)

简介

朱迪树是什么?

朱迪树，或朱迪数组(judy trie/array/tree)是一种对内存使用率和CPU高速缓存命中率进行优化的trie树。与哈希表，二叉树(包括红黑树等)，B-树等相比占用更少的内存，同时又具有很高的运行效率，在某些情况下甚至胜过哈希表。

 

朱迪是谁?

朱迪是朱迪树的发明者的妹妹或者姐姐，可能是因为作者没有找到好听的名字就直接拿sister的名字来命名了。

 

朱迪树的设计考虑了传统数据结构没有考虑的一些概念:

1.       区间(Expanse)：所有可能的关键字构成的区间

2.       数量(Population)：关键字区间中包含的关键字的个数

3.      密度(Density)：用于描述关键字的稀疏性，Density = Population/Expense，

 

并根据这些概念对数据结构进行调整以便提高内存利用率。

 

朱迪树的分类

 朱迪树有以下几种：

1.      Judy1 机器字长到某一位的映射，应该只可以作为ordered_set来使用

2.       JudyL 机器字长到机器字长的映射，可以作为整数到void*的ordered_map来使用

3.       JudySL 将字符串映射到机器字长

4.       JudyHS 将字节数组映射到机器字 

 

 

主要思想

 

朱迪树在逻辑上可以看作是度为256的trie。

 

朱迪树根据节点孩子的密度和数量使用不同的数据结构表示trie的节点，当孩子数量较少时，使用有序列表，当孩子数量较多但比较稀疏时，使用bitmap，当数量很多时使用全索引，从而减低内存使用。

 

朱迪树对叶子节点也采取了优化，叶子节点与trie中的节点不同，朱迪树中的每个叶子节点保存多个索引关系。并将多层孩子节点合并到同一个朱迪叶子节点。

 

通常树形结构使用指针来访问数据，每次查询都会在不同的内存地址之间跳跃，这使得树的实现对高速缓存很不友好，朱迪树的实现也无法避免此问题，朱迪树把指针和节点信息（类型，孩子数量等）绑定到一起作为一个朱迪指针，以此利用缓存带宽，并节约内存使用。

 

朱迪指针(JP)

朱迪树中大部分节点间的链接关系都通过朱迪指针来完成，朱迪指针可以看做是带有附加信息的原生指针。朱迪指针占用两个机器字长（2x4字节或2x8字节）。其中一个机器字长（4或8字节）用来保存原生指针（指向孩子节点，或叶子节点中的value），另一个机器字长保存指针类型（1字节），孩子节点数量，编码方式等信息。其中子节点数量和解码信息是变长的，具体长度由节点类型决定。朱迪指针中的类型非常的多（当然小于等于256），这也是实现复杂的原因之一。

 

将类型信息保存与指针地址保存在一起，应该是为了提高缓存命中，直接可以读取类型相关信息，而不需要更新高速缓存。

 

 

朱迪指针总体上分为以下几类：

1.       空指针

2.     分支节点（线性，位图，无压缩）

3.     叶子节点（线性，位图）

4.       直接索引节点（也可以看做一种叶子节点，只保存很少的索引）

分支节点(B)

朱迪分支节点与trie中的分支节点在逻辑上是一致的，只不过考虑了内存使用和缓存利用。朱迪树根据分支节点孩子的数量和密度选用不同的数据结构表示分支节点。

 线性分支节点(BL)

当非空孩子较少时使用，用有序表来保存孩子节点。

位图分支节点(BB)

位图（分支/叶子）节点，当非空孩子较多并且稀疏时使用，使用256bit的位图来表示非空孩子，并将非空孩子作为数组保存。为了更好的利用高速缓存，位图节点将256bit分为八组，每组包含一个64bit位图掩码和指向掩码中非空孩子的数组指针。

无压缩分支节点(BU)

无压缩分支节点，与传统的trie分支节点一致，直接使用大小为256的数组来保存下一级的孩子节点，当非空孩子很多并且稠密时使用。

 

这三种分支随着孩子节点的密度，数量，区间进行转化，从而起到减少内存使用的目的。

叶子节点(L)

在传统的trie中，叶子节点是关键字的最后一级索引，而 朱迪树中叶子节点的处理与传统的trie有一些不同：朱迪树将trie中某分支节点的所有叶子节点（这些叶子节点可能具有不同的深度）合并到一起作为一个叶子节点，以此来减少索引的层级和内存占用。

直接索引节点

当叶子中的索引很少时，进行的优化。直接索引节点利用朱迪指针中的对应位来存储value信息。

线性叶子节点

 线性叶子节点不保存孩子的个数，孩子的个数由指向线性叶子节点的朱迪指针对应字段保存，线性叶子节点与线性分支节点类似，保存一个索引数组和一个指针数组。由于孩子的深度可变，索引的长度也是可变的，因此线性叶子节点根据孩子深度可以划分为不同的子类型。

 

位图叶子节点

位图叶子节点只会出现在传统的trie的最深一层，用来处理最后一级索引，位图叶子节点与位图分支节点基本类似。

节点之间的转化

朱迪树会根据节点的密度，数量对节点的数据结构进行调整，无非就是叶子节点变成分支节点，分支节点改变数据结构，叶子节点改变数据结构，这里就不细说了。

 根一级叶子节点

当树中的节点数量很少时做的优化，与线性叶子节点类似。

 

 

 更多细节请参考http://judy.sourceforge.net/application/shop_interm.pdf