MySQL索引的数据结构-B+树介绍

1.聚集索引和辅助索引

在数据库中，B+树的高度一般都在24层，这也就是说查找某一个键值的行记录时最多只需要2到4次io，这倒不错。因为当前一般的机械硬盘每秒至少可以做100次IO，24次的IO意味着查询时间只需要0.02~0.04秒。

数据库中的B+树索引可以分为聚集索引（clustered index）和辅助索引（secondary index），

聚集索引与辅助索引相同的是：不管是聚集索引还是辅助索引，其内部都是B+树的形式，即高度是平衡的，叶子结点存放着所有的数据。

聚集索引与辅助索引不同的是：叶子结点存放的是否是一整行的信息

2.聚集索引
InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。 而聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时叶子结点存放的即为整张表的行记录数据，也将聚集索引的叶子结点称为数据页。 聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。

如果未定义主键，Mysql取第一个唯一索引（unique）而且只含非空列（NOT NULL）作为主键，InnoDB使用它作为聚簇索引。

如果没有这样的列，InnoDB就自己产生一个这样的ID值，它有六个字节，而且是隐藏的，使其作为聚簇索引。

由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚集索引。 在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据。 此外由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值得查询。

聚集索引的好处之一：它对主键的排序查找和范围查找速度非常快，叶子节点的数据就是用户所要查询的数据。如用户需要查找一张表，查询最后的10位用户信息，由于B+树索引是双向链表，所以用户可以快速找到最后一个数据页，并取出10条记录

聚集索引的好处之二：范围查询（range query），即如果要查找主键某一范围内的数据，通过叶子节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可。

3.辅助索引
表中除了聚集索引外其他索引都是辅助索引（Secondary Index，也称为非聚集索引），与聚集索引的区别是：辅助索引的叶子节点不包含行记录的全部数据。

叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含一个书签（bookmark）。该书签用来告诉InnoDB存储引擎去哪里可以找到与索引相对应的行数据。

由于InnoDB存储引擎是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引，但只能有一个聚集索引。

当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶子级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。

举例来说，如果在一棵高度为3的辅助索引树种查找数据，那需要对这个辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问才能得到最终的一个数据页。

4.聚集索引和非聚集索引的区别
4.1聚集索引
a)纪录的索引顺序与无力顺序相同 因此更适合between and和order by操作
b)叶子结点直接对应数据 从中间级的索引页的索引行直接对应数据页
c)每张表只能创建一个聚集索引

2非聚集索引
a)索引顺序和物理顺序无关
b)叶子结点不直接指向数据页
c)每张表可以有多个非聚集索引，需要更多磁盘和内容
d)多个索引会影响insert和update的速度