Monthly Archives: June 2009

本系列文章都是原创，转载务必注明出处。 Judy Population/Memory Node (JPM) 当 Judy 中元素个数达到一定数量时，JPM 将开始产生。它将被认为是 Judy 下面数组的头。也提供了对整个 Judy 进行方便搜索和统计的概要信息。在 JPM 下面是几种分支。

本系列文章都是原创，转载务必注明出处。 最后的几个问题： 1、各种分支的转换临界值； 2、cascade 的原则，为什么需要这么做，是否节省了内存？ 3、narrow pointer 是什么？ 应用实例： 考虑类似 Netflow 的统计和分析，一条记录有 7 个字段：srcIP、dstIP、protocol、srcPort、dstPort、octets、packets，可能有时候你需要按照一些字段来分组汇总，比如按照 srcIP 来分组，类似数据库当中的 group by 之后 sum。貌似首先想到的是用 hash 来完成，但是当分组的字段增加到多个时，hash 算法的效率下降剧烈。以 flow-tools 工具为例，如果要使用 flow-report 工具做报告，比如对 ip-source-address-destination-count 的统计（统计每个 srcIP 下的 dstIP），flow-report 在数据量增加时效率下降厉害，但使用 Judy 数组，不但可以统计出每个 srcIP 的汇总，还可以看到和每个 dstIP 的明细。

本系列文章都是原创，转载务必注明出处。 Judy 中的立即索引与叶节点 在立即索引中，索引直接存放在 JP 之中，而不像叶节点那样（在叶节点中，索引和值区域在 JP 之外，被一个 JP 指向）。由于 JP 中的字节数是有限的，因此能装入的索引数量也是有限的。 如果索引只有 1 个，那么 JP 中的指向下级 JP 的那个指针将会是索引的值，而不再是一个指针； 如果索引大小是 1 个字节，那么这个 JP 中最多可以存放 3 个（这种索引）； 如果索引大小是 2 个字节或 3 个字节，那么这个 JP 中最多可以存放 1 个（这种索引）； 总之不能超过 3 个字节。

本系列文章都是原创，转载务必注明出处。 Judy Pointer（JP） 前面谈到的分支结构中都提到了 JP。每个 JP 占用 8 个字节。因此数字树的分支总是 8 字节的对象数组。其中有 1 个字节是类型（type）字段。参考 JudyL.h 中的 jpL_Type_t 类型。 decode 字段和 population 字段是共享的，它们共享 3 个字节，它们之间不同的组合造就了繁多的 JP 类型。细节稍后介绍。其中有一种类型是立即索引（immediate index），对于这种 JP，索引值直接存在于 JP 中，而不像其他的 JP 分支那样，存放的都是 subexpanse。JP 的定义存放在 JudyPrivateBranch.h 中。 下面的程序可以顺着 Judy 数组的根打印出整棵树结构，注意观察 JP 的类型。