Bitmap Indexing(位图索引)

Bitmap Indexing 顾名思义,使用位图实现索引。广泛应用于大规模数据查询,OLAP 数据库。

为证明位图索引的优势,下面假设了一张数据表 employee。ID 为员工 ID,自增主键,唯一。Job 只含有 A,B 和 C 三种类型。Sex 则只有男和女两种类型。

IDJobSex
1A
2B
3A
4C

因我们需要频繁的对 employee 表进行分析,故在 Job 和 Sex 列上均建立 bitmap 索引。ID 因其为自增序列,本身就有索引,不需要额外创建。

Bitmap 存储格式

这里我不具体讲解 bitmap 索引的规则,直接给例子,其实一看就能懂。

对 Job 建立 bitmap 索引时,会创建“三个索引“,存储的格式如下:

JobBitmap
A1010
JobBitmap
B0100
JobBitmap
C0001

这也看到为每一种 Job 类型都建立了一个 bitmap。Bitmap 中 1 代表有,0 代表没。Job = A 的 bitmap 中 1010 代表 ID = 1ID = 3 的 Job 为 A。

同理,Sex 建立 bitmap 后的存储格式为:

SexBitmap
0110
SexBitmap
1001

Bitmap 优势

假设我们执行如下 SQL 语句,查询所有 Job = ASex = 女 的员工。

SELECT *
    FROM employee
    WHERE Job = "A" and Sex = "女";

这时数据库可以采用位运算一步到位:

索引Bitmap
Job = “A”1010
Sex = “女”1001
执行 AND 位运算&
结果1000

结果是 1000 ,也就是 ID = 1 的员工符合该要求。

如果采用传统的 B+ 树,那么就会很复杂。首先你要过滤出所有 Job = “A” 的用户,然后再过滤 Sex = “女” 的用户。考虑到 B+ 树复杂的结构,整体的开销很高。

如果这张表有 100 列,然后我使用 20 列作为查询条件,那么使用 B+ 树的效率会十分低下,甚至可能不如使用顺序遍历来得快。而 Bitmap 索引使用位运算,就能轻轻松松处理这种事情。

总结

最后总结下 bitmap 索引的优点和缺点。

优点:

  • 适用于重复度高的列(low cardinality),比如上面的 Job 和 Sex 列,只有固定的几种值。
  • 适合执行逻辑运算,如 COUNT,AND,OR 等等,这些可以对 bitmap 进行位运算高效的实现。
  • 适合多维分析的场景,即 OLAP 场景,比如一张表有上百列这样。

缺点:

  • 不合适用在重复度低的列,比如身份证号码。在重复度低的列上建立 bitmap 索引,会耗费大量的空间。
  • 如果在重复度过高的列,如性别,可以建立 bitmap 索引,但不建议单独作为查询条件使用,建议与其他条件共同过滤(将来再补充)。
  • 不适合用在需要频繁更新的列。因为一个 bitmap 会涉及到很多行,如果同时修改,涉及到的锁开销很大(将来再补充)。

参考资料

原创文章,作者:Smith,如若转载,请注明出处:https://www.inlighting.org/archives/what-is-bitmap-indexing

打赏 微信扫一扫 微信扫一扫
SmithSmith
上一篇 2022年2月2日
下一篇 2023年10月1日

相关推荐

  • 2021 CMU 15-445 实验笔记

    陆陆续续终于把 CMU 15-445 刷完了(中间插了个 TinyKV),这也算是自己数据库的启蒙之课。编码耗时共计 98 小时 43 分钟。 我个人给整个项目难度评级:Proje…

    2022年2月2日
    11.2K198
  • 数据库并发控制原理

    数据库的事务 transaction (txn)很有搞头,特此特别记下这篇笔记,方便自己的回顾,如有错误,请指正。 Transaction 数据库事务以 Begin() 开始,以 …

    2022年1月26日
    4.4K5
  • Extendible Hash Table 算法实现

    Extendible Hash Table 属于动态哈希的一种,网上有很多关于它的介绍,但是真的在实现它的时候,或多或少有着很多问题。网上很多教程光讲怎么扩容,不讲收缩,而且网上很…

    2021年11月4日
    5.6K41

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

评论列表(2条)

  • 油屋
    油屋 2022年8月3日 下午3:09

    优点中的最后一条的“OLTP”应该打错了吧,是“OLAP”吧?,因为OLAP型数据库的更新较少,OLTP型数据库的更新操作较多。