InnoDB 索引原理

InnoDB索引原理

索引能够提高访问的速率

B+树索引（最为常用和最为有效）、全文索引、哈希索引。

数据库中的B+树索引可以分为聚集索引和辅助索引，但是不管是聚集还是辅助的索引，其内部都是B+树，是高度平衡的，叶子结点存放着所有的数据。聚集索引和辅助索引最大对的不同就是，叶子结点存放的是否是一整行的信息。

B+树

B+树是为磁盘或者其它直接存取辅助设备设计的一种平衡树，在B+树中，所有纪录结点都是按照键值的大小顺序存放在同一层的叶子结点上，由各叶子结点指针进行连接。

举个例子，上面为index page、下面为leaf page，如下图：

插入

插入分为三种情况，但都必须保证插入后叶子结点中的纪录依然排序。

还是根据上面的那副图作为例子，往里面加入28，我们索引到具体的位置，在25-30中间，我们发现当前的情况为叶子结点不为空，父亲结点也不为空，查询表格发现我们可以直接将纪录插入到叶子结点中，所以如下：

接着往里面插入70，我们发现在叶子结点已经满了，但是父亲结点并没有满，所以需要将叶子结点进行分裂，因为70在最右边，所以将中间的数字60向上移动，放到原来父亲结点中75的位置，而75则向后移动一位，得到如下图：

注意：因为图片大小关系，图中的叶子结点中的双链表没有显示，但是实际是应该显示的。

最后插入95，根据图片索引到其插入位置为叶子结点中90的后面，此时我们发现叶子结点和父亲结点都已经满了，于是它们两个都需要进行分裂，首先将叶子结点中的中间位置85向上移动，并且同时分裂成两个叶子结点（左边比85小，右边比85大），此时父亲结点也放不下85，于是将中间位置的60向上移动单独成为一个结点，左子结点中的值比60小，右子结点的值比60大，具体如下图：

旋转

上面的操作为了保持平衡而进行大量的拆分页操作，因为B+树主要用于磁盘，而拆分则意味着磁盘的操作，所以要在尽可能的情况下减少拆分的动作。B+树也提供了旋转的功能：在当前叶子结点满了，但是兄弟结点没有满的情况下，可以将部分结点移动到兄弟结点中，并且调整父亲结点。

比如在前面提到的加入70，其图可以为：

可以看到，采用旋转操作使得B+树减少了一次页的拆分动作，而且还保持了高度为2。

删除

B+树使用填充因子来控制树的删除变化，填充因子最小可设为50%，同样的，B+树的删除操作需要保证删除后叶子结点中的纪录依然排序，删除分为好几种情况，如下：

我们就继续在插入的树的基础上进行删除操作。删除70后，发现叶子结点和其父亲结点的值的个数并没有小于一半，所以不需要进行其它的操作。

接下来删除25，因为同样是删除表格中的第一种操作，所以直接删除即可，但是需要注意的是，其父亲结点仍然存在25，所以需要将最左边的28更新到父亲结点中即可，如图下：

接着删除60，我们发现删除60后，该叶子结点已经小于填充因子，因此这种情况属于表格中的第三种情况，则需要合并兄弟结点，因为剩余的数字小于75，所以要合并左边的兄弟结点，同时把根结点的60删除掉，合并它的两个子结点，如图下：

索引

数据库中的B+树索引可以分为聚集索引和辅助索引，但是不管是聚集索引还是辅助索引，其内部都是B+树的，即高度平衡的，叶子结点存放着所有的数据，它们不得不同点在于，叶子结点存放的是否是一整行信息。

聚集索引

InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放，而聚集索引就是按照每张表的主键构造一颗B+树，同时叶子结点存放的即为整张表的行纪录数据（聚集索引的叶子结点也称为数据页）。聚集索引的这个特性也决定了索引组织表中数据也是索引的一部分，和B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。

聚集索引的另外一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子结点的数据就是用户所要查询的数据。另外一个是范围查询，即如果要查找住主键某一个范围内的数据，通过叶子结点的上层中间结点就可以得到页的范围，之后直接读取数据页即可。

辅助索引

辅助索引，叶子结点并不包含行纪录的的全部数据，叶子结点除了包含键值以外，每个叶子结点中的索引行还包含了一个书签，该书签用来告诉InnoDB存储引擎哪里可以找到索引相对应的行数据，因为InnoDB存储引擎表是索引组织表，因此辅助索引的书签就是相应行数据的聚集索引键。也就是说当通过辅助索引查找数据时，InnoDB会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键。然后再通过主键索引找到一行完整的数据。

建索引的几大规则

1. 最左前缀匹配原则，数据库会一直向右匹配直到遇到范围查询就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的；
2. =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序；
3. 尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，所以最好别对这些字段创建索引；
4. 索引列不能参与计算，保持列“干净”，因为B+树中存的都是数据表中的字段值，但进行检索的时候，需要把所有元素都应用函数才能比较，显然成本太大；
5. 尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可；

索引优化

1. 应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描；

   例子：select id from t where num is null

2. 应尽量避免在 where 子句中使用!=或<>操作符，否则将引擎放弃使用索引而进行全表扫描；

3. 应尽量避免在 where 子句中使用 or 来连接条件，否则将导致引擎放弃使用索引而进行全表扫描；（可以使用union来代替or）

4. in 和 not in 也要慎用，因为in会使系统无法使用索引，而只能直接搜索表中的数据，对于连续的数值，能用 between 就不要用 in；

5. 尽量避免在索引过的字符数据中，使用非打头字母搜索，这也使得引擎无法利用索引；

   比如：SELECT * FROM T1 WHERE NAME LIKE ‘%L%’

6. 应尽量避免在 where 子句中对字段进行表达式操作或者函数操作，都会导致引擎放弃使用索引而进行全表扫描；

   比如：SELECT * FROM T1 WHERE SUBSTING(NAME,2,1)=’L’

应用

联合索引

联合索引是指对表上的多个列进行索引，加快搜索的效率。

覆盖索引

从辅助索引中就可以得到查询的纪录，避免了去查询聚集索引中的纪录所造成的消耗。