索引概念：

概念：索引是提高mysql查询效率的数据结构。总的一句话概括就是索引是一种提高查询效率的数据结构。

数据库查询是数据库的最主要功能之一。设计者们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。

最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如：有顺序查找、折半查找、快速查找等。

但是，每种查找算法都只能应用于特定的数据结构之上，例如顺序查找依赖于顺序结构，折半查找通过二叉查找树或红黑树实现二分搜索。

因此，在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这种数据结构，就是索引

索引性能分析

目前，大多数数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。B+ 树索引是 B+ 树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。

B+ 树是由二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree）逐步优化而来。

        有序数组、Hash索引、红黑树、二叉查找树、AVL树也可以作为数据结构也可以用来实现索引，但是文件系统以及数据库系统普遍采用B树或者B+树，这里结合各个索引的特点以及计算的组成原理来深入的分析。

但是，对于Mysql来说适合它的才是最好的查询，一方面要实现高效的查询，除了简单的条件查询，还要支持有序的高效索引的范围查询、分组。

       有序数组在等值查询和范围查询性能都是非常好的，那为什么又不用有序数组作为索引呢？因为对于数组而言作为索引更新的成本太高，新增数据要把后面的数据都往后移一位，所以也不采用有序数组作为索引的底层实现。

       hash是以key-value的形式进行存储，适合于等值查询的场景，查询的时间复杂度为O(1)，因为hash储存并不是有序的，所以对于范围查询就可能要遍历所有数据进行查询，而且不同值的计算还会出现hash冲突，所以hash并不适合于做Mysql的索引。

             另一方面就是除了查询的效率要高，还要有高效的读取数据效率（io），我们都知道计算机的随机磁盘io效率是非常低下的

B+树索引原理

在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

在B+树的结构中，只在叶子节点存储数据，在非叶子节点中只存储的索引，在非叶子节点中可以有更大的空间储存更多的索引，这样B+树的出度d就可以大大的增加，从而降低的B+树的高度h，B树中一个节点的大小为一个page的大小，也就是一次IO的读取，h越小IO的次数就可以减少：dmax=floor(pagesize/(keysize+datasize+pointsize))

B+树的搜索过程:

 假设我们要搜索id为15的数据：

1. 根据根节点找到磁盘块 1，读入内存，一般根节点也会常驻内存，甚至可以省略一次磁盘IO操作。【磁盘 I/O 操作第 1 次】
2. 比较id 15在区间28的左边，于是根据p1找到磁盘2。
3. 将磁盘2读入内存，查找结果15在（10,17）之间。【磁盘 I/O 操作第 2 次】
4. 然后根据磁盘2的指针p2找到磁盘块5，读入内存。【磁盘 I/O 操作第 3 次】
5. 最后根据id=15找到对应的数据，返回结果。

根据上面的查找只需要至多三次的磁盘IO就可以找到对应的数据。从上面的B+树的原理图中非叶子节点构成了类似于一个一个目录一样，也可以叫做索引页，最后找到叶子结点的数据.

MyISAM

在MyISAM储存引擎中，数据和索引文件是分开储存的，Myisam 的存储文件有三个，后缀名分别是 .frm、.MYD、MYI，其中 .frm 是表的定义文件，.MYD 是数据文件，.MYI 是索引文件。

 Myisam 只支持表锁，且不支持事务。Myisam 由于有单独的索引文件，在读取数据方面的性能很高 。

Myisam 也是B+树结构，但是MyISAM索引的叶子节点的数据保存的是行数据的地址。因此，MyISAM中索引检索的算法首先在索引树中找到行数据的地址，然后根据地址找到对应的行数据。

 可以看出MyISAM的索引文件仅仅保存数据记录的地址。主键索引和辅助索引，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的如下图：

InnoDB

在InnoDB中，数据和索引文件是合起来储存的，如图所示，InnoDB 的存储文件有两个，后缀名分别是 .frm 和 .idb，其中 .frm 是表的定义文件，而 idb 是数据文件。

 如果给另一个字段指定为普通索引，则普通索引树的结构如下图所示：

 所以，当查询不是按照主键查询时候就会先在辅助索引树上先找到主键的值，然后再到主索引树找到对应的行数据的值，这叫做回表，回表降低了表的查询效率。

Mysql索引种类

Mysql中索引的种类也不是很多，不同类型的索引有不同的作用，索引的作用相互之间也存在交叉关系，Mysql中索引主要分为以下几类：

1. 「主键索引」（PRIMARY KEY）：主键索引一般都是在创建表的时候指定，「一个表只有一个主键索引」，特点是「唯一、非空」。
2. 「唯一索引」（UNIQUE）：唯一索引具有的特点就是唯一性，可以在创建表的时候指定，也可以在创建表后创建。
3. 「普通索引」（INDEX）：普通索引唯一的作用就是加快查询。
4. 「组合索引」（ INDEX）：组合索引是创建一个「多个字段的索引」，这个概念是相对于上上面的单列索引而言，组合索引查询遵循「最左前缀原则」。
5. 「全文索引」（FULLTEXT）：全文索引是针对一些大的「文本字段」创建的索引，也称为「全文检索」。
6. 「聚簇索引」和「非聚簇索引」：聚簇索引和非聚簇索引的概念比上面的概念要大，属于包含和被包含的关系。例如：InnoDB中主键索引使用的就是聚簇索引。

查看一个表的所有索引，可以执行下面的sql来查看：-====================>show index from 表名

主键索引

主键索引在InnoDB存储引擎中是最常见的索引类型，一个表都会有一个主键索引，它索引的字段不允许为空值，并且唯一。

一般是在创建表的时候，可以通过RIMARY KEY指定主键索引，在InnoDB存储引擎中，若是创建表的时候没有主观创建主键索引，Mysql就会看表中是否有唯一索引，有，就会指定「非空的唯一索引」为主键索引

若是没有唯一索引，就会默认生成一个6byte空间的自动增长主键作为主键索引，可以通过select _rowid from 表名查询的是对应的主键值.。