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

读取第三部分索引数组，根据二分查找的算法，定位到最中间的索引内容（偏移量、key的长度），然后和待查找的值进行比较，指导查找结束。

如果没有找到则返回NULL，找到该key根据偏移量、key长度和value的长度计算出value的偏移量和长度返回。

有了这样的一个存储结构，是否可以再进行进一步的优化呢？答案是肯定的，在二分查找的过程中，最坏情况下的时间复杂度是O(log N)，是当待查找的值不存在的情况，是否有更高效的方案判断一个key是否存在呢，如果不存在则可以直接返回NULL了，于是想到了Bloom Filter算法，它存在一定的误差，但是具有如下的特性：

它判断一个key不存在，那么这个key肯定不存在。

它判断一个key存在，那么这个key可能不存在。

这个特性正好能够符合我们的需求，因此可以考虑在MAGIC和HEADER_LEN部分中间插入计算好的bloom filter信息，但是这个是否值得还需要进一步测试对比，因为引入了Bloom Filter会增大了计算的开销（虽然Bloom Filter的计算只是几个哈希函数的计算），如果待查找的key在大部分情况下（例如90%）都是能够找到的，那么这个开销就有点得不偿失；如果待查找的key大多数情况下是不存在的，这种开销可以大大提升查询的性能。

但是上面的结构只表示除了单层的key/value结构，这和json表示的语义是有差别的，怎么协调这种差别呢？其实在JSON中无外乎两种嵌套结构，一种是MAP一种是ARRAY，假设MAP中的key不包含字符’.’，我们可以将子节点通过’.’和父节点进行连接，转换成扁平的格式，数组同样，可以通过父节点的名字和数组下表将其转换成扁平结构。如下：

{
    "name" : "yu",
    "location" : {
        "province" : "ZZ",
        "city" : "HZ"
    },
    "education" : ["ABC", "DEF", "GH"]
}

可以转换成name = yu，location.province = ZZ, location.city = HZ, educaion.0 = ABC, education.1 = DEF education.2 = GH 这样扁平的结构存储在上面提到的结构中，查询的时候也根据需要查询的节点路径输入就可以解决了。

本文我们对比了impala中原生MAP和使用JSON UDF的方法进行不确定属性字段的查询，然后提出了一种新的基于关键字查找的方案提升了JSON字段内容解析的性能，并比原生的MAP有了将近50%的性能提升，但是我们没有止步于此，而是探索出一种特定的可以实现二分查找的存储结构，使用这种结构可以使用二分查找来完成属性的查找，并提出进一步基于Bloom Filter的优化方案。最终结果有待于进一步的对比测试。

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