MySQL索引的工作机制

MySQL自v5.5.8后开始使用Innodb作为默认的存储引擎，以下内容将以Innodb作为前提条件

MySQL是将数据作为行结构进行存储的，每一条数据都作为组织成一个行级结构，而许多的行，是存在页里面的（一页可以存储很多行），所以行与页便是MySQL的基础存储结构。

页结构

页有固定大小，为16k

页的存储结构

Infimum/Supremum，这两个分别是标志着这一页的最小和最大的记录，是虚拟的记录，并不真正存储数据，可以认为是dummy指针，Inf的next指向页中的第一条有效数据，而最后一条数据的next指向Sup。
页与页之间也通过FileHeader中的prev、next连接成双链表。所以页面的整体组织方式如下图。
PageHeader则记录数据页内的元数据信息，非数据页就不需要这个字段，例如Index_id(当前页属于哪个索引)，B+树层级等等
FileTailer是一个校验信息的位置
PageDirectory是比较重要的数据，首先将Inf作为一个分组，Sup和往前最多8条数据为一个分组，中间的数据最多4条为一个分组，通过此方式将页内数据进行分组，每一组最后一条数据的记录头中n_owned字段记录了该组一共多少条数据，并且PageDirectory存储每个分组最后一条数据的地址，因为分组数取决于数据量，这部分的大小=地址长度x分组数，所以也是不确定大小的。通过这个目录，再查询当前分页的数据时就可以实现二分查找。

页与页的连接

逻辑连续：页间的行数据只是逻辑连续，在物理地址上不一定连续。

当所有的行数据根据索引字段进行排序完成并生成B+树之后，每个节点便是一页，然后在叶子节点进行数据的查询。叶子节点是真正存储数据的，又叫数据页，而其他节点只存储索引值+页号，叫做目录页

以聚簇索引为例

根节点的内容便是一页，页内的id有1、320，各自对应的页数为30、32，则左子树的根节点对应页数为30，右子树的根节点对应页数为32，在数据进行添加的时候则是对叶子节点进行数据添加，当数据量到达页存储上限时则进行页的分裂，以此便完成成B+树的生成。定位到指定页后则可进行二分查找。

B+树

二级索引原理同上