Mysql索引基本原理

1.Mysql表空间、段、区、页

    在讲索引的概念之前我们先说一下mysql中段区页的概念。

    表空间是Mysql数据库存储的最高层，默认情况下InnoDB引擎只有一个表空间，所有的数据都是存放在这个表空间内。

    在表空间下数据是以段区页的形式进行存储的。一张Mysql表存储在数据库当中不是以行为单位存储数据读取的，mysql数据库读取的最小单位是页。

    段：一个段是由多个区构成的， 常见的段有数据段、索引段、回滚段等，在InnoDB存储引擎中，对段的管理都是由引擎自身所完成的。

    区：一个区是由多个连续的页组成的空间 ，无论页的大小怎么变动，一个区的默认大小是1M，默认情况下一个区包含64个连续的页，为保证区中的页是连续的 InnoDB会一次从磁盘中申请4~5个区。

    页：页也叫做块，默认情况下一个页大小为16K(可以通过 innodb_page_size 参数来设置一个页的大小)， 常见的页类型有：数据页，索引页， undo页 ，系统页，事务数据页等。 每页存储最多的行记录也是有硬性规定的最多16KB/2-200,即7992行 。

    我们在数据库中查找数据其实是将磁盘中的数据加载到内存的一个过程。在这里，数据库不是将我们所需要查看的某一行或者某几行数据加载到内存当中，而是将我们需要查看的数据所在的页加载到内存当中。

2.数据库索引

    索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。

    常见的索引类型有：主键索引、唯一索引、普通索引、全文索引、组合索引。同时索引还分为聚簇索引和非聚簇索引，一张表只能有一个聚簇索引，其它的索引都是非聚簇索引。

聚簇索引：一个表中只能有一个聚簇索引。一般情况下聚簇索引默认是主键 ，如果表中没有定义主键，InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚簇索引。而且聚簇索引对应的索引值在物理上是连续的。

非聚簇索引：除了聚簇索引以外的索引是非聚簇索引。非聚簇索引是以聚簇索引为基础创建的。非聚簇索引记录的是聚簇索引的索引值，当我们通过一个普通索引去查找数据的时候其实普通索引会先去差对应数据的聚簇索引的索引值，然后再通过聚簇索引的索引值去查询对应的数据。

    这里说的是InnoDB引擎下的聚簇索引，对于MyISAM来说是没有聚簇索引的。使用MyISAM引擎的表的主键不是聚簇索引，MyISAM引擎的主键索引和其它索引一样可以直接找到对应数据的位置，其它索引不需要先找到主键索引，再通过主键索引去找对应数据。这个和两个引擎一个使用B树一个使用B+树来实现索引有关系。

3.索引的数据结构

    Mysql索引用到的数据结构主要为B树，但是也有用到hash，不同的引擎用到的数据结构不同。InnoDB引擎用到的是B+树索引， MyISAM引擎用到的是B树索引，还有 Memory引擎用到的HASH索引。

    由于HASH索引是利用HASH值来计算索引值，在等值查询的情况下对数据的查询效率比较高，但是再范围查询的时候的查询效率与B树索引相比就差很多了，所以我们使用当中更多的是用到的B+树索引。

多路查找树

    多路查找树的每一个节点可以存储多个元素且每个节点的孩子节点数可以有多个。和普通树相比，多路查找树的一个节点不再是只能存储一个元素 ，这打破了我们对树的理解，但是正是这个特性，使得它能够出色地解决io问题(多路查找树的高度低于其它二叉树，高度越低查询数据需要进行的磁盘IO的次数相对就越少)。Mysql数据库中将一个节点的大小设置为Mysql数据库一页的大小，使每一个节点只需要一次IO就可以从磁盘加载到内存当中。

MyISAM引擎B树索引

     B-Tree 索引（或Balanced Tree），是一种很普遍的数据库索引结构。其特点是定位高效、利用率高、自我平衡，特别适用于高基数字段，定位单条或小范围数据非常高效。理论上，使用 B-Tree 在亿条数据与100条数据中定位记录的花销相同。 B-Tree 能加快数据的访问速度，因为存储引擎不再需要进行全表扫描来获取数据，数据分布在各个节点之中。

InnoDB引擎B+树索引

    B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构，InnoDB 存储引擎就是用 B+Tree 实现其索引结构。通常在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

    Mysql数据库中InnoDB引擎用到的数据结构就是B+Tree索引，因为InnoDB引擎有使用到聚簇索引，所以如果我们数据库表使用的是InnoDB引擎的情况下查询数据如果用到了索引有两种情况。一种情况是用到的索引为聚簇索引，这个时候只需要遍历聚簇索引所在的B+Tree便可以找到我们想要的数据位置。还有一种情况是到了非聚簇索引，这种情况下需要先遍历使用到的索引的B+Tree知道对应聚簇索引的索引值，然后再通过聚簇索引的索引值去遍历聚簇索引的B+Tree来找到我们想要的数据。

    由此可见，我们在查询当中使用聚簇索引的效率是远高于使用非聚簇索引的，因为使用聚簇索引的情况下可以避免回表，减少磁盘IO的次数。