json格式转换工具 一种解决Impala自定义属性查询的方案(2)

通过测试结果可以发现，随着查询的关键字个数的增加两者都是X + N * Y（N是关键字的个数），其中MAP表的Y = 13s，新的JSON UDF的Y大于等于7s，这意味着随着查找关键字个数的增长，查询性能有了大约45%的提升，这也意味着我们减少查询平均时间复杂度的做法是可行的，但是这种方案的查询时间复杂度仍然是O(n)，有没有什么办法进一步提升查询性能呢？

将之前JSON格式的查询问题转换成字符串查找问题之后，思路就可以放宽了，我们都知道在查找算法中有两种实现的性能比较好，分别是哈希表和二分查找树，这也对应着Map的两种实现，我们是否可以将需要写入的key：value转换成这样的格式呢？但是看着这样复杂的结构序列化和反序列化都是一个比较头大的问题，除了这两个数据结构，我们还知道二分查找的性能最快情况下是O(log N)，那我们能不能使用二分查找呢？

先来分析一下二分查找的两个前提条件：

待查找的值必须是有序的。json格式转换工具

对于第一个条件我们比较熟悉，因为二分查找都是通过数组来实现存储的，数组的每一个元素都是可以随机访问的，这意味着我们可以通过arr [(high + low) / 2]访问下一个比较的元素。但是输入的key和value都是未知大小的，我们需要根据key进行比较，难不成要将所有的key都存储成一样的大小？这样意味着所有的key都需要存储成最大的key的长度，浪费了不少存储空间，最终我们选择这样一种二进制的存储格式：

通过这样的结构，我们将key:value转换成一个定长的索引信息，整个结构从前往后包括如下几部分：

Magic Number：魔数，用于标记该值是否是可识别的存储格式，4个字节

HEADER_LEN：标记该结构中存储的key:value值的个数，如果预定义该结构最大的值数量为65535，只需要2个字节。

值的索引数组：每一个值通过固定大小的索引来表示，它包含三部分：偏移量（表示当前key的偏移量，对一个key从0开始，第二个key的偏移量等于第一个key长度+value长度，依此类推，2个字节或者4个字节）；key的长度（如果key的大小限定在256字节，只需要1个字节）；value的长度（value的偏移量可以通过该值的偏移量+key的长度计算，1个字节或者2个字节）。

真正的key和value对，key和value连续存储。json格式转换工具

这样除了真正的key和value的值，额外需要4 + 4 + （4 + 2 + 2） * N的存储空间存储索引信息（为了保持8字节对齐可以扩大成8 * (N + 1)字节），其中N等于key/value对的个数。这种格式可以存储多大65536个key/value对，每一个key和value的最大长度为65536字节。

从上面的JSON和MAP对比测试可以发现数据量的增大并不是性能变慢的主要原因（优化之后的JSON UDF同样需要读取两倍的数据量，但是性能提升了许多），因此这种存储上的浪费是可以接受的。而采用了新的存储结构，可以使得查询的时间复杂度从O(N)提升到O(log N)，那么对于写入和查询的流程又需要做哪些额外的工作呢？

写入端（Java端）：

写入的时候需要首先将key进行排序（放入到一个TreeMap中）。

分别构造出每一段，最后通过UDF-8编码成byte数组写入（不像JSON有现成的库使用）。

读取端（C++ UDF）：

读取的时候首先读取前4个字节，判断魔数是否等于预定义的值，如果不等于直接返回错误。

读取第二个4字节，获取成员的个数，该值也就是后面数组的大小。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-63711-2.html