索引的概念、原理（为什么要建立索引）

1-什么是索引？

索引是存储引擎用于快速查找记录的一种数据结构。在MySQL中，也叫作 "键(key)"。

2-索引原理（为什么索引能加快查找效率？）

索引常用两种数据结构实现，接下来我们来分别看下两种不同的索引。

2-1  B-Tree 索引

要了解B-Tree索引，我们肯定得先对B-Tree 一数据结构有一定的了解。

假设一颗m阶的B树，则其具有以下特点：

根节点至少有2个节点

除根节点外，每个节点存储的key的数量必须满足：m/2<=x<=m-1 (x为节点存储的key的数量)

位于第x-1个和x个之间的key存储的值也必须x-1个和x对应key的值之间

那么应用B树之后为什么查找 效率会高很多呢？我们来举个例子说明

假设这是我们user表中的数据，键值即为我们的 id ，现在我们要查找id为28的记录。

建立索引的情况下：

1、读取磁盘块1中的数据（已经在内存中），判断出应该读取p2指向的磁盘块3.

2、读取磁盘块3中的数据，判断出应该读取p2指向的磁盘块8.

3、读取磁盘快8的数据，查找到id为28的记录。

没有建立索引的情况下：

扫描全表，直到查找到id为28 的记录。

对比有无索引的情况，我们就可以很明显的发现，如果我们的表记录数很大，建立索引后只要保持树的深度H，我们就可以在<=H-1次下，查找到我们的记录（根节点常驻内存）。没有建立索引时，则需要进行扫描全表，很耗费系统资源，且效率非常低下。

2-2 B+Tree 索引

为了理解B+Tree 索引，我们还是先来了解下B+Tree这种数据结构。

B+Tree区别B-Tree（B树）的地方在于，B+Tree的非叶子结点只存储导航信息，数据全部存储在叶子结点处并且用链表连接。

B+Tree 树非叶子结点只起导航作用，这样做的好处是内页可以存储更多的key，数据更紧密，可以简单的理解为B+Tree 相对于B-Tree来说可以进一步降低树的深度，降低io的读取次数，提高效率。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。

数据库的设计者也巧妙的利用磁盘的预读，将每个节点设为一个页的大小，这样我们就可以只需要一次io便可以读取整个节点的信息。

现在我们依旧寻找 id 为28的记录：

1、根据磁盘块1判断应该寻找磁盘块3的数据（根节点常驻内存）。

2、读取磁盘块3的数据，判断出应该读取磁盘块8的数据。

3、读取磁盘块8的数据，寻找到id为28的记录，结束。

看到这里大家可能还不能体会到索引的高效性，我们把数据量扩大点来计算下：

InnoDB存储引擎中页的大小为16kb，为了方便计算我们假设表中id占8个字节，其他数据占8个字节，也就是说一个页，我们可以存储16kb/16B=1000  个键值对（方便计算去进制为1000而不是1024），那么一个深度为3的可以存储多少条数据呢？答案是10^3*10^3*10^3=10亿条记录，而当我们要查找其中一条数据的时候我们只需要进行两次IO（根节点常驻内存）。10亿条数据中查找1条数据，只需要进行2次io，这效率至高相对于没有索引进行一条一条记录扫描是可想而知的。

3-常见存储引擎中的索引

     在讲解概念的时候我们就已经知道索引是存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，InnoDB和MyISAM的索引底层都是使用B+Tree数据结构，但是使用了两种不同的实现方式。

假设这是我们数据库中的一张表，id为我们的主键（比较懒，id应为第二张图图中的key，3,5,9等等 ）

我们依旧拿这张图来讲解，在MyISAM中，叶子节点存储的值（图中的data）不是我们的其他字段的值，而是存储记录的地址。

而在InnoDB中data即为我们除索引键外的数据，在我们的表中也就是encode的值。

依旧是在InnoDB存储引擎下，如果我们在encode上建立了索引，则data中存储的仅仅是我们的主键（不是除encode外所有的数据），查找时拿到我们的主键，再根据我们的主键索引去查找对应的记录。了解不同存储引擎下索引如何工作可以帮助我们排查性能问题。

这里又会延伸出二个概念：聚集索引和非聚集索引

聚集（clustered）索引，也叫聚簇索引。

定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。

概念很难理解，我们可以按照我们上面讲的来理解，根据聚集索引查找我们可以直接查找到们的数据（如我们根据id查找），根据非聚集索引查找时要先找到聚集索引，然后根据聚集索引查找记录（如上面我们根据encode查找）。