当前位置：首页 > news >正文

福州企业网站网络销售靠谱吗

news 2025/7/4 13:14:13

福州企业网站,网络销售靠谱吗,一般纳税人企业所得税,湖南省政务服务网网站建设要求这是一篇读书笔记，因对 bitmap 技术感兴趣，参考论文和官网资料学习和整理。本文讨论用于在数据仓库应用程序中进行高效查询处理的各种位图索引技术。我们回顾了现有的文献并将该技术分为三类，即位图编码、压缩和分箱。我们引入了一种高效的位…

这是一篇读书笔记，因对 bitmap 技术感兴趣，参考论文和官网资料学习和整理。

本文讨论用于在数据仓库应用程序中进行高效查询处理的各种位图索引技术。我们回顾了现有的文献并将该技术分为三类，即位图编码、压缩和分箱。我们引入了一种高效的位图压缩算法，并在来自实际应用的大型数据集上检查压缩位图索引的空间和时间复杂度。根据传统观点，位图索引仅对低基数属性有效。然而，我们展示了压缩位图索引对于高基数属性也是有效的。时序结果表明，位图索引明显优于投影索引，投影索引通常被认为是多维查询最有效的访问方法。最后，我们回顾了目前常用的商业数据库系统支持的位图索引技术，并讨论了未来研究和开发的开放问题。

介绍

查询大型数据集以定位某些选定的记录是数据仓库应用程序中的常见任务。由于数据复杂性，高效地实现查询通常很困难。一个典型的搜索场景是统计生产者P在时间间隔T内卖出的汽车数量。这种过程通常使用B-tree索引来加速。传统的关系型数据库大多数都支持B-tree索引。然而，随着数据属性数量的增加，可能的索引组合的数量也随着增加。多场景下高效查询变得艰难。这体现在复杂业务中，对于多个属性值，是否为空、等值筛选、范围筛选、排序等一些列的条件组合。在文献中，这种困境通常被称为 curse of dimensionality。

本文讨论一种索引技术，有望打破数据仓库应用程序的维度诅咒，即位图索引技术。位图索引的一个非常显着的特点是它对查询的主要解决方案是位图。打破维度诅咒的一种方法是为数据集的每个属性建立一个位图索引。为了解决涉及多个属性条件的查询，首先使用相应的位图索引解析每个属性的条件，并将每个条件的解决方案作为位图获得。然后我们通过组合这些位图来获得整个查询的答案。由于计算机硬件很好地支持对位图的操作，因此位图可以轻松有效地组合。总体而言，我们希望总查询响应时间与查询中涉及的属性数量呈线性关系，而不是与数据集的维度（属性）数量呈指数关系，从而打破维度诅咒。

背景

几乎每个数据库产品都有B-tree，这种类型的基于树的索引方法具有几乎相同的搜索和更新索引的操作复杂性，这对于OLTP场景十分有效。然而对于OLAP场景来说，查询操作执行频率比更新操作频率高得多，这种情况下B-tree已不再是最优解决方案。本文将证明，位图索引在 OLAP 操作的搜索和更新之间具有最佳平衡。

通常，在 OLAP 场景下，每个查询都涉及许多属性，不同查询通常涉及不同的属性或者不同属性的组合。使用传统的多维索引方法，几乎每个属性组合都需要一个单独的索引。这种方案索引的数量随着数据集中属性的数量呈指数增长。在文献中，这有时被称为维度灾难。对于具有中等维度的数据集，解决此问题的常用方法是使用一种多维索引方法，例如 R-Trees 或 kd-trees。这些方法有两个显着的缺点。首先，它们仅对维数适中的数据集有效，例如，< 15。其次，它们仅对涉及所有索引属性的查询有效。但是，在许多应用程序中，查询中只使用了一些属性。在这些情况下，传统的索引方法通常效率不高。对于范围查询，大多数已知的索引方法的性能不如投影索引，这可以看作是组织基础的一种方式。另一方面，位图索引在这些查询上具有出色的性能特征。如理论分析和时序测量所示，压缩位图索引对于一维范围查询是非常高效的。由于可以有效地组合对一维范围查询的答案以应对任意多维范围查询，因此压缩位图索引对于任何范围查询都是有效的。在计算复杂度方面，一种类型的压缩位图索引被证明在理论上对于一维范围查询是最优的。理论上证明最优的原因是查询响应时间是命中数的线性函数，即结果集的大小。有许多索引方法，包括 B*-tree 和 B+-tree，理论上对于一维范围查询是最优的，但它们中的大多数不能用于有效地回答任意多维范围查询.

各种形式的位图索引在关系数据库系统或数据仓库系统被开发之前就已经使用了很长时间。早些时候，位图索引被认为是一种特殊形式的倒排文件。位转置文件非常接近当前使用的位图索引。名称位图索引由 O'Neil 及其同事推广。遵循 Model 204 描述中设置的示例，这是位图索引的第一个商业实现，许多研究人员将位图索引描述为 B 树索引的变体。为了尊重它早期的化身为反转文件，我们将位图索引视为由键和位图组成的数据结构。此外，我们将 B-tree 视为在文件中布局键和位图的一种方式。由于大多数位图索引的商业实现是在产品已经包含 B-tree 的实现之后出现的，因此这些产品利用现有的 B-tree 软件是很自然的。对于新的开发和实验或研究代码，不需要将位图索引与 B 树耦合。例如，在一个实现本章后面讨论的许多位图索引方法的研究程序中，键和位图在二进制文件中被组织为简单的数组。发现这种安排比在 B 树中实现位图索引或作为 DBMS 之上的层更有效。

基本位图索引使用索引属性的每个不同值作为键，并生成一个位图，其中包含与每个键的数据集中记录数一样多的位。让属性基数是数据集中存在的不同值的数量。对于“性别”、“每月销售的汽车类型”或“空客和波音生产的飞机模型”等低基数属性，基本位图索引的大小相对较小。然而，对于诸如“超新星爆炸中的温度值”之类的高基数属性，索引大小可能太大而无法实际使用。在文献中，减少位图索引大小的基本策略有三种：（1）使用更复杂的位图编码方法来减少位图的数量或提高查询效率，（2）压缩每个单独的位图，以及（3）使用分箱或其他映射策略以减少键的数量。在剩下的讨论中，我们将这三种策略简称为编码、压缩和分箱。

位图索引设计

基础位图索引

如上图，其中每一行（每个特征）都是一个位图，指示哪些动物具有该特征。虽然这是一个相当简单的概念，但相等编码可以非常强大。因为它让我们可以将一切都表示为布尔关系（即海牛有翅膀：是/否），我们可以对数据执行各种按位运算。

图下方显示了我们如何通过对 Invertebrate 和 Breathes Air 位图执行逻辑 AND 来找到所有呼吸空气的无脊椎动物。根据我们的样本数据，我们可以看到香蕉蛞蝓、花园蜗牛和轮虫都具有这两个特征。

这种基本位图索引也称为相等编码位图索引，因为每个位图都只是属性值是否等于键。此策略对于等值查询最有效。

等值编码

再来思考一个场景，添加一个名为Captivity的特征，表示当前被圈养的样本总数，并且我们想要执行这些值的过滤查询。

基于等值编码，创建如下位图：

这个方法是可以的，但是有限制。首先，高基数情况下并不是很有效，需要创建大量的位图来代表所有可能的值。其次，如果你想通过范围查询过滤，需要对应范围内每个可能的值都执行or逻辑。例如，这里想知道captivity<100的动物，需要 captivity=99 OR captivity=98 OR captivity=97 OR...

分箱策略

另一种方法不是将每个可能的值都表示为唯一的位图，而是创建Captivity范围桶。这种情况下如下图：

binning 的基本思想是为一个 bin 而不是每个不同的属性值构建一个位图。这种策略将位图的数量与属性基数分离，并允许构建一个规定大小的位图索引，无论属性基数有多大。这种方法的一个明显优势是它允许控制索引大小。但是，如果只使用索引，它也会在答案中引入一些不确定性。为了生成准确的答案，可能需要检查原始数据记录（候选）以验证是否满足用户指定的条件。读取基础数据以验证查询条件的过程称为候选检查。

有许多策略可以最大限度地减少候选检查所需的时间。专家考虑了为给定的一组相等查询和范围查询找到最佳分箱的问题。他们的方法基于动态规划。由于动态规划所需的时间随问题大小呈二次方增长，因此这些方法仅对具有相对较小属性基数的属性或具有相对较小的已知查询集有效。也有人考虑了优化评估多维范围查询的顺序问题，关键思想是在位图上使用更多操作来减少检查的候选数量。这样通常会减少总查询响应时间。这种方法的进一步改进是考虑影响候选检查所需的实际时间的属性分布和其他因素。

为了在候选检查期间最小化磁盘页面访问次数，有必要对属性值进行聚类。一种常用的聚类（数据布局）技术称为垂直分区或称为投影索引。一般来说，垂直数据布局对于搜索更有效，而水平组织（在 DBMS 中常用）对于更新更有效。为了让候选者检查更有效率，我们推荐垂直数据组织。

范围编码

等值编码和分箱策略都能解决问题，但是对于高基数且不接受丢失信息的情况，我们需要用另一种表示非布尔值的方法。即不需要编写非常大和繁琐的OR操作的情况下对值范围执行查询。这就是范围编码位图。

与相等编码类似，需要设置特定值的位，此外，还要为每个大于实际值的值设置一个位。例如，圈养的考拉熊有14只，在位图14，15，16等设置该位。位图不代表具有特定数量，二十代表数量达到并包括该数量。

这种编码方法可以执行之前所做的那些范围查询，而不需要OR对许多不同的位图操作，从一个或两个位图中就可以得到我们想要的。例如，想知道哪些动物的圈养标本少于 15 个，我们只需拉出 14 位图就完成了。如果我们想知道哪些动物有超过 15 个被圈养的标本，拉取表示最大计数的位图（在我们的例子中是 956 位图），然后减去 15 位图。

这些操作比我们以前的方法更简单，也更有效。我们已经解决了将OR数十个位图组合在一起以找到我们的范围的问题，并且不会像在分桶方法中那样丢失任何信息。但是我们仍然有几个问题使这种方法不太理想。首先，我们仍然必须保留一个位图来表示每个特定的值计数。最重要的是，我们增加了复杂性和开销，不仅要为我们感兴趣的值设置一些值，而且还要为每个大于该值的值设置一些值。这很可能会在写入繁重的用例中引入性能问题。

位切片

等值编码

理想情况下，我们想要的是具有范围编码位图的功能和相等编码的效率。接下来，我们将讨论位切片索引，看看它如何帮助我们实现我们想要的。

当基数变得非常高时，我们需要维护得位图数量会变得令人望而却步。位切片索引让我们以更有效地方式来表示这些相同的值。

将值分解为三个以10为底得组件，第一列表示值003，即圈养海牛得数量。组件0的值是003中得3，组件1和组件2的值是003中的0，在对应值中设置位。base-10索引中的每个组件需要10个位图来表示所有可能的值，因此需要表示范围从0~956的值时，只需要3x10=30个位图。这样做大大减少了位图的数量。我们基本上找到了一种方法来提高平等编码策略的效率。

范围编码

将位切片索引与范围编码结合，情况如下：

观察上图，每个组件中9对应的位始终为1，因此，不需要存储最高值。对于base-10、范围编码、位切片索引，只需要9个位图来表示一个组件。除此之外，还需要存储一个名为“not null” 的位图，指示是否为该列设置了值。

所以对于3分量值，需要（3*9+1）=28个位图来表示0~999范围内的任何值。现在我们有一种非常有效的方式来存储值，受益于范围编码，因此我们可以执行过滤范围的查询。

二进制-范围编码

如果我们不是将我们的Captivity值表示为以10 为底的分量，而是使用以2 为底的分量，那么我们最终会得到一组范围编码的位切片索引，如下所示：

第一列位表示以 2 为底的值000000011，即圈养海牛的数量（以 10 为底的 3）。由于组件 0 和组件 1 000000011都是1，我们在组件 0 第 1 行和组件 1 第 1 行中设置一个位。由于的其余组件000000011都是0，我们在第 0 行中为组件 2 到 9 设置一个位，并且因为这些是范围编码的，在每个大于 0 的值中设置一个位。对于以 2 为底的组件，这意味着我们还在第 1 行中为组件 2 到 9 设置了位。

就像我们之前看到的基于 10 表示的位图 9 一样，位图 1 始终是 1，因此我们不需要存储它。这给我们留下了这个：

通过这种编码，我们可以仅用 10 个位图来表示样本值的范围！另外，请注意，base-2、范围编码、位切片索引是整数值的二进制表示的倒数。这告诉我们的是，我们可以仅使用 (n + 1) 个位图（其中附加位图是“非空”位图）来表示具有基数 n 的任何值范围。这意味着我们可以对大整数值执行范围查询，而无需存储不合理数量的位图。

多分量编码

二进制编码的优点是它需要的位图比间隔编码少得多。但是，要做范围查询，使用区间编码的人只需访问两个位图，而使用二进制编码的人通常必须访问所有位图。

许多学者提出了在空间和时间要求之间找到平衡的策略。提出的一种称为多分量编码的方法可以被认为是二进制编码的一种推广。在二进制编码中，每个位图代表属性值的一个二进制位；多分量编码以类似地方式切分值，其中每个分量可能具有不同的大小。考虑一个整数属性，其值范围为 0 到 c-1。设 b1 和 b2 是两个分量 c1 和 c2 的大小，其中 b1b2>=c。任何值 v 都可以表示为 v = c1b2+c2，其中 c1 = v / b2 和 c2 = v % b2，其中“/”表示整数除法，“%”表示取模运算。可以使用一种简单的位图编码方法分别对 c1 和 c2 的值进行编码。接下来，我们举一个更具体的例子来说明多分量编码。

上图说明了基数 c=1000 的属性的 2 分量编码位图索引。这两个组件的基本尺寸为 b1=25 和 b2=40。假设属性值在 [0; 999]。一个属性值 v 被分解为两个分量，c1 = v / 40 和 c2 = v % 40。分量 c1 可以被视为 0 到 24 范围内的整数属性；组件 c2 可以被视为 0 到 39 范围内的整数属性。可以构建两个位图索引，每个组件一个，例如，具有相等编码的 c1 和具有范围编码的 c2。如果两个分量都使用范围编码，则分量 1 使用 24 个位图，分量 2 使用 39 个位图。在这种情况下，2 分量编码使用 63 个位图，比二进制编码使用的 10 个位图多。要使用 2 分量索引做相同的查询“v < 105”，该查询被有效地转换为“c1<2 OR (c1=2 AND c2<25)”。评估这个表达式需要三个位图，分别代表“c1<=1”、“c1<=2”和“c2<=24”。相反，使用二进制编码的位图索引来评估相同的查询，需要所有 10 个位图。

使用更多组件可以减少位图的数量，从而减少总索引大小。然而，使用更多的组件也会增加为了回答查询而访问的位图数量，从而增加查询响应时间。显然，在索引大小和查询响应时间之间存在权衡。在不考虑压缩的情况下，Chan & Ioannidis (1999) 分析了这种时空权衡。他们建议权衡曲线的拐点在 2 个分量处。他们进一步建议这两个组件应该具有几乎相同的基本大小以减小索引大小。

压缩

方法

压缩是减小位图索引大小的第三种策略。由于位图索引的每个位图可以与其他位图分开使用，因此通常对每个单独的位图应用压缩。压缩是一个经过充分研究的主题，高效的压缩软件包广泛可用。尽管这些通用压缩方法在减小位图大小方面是有效的，但压缩位图上的查询处理操作通常比未压缩位图上的要慢。这促使许多研究人员提高压缩位图索引的效率。两种最著名的压缩方法是字节对齐位图编码 (BBC) 和字对齐混合 (WAH) 编码。使用 BBC 压缩的位图比使用最佳通用压缩方法压缩的位图稍大。然而，对 BBC 压缩位图的操作通常更快。显然，有一个值得的时空权衡。 WAH 压缩使这种时空权衡更进了一步。更具体地说，WAH 压缩位图比 BBC 压缩位图大，但 WAH 压缩位图的操作比 BBC 压缩位图快得多。因此，WAH 压缩位图索引可以更快地回答查询。

WAH 位图压缩基于游程长度编码，其中连续的相同位用其位值（0 或 1）和计数（游程长度）表示。在 WAH 中，字有两种情况, 原文字(literal word)和压缩字(fill word)。两种字通过32个bit中的第一个bit来区分, 第一个bit为0是原文字, 为1则是压缩字。如果是压缩字, 那么剩余31个bit中，第2bit表示压缩的值是0还是1。剩余30个bit表示有多少字的重复的值, 称为run number。比如第一个bit是1, 第2个bit是1, 剩下30个bit是数值5, 则表示有连续的5*31个1。WAH 的一个关键思想是定义fill word 和literal word，以便它们可以存储以word（现代计算机硬件的最小操作单元）的形式存储。

在理论分析中，使用 WAH 压缩索引的一维范围查询的查询响应时间显示出随着命中数线性增长。这种时间复杂度对于任何搜索算法都是最佳的。各种众所周知的索引方法，例如 B+-trees 和 B-trees，都具有相同的最佳缩放属性。但是，压缩位图索引具有独特的优势，即它们可以轻松组合以回答多维即席范围查询，而 B+-tree 或 B-tree 的组合效率几乎不高。

一般来说，查询响应时间可以分为I/O时间和CPU时间。由于 WAH 压缩位图的大小比 BBC 压缩位图大，我们预计 WAH 需要更多 I/O 时间来读取压缩位图。对于许多数据库操作，CPU 时间与 I/O 时间相比可以忽略不计。事实证明，在使用压缩位图索引回答查询时情况并非如此。在一项性能实验中，学者将 WAH 压缩索引与 BBC 压缩索引的两种独立实现进行了比较，结果表明，使用 WAH 压缩位图索引的总查询响应时间比使用 BBC 压缩位图的要小，即使在一个相对较慢的磁盘系统上，从磁盘读取文件只能维持 5 MB/s。在速度更快的磁盘系统上，WAH 压缩位图索引的性能优势更加明显。使用 WAH 可能比使用 BBC 快 10 倍。

位图索引拐点

除非使用二进制编码，否则压缩位图索引很重要。为了构建有效的压缩位图索引，要考虑的三个主要因素是：编码，分箱数，以及分箱策略。在下文中，我们提出了选择这三个参数的经验法则。

最佳位图编码技术取决于评估的查询类型。范围编码是范围查询的最佳位图编码技术，但是，范围编码可能并不总是适用于高基数属性或大量分箱。正如我们将在下一节中展示的那样，范围编码的位图索引不像等式编码的位图索引那样压缩。

选择 bin 数量的一般规则如下： bin 越多，候选检查的工作量就越少。随着 bin 数量的增加，每个 bin 的候选者数量会减少。假设基础数据服从均匀随机分布。对于 8KB 的典型页面大小，使用投影索引，一个页面可以容纳 2048 个 4 字节字。如果在候选检查期间访问了千分之一的word，则很可能会触及包含属性值的每一页。因此，我们建议使用 1000 个或更多分箱。

对于相等编码有一个额外的权衡，即使用更多的 bin 也可能会增加索引扫描的成本。对于范围编码，索引扫描的成本不受 bin 数量的显着影响，因为需要访问不超过两个位图来评估范围查询。如果没有压缩，人们显然会倾向于范围编码。然而，随着压缩，相对强度并不那么明显。使用 WAH 压缩等值编码索引，索引扫描的成本与命中数成正比，与所涉及的位图数量无关。因为等值编码索引更容易压缩，这使 WAH 压缩的等值编码索引成为首选。

分箱策略对候选检查有影响。最简单的一种分箱称为等宽分箱，将索引属性的域划分为大小相等的箱。因此，每个 bin 可能有不同数量的条目。另一方面，等深度分箱在分箱之间平均分配条目数。这种技术比等宽分箱更好，但构建成本更高，因为通常必须先扫描数据以生成精确的直方图，然后再开始分箱。

降低构建一组等深 bin 的成本的一种方法是使用采样直方图而不是精确直方图。另一种方法是首先构建一个等宽分箱索引，其中包含比期望更多的分箱，然后将相邻分箱组合形成近似等深分箱。但是，第二种方法可能由于异常值不会产生平衡良好的 bin。采样直方图的方法在检测异常值方面通常更可靠，并且通常会产生平衡良好的 bin。

空间复杂性

分析压缩位图索引的大小，这里主要集中在 WAH 压缩方法上，因为 BBC 压缩在 (Johnson, 1999) 中得到了广泛的研究。我们给出了最坏情况大小的上限，并为各种应用数据集提供了压缩位图索引的实验研究。

索引大小：最坏情况的行为

在上一节中，我们将 WAH 运行定义为原文字(literal word)和压缩字(fill word)。为了使讨论更具体，让我们假设一个机器字是 32 位。在这种情况下，WAH 尾部正好包含来自输入位图的 31 位，而 WAH 填充包含 31 位的倍数，它们都是相同的（0 或 1）。因为已知位图索引对低基数属性有效，所以我们进一步将讨论仅限于高基数属性，例如 c > 100。在等值编码的位图索引中，有 c 个键（属性的不同值）因此 c 位图。我们不知道每个位图中有多少位被设置为 1。但是，我们知道为 1 的总位数正好是 N（数据集中的行数）。在最坏的情况下，位图中有 (N+c) 个 WAH 运行，其中 N 是指尾字的最大数量（每个包含一个设置为 1 的位），c 是指在结尾处的最大运行数每个不以尾字结尾的位图。

每个 WAH 运行由两个机器字编码。因此，我们总共需要 2(N+c) 个词来表示位图。假设每个键由一个单词和一个附加单词编码以将键与位图相关联，则总索引大小为 2N+4c 个单词。在大多数情况下，属性基数 c 远小于 N。在这些情况下，WAH 压缩的等值编码位图索引大小最多为 2N 个字。使用分箱，可以使用数千个 bin，最大索引大小仍不超过 2N。由于观察到许多 B 树的商业实现使用 3N 到 4N 个字，因此压缩位图索引的最大大小相对适中。正如将针对实际应用程序数据展示的那样，WAH 压缩索引通常远小于预测的最坏情况大小。

对于 WAH 压缩，在最坏的情况下，范围编码位图索引中大约 90% 的位图将不可压缩（Wu 等人，2006 年）。除非可以容忍非常大的索引，或者事先知道压缩会有效，否则我们通常建议对范围编码位图索引使用不超过 100 个 bin。这保证了位图索引的大小在最坏的情况下是 B 树的大小。

实际应用

我们现在将通过实验分析各种应用程序数据集的压缩位图索引的大小。

燃烧数据集

燃烧数据集来自于 TeraScale High-Fidelity Simulation of Turbulent Combustion withDetailed Chemistry（Tera Scale Combustion，2005 年）中对湍流氢-空气混合物的自动点火的模拟。该数据集包含 2400 万条记录，每条记录有 16 个属性。对于这个数据集，我们使用不同数量的等深 bin 构建了等值编码和范围编码的位图索引。下图显示了每个属性的压缩位图索引的平均大小。我们可以看到，具有 1000 个 bin 的等值编码位图索引和具有 100 个 bin 的范围编码位图索引与基本数据的大小大致相同。请注意，具有 100 个 bin 的未压缩位图索引的大小约为基础数据的 3 倍。使用 1000 个 bin，未压缩位图索引的大小大约是 30 倍。这表明 WAH 压缩算法在该数据集上运行良好。

高能物理数据集

第二个数据集来自斯坦福直线加速器中心的高能物理实验。它由具有 10 个属性的 760 万条记录组成。下图显示了压缩位图索引的大小。我们注意到具有 100 个 bin 的范围编码位图索引的大小大约是基础数据的两倍。具有 1000 个 bin 的等式编码位图索引比基本数据小约 30%。

通常，这些高能物理实验的记录彼此不相关。因此，游程编码通常很难有效。这就是为什么范围编码的索引大小与之前的数据集相比相对较大的原因。然而，等值编码对于这个物理数据集的压缩非常好。总体而言，我们看到实际位图索引大小远小于基础数据大小，并且小于 B 树的典型商业实现的大小（通常是基础数据大小的三到四倍）。

时间复杂度

等式编码被证明是最节省空间的方法。另一方面，范围编码是我们在实验中使用的单边范围查询最省时的方法。

分析表明，使用 WAH 压缩的基本位图索引（没有分箱的等值编码）回答一维范围查询的最坏情况查询响应时间是命中数的线性函数。分析还表明，最坏情况下的行为是遵循均匀随机分布的属性。

接下来将提供更多时间测量来比较相等编码和范围编码位图索引的查询响应时间。所有索引都使用 WAH 压缩进行压缩。由于这两个数据集的结果相似，我们仅报告基于更大且更具挑战性的燃烧数据集的测量结果。我们使用投影指数作为所有比较的基线。我们注意到这是一个很好的基线，因为投影指数以优于许多多维指数而闻名。

通常，我们看到位图索引的查询处理时间随着查询变得更具选择性而减少。另一方面，投影索引的查询处理时间随着选择性的变化而保持不变。对于所有查询维度，具有 100 个 bin 的范围编码位图索引显示出最佳性能特征，但有时会以更大的索引为代价。如果存储空间是一个限制因素，最好选择具有 1000 个 bin 的等式编码位图索引。如下图，等式编码位图索引的性能与范围编码位图索引的性能没有显著差异。

总结

对不同的位图编码方法，我们做如下简要总结:

	总Bitmap个数	查询获取Bitmap 个数	是否精确	查询复杂度
等值编码	=N（属性值个数）	<=N/2	是	高
分箱策略	与基数无关，可自由控制	取决于分箱个数	否	取决于分箱策略和候选检查如何平衡
范围编码	=N（属性值个数）	1	是	低
区间编码	=N（属性值个数）	2	是	低
位切片-等值编码	10*log(10)N	10*log(10)N	是	高
位切片-范围编码	9*(log(10)N)+1	9*(log(10)N)+1	是	低
位切片-二进制范围编码	log(2)N+1	log(2)N+1	是	低

商业产品的主要特性

由于生产和维护强大的商业软件系统涉及大量工作，因此只有最有效和经过验证的索引技术才能进入商业 DBMS。在本节中，我们将简要回顾各种知名商业产品目前使用的关键位图索引技术。这并不意味着是一个详尽的调查。我们的主要兴趣是了解缺少哪种位图索引技术以及哪种技术可能会对商业产品产生影响。

第一个使用位图索引名称的商业产品是 Model 204。O'Neil 在 (O'Neil, 1987) 中发表了对索引方法的描述。Model 204 实现了基本的位图索引。它没有分箱或压缩。目前，Model 204 由美国计算机公司销售。从 7.3 版开始，ORACLE 在其旗舰产品中具有一个压缩位图索引版本。他们实施了一种专有的压缩方法。根据观察到的性能特征，它似乎使用相等编码而不进行分箱。

Sybase IQ 实现了位切片索引。Sybase IQ 支持未合并、二进制编码、未压缩的位图索引。此外，它还具有低基数属性的基本位图索引。 IBM DB2 实现了一种二进制编码位图索引的变体，称为编码向量索引。 IBM Informix 产品还包含一些版本的位图索引，用于涉及一个或多个表的查询。这些索引是专门为加速连接操作而设计的，通常被称为连接索引。 InterSystems Corp 的 Cache 从 5.0 版开始也支持位图索引。

达梦数据库的位图索引采用了二进制范围编码的方案，支持对低基数的列创建位图索引, 其建立过程是，首先构造二进制等值编码位图索引，然后采用逐级位图向量相加构造二进制范围编码位图索引。在查询阶段采用了流水线方式读取位图块，实现了IO异步化。另外在数据仓库中，也支持针对两个或者多个表连接的位图索引，称为位图连接索引。

Postgresql在8.3 提供了 on disk bitmap索引，后续移除了，但是Postgres的延展数据库Greenplum DB中被保留了下来。pg支持 in memory bitmap索引，在bitmap scan index 时，通过在内存中建立基础位图的方式，将回表过程中对标访问随机性IO的转换为顺行性行为，从而减少查询过程中IO的消耗。

尽管我们没有关于大多数这些商业产品的技术细节，但通常很清楚它们倾向于使用基本位图索引或位切片索引。没有使用分箱和多分量编码等策略，部分原因是没有稳健的策略来选择适合不同应用的分箱数量或组件数量等参数。