众所周知,在MySQL的InnoDB引擎,为了提高查询速度,可以在字段上添加索引,索引就像一本书的目录,通过目录来定位书中的内容在哪一页。

InnoDB支持的索引有如下几种:

B+树索引

全文索引

哈希索引

笔者上一篇文章已经提到过,InnoDB的哈希索引是自适应的,用户无法对其进行干预,在此不再赘述,本文重点介绍B+树索引。

一、数据结构——B+树

相信大家在大学的数据结构的课程中都学过二分查找、二叉树和平衡二叉树。在一组有序的数据中,利用二分查找可以在log2N的复杂度中快速检索数据,平衡二叉树是在二叉查找树的基础上演变而来,解决了二叉查找树在极端情况下转化为单链表的问题。而B+树呢?让我们来看B+树的结构

在B+树中,数据都是按照从下到大的顺序存放在叶子节点中,由上图的B+树可得出,这颗B+树的高度为2,每页可存储4条数据,扇出为5,第一层是索引页,第二层是数据页。数据库B+树索引的本质就是B+树在数据库中的实现,并且B+树的高度一般限制在2-4层,磁盘的IO操作只需要2-4次,所以在索引上查找数据,速度很快。

二、B+树索引

1、聚集索引

在InnoDB引擎中,都有一个聚集索引,一般是primary key,若用户没有显示指定primary key,InnoDB会默认选择表的第一个not null的unique索引为主键,若没有,则会自动创建一个6字节大小的_rowid作为主键。

上图是一张聚集索引的示意图,由上图,我们可以看到,该树分为两层,同样第一层是索引页,第二层是数据页,实实在在存放数据的地方。我们还可以得出,索引页存放的并不是数据而是指向真实数据的一个偏移量,而真实数据存放在第二层的数据页,所以如果一条SQL语句命中索引,只是命中了索引页的数据,然后通过索引页找到真实数据所在的页。

聚集索引的存储在物理上不是连续的,在逻辑上却是连续的,这是因为页与页是通过双向链表维护的,而每页中行记录也是通过双向链表维护。为什么要双向链表??这是因为方便范围查询和排序,如过找到某个索引所在数据页的偏移量,直接遍历这个链表或者逆序遍历这个链表,便可以方便的进行范围查询和逆序排序。比如

select * from table where id>10 and id<1000;

2、辅助索引

InnoDB的另一种索引,辅助索引,也叫二级索引或非聚集索引。对于辅助索引,叶子并不包含行记录的全部数据,叶子节点除了包含键值外,还包含了一个被称作“书签”的东西,该书签用来告诉InnoDB到哪里可以找到所需的行的数据,所以书签实际存放的是聚集索引,所以如果SQL命中了辅助索引,查询流程分为两步:

1、找到索引页

2、通过索引页找到数据页,该数据页包含聚集索引的的值

3、通过聚集索引找到行记录

所以,辅助索引一般比聚集索引多一次IO。

一个很容易被DBA忽略的问题:如果一条SQL语句命中索引,B+树索引不能找到一个给定查询条件的具体行,只能找到被查询数据行所在的页,然后将这个数据读入内存,然后再内存中遍历所有行找到数据。另外,每一页大小为16k,每一页会包含多行,行与行之间是通过双向链表组织的,所以范围查询或者顺序倒序排序查询时,只需遍历链表就可以了。