索引原理和优势

1.定义：

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。

2.原理： 

不同的数据库，不同的存储引擎其索引的原理也不尽相同。这里只了解下MySQL的索引原理。不过，在了解索引之前我们需要先了解什么是磁盘IO，局部预读，二叉树。

   磁盘IO：很简单，我们知道数据库表里的数据最终会持久化到磁盘里面，当我们读取数据的时候就需要从磁盘里面读取，每一次读取就称为一次磁盘IO。

   局部预读：也称为局部预读原理，指的是当我们读取一个数据的时候，该数据所在位置的相邻数据也很快会被访问到。

基于这两个，我们就能了解下面的这句话;每一次读取数据都会将其相邻的数据也读取出来，存放到数据库内存缓存中，这个数据块称为“页”，也就是说，每一次磁盘IO读取到一页数据，页的大小和操作系统有关，一般是4K或8K或16K。这也是我们经常听到的，页是其磁盘管理的最小单位。

二分法查找二叉树：二叉树分为很多种，平衡二叉树，完全二叉树等，这里的二叉树是基于二分法查找的，二分法简单来讲就是一串数据，提起中间的数据作为根节点将数据分为左右两边，左边的数据再取中间的为节点提起来将其分为左右两边，右边一样，以此类推形成一棵倒着的树，是为二叉树。但这种树要有一个要求就是数据必须是有序的，这也是我们一般要求聚集索引最好选用自增字段的原因。如图;

 

  1）MySQL：

       MySQL存储引擎分为两种：MyISAM和InnoDB。

    　InnoDB：InnoDB存储引擎一般分为以下几种索引：B+树索引，全文索引和哈希索引。其中哈希索引是自适应的，人为无法干预。B+树索引就是我们一般通常所说的索引，B+树索引的构造类似于二叉树，注意，是类似，因为B+树是从平衡二叉树演化而来的，但B+树不是一个二叉树。这里可能有人就不太明白了，要想明白这句话，首先得了解二分法和二叉树。我们插入一段二叉树得的解释。

       二分查找法：也称折半查找法，基本方法就是，将一组数据有序排列，采用跳跃方式查找到这组数据中心点的位置，如果要找的数据小于中心点位置的数据，就在中心点左边（也就是小于中心点数据的一边）再次跳跃到这部分数据的中心位置比较，以此类推直到找到所要找的数据。这种方法的思路大概就是通过折半不断缩小数据范围。例如：

如有5、10、19、21、31、37、42、48、50、52这10个数，现要从这10个数中查找48这条记录，其查找过程如图所示。先找到这组数据中心位置37，判断要找的48大于37就到37的右边继续二分定位到50，再判断48小于50，直到找到48.

 

 

 二叉树：

B+树是通过二叉查找树，再由平衡二叉树，B树演化而来。二叉查找树是一种经典的数据结构，如图：

 

 

 

图中的数字代表每个结点的键值，在二叉查找树中，左子树的键值总是小于根键值，右子树的键值总是大于根键值。

当然，二叉树可以任意构造，不一定非要求根节点一定是中心位置的键值，也可以这样如下图，它同样满足二叉树的定义，右子树键值大于根键值。但是显然，这样构造的二叉树查找的时候效率就很低了，为了最大性能的构造一棵二叉树，平衡二叉树（也称AVL树）应运而生！！

 

 

 

 

 平衡二叉树：首先满足查找二叉树，其次还需要满足任何节点的两个子树的最大高度最大差为1，这样一棵树的性能是比较高的，但还不是最好的，最好性能的树应该是最优二叉树，但是世上哪得双全法，最优二叉树要求较高，需要大量的操作，因此，我们使用平衡二叉树就足够满足我们了。

平衡二叉树的查询速度还是很快的，但是建立和维护一棵平衡二叉树的代价也是很大的，通常需要1次或多次左旋和右旋来得到插入或更新后的树的平衡，每一次数据的变化都意味着平衡二叉树的变动。如图，假如要插入一个值为9的节点，我们需要做的变动如下：

 

 这里通过一次左旋就可以将树维护到平衡状态，但是有的情况要复杂一些，比如：

 

 

 

        可以看到，每次数据的增删改都会引起二叉树的变动，因此维护一颗平衡树是需要开销的，不过平衡二叉树一般用于内存结构对象中，因此维护的开销相对较小。

最后重点来了，B+树！！！

B+树：B+树是由B树和索引顺序访问法（ISAM:MySQL最初存储引擎MyISAM的数据结构结构）演化而来。B+树的定义在任何一本数据结构书中都能找到，其定义十分复杂，在这里列出来只会让读者感到更加困惑。这里，我来精简地对B+树做个介绍：B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。先来看一个B+树，其高度为2，每页可存放4条记录，扇出（fan out）为5，如图：

 

 

从图可以看出，所有记录都在叶子节点上，并且是顺序存放的，如果用户从最左边的叶子节点开始顺序遍历，可以得到所有键值的顺序排序：5、10、15、20、25、30、50、55、60、65、75、80、85、90。

 

B+树索引：本质就是B+树在数据库中的实现，可分为集聚索引和非聚集索引，不管是哪种都是基于B+树高度平衡的，叶子节点存放着所有数据，不同的是，聚索引存放的是一整行的信息。

聚集索引：在InnoDB中，存储引擎表就是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造的一棵B+树，同时叶子节点存放着整张表得行记录数据。也将聚集索引的叶子节点称为数据页。由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能有一个聚集索引。可以这样理解，找到索引就找到了数据。B+树如下图：

 

 

 有些文档会说聚集索引是按照顺序物理地存储数据，但这是不准确的。在《MySQL技术内幕》里有介绍到，个人也比较认可这个：如果真的按照特定的物理顺序存放，那么维护成本相当之高，对于一些非自增主键的更新的处理代价非常大。聚集索引是逻辑上连续的，首先，数据页是通过双向链表进行维护的，页按照主键的顺序排序，并且每页得记录也是按照双向链表维护的，物理存储上也可以不按照主键存储，如果已经按照物理顺序排序了那么双向链表显得多余了。

非聚集索引：也叫辅助索引，叶子节点并不包含行记录的全部数据，叶子节点除了包含键值外，还有一个书签，这个书签只是告诉你哪里可以找到你要的数据，哪里呢？聚集索引里面去找吧。因此，整个辅助索引查找过程是这样的：先在辅助索引得B+树上找到对应索引得书签，在根据书签信息（对应的聚集索引树的键值）去聚集索引的B+树上找到对应的叶子节点数据。

    MyISAM:这是MySQL最早提供的引擎，也是B+树。我们知道一般来讲索引分为聚集索引和非聚集索引，在MyISAM中，这两个原理差不多一样，都是叶子节点存放地址信息，即数据所在的行列信息，再根据行列信息找到数据。不同的是非聚集索引的键值允许重复。

稍微提一下SQL server索引，他的索引是基于B树的。B树设计之初的目的很简单就是为了减少磁盘扫描的次数，也就是减少IO操作，避免全盘扫描。没有聚集索引的表数据会以堆的结构无序存放。

B树和B+树的区别在于索引节点，B树的索引节点里面除了键值和指针为还有数据，但B+树只有键值和指针，他的数据再叶子节点中，并且B+树的叶子节点是一个双向链表，查找范围非常快。那么为什么B+树会比B树好呢，除了上面提到的快速查找外，还有一个原因是页的容量大小是固定有限的，B+树的索引节点页不存放数据，可以容纳更多的索引值。那么相对应的B+树的深度就会较浅，查找更快。