B树索引与位图索引

简说

在理解索引时,可以想象一本书,其中书的内容就相当于表里的数据,而书前面的目录就相当于该表的索引。
同时,通常情况下,索引所占用的磁盘空间要比表要小得多,其主要作用是为了加快对数据的搜索速度,也可以用来保证数据的唯一性。
普遍运用在数据库和文件系统。

索引作为一种可选的数据结构,你可以选择为某个表里的创建索引,也可以不创建。这是因为一旦创建了索引,就意味着数据库对表进行DML(包括INSERT、UPDATE、DELETE)时,必须处理额外的工作量(也就是对索引结构的维护)以及存储方面的开销。所以创建索引时,需要考虑创建索引所带来的查询性能方面的提高,与引起的额外的开销相比,是否值得。

从物理上说,索引通常可以分为:常规B树索引、位图(bitmap)索引、翻转(reverse)索引等等…

B树索引

即二叉搜索树,也是一种树状数据结构;
大量的数据库(如MySQL、oracle、PostgreSQL等)都在使用B树。B树索引本质上是对索引字段进行排序,然后通过类似二分查找的方法进行快速查找,即它要求索引的字段是可排序的,一般而言,可排序的是一维字段,比如时间、身份证号码 手机号码、QQ等等。

数据结构

特点

  1. 索引不存储null值,单一索引不存储null值,复合索引不存储全为null的值;
  2. 不适合键值较少的列(重复数据较多的列);比如时间、身份证、手机、QQ等
  3. 前导模糊查询不能利用索引(like '%XX’或者like ‘%XX%’)

位图索引

我们知道计算机所有信息最终都是通过“位bit”来运算的,二进制位运算在计算机中非常高效。而位图索引也是用0或1来处理索引进程,故得名位图索引。
位图索引主要针对大量相同值的列而创建的,索引块的一个索引行中存储键值、起止RowId及此键值的位图,根据位图信息可以得知每一条记录的ROWID。它为列的每个键值建立位图,位图中的每一位可能对应多个列,位图中位的值为1表示此行的值为对应的键值。

特点

  1. 可以存储null值;
  2. 不适合键值较多的列(重复数据较少的列),适合只有几个固定值的列;如性别、婚姻状况、行政区等等
  3. 相对于B*Tree索引,占用的空间非常小,创建和使用非常快;
  4. 适合静态数据,而不适合索引频繁更新的列;
  5. 使用count、and、or或in查询时,直接用索引的位图进行或运算,快速得出结果行数据。