位图索引压缩方法和位图索引解压方法

摘要

本发明实施例提供一种位图索引压缩方法及装置，通过按预设段宽度分段，得到索引关键字对应的位图索引的各段位图信息，并将各段位图信息中各有效值的偏移值按对应的二进制存储位数进行存储，得到该段位图信息的压缩信息，由于只存储各段位图信息中各有效值的偏移值，因此能够减小位图索引的存储空间。相应地，本发明实施例提供一种位图索引解压方法及装置，利用各有效值的偏移值的二进制表示信息的存储位数，得到各段位图信息的压缩信息中各有效值的偏移值，并通过将所述初始化位图信息中各有效值的偏移值对应的位设置为有效值，得到该段位图信息的压缩信息对应的解压信息，能够降低位图索引的解压复杂度，并提高了位图索引的检索查询效率。

说明书

技术领域

本发明实施例涉及数据库技术领域，尤其涉及一种位图索引压缩方法和位 图索引解压方法。

背景技术

随着计算机信息技术的快速发展，越来越多的用户对海量数据的存储和检 索提出了更高的要求。位图索引对应于数据基表中的索引关键字，位图索引在 海量数据上的应用是普遍的，例如在数据基表上通过位图索引检索某个产品在 某个时间段的销售情况等等。在提升位图索引检索性能的同时，对位图索引存 储空间的要求也越来越高，因此位图索引压缩技术应运而生。

现有的位图索引压缩技术，一般是通过计算数据基表的索引关键字对应的 位图索引中每个1之前的0的个数，并确定该个数的二进制表示位数，同时通 过添加控制信息对该个数的二进制表示位数以及该个数的二进制数进行编码， 从而实现数据基表的索引关键字对应的位图索引的压缩存储。

上述位图索引压缩技术的缺陷在于：虽然通过将每个1前面的0的个数用 相应位数的二进制记录，可以减少每个1前面的0的个数的存储空间，但在编 码中添加的控制信息会导致位图索引的存储空间的增大；而且复杂的编码方式 增加了位图索引的解压复杂度，从而影响位图索引的检索查询效率。

发明内容

本发明实施例提供一种位图索引压缩方法及装置，以减小位图索引的存储 空间；本发明实施例还提供一种位图索引解压方法及装置，以降低位图索引的 解压复杂度，以提高位图索引的检索查询效率。

第一方面，本发明实施例提供了一种位图索引压缩方法，包括：

对于预先建立的数据基表中所包含的索引关键字的位图索引，将该位图索 引按预设段宽度分段，得到多段位图信息；

对于各段位图信息，确定该段位图信息中各有效值的偏移值，其中，所述 偏移值为对应的有效值在该段位图信息中的位数；根据各有效值的偏移值确定 各偏移值的二进制存储位数；根据所述二进制存储位数得到该段位图信息中各 偏移值的二进制表示信息，生成并存储该段位图信息的压缩信息，该压缩信息 包含各偏移值的二进制表示信息。

第二方面，本发明实施例提供了一种位图索引压缩装置，包括：

分段模块，用于对于预先建立的数据基表中所包含的索引关键字的位图索 引，将该位图索引按预设段宽度分段，得到多段位图信息；

偏移值确定模块，用于对于各段位图信息，确定该段位图信息中各有效值 的偏移值，其中，所述偏移值为对应的有效值在该段位图信息中的位数；

二进制存储位数确定模块，用于根据各有效值的偏移值确定各偏移值的二 进制存储位数；

第一存储模块，用于根据所述二进制存储位数得到该段位图信息中各偏移 值的二进制表示信息，生成并存储该段位图信息的压缩信息，该压缩信息包含 各偏移值的二进制表示信息。

第三方面，本发明实施例提供了一种位图索引解压方法，包括：

获取数据基表中所包含的索引关键字的位图索引的各段位图信息的压缩信 息，其中，所述各段位图信息通过将该位图索引按预设段宽度分段获得，对于 各段位图信息的压缩信息，该段位图信息的压缩信息包含二进制表示信息和二 进制存储位数，所述二进制表示信息包含该段位图信息中各有效值的偏移值的 二进制表示信息；所述二进制存储位数包含该段位图信息中各有效值的偏移值 的二进制表示信息的存储位数，所述偏移值为对应的有效值在该段位图信息中 的位数；

对于各段位图信息的压缩信息，生成宽度为预设段宽度的初始化位图信息； 根据该段位图信息的压缩信息中的二进制存储位数，将该段位图信息的压缩信 息中的二进制表示信息转换为十进制信息，得到该段位图信息的压缩信息中各 有效值的偏移值；通过将所述初始化位图信息中各有效值的偏移值对应的位设 置为有效值，得到该段位图信息的压缩信息对应的解压信息。

第四方面，本发明实施例提供了一种位图索引解压装置，包括：

压缩信息获取模块，用于获取数据基表中所包含的索引关键字的位图索引 的各段位图信息的压缩信息，其中，所述各段位图信息通过将该位图索引按预 设段宽度分段获得，对于各段位图信息的压缩信息，该段位图信息的压缩信息 包含二进制表示信息和二进制存储位数，所述二进制表示信息包含该段位图信 息中各有效值的偏移值的二进制表示信息；所述二进制存储位数包含该段位图 信息中各有效值的偏移值的二进制表示信息的存储位数，所述偏移值为对应的 有效值在该段位图信息中的位数；

初始化位图信息生成模块，用于对于各段位图信息的压缩信息，生成宽度 为预设段宽度的初始化位图信息；

偏移值确定模块，用于根据该段位图信息的压缩信息中的二进制存储位数， 将该段位图信息的压缩信息中的二进制表示信息转换为十进制信息，得到该段 位图信息的压缩信息中各有效值的偏移值；

第一解压模块，用于通过将所述初始化位图信息中各有效值的偏移值对应 的位设置为有效值，得到该段位图信息的压缩信息对应的解压信息。

本发明实施例提供的位图索引压缩方法及装置，通过按预设段宽度分段， 得到索引关键字对应的位图索引的各段位图信息，并将各段位图信息中各有效 值的偏移值按对应的二进制存储位数进行存储，得到该段位图信息的压缩信息， 由于只存储各段位图信息中各有效值的偏移值，因此能够减小位图索引的存储 空间。相应地，本发明实施例提供的位图索引解压方法及装置，利用各有效值 的偏移值的二进制表示信息的存储位数，得到各段位图信息的压缩信息中各有 效值的偏移值，并通过将所述初始化位图信息中各有效值的偏移值对应的位设 置为有效值，得到该段位图信息的压缩信息对应的解压信息，能够降低位图索 引的解压复杂度，并提高了位图索引的检索查询效率。

附图说明

为了更清楚地说明本发明，下面将对本发明中所需要使用的附图做一简单 地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域 普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获 得其他的附图。

图1为本发明实施例一提供的一种位图索引压缩方法的流程图；

图2为本发明实施例二提供的一种位图索引压缩方法的流程图；

图3为本发明实施例三提供的一种位图索引压缩方法的流程图；

图4为本发明实施例四提供的一种位图索引压缩装置的结构示意图；

图5为本发明实施例五提供的一种位图索引解压方法的流程图；

图6为本发明实施例六提供的一种位图索引解压方法的流程图；

图7为本发明实施例七提供的一种位图索引解压装置的结构示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明 实施例中的技术方案作进一步详细描述，显然，所描述的实施例是本发明一部 分实施例，而不是全部的实施例。可以理解的是，此处所描述的具体实施例仅 用于解释本发明，而非对本发明的限定，基于本发明中的实施例，本领域普通 技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发 明保护的范围。另外还需要说明的是，为了便于描述，附图中仅示出了与本发 明相关的部分而非全部内容。

实施例一

请参阅图1，为本发明实施例一提供的一种位图索引压缩方法的流程图。本 发明实施例的方法可以由配置以硬件和/或软件实现的位图索引压缩装置来执 行，该实现装置典型的是配置于能够提供位图索引压缩服务的服务器中。如图1 所示，所述方法包括：

步骤110、对于预先建立的数据基表中所包含的索引关键字的位图索引，将 该位图索引按预设段宽度分段，得到多段位图信息；

数据基表是数据库中一个重要的对象，由各元素组成。数据基表中所包含 的索引关键字代表数据基表中各列属性所包含的元素的取值情况。位图索引是 一种使用位图的特殊的数据库索引技术，在位图索引中，每个位的取值为1或0， 表示对应的基行的元素是否满足对应的索引关键字的值，因此，索引关键字的 位图索引的长度等于基行的长度。

在本步骤中，优选地，所述预设段宽度为8的整数倍。

需要说明的是，一个位图索引划分为了若干段，每个段的宽度为预设段宽 度，当最后一段对应的位图索引信息小于预设段宽度时，在末尾以0补足。

示例性地，通过表1中的数据基表为例进行说明。表1中的数据基表中基 行的长度为n，包含A和B两列，其中A的取值包括L、T和M三种情况，B 的取值包括X和Y两种情况，因此，A的索引关键字分别为L、T和M，B的 索引关键字分别为X和Y。表2为A的索引关键字及对应的位图索引，表3为 B的索引关键字及对应的位图。以A的索引关键字L为例说明，由表1可知， A取值为L时所对应的行号分别为1、3、...、和n，由表2可知，A的索引关键 字L对应的位图索引101000...1，该索引关键字的位图索引的长度为n，等于基 行的长度。其中，第一位的值为1，表示数据基表中A列第1行的元素的值为L， 第二位的值为0，表示数据基表中A列第2行的元素的值不为L，第三位的值为 1，表示数据基表中A列第3行的元素的值为L，依次类推。

表1

行号 A B 1 L X 2 T Y 3 L Y 4 M X 5 T Y 6 M Y ... ... ... n L X

表2

序号 索引关键字 位图索引 1 L 101000...1 2 T 010010...0 3 M 000101...0

表3

序号 索引关键字 位图索引 1 X 100100...1 2 Y 011011...0

例如，若索引关键字L的位图索引为101000000000100000100001，当预设 段宽度为16时，则索引关键字L的位图索引的分段结果如表4所示。其中，第 1段位图信息为1010000000001000，由于第2段信息00100001的宽度小于预设 段宽度，因此在该信息末尾用0补足，补足后，第2段位图信息为 0010000100000000。

表4

段号 段位图信息 1 1010000000001000 2 0010000100000000

步骤120、对于各段位图信息，确定该段位图信息中各有效值的偏移值，其 中，所述偏移值为对应的有效值在该段位图信息中的位数；根据各有效值的偏 移值确定各偏移值的二进制存储位数；根据所述二进制存储位数得到该段位图 信息中各偏移值的二进制表示信息，生成并存储该段位图信息的压缩信息，该 压缩信息包含各偏移值的二进制表示信息。

具体地，位数可以为该段位图信息从左向右数的顺序位。

仍以步骤110中的实例为例进行说明。表5所示为索引关键字L所包含的 两段位图信息对应的各有效值的偏移值，其中，有效值为1。

表5

段号 段位图信息 各有效值的偏移值 1 1010000000001000 1,3,13 2 0010000100000000 3,8

作为步骤120的一种实施方式，可以将根据各有效值的偏移值确定各偏移 值的二进制存储位数，优化为：对于各有效值的偏移值，分别确定该偏移值对 应的最小二进制存储位数。

例如，表5中的第1段位图信息中偏移值1的最小二进制存储位数为1，偏 移值3的最小二进制存储位数为2，偏移值13的最小二进制存储位数为4。

类似地，表5中的第2段位图信息中偏移值3的最小二进制存储位数为2， 偏移值8的最小二进制存储位数为4。

下面分别说明步骤120中根据所述二进制存储位数得到该段位图信息中各 偏移值的二进制表示信息，生成并存储该段位图信息的压缩信息，该压缩信息 包含各偏移值的二进制表示信息。

表5中的第1段位图信息中偏移值1的最小二进制存储位数为1，对应的二 进制表示信息位1；偏移值3的最小二进制存储位数为2，对应的二进制表示信 息位11；偏移值13的最小二进制存储位数为4，对应的二进制表示信息位1101。 因此生成并存储的该段位图信息的压缩信息可以为1111101。

类似地，表5中的第2段位图信息中偏移值3的最小二进制存储位数为2， 对应的二进制表示信息位11；偏移值8的最小二进制存储位数为4，对应的二 进制表示信息位1000。因此生成并存储的该段位图信息的压缩信息可以为 111000。具体结果如表6所示。

表6

段号 段位图信息 压缩信息 1 1010000000001000 1111101 2 0010000100000000 111000

由此可知，第1段位图信息的压缩信息的存储空间小于该段位图信息本身 的段宽度；而第2段位图信息的压缩信息的存储空间小于该段位图信息本身的 段宽度，因此采用本实施方式的方法可以减小位图索引的存储空间。

作为步骤120的另一种实施方式，可以将根据各有效值的偏移值确定各偏 移值的二进制存储位数，优化为：对于各有效值的偏移值，根据各有效值中最 大的偏移值，确定该最大的偏移值的最小二进制存储位数，并将该最小二进制 存储位数作为各有效值的偏移值的二进制存储位数。

例如，表5中的第1段位图信息中各有效值中最大的偏移值为13，偏移值 13的最小二进制存储位数为4，从而确定该段位图信息中偏移值1、3和13的 二进制存储位数均为4。

类似地，可以得到表5中的第2段位图信息中各偏移值的二进制存储位数， 此处不再赘述，确定结果为偏移值3的二进制存储位数为4，偏移值8的二进制 存储位数为4。

下面分别说明步骤120中根据所述二进制存储位数得到该段位图信息中各 偏移值的二进制表示信息，生成并存储该段位图信息的压缩信息，该压缩信息 包含各偏移值的二进制表示信息。

表5中的第1段位图信息中偏移值1的二进制存储位数为4，对应的二进制 表示信息位0001；偏移值3的二进制存储位数为4，对应的二进制表示信息位 0011；偏移值13的二进制存储位数为4，对应的二进制表示信息位1101。因此 生成并存储的该段位图信息的压缩信息可以为000100111101。

类似地，表5中的第2段位图信息中偏移值3的二进制存储位数为4，对应 的二进制表示信息为0011；偏移值8的二进制存储位数为4，对应的二进制表 示信息为1000。因此生成并存储的该段位图信息的压缩信息可以为00111000。 具体结果如表7所示。

表7

段号 段位图信息 压缩信息 1 1010000000001000 000100111101 2 0010000100000000 00111000

由此可知，第1段位图信息的压缩信息的存储空间小于该段位图信息本身 的段宽度；而第2段位图信息的压缩信息的存储空间小于该段位图信息本身的 段宽度，因此采用本实施方式的方法可以减小位图索引的存储空间。

本实施例的技术方案，通过按预设段宽度分段，得到索引关键字对应的位 图索引的各段位图信息，并将各段位图信息中各有效值的偏移值按对应的二进 制存储位数进行存储，得到该段位图信息的压缩信息，由于只存储各段位图信 息中各有效值的偏移值，因此能够减小位图索引的存储空间。

在上述实施例中，优选地，步骤110与步骤120可以并行执行。

也就是说，不需要等待该位图索引的各段位图信息都生成后，再执行步骤 120，而是当当前段的宽度达到预设段宽度时，即可对该段位图信息按步骤120 进行操作，从而在减小位图索引的存储空间的同时，可以提高位图索引的存储 处理速度。

实施例二

请参阅图2，为本发明实施例二提供的一种位图索引压缩方法的流程图。如 图2所示，所述方法包括：

步骤210、对于预先建立的数据基表中所包含的索引关键字的位图索引，将 该位图索引按预设段宽度分段，得到多段位图信息；

步骤220、对于各段位图信息，确定当前段位图信息的稀疏因子；

在本步骤中，当有效值为1时，所述稀疏因子为当前段位图信息中0的个 数与预设段宽度的比值；当有效值为0时，所述稀疏因子为当前段位图信息中1 的个数与预设段宽度的比值。

步骤230、判断当前段位图信息的稀疏因子是否大于等于预设稀疏阈值，若 是，执行步骤240；若否，执行步骤250；

步骤240、确定该段位图信息中各有效值的偏移值，其中，所述偏移值为对 应的有效值在该段位图信息中的位数；根据各有效值的偏移值确定各偏移值的 二进制存储位数；

在本步骤中，优选地，所述根据各有效值的偏移值确定各偏移值的二进制 存储位数，包括：对于各有效值的偏移值，分别确定该偏移值对应的最小二进 制存储位数。

步骤241、判断各偏移值的二进制存储位数的总和是否小于预设段宽度，若 是，执行步骤242，若否，执行步骤250；

也就是说，根据各有效值的偏移值确定各偏移值的二进制存储位数的确定 结果包括两种，一种为各有效值的偏移值对应的二进制存储位数不同，例如， 表5中的第1段位图信息中偏移值1的最小二进制存储位数为1，偏移值3的最 小二进制存储位数为2，偏移值13的最小二进制存储位数为4；另一种为各有 效值的偏移值对应的二进制存储位数相同，例如，表5中的第1段位图信息中 偏移值1、3和13的二进制存储位数均为4。

各偏移值的二进制存储位数的总和可以表征将该段位图信息中各偏移值按 对应的二进制存储位数存储后，占用的存储空间的大小。

当各有效值的偏移值对应的二进制存储位数相同时，所述各偏移值的二进 制存储位数的总和可以通过各偏移值的二进制存储位数与偏移值的个数的乘积 确定。

步骤242、根据所述二进制存储位数得到该段位图信息中各偏移值的二进制 表示信息，生成并存储该段位图信息的压缩信息，该压缩信息包含各偏移值的 二进制表示信息，流程结束；

步骤250、利用普通位图压缩算法对当前段位图信息进行压缩，生成并存储 该段位图信息的压缩信息，其中所述普通位图压缩算法包括zip压缩算法或rar 压缩算法，流程结束。

也就是说，对于多段位图信息，当当前段位图信息的稀疏因子大于等于预 设稀疏阈值时，确定该段位图信息中各有效值的偏移值；根据各有效值的偏移 值确定各偏移值的二进制存储位数；当各偏移值的二进制存储位数的总和小于 预设段宽度时，采用根据所述二进制存储位数得到该段位图信息中各偏移值的 二进制表示信息的方式对当前段位图信息进行压缩；而当当前段位图信息的稀 疏因子小于预设稀疏阈值时，则利用普通位图压缩算法对当前段位图信息进行 压缩。

对于多段位图信息，当当前段位图信息的稀疏因子小于预设稀疏阈值时， 则利用普通位图压缩算法对当前段位图信息进行压缩。

本实施例的技术方案，通过按预设段宽度分段，得到索引关键字对应的位 图索引的各段位图信息，当当前段位图信息的稀疏因子大于等于预设稀疏阈值 时，确定该段位图信息中各有效值的偏移值，并根据各有效值的偏移值确定各 偏移值的二进制存储位数，当各偏移值的二进制存储位数的总和小于预设段宽 度时，将各段位图信息中各有效值的偏移值按对应的二进制存储位数进行存储， 得到该段位图信息的压缩信息，由于只存储各段位图信息中各有效值的偏移值， 因此能够减小位图索引的存储空间；当当前段位图信息的稀疏因子小于预设稀 疏阈值时，或当各偏移值的二进制存储位数的总和不小于预设段宽度时，则利 用普通位图压缩算法对当前段位图信息进行压缩，减小了位图索引的存储空间。

实施例三

请参阅图3，为本发明实施例三提供的一种位图索引压缩方法的流程图。如 图3所示，所述方法包括：

步骤310、对于预先建立的数据基表中所包含的索引关键字的位图索引，将 该位图索引按预设段宽度分段，得到多段位图信息；

优选地，所述预设段宽度为8的整数倍。

步骤320、对于各段位图信息，确定该段位图信息的第一辅助信息；

其中，所述第一辅助信息至少包括该段位图信息的起始行号和该段位图信 息的结束行号。所述第一辅助信息还可以包括分段号。所述结束行号与所述起 始行号和预设段宽度有关。

例如，若索引关键字L的位图索引为101000000000100000100001，当预设 段宽度为16时，则索引关键字L的位图索引的分段结果如表4所示。其中，第 1段位图信息为1010000000001000，该段位图信息的起始行号为1，结束行号为 16；第2段位图信息为0010000100000000，该段位图信息的起始行号为17，结 束行号为32。

需要说明的是，根据各段位图信息的第一辅助信息，有利于得到分段前各 段位图信息对应的位图索引。

步骤330、确定该段位图信息中各有效值的偏移值；根据各有效值的偏移值 确定各偏移值的二进制存储位数；

其中，所述偏移值为对应的有效值在该段位图信息中的位数，所述有效值 优选为1。

步骤340、确定该段位图信息的第二辅助信息；

所述第二辅助信息至少包括各偏移值的二进制存储位数；所述第二辅助信 息还可以包括该段位图信息的压缩类型，所述压缩类型可以表征该段位图信息 的压缩算法。

例如，采用本实施例的方法对段位图信息中各偏移值进行压缩存储对应的 压缩类型为Ⅰ，而采用普通位图压缩算法对当前段位图信息进行压缩的压缩类 型为Ⅱ。

需要说明的是，根据各段位图信息的第二辅助信息，有利于通过解压得到 分段前各段位图信息对应的位图索引。

步骤350、根据所述二进制存储位数得到该段位图信息中各偏移值的二进制 表示信息，生成并存储该段位图信息的压缩信息，该压缩信息包含各偏移值的 二进制表示信息、该段位图信息的第一辅助信息和/或该段位图信息的第二辅助 信息。

本实施例的技术方案，通过按预设段宽度分段，得到索引关键字对应的位 图索引的各段位图信息，并将各段位图信息中各有效值的偏移值按对应的二进 制存储位数进行存储，得到该段位图信息的压缩信息，压缩信息中除包含各偏 移值的二进制表示信息，还包含该段位图信息的第一辅助信息和/或该段位图信 息的第二辅助信息，由于只存储各段位图信息中各有效值的偏移值，因此能够 减小位图索引的存储空间，同时第一辅助信息和/或第二辅助信息有利于降低位 图索引的解压复杂度，能够提高位图索引的检索查询效率。

实施例四

请参阅图4，为本发明实施例四提供的一种位图索引压缩装置的结构示意 图。该装置包括：分段模块410、偏移值确定模块420、二进制存储位数确定模 块430和第一存储模块440。

其中，分段模块410用于对于预先建立的数据基表中所包含的索引关键字 的位图索引，将该位图索引按预设段宽度分段，得到多段位图信息；偏移值确 定模块420用于对于各段位图信息，确定该段位图信息中各有效值的偏移值， 其中，所述偏移值为对应的有效值在该段位图信息中的位数；二进制存储位数 确定模块430用于根据各有效值的偏移值确定各偏移值的二进制存储位数；第 一存储模块440用于根据所述二进制存储位数得到该段位图信息中各偏移值的 二进制表示信息，生成并存储该段位图信息的压缩信息，该压缩信息包含各偏 移值的二进制表示信息。

优选地，所述预设段宽度为8的整数倍。

本实施例的技术方案，通过按预设段宽度分段，得到索引关键字对应的位 图索引的各段位图信息，并将各段位图信息中各有效值的偏移值按对应的二进 制存储位数进行存储，得到该段位图信息的压缩信息，由于只存储各段位图信 息中各有效值的偏移值，因此能够减小位图索引的存储空间。

在上述方案中，所述装置还包括：稀疏因子确定模块。

其中，稀疏因子确定模块用于在对于预先建立的数据基表中所包含的索引 关键字的位图索引，将该位图索引按预设段宽度分段，得到多段位图信息之后， 确定当前段位图信息的稀疏因子。其中当有效值为1时，所述稀疏因子为当前 段位图信息中0的个数与预设段宽度的比值；或当有效值为0时，所述稀疏因 子为当前段位图信息中1的个数与预设段宽度的比值。

偏移值确定模块420具体用于对于各段位图信息，当当前位图信息的稀疏 因子大于等于预设稀疏阈值时，确定该段位图信息中各有效值的偏移值，其中， 所述偏移值为对应的有效值在该段位图信息中的位数。

在上述方案中，所述装置还包括：第二存储模块。

第二存储模块用于当前段位图信息的稀疏因子小于稀疏阈值时，利用普通 位图压缩算法对当前段位图信息进行压缩，生成并存储该段位图信息的压缩信 息，其中所述普通位图压缩算法包括zip压缩算法或rar压缩算法。

在上述方案中，所述装置还包括：判断模块。

判断模块用于判断各偏移值的二进制存储位数的总和是否小于预设段宽 度；

第一存储模块440具体用于在根据各有效值的偏移值确定各偏移值的二进 制存储位数之后，当各偏移值的二进制存储位数的总和小于预设段宽度时，根 据所述二进制存储位数得到该段位图信息中各偏移值的二进制表示信息，生成 并存储该段位图信息的压缩信息，该压缩信息包含各偏移值的二进制表示信息。

在上述方案中，第二存储模块还用于当各偏移值的二进制存储位数的总和 不小于预设段宽度时，利用普通位图压缩算法对当前段位图信息进行压缩，生 成并存储该段位图信息的压缩信息，其中所述普通位图压缩算法包括zip压缩算 法或rar压缩算法。

在上述方案中，所述分段模块410，与所述偏移值确定模块420、二进制存 储位数确定模块430和第一存储模块440，可以并行执行。

在上述方案中，所述装置还可以包括：第一辅助信息确定模块、第二辅助 信息确定模块。

其中，第一辅助信息确定模块用于在对于预先建立的数据基表中所包含的 索引关键字的位图索引，将该位图索引按预设段宽度分段，得到多段位图信息 之后，确定该段位图信息的第一辅助信息，所述第一辅助信息至少包括该段位 图信息的起始行号和该段位图信息的结束行号；第二辅助信息确定模块用于在 根据各有效值的偏移值确定各偏移值的二进制存储位数之后，确定该段位图信 息的第二辅助信息，所述第二辅助信息至少包括各偏移值的二进制存储位数； 第一存储模块440具体用于根据所述二进制存储位数得到该段位图信息中各偏 移值的二进制表示信息，生成并存储该段位图信息的压缩信息，该压缩信息包 含各偏移值的二进制表示信息、该段位图信息的第一辅助信息和/或该段位图信 息的第二辅助信息。

本发明实施例提供的位图索引压缩装置可执行本发明任意实施例所提供的 位图索引压缩方法，具备执行方法相应的功能模块和有益效果。

实施例五

请参阅图5，为本发明实施例五提供的一种位图索引解压方法的流程图。本 发明实施例的方法可以由配置以硬件和/或软件实现的位图索引解压装置来执 行，该实现装置典型的是配置于能够提供位图索引解压服务的服务器中。如图5 所示，所述方法包括：

步骤510、获取数据基表中所包含的索引关键字的位图索引的各段位图信息 的压缩信息；

其中，所述各段位图信息通过将该位图索引按预设段宽度分段获得，对于 各段位图信息的压缩信息，该段位图信息的压缩信息包含二进制表示信息和二 进制存储位数，所述二进制表示信息包含该段位图信息中各有效值的偏移值的 二进制表示信息；所述二进制存储位数包含该段位图信息中各有效值的偏移值 的二进制表示信息的存储位数，所述偏移值为对应的有效值在该段位图信息中 的位数。

其中，优选地，所述预设段宽度为8的整数倍。

步骤520、对于各段位图信息的压缩信息，生成宽度为预设段宽度的初始化 位图信息；根据该段位图信息的压缩信息中的二进制存储位数，将该段位图信 息的压缩信息中的二进制表示信息转换为十进制信息，得到该段位图信息的压 缩信息中各有效值的偏移值；通过将所述初始化位图信息中各有效值的偏移值 对应的位设置为有效值，得到该段位图信息的压缩信息对应的解压信息。

示例性地，通过表8所示的获取的数据基表中所包含的索引关键字L的位 图索引的各段位图信息的压缩信息为例进行说明，其中预设段宽度为16，各段 位图信息中有效值为1。

表8

对于第1段压缩信息，生成宽度为预设宽度的初始化位图信息，可选地， 所述初始化位图信息的各位均可以为0。例如，生成宽度为16的初始化位图信 息，0000000000000000。根据该段位图信息的压缩信息中的二进制存储位数1、 2和4，将该段位图信息的压缩信息中的二进制表示信息1111101转换为十进制 信息，具体地，二进制表示信息1111101中的第1位转换为十进制信息1；二进 制表示信息1111101中的第2位和第3为这2位转换为十进制信息3；二进制表 示信息1111101中的第4位到第8为这4位转换为十进制信息13；因此，得到 的该段位图信息的压缩信息中各有效值的偏移值为1,3和13。通过将所述初始 化位图信息中各有效值的偏移值对应的位设置为有效值，即第1、3和13位设 置为有效值1，从而得到该段位图信息的压缩信息对应的解压信息为 1010000000001000。

类似地，对于第二段压缩信息，得到的该段位图信息的压缩信息中各有效 值的偏移值为3和8。通过将所述初始化位图信息中各有效值的偏移值对应的位 设置为有效值，即第3和8位设置为有效值1，从而得到该段位图信息的压缩信 息对应的解压信息为0010000100000000。

本实施例的技术方案，利用各有效值的偏移值的的二进制表示信息的存储 位数，得到各段位图信息的压缩信息中各有效值的偏移值，并通过将所述初始 化位图信息中各有效值的偏移值对应的位设置为有效值，得到该段位图信息的 压缩信息对应的解压信息，降低了位图索引的解压复杂度，并提高了位图索引 的检索查询效率。

在上述方案中，在步骤510之后，还可以包括：

步骤511、获取各段位图信息的压缩信息对应的各段位图信息的第一辅助信 息；

所述第一辅助信息至少包括该段位图信息的起始行号和该段位图信息的结 束行号。

仍以上述实例为例进行说明。获取索引关键字L的位图索引的第1段位图 信息1010000000001000的第一辅助信息，其中，所述第一辅助信息至少包括该 段位图信息的起始行号1和该结束行号16。

类似地，获取索引关键字L的位图索引的第2段位图信息0010000100000000 的第一辅助信息，其中，所述第一辅助信息至少包括该段位图信息的起始行号 17和该结束行号32。

在步骤520之后，还可以包括：

步骤530、根据各段位图信息的压缩信息对应的解压信息，并根据对应的第 一辅助信息，得到对应的索引关键字的位图索引。

仍以上述实例为例进行说明。根据索引关键字L的位图索引的第1段位图 信息1010000000001000的第一辅助信息，以及第2段位图信息 0010000100000000的第一辅助信息，按行号从小到大将各段位图信息进行排序， 得到对应的索引关键字L的位图索引为10100000000010000010000100000000， 从而实现对索引关键字L的位图索引的解压。

类似地，可以得到数据基表中其余索引关键字的位图索引，此处不再赘述。

本实施例的技术方案，通过进一步获取各段位图信息的压缩信息对应的各 段位图信息的第一辅助信息，并根据各段位图信息的压缩信息对应的解压信息， 可以得到对应的索引关键字的位图索引。

实施例六

请参阅图6，为本发明实施例六提供的一种位图索引解压方法的流程图。该 方法包括：

步骤610、获取数据基表中所包含的索引关键字的位图索引的各段位图信息 的压缩信息，并获取各段位图信息的稀疏因子；

其中，所述各段位图信息通过将该位图索引按预设段宽度分段获得，对于 各段位图信息的压缩信息，该段位图信息的压缩信息包含二进制表示信息和二 进制存储位数，所述二进制表示信息包含该段位图信息中各有效值的偏移值的 二进制表示信息；所述二进制存储位数包含该段位图信息中各有效值的偏移值 的二进制表示信息的存储位数，所述偏移值为对应的有效值在该段位图信息中 的位数。

其中当有效值为1时，所述稀疏因子为该段位图信息中0的个数与预设段 宽度的比值；或当有效值为0时，所述稀疏因子为该段位图信息中1的个数与 预设段宽度的比值。

步骤620、判断当前段位图信息的压缩信息中该段位图信息的稀疏因子是否 大于等于预设稀疏阈值；若是，执行步骤630；若否，执行步骤640；

步骤630、判断各偏移值的二进制存储位数的总和是否小于预设段宽度；若 是，执行步骤631；若否，执行步骤640；

步骤631、根据该段位图信息的压缩信息中的二进制存储位数，将该段位图 信息的压缩信息中的二进制表示信息转换为十进制信息，得到该段位图信息的 压缩信息中各有效值的偏移值；通过将所述初始化位图信息中各有效值的偏移 值对应的位设置为有效值，得到该段位图信息的压缩信息对应的解压信息，流 程结束；

步骤640、利用普通位图解压算法对当前段位图信息的压缩信息进行解压， 得到该段位图信息的压缩信息对应的解压信息，其中所述普通位图压缩算法包 括zip压缩算法或rar压缩算法，流程结束。

也就是说，对于各段位图信息的压缩信息，当当前段位图信息的压缩信息 中该段位图信息的稀疏因子大于等于预设稀疏阈值，并且当各偏移值的二进制 存储位数的总和小于预设段宽度时，则将该段位图信息的压缩信息中的二进制 表示信息转换为十进制信息，得到该段位图信息的压缩信息中各有效值的偏移 值；通过将所述初始化位图信息中各有效值的偏移值对应的位设置为有效值， 得到该段位图信息的压缩信息对应的解压信息。而当当前段位图信息的压缩信 息中该段位图信息的稀疏因子小于预设稀疏阈值，或当各偏移值的二进制存储 位数的总和不小于预设段宽度时，则利用普通位图解压算法对当前段位图信息 的压缩信息进行解压。

本实施例的技术方案，根据当前段位图信息的压缩信息中该段位图信息的 稀疏因子是否大于等于预设稀疏阈值，采用不同的解压方法。当当前段位图信 息的压缩信息中该段位图信息的稀疏因子大于等于预设稀疏阈值，并且当各偏 移值的二进制存储位数的总和小于预设段宽度时，利用该段位图信息的压缩信 息中的二进制存储位数，得到各段位图信息的压缩信息中各有效值的偏移值， 并通过将初始化位图信息中各有效值的偏移值对应的位设置为有效值，得到该 段位图信息的压缩信息对应的解压信息，降低了位图索引的解压复杂度，并提 高了位图索引的检索查询效率。而当当前段位图信息的压缩信息中该段位图信 息的稀疏因子小于预设稀疏阈值，或当各偏移值的二进制存储位数的总和不小 于预设段宽度时，则利用普通位图解压算法对当前段位图信息的压缩信息进行 解压。

实施例七

请参阅图7，为本发明实施例七提供的一种位图索引解压装置的结构示意 图。该装置包括：压缩信息获取模块710、初始化位图信息生成模块720、偏移 值确定模块730和第一解压模块740。

其中，压缩信息获取模块710用于获取数据基表中所包含的索引关键字的 位图索引的各段位图信息的压缩信息，其中，所述各段位图信息通过将该位图 索引按预设段宽度分段获得，对于各段位图信息的压缩信息，该段位图信息的 压缩信息包含二进制表示信息和二进制存储位数，所述二进制表示信息包含该 段位图信息中各有效值的偏移值的二进制表示信息；所述二进制存储位数包含 该段位图信息中各有效值的偏移值的二进制表示信息的存储位数，所述偏移值 为对应的有效值在该段位图信息中的位数；初始化位图信息生成模块720用于 对于各段位图信息的压缩信息，生成宽度为预设段宽度的初始化位图信息；偏 移值确定模块730用于根据该段位图信息的压缩信息中的二进制存储位数，将 该段位图信息的压缩信息中的二进制表示信息转换为十进制信息，得到该段位 图信息的压缩信息中各有效值的偏移值；第一解压模块740用于通过将所述初 始化位图信息中各有效值的偏移值对应的位设置为有效值，得到该段位图信息 的压缩信息对应的解压信息。

优选地，所述预设段宽度为8的整数倍。

本实施例的技术方案，利用各有效值的偏移值的二进制表示信息的存储位 数，得到各段位图信息的压缩信息中各有效值的偏移值，并通过将所述初始化 位图信息中各有效值的偏移值对应的位设置为有效值，得到该段位图信息的压 缩信息对应的解压信息，降低了位图索引的解压复杂度，并提高了位图索引的 检索查询效率。

在上述方案中，压缩信息获取模块710可以包括：稀疏因子获取单元。

稀疏因子获取单元用于获取各段位图信息的稀疏因子，其中当有效值为1 时，所述稀疏因子为该段位图信息中0的个数与预设段宽度的比值；或当有效 值为0时，所述稀疏因子为该段位图信息中1的个数与预设段宽度的比值。

偏移值确定模块730具体用于在当前段位图信息的压缩信息中该段位图信 息的稀疏因子大于等于预设稀疏阈值时，根据该段位图信息的压缩信息中的二 进制存储位数，将该段位图信息的压缩信息中的二进制表示信息转换为十进制 信息，得到该段位图信息的压缩信息中各有效值的偏移值。

在上述方案中，该装置还可以包括：第二解压模块。

第二解压模块用于在当前段位图信息的压缩信息中该段位图信息的稀疏因 子小于预设稀疏阈值时，利用普通位图解压算法对当前段位图信息的压缩信息 进行解压，得到该段位图信息的压缩信息对应的解压信息，其中所述普通位图 压缩算法包括zip压缩算法或rar压缩算法。

在上述方案中，该装置还可以包括：判断模块。

判断模块，用于在当前段位图信息的压缩信息中该段位图信息的稀疏因子 大于等于预设稀疏阈值时，判断各偏移值的二进制存储位数的总和是否小于预 设段宽度。

偏移值确定模块730具体用于在当前段位图信息的压缩信息中该段位图信 息的稀疏因子大于等于预设稀疏阈值时，并且当各偏移值的二进制存储位数的 总和小于预设段宽度时，根据该段位图信息的压缩信息中的二进制存储位数， 将该段位图信息的压缩信息中的二进制表示信息转换为十进制信息，得到该段 位图信息的压缩信息中各有效值的偏移值。

在上述方案中，第二解压模块还可以用于当各偏移值的二进制存储位数的 总和不小于预设段宽度时，利用普通位图解压算法对当前段位图信息的压缩信 息进行解压，得到该段位图信息的压缩信息对应的解压信息，其中所述普通位 图压缩算法包括zip压缩算法或rar压缩算法。

在上述方案中，压缩信息获取模块710还可以包括：第一辅助信息获取单 元。

第一辅助信息获取单元用于获取各段位图信息的压缩信息对应的各段位图 信息的第一辅助信息，所述第一辅助信息至少包括该段位图信息的起始行号和 该段位图信息的结束行号。

所述装置还可以包括：位图索引确定模块。

位图索引确定模块用于在通过将所述初始化位图信息中各有效值的偏移值 对应的位设置为有效值，得到该段位图信息的压缩信息对应的解压信息之后， 根据各段位图信息的压缩信息对应的解压信息，并根据对应的第一辅助信息， 得到对应的索引关键字的位图索引。

本发明实施例提供的位图索引解压装置可执行本发明任意实施例所提供的 位图索引解压方法，具备执行方法相应的功能模块和有益效果。

本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤 可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取 存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的 存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上各实施例仅用于说明本发明的技术方案，而非对其 进行限制；实施例中优选的实施方式，并非对其进行限制，对于本领域技术人 员而言，本发明可以有各种改动和变化。凡在本发明的精神和原理之内所作的 任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。