首先需要知道的是MySQL中都是是用B+树来实现底层数据结构的。首先需要介绍一下B+树。
如图所示就是一颗B+树，这里简单介绍一下B+树的结构和特点。图中浅蓝色的块称之为一个磁盘块，其中每个磁盘块中包含几个数据项（深蓝色块，也叫关键字）和指针（黄色块），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。
如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。
通过上面的分析，我们知道IO次数取决于b+数的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页（根据操作系统而定，4K、8K或16K）的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。
当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。
通过以上对B+树的介绍，我们知道B+树只有在叶子节点上才会存储真实数据，而非叶子节点上只会存储关键字和指针。
前面提到mysql中是通过B+树来组织一张表数据的，而B+树每个节点上都有一个关键字，在进行搜索的时候要从根节点开始查找，直到在叶子节点上查询到对应的关键字和这行数据。那么MySQL中是使用什么作为B+树节点上的关键字呢？答案是主键索引，MySQL是通过主键索引作为B+树节点上的关键字来组织数据的。那么MySQL又是怎样确定使用哪个字段作为主键索引呢？规则如下：
如果建表时指定了主键，则使用主键作为B+树节点的关键字。如果表中没有主键，但是有唯一索引，则会选取一个唯一索引作为关键字。如果既没有主键也没有唯一索引，MySQL会自动生成一个6字节的整型唯一标识作为关键字。也就是说，MySQL每张表中都必须有一个主键索引，使用这个主键索引作为关键字将整张表组织成一棵B+树。
主键索引是MySQL自动创建的，不是由用户创建的。而在使用中为了提高查询效率，开发者会根据查询条件自己创建一些索引，而这些索引就叫作二级索引。
在MySQL中不管是InnoDB还是MyISAM都是使用B+树来组织表中的数据的。但是在具体实现方法上略有不同。InnoDB的主键索引是聚簇索引，在InnoDB的实现中，把主键作为关键字组织到B+树的各个节点上，而叶子节点上存储的是主键列的值和对应的整行数据。注意这里说的是将表中实际的一整行数据直接存到叶子节点上MyISAM是非聚簇索引，在MyISAM的实现中，叶子节点中存储的是一行数据在磁盘上的地址（可以理解为行号）。所以聚簇索引和非聚簇索引本质的区别就是B+树的叶子节点上存储的是行数据还是行数据的地址（行号）。
InnoDB中每张表有且仅有一个聚簇索引（就是主键索引），InnoDB中的二级索引是非聚簇索引，那二级索引是怎么组织的呢？
InnoDB和MyISAM主键索引和二级索引的对比：
从图中可以看出，InnoDB中的二级索引的叶子结点中存的是索引列的值和主键值，所以在使用二级索引查询的时候，首先通过二级索引查找到主键值，然后再根据主键值到主键索引的叶子结点中查到对应的整行数据。
而MyISAM的二级索引的叶子节点中保存的是指向物理数据的指针，因此它的主建索引和二级索引的结构并没有任何区别，只是说主键索引的索引值是唯一且非空的。
InnoDB的主键索引设计成聚簇索引有两个优点：
数据和主键索引存放在一起，可以直接根据主键值获取到整行数据，如果是非聚簇索引则只能根据主键值获取到行数据的地址，然后再读一次磁盘去获取行数据。因为B+树的叶子节点是根据关键字排序的，所以表中主键值连续的数据在磁盘中的存储也是连续的。有如下一张InnoDB表：
CREATE TABLE `user` ( `id` INT NOT NULL , `name` VARCHAR NOT NULL , `age` INT NOT NULL);其中id为自增主键，name是一个普通索引。在执行select * from user where id = 1时，会在主键索引对应的B+树的叶子结点上搜索到关键字id=1的节点，并读取位于该节点上的整行数据。但是在执行select * from user where name = 'tom'时，会分为两个步骤：
先到name索引对应的B+树的叶子结点上搜索到关键字name='tom’的节点，并从该节点上获取对应的主键id值。
然后再根据id值使用主键索引读取到整行数据。
其中第二个步骤叫作回表查询。需要扫描普通索引和主键索引两棵B+树才能拿到整行数据，效率较低。
如果执行select id, name from user where name = 'tom',则只需要扫描name索引树就可以获取到所有的字段，因为id和name都保存在name索引B+树的叶子节点上，所以不需要再去主键索引上查找。这就是所谓的索引覆盖。只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快。
而select id, name, age from user where name = 'tom'，因为age字段没有存储到name索引的叶子节点上，所以需要根据主键索引回表查询到age列值。如果把name索引改成（name，age）的联合索引就可以实现索引覆盖，无需回表了。
