数据库之索引模块

索引模块除了是数据库最重要的模块之一，也是面试中最经常被问到的，关于索引模块常见问题如下：

• 为什么要使用索引
• 什么样的信息能成为索引
• 索引的数据结构
• 密集索引和稀疏索引的区别

为什么要使用索引：

数据库中最小存储单位通常是块或者页，每个块里面都会包含多行数据。而我们在查询一些没有使用索引的数据时，通常都需要进行全表扫描，也就是说需要加载所有的块，然后逐个遍历这些块直到查找出我们需要查找的数据。可想而知这种查询方式在数据量比较大的时候效率是比较慢的，所以我们很多时候都需要避免全表扫描。不过数据库的设计者早已考虑到这一点所以引入了更高效的查询机制，即使用索引。索引的灵感来自于字典，我们都知道字典会记录一些关键信息，例如偏旁部首拼音等，我们通过这些关键信息就可以快速查找到那个字所在的页面。而索引也是如此，数据库能够通过索引记录的关键信息迅速定位目标数据在哪个位置上，就可以避免全表扫描的发生。所以使用索引的目的就是为了让查询更高效。

什么样的信息能成为索引：

主键id，唯一的字段，以及频繁被作为查询条件的字段，若同时多个字段频繁作为查询条件时可以对这几个字段建立组合索引

索引的数据结构：

通常是B+树、Hash以及少数数据库支持的BitMap

二叉查找树

接下来简单的说下索引的数据结构，我们都知道索引最常用的数据结构是B+树，在介绍什么是B+树之前，首先得了解二叉查找树和B树，并简单说明一下为什么没有采用二叉树或B树作为索引的数据结构。

现在我们已经知道给字段建立索引的目的是为了帮助我们快速定位到目标数据所在的位置，若让我们自己去设计索引的话，对于快速查找这个需求可能第一时间就会想到二叉查找树之类的树形数据结构。所以本小节先介绍二叉查找树，并一步一步地了解为何在众多的树形结构中会采用B+树作为索引的数据结构。

二叉查找树是一种常用的树形数据结构，二叉查找树的每个节点最多只有左右两个子节点，分别成为左子树和右子树，通常左子树的元素小于它的父节点，而右子树则大于它的父节点。位于最顶端的节点通常称为根节点，二叉查找树的查找算法是二分查找。下图是一颗平衡二叉树，所谓平衡二叉树就是末端左右两个节点的高度相差不超过1：

二叉查找树由于同一级最多只能有两个节点，且对磁盘io没有优化，因为每次IO读取都只能读两个节点，所以并不能达到较理想的查询速度，不能作为索引的数据结构。

B树

由于二叉树每次只能读取两个节点对磁盘IO没有优化，并且只有左右两个查找路径，树的深度就会随着日益增加的数据量而递增，所以这时候就需要寻找一个每个层级可以有多个节点的多路树形结构，而B树就符合该需求，B树又称为多路平衡查找树，其大致结构如下图：

同一层有m个节点通常称为m阶，一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

1. 根节点至少有两个子节点
2. 树中每个节点最多含有m个子节点（m >= 2）
3. 除根节点和叶子节点外，其他每个节点至少有ceil(m/2)个子节点
4. 所有的叶子节点都位于同一层
5. 假设每个非终端节点中包含有n个关键字信息，其中：
   • Ki (i=1...n)为关键字，且关键字按顺序升序排序 K(i-1) < Ki
   • 关键字的个数 n 必须满足：[ceil(m / 2) - 1] <=n <= m - 1，即任意节点的关键字个数上限比它的子树上限少一个，且对于非叶子节点来说任意节点的关键字个数比它的指向孩子的指针个数少一个
   • 非叶子节点的指针：P[1], P[2], ..., p[M]; 其中 P[1] 指向关键字小于 K[1] 的子树①，P[M] 指向关键大于 K[M - 1] 的子树②，其他 P[i] 指向关键字属于 (K[i - 1], K[i]) 的子树③

①：某节点最左子节点里关键字的值均小于该节点最左关键字的值
②：某节点最右子节点里关键字的值均大于该节点里所有关键字的值
③：某节点除左右以外所有子节点里关键字的值大小，均位于离该子节点指针最近的两个关键字的值之间

B+树

B 树虽然已经达到可以用作于索引数据结构的标准，但是还有更好的替代品，那就是B+树，从名字也可以看出B+树相当于是B树的变体。其定义基本与B树相同，除了：

1. 非叶子节点的子树指针与关键字个数相同
2. 非叶子节点的子树指针 P[i]，指向关键字值[K[i], K[i + 1])的子树
3. 非叶子节点仅用来做索引，数据都保存在叶子节点中
4. 所有叶子节点均有一个链指针指向下一个叶子节点，叶子节点形成的链会按大小排序

B+树结构图：

B+树相比于B树及其他树形数据结构来说，更适合用来做存储索引，原因如下：

• B+ 树的磁盘读写代价更低，B+ 树由于非叶子节点只会存储索引，因此B+ 树的非叶子节点相对于B 树来说更小，如果把所有同一内部节点的关键字存储在同一盘块中，那么该盘块所能容纳的关键字数量也越多，一次性读入内存中的关键字也就越多，相对来说IO读写次数也就降低了
• B+ 树的查询效率更加稳定，因为具体数据存储在叶子节点中，所以无论查询任何数据都需要从根节点走到叶子节点，那么所有查询的长度也就相同，这样每个数据查询的效率就几乎是相同的
• B+ 树更有利于对数据库的扫描，B 树在提高了磁盘IO的同时并没有解决遍历元素效率低下的问题，而B+ 树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对数据库中频繁使用的范围查询来说B+ 树更高效

Hash以及BitMap

除了上一小节所介绍的B+ 树索引结构之外，还有一个常用的Hash索引结构。Hash稍微简单一些，就是对索引的key进行一次hash计算，然后就可以定位出数据存储的位置，所以在某些特定场景来说Hash索引要比B+ 树索引更高效。如图：

既然理论上来说Hash索引要比B+ 树索引更高效，但是为什么没有成为主流索引结构呢，这是因为Hash索引存在以下缺点：

• 因为hash的特性，所以仅仅能满足 “=”，“IN”，不能使用范围查询
• 无法被用来避免数据的排序操作
• 不能利用部分索引键查询，因为在使用组合索引的时候，Hash索引是将组合索引里的字段合并后再计算的hash值，而不是单独计算的hash值。所以不使用组合索引里全部字段去查询的话，Hash索引就无法被利用
• 不能避免表扫描，因为数据量大的时候就会有出现重复Hash较多的情况，那么就得拿出所有相同Hash值的数据来比较才能取到具体的数据，所以普遍来说数据量越大Hash索引的效率就越低
• 遇到大量Hash值相等的情况后性能并不一定就会比B+树索引高

BitMap：

除了B+ 树及Hash索引外，还有一种索引结构就是BitMap，即位图索引，但是仅有少量数据库支持，所以这里仅做简略提及。当表中的某个字段只有几种值的时候，例如存储性别信息的字段之类的，在这种字段使用BitMap索引就是最佳的选择。BitMap结构图如下：

但是BitMap有一个很大的缺陷就是锁的粒度会非常的大，在新增和更新数据时，与该数据在同一个位图的数据也会被锁住。

密集索引和稀疏索引的区别

密集索引和稀疏索引的区别：

• 密集索引文件中的每个搜索码值都对应一个索引值
• 稀疏索引文件只为索引码的某些值建立索引项
• 密集索引和稀疏索引的主要区别就是前者叶子节点保存完整的数据，而后者保存的是指向data的指针

密集索引和稀疏索引的区别图：

密集索引：叶子节点保存的不仅仅是键值，还保存了位于同一行数据里其他列的信息，由于密集索引决定了表的物理排列顺序，而一个表只能有一个物理排列顺序，所以一个表只能创建一个密集索引

稀疏索引：叶子节点仅保存了键位信息，以及该行数据的地址或主键。所以需要通过数据的地址或主键才能进一步定位到数据。

我们来看看具体到Mysql的主流存储引擎：

• MyISAM：不管是主键索引、唯一索引还是普通索引都属于稀疏索引，所以MyISAM只有稀疏索引，没有密集索引。并且MyISAM中索引与数据是分开存储的
• InnoDB：表只会有且只有一个密集索引，其他索引都是稀疏索引。并且InnoDB中索引与数据是存储在同一个文件中的
  • 若一个主键被定义，该主键则作为密集索引
  • 若没有主键被定义，该表的第一个唯一非空索引则作为密集索引
  • 若不满足以上条件，InnoDB内部会生成一个隐藏主键作为密集索引，这个隐藏的主键是一个6字节的自增列
  • 非主键索引存储相关键位和其他对应的主键值，包含两次查找

InnoDB与MyISAM引擎的检索流程对比：

索引额外问题之联合索引最左匹配原则的成因

假设我们对A、B两个字段建立联合索引：(A, B)，此时该联合索引的左边是A而右边是B，当执行where A = '' and B = '' 时会走这个(A, B)联合索引，where A = ''也会走(A, B)联合索引，但是where B = ''则不会走(A, B)联合索引。这就是所谓的最左匹配原则

在最左匹配原则中，有如下说明：

1. 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
2. =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式

我们来做个实验，验证下最左匹配原则。建表sql如下，该表中有一个联合索引：

CREATE TABLE `student` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(20) NOT NULL,
  `age` int(11) NOT NULL,
  `sex` varchar(20) NOT NULL,
  `address` varchar(100) NOT NULL,
  `cid` int(11) NOT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_name_age` (`name`,`age`)
) ENGINE=InnoDB AUTO_INCREMENT=19 DEFAULT CHARSET=utf8;

当where条件存在name字段时，会使用索引查询：

当where条件不存在name字段时，则不会使用索引查询：

当where条件存在name字段时，即便是乱序也会使用索引查询，因为MySQL的执行优化器会自动调整顺序以满足使用索引的条件：

参考文章：

• Mysql中联合索引的最左匹配原则
• Mysql联合索引最左匹配原则

现在我们来回答一下最左匹配原则的成因：

MySQL创建联合索引时，是先对联合索引中最左字段的数据进行排序，在最左字段排序的基础上，再对后一个字段的数据进行排序，类似于order by 字段1，order by 字段2 这样的一种排序规则。所以联合索引中最左字段是绝对有序的，而后一个字段则是无序的了，因此使用除最左字段以外的字段进行条件查询是利用不到索引的，这就是最左匹配原则的成因

索引额外问题之索引是建立越多越好吗

答案是否定的，所谓物极必反：

• 数据量小的表不需要建立索引，建立索引会增加额外的索引维护开销
• 数据变更需要维护索引，因此更多的索引意味着更多的维护成本
• 更多的索引也意味着需要更多的存储空间