2.4 生成位图编码映射表

　　当遇到哈希碰撞的时候，由于为了解决碰撞冲突，使用了哈希算法2中的一个或者多个哈希函数，当我们在进行查询操作的时候，不知道使用了哪一个哈希函数来计算产生碰撞的产品，因此我们需要将哈希算法2中计算出来的哈希值和对应的产品名称在位图编码映射表中记录下来，供查询时使用。

　　运用该方式，对关系表中所有的记录进行哈希计算，最后，基于哈希算法的编码位图索引和编码映射表就建立完成，如图1所示。

　　图1 基于哈希的增强编码位图索引

　　从示意图1，可以看出，当使用哈希算法1对产品g进行计算的时候，发生了碰撞，因此使用哈希算法2中的一个哈希函数进行计算，产生一个21位二进制的哈希函数，并将之记录在编码映射表中。按照这种方式，处理所有的产品名称，由于产生20位二进制哈希函数发生碰撞的几率大约为几十万分之一，所以，最后形成的编码映射表非常小，对于百万级来说，编码映射表中只有十几条记录。

　　2.5 查询操作

　　当我们在对产品关键字进行查询的时候，仍然要用到哈希算法1的函数，但是不用再使用哈希算法2中的哈希函数了，哈希算法2中的一系列哈希函数，仅仅在构造索引的时候需要用到，比如我们要查询产品x的记录，首先在编码映射表中进行定位，确认产品x是否在编码映射表中，如果产品x不在编码映射表中，表明x在计算哈希值的时候，没有与之前的产品的哈希值重复，故只需要对x使用哈希算法1来计算其哈希值，然后通过这个哈希值在编码索引表中进行定位，从而快速搜寻满足条件的记录。

　　但是如果x能够在编码映射表中找到，说明在使用哈希算法1计算x的哈希值的时候，与之前的某个产品计算出来的哈希值重复了，这个时候，只需要从编码映射表中取出x对应的哈希值，然后利用这个哈希值去索引表中查询满足条件的记录，由于索引编码表非常小，查询产品x是否在索引编码中以及从索引编码表中取出对应的哈希值，都是非常迅速的。

　　3 存储空间和查询性能分析

　　本方法的实现可以在Windows和Linux/Unix平台上运行，运行测试的机器为Windows PC机，硬件配置为4核处理器，16G内存，数据方体的测试产品名称数量为100万，基于该产品的记录数为1000万，针对这一产品维建立基于哈希算法的增强位图索引，在存储空间和查询性能上与编码位图索引进行了比较，在存储空间上尽管增加了一位来处理哈希重复问题，但编码映射表却大大节省了空间，总的说来节省了约50M，几乎节省了整个编码映射表。由于在一个只有十几条记录上查询哈希值，因此在查询性能上也有大幅提高，做到了既节省空间，有提高了查询效率。但是要做到既节省空间又要提高索引查询效率，很关键的一点是要提前设计好产生不同位数的哈希函数，并且要降低这些哈希函数的碰撞概率。

　　4 结束语

　　因此，基于该哈希算法的增强的位图编码索引方法，在数据方体中的使用，不但可以大大减少索引的存储空间，而且也能大大地优化，提高了查询性能。该方法也为研究数据方体索引技术的相关人员提供了一个新的思路和一定的参考价值。

　　参考文献：

　　[1]王珊，李翠平，李盛恩.数据仓库与数据分析教程[M].北京：高等教育出版社，2012.

　　[2]郭伟斌，陈东文.数据库索引技术的研究与应用[J].电脑开发与应用，2007（09）.

　　[3]李晓东，陈忱.基于多维链表的数据库索引技术研究与实现[J].计算机工程与应用，2004（22）.

　　

---

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

---

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。