Mysql学习——InnoDB索引（B+树）

一、没有索引如何查询

通过对InnoDB页的学习，我们可以知道在页中怎么根据主键快速的查找一条数据，因此，我们现在归纳一下，没有索引的时候，查询一条数据的情况：

1. 在一个页中查找数据：

1. 根据主键查找数据：这就是之前说的，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

2. 根据其他普通列查找数据：对于非主键只能从最小的记录一直遍历下去，查找数据。
   

2. 在很多页中查找数据：定位到所要找的页，然后再去一个页中查找数据。

二、索引是如何提高查询效率的

索引的本质其实是一个B+树，如图所示：

观察这个图，我们可以发现：

1. 在页中，每一个主键都是递增的，是一个顺序的单项链表

2. 下一个页与上一个页互相指向，是一个双向链表

3. 目录项中会存储所指向页的页号和该页中最小的主键

当我们要查找主键为,10的数据的时候，首先会通过2分法，找到1,5,12,209中中间的数，我们发现是5，然后5比10小，10比12大，于是就会找到页号为28的页，在页中找到主键为10的这条数据。

而这就是聚簇索引（主键是默认有索引的），与之相对应的还有二级索引，就是根据其他搜索条件而不是主键去查找数据使用的。二级索引会根据所查找的列，对数据进行排序，这里的数据仅仅只有主键和所创建索引的列，然后还是根据二分法，查找到所需要的主键，再根据主键去查聚簇索引，这称之为回表。

二、索引的代价

索引虽然好，能够提高查询效率，但是代价也很高：

1. 空间上，每建立一个索引，都会生成一个B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，一棵很大的B+树由许多数据页组成。

2. 时间上，每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引。

因此，如果不合理创建索引，创建了太多的索引，很容易造成空间和时间上的浪费。