摘 要：随着信息技术的蓬勃发展，信息技术应用领域的数据量也越来越大，数据仓库的运用也越来越广泛和普遍，特别是在大数据时代，随着数据量的增加，数据仓库管理的数据也越来越多，数据方体的数据量也越来越大，因此也给数据方体的存储和查询带来了巨大的挑战，怎样能够支持对大型数据方体的快速查询，又能减少存储空间，在联机分析处理系统将是非常关键的一环，通过基于哈希算法的增强编码位图索引技术能够有效地减少存储空间并且提高查询效率。

　　关键词：数据方体；哈希；增强编码位图索引

　　中图分类号：TP391.3；TP181

　　随着信息技术的高速发展，数据量也越来越大，数据仓库管理的数据方体的数据量也与日俱增，这给数据方体的存储和管理以及查询，利用都带来了巨大的挑战和困难，不但存储是个问题，而且想要快速地从数据仓库中准确地获取数据也是一大难点。数据方体一般采用多维数组或者关系表的形式来存储，由于关系表历史悠久，使用广泛，各大数据库厂商都支持，并且具有很成熟的模型，经受住了时间的考验，还有一些多维数组不具有的优点比如对海量数据的适应能力以及对软硬件的适应能力等，所以很多时候数据方体都以关系表方式存储数据。由于数据方体的数据量一般都非常大，特别是在大数据时代，数据方体存储的数据就更大了，因此，当数据方体以关系表方式存储数据的时候，为了提高查询处理性能，快速响应查询需求，除了对数据方体进行一些预处理之外，还必须对数据方体建立索引以满足日益增加的数据量和查询需求，目前，数据方体都采用树索引和位图索引。

　　1 现有编码位图索引的不足与缺陷

　　位图索引有简单的位图索引（也称之为标准的位图索引）和编码的位图索引，简单位图索引，实现简单，而且一目了然，对于基数较小的列，效果很好，可以节省空间，简单位图索引的大小与列的不同值的个数成正比，也可以大大降低被扫描数据的数量，索引只需扫描一次，位图就可以对所有的行通过位操作进行定位，从而大大提高查询速度。但是对于高基数的列，简单的位图索引不再有效，为此，有人提出了编码位图索引，假设某个事实表的产品维具有1000000种不同的商品，如果要在产品维上创建简单的位图索引的话，将会产生1000000个位向量，但是如果采用编码位图索引的话，只需要[log21000000]=20个位向量，再加上一个映射表。这样编码位图索引相对简单位图索引来说，就大大减少了存储空间。

　　由于引入了编码映射表，从而也就减少了位向量的数量，但是，在很多情况下，并不总是有效，比如产品名属性，通常名称很长，产品的种类也很多，比如淘宝的产品种名称通常有几十个汉字，品种也上百万种，以品种数量100万为例，编码映射表将需要几十M或者上百M的存储空间，有时甚至比整个位向量的存储空间还要大，这样，不但占据大量的存储空间，而且查询效率也很低下，因为如果编码映射表很大的话，有时候还不得不为编码映射表建立索引来提高查询效率，这是二级索引，为编码映射表建立索引，又额外地增加了存储空间。

　　2 基于哈希算法的增强编码位图索引实现

　　本文将使用一种新的基于哈希算法方法来优化编码位图索引，从而减少存储空间，并且提高查询效率。

　　哈希算法是将任意长度的数据值映射为较短的长度，通常为固定位数的二进制值，这个较短的固定位数的二进制值称为哈希值，本方法的基本思路是通过增加1个位向量，使用有限数量的编码映射表来提高查询速度和减少编码映射表的存储空间。

　　2.1 设计哈希函数

　　由于产品品种是100万（以前文提到的淘宝产品数量和名称为例），所以，我们至少需要[log21000000]=20个位向量来存储产品名称列的索引，前文提到，我们会增加一个二进制位来存储索引，我们最多会有可能使用21位二进制来存储该产品名称列的索引。因此，我们需要设计一个能够产生20位二进制的哈希函数，我们称之为哈希函数1，同时设计多个能够产生21位二进制的哈希函数，我们称之为哈希函数2。为什么还要设计多个能够产生21位二进制的哈希函数，后面会有更进一步的介绍。

　　2.2 计算产品哈希值

　　扫描整个关系表，对每条记录中的产品名称用哈希函数1计算哈希值，将生成的哈希值存到相应位向量里，由于我们使用了21位位向量，所以这个时候最高位为0，其余20位就是用哈希算法1计算出来的哈希值。

　　2.3 处理哈希碰撞问题

　　由于哈希函数总是会有一定的概率出现碰撞问题，也就是说会有一定的概率即使不同的输入值也会产生相同的二进制结果。事实证明，即使设计很好的哈希算法，也总是会有一定的概率出现碰撞问题，只是出现碰撞的概率不同罢了，哈希算法2就是用来解决碰撞问题的，下面进行更为详细的描述。

　　假设对产品y用哈希算法1来计算哈希值，碰巧的是，对y进行计算出来的哈希值与之前某个产品x计算的哈希值发生了碰撞，即二者的哈希值一样，由于x在前面已经计算过，不需要再进行修改，所以我们这个时候从哈希算法2中取出一个算法来对y产品来重新进行哈希计算，由于哈希算法2计算出来的结果是21位二进制值，而计算x使用的是哈希算法1，生成的哈希值是20位的，因此哈希算法2计算出来的哈希值一定不会与x的哈希值相同，这就解决了碰撞问题。

　　由于每一个哈希算法都有可能产生碰撞问题，同样，用同一个哈希算法2计算出来的哈希值也有可能会产生碰撞问题，当遇到产品z计算出来的哈希值与y产生碰撞的时候，需要使用哈希算法2中的另一个哈希算法来产生哈希值以避免碰撞。由于一个设计良好的哈希算法尽管有一定的概率会产生碰撞问题，但往往概率很小，对于一个产生20位，21位二进制这样的哈希算法，其重复率一般为几十万分之一，故哈希算法2并不需要太多函数，对于100万产品级别来说，只需要两到三个哈希算法2对应的哈希函数。

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

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