数据库中的索引，原理是什么？为什么查询使用索引就会快？

相信很多程序员朋友对数据的索引并不陌生，最常见的索引是 B+ Tree 索引，索引可以加快数据库的检索速度，但是会降低新增、修改、删除操作的速度，一些错误的写法会导致索引失效等

索引是存储引擎用于快速查找记录的数据结构，MySQL 数据库内部索引是由不同的引擎实现的，主要说一下最常用的InnoDB引擎中的索引，InnoDB引擎中的索引是使用B+ 树的结构来存储的，B+ 树结构如下图：

先来说一下B+ 树的特点：

叶子节点（最下面一层）存储关键字（索引字段的值）信息及对应的全部数据记录。

非叶子节点只存储关键字的信息及子节点的指针。

每个叶子节点相当于MySQL中的一个数据页，同层级的叶子节点以双向链表的形式连接。

每个节点中存储了多条记录，记录之间用单链表的形式连接组成了一条有序的链表。

在 B+ 树中检索数据时：每次检索都从根节点开始，一直搜索到叶子节点。

InnoDB 的数据是按数据页为单位来读写的。也就是说，当需要读取一条记录的时候，并不是将这个记录本身从磁盘读取出来，而是以页为单位，将整个也加载到内存中，一个页中可能有很多记录，然后在内存中对页通过二分法进行检索。在InnoDB 中，每个页的大小默认是16kb。

总体来说，MySQL中的索引用到了B+树、链表、二分法，实现了快速查找数据。

MySQL索引类型

InnoDB 中有两种索引类型：主键索引与辅助索引。

主键索引（聚集索引）：每个表只有一个主键索引，叶子节点同时保存了主键的值以及对应的全部记录。

辅助索引（非聚集索引）：叶子节点保存了索引字段的值以及主键的值。

我们以上图中Person表 为例，其中id 是主键，name 是辅助索引，接下里我们来看一下InnoDB引擎中数据检索过程：

若需要查询 id=1 的数据，只需要使用主键索引中检索就可以查询到数据。（红色线）

若需要搜索 name='Jacy' 的数据，需要使用非聚集索引与聚集索引，需要2步（蓝色线）：

先通过辅助索引中检索 name='Jacy'的数据，获取 id 的值。

再通过id值 到主键索引中 检索id=12的数据。

接下来，我们再看下以下查询的数据检索过程。

主键索引（或唯一索引）查询

上图中所有的数据都是唯一的，我们查询26的记录，过程如下：

首先把page1 页加载到内存中通过二分法查找。

确定26位于[20,40)中间，然后加载20所关联的page3 页.

将page3 页加载到内存中，采用二分法找到26的记录后退出。

非唯一索引查询

上图中查询26的所有记录，数据不唯一，过程如下：

将page1 页加载到内存中通过二分法查找。

确定26位于[20,40)中间，然后加载20所关联的page3 页。

将page3 页加载到内存中通过二分法找到最后一个小于26的记录是23，然后通过链表从23开始向后访问，找到所有的26记录，直到遇到第一个大于26的值退出。

模糊查询

上图中查询以 b字母开头的所有记录，过程如下：

将page1页加载到内存中，通过二分法查找最后一个小于等于b的值(b)，和第一个大于b的(z)，b指向叶节点page3，z指向叶节点page5。

如此一来，可以确定以 b 开头的记录存在于[page3,page5) 这个范围内。

最后依次加载page3 到内存中，通过二分法找到第一条b开头的记录，然后以链表方式继续向后访问page4 中的记录，直至遇到一个字母为z的值退出。

如果查询包含b的记录，是如何执行的呢？

当我们使用 '%b%' 全模糊查询时，通过索引我们还可以快速定位所在的页嘛？

如上图包含b字母的数据在每个页中都存在，因此无法判断包含 b 的记录在哪些页中，只能通过IO的方式加载所有页，遍历所有记录进行过滤，才可以找到包含b的记录。因此使用LIKE %b%进行全模糊查询时，索引是无效的。

更多内容可以浏览《MySQL数据库中如何正确的理解与使用索引》https://www.toutiao.com/i6759910720944472588/