简介
朱迪树是什么?
朱迪树,或朱迪数组(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
相关推荐
Judy array 372 Directed acyclic word graph 374 Multiway trees 376 Ternary search tree 376 And–or tree 379 (a,b)-tree 380 Link/cut tree 381 SPQR tree 381 Spaghetti stack 384 Disjoint-set data ...
Judy数组由指向节点树的指针组成。 空树由NULL指针指示。 Judy对象由judy_open返回,并且最初包含一棵空树。 使用judy_cell将整数或字符串键添加到树中,该键针对添加的每个键值返回指向映射的uint(在64位版本中为...
标题中的"Python库 | judy-1.0.13-pp37-pypy37_pp73-manylinux1_x86_64.whl"指的是一个特定版本的Python库,名为Judy,其版本号为1.0.13。这个库是专为Python 3.7(pp37)设计的,且与PyPy 3.7(pypy37_pp73)兼容,...
这使用了Judy Array 实现。 可以通过 Doug Baskins 在 sourceforge 或上的找到更多信息。模板judyLArray - int-int Judy Array 的 C++ 模板包装器。 JudyKey 和 JudyValue 必须是整数类型且大小与指针相同(即 32 ...
judy安装包,rpm,1.0.5版本。可用。for redhat centos 6
资源分类:Python库 所属语言:Python 资源全名:judy-1.0.8-cp38-cp38-manylinux2010_x86_64.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Judy是一款高效的、开源的通用动态数组,它以C语言编写的库形式提供。作为一款数据结构,Judy的设计目标是提供快速的插入、删除和查找操作,同时在内存使用上优化,尤其适合处理大规模的数据集。在本文中,我们将...
标题"netdata依赖库libjudy-Judy-1.0.5源码"指出,我们正在讨论的是netdata监控工具的一个关键依赖库——libjudy,其版本为1.0.5,而且是源码形式。这暗示我们将深入探讨libjudy库的源代码,以及它在netdata中的作用...
Judy 数组是一种复杂但非常快速的关联数组数据结构,用于使用整数或字符串键存储和查找值。 与普通数组不同,Judy 数组可能是稀疏的; 也就是说,它们可能有大范围的未分配索引。 -> PHP 扩展基于实现动态数组的...
官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装
官方离线安装包,亲测可用
离线安装包,亲测可用
Judy,是一个使用用开发的简单机器人,通过它您可以使您的服务器对所有人而言都更舒适,更安全。 如果您有兴趣,请邀请Judy加入您的服务器 指令 :pager: Judy有几个命令可以使服务器成为圆角。 某些命令可能没有...
`Judy`这个名字可能来源于一种高效的数据结构,例如Judy arrays,这是一种稀疏数组实现,以极高的空间效率和快速的查找速度著称。 **Python版本与兼容性** `cp36-cp36m`这部分表示这个库是为Python 3.6编译的,...
judy 是一个基于javascript的图表组件,支持多种图表类型。 标签:judy
6.170 项目团队 - 2014... details.js: Judy Chang login.js: Judy Chang map.js: Judy Chang 路线/ API: events.js:达娜·穆库舍娃location.js: Judy Chang subscriptions.js:达娜·穆库舍娃users.js:查丽贝卡路线
通过这个模块,用户可以创建和操作Judy Array,执行插入、删除、查找等操作,而无需关心底层的实现细节。这对于需要处理大规模数据的项目,如数据分析、日志处理或大规模数据存储,尤其有用。 在RJudy-1.0这个版本...
离线安装包,亲测可用
官方离线安装包,亲测可用。使用rpm -ivh [rpm完整包名] 进行安装