Bitmap Indexing(位图索引)

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

为证明位图索引的优势,下面假设了一张数据表 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 进行位运算高效的实现。
  • 适合多维分析的场景,即 OLTP 场景,比如一张表有上百列这样。

缺点:

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

参考资料

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇