要想弄清索引在MySQL中的工作原理首先要从MySQL的存储结构说起也就是关于页的内容1.什么是页在一个数据库中创建一张表时此时就会生成一个.ibd文件一张表对应一个.ibd文件而页就是.ibd文件中最重要的结构体在MySQL中页是内存与磁盘交互的最小单元一个页的默认大小为16KB且每次内存与磁盘交互是都至少读取一页且在磁盘中每个页内部的地址都是连续的之所以这样做因为根据局部性原理将来要使用的数据的位置与当前使用的数据的位置大概率是相邻的所以一次性将一页的数据加载到内存中如果将来要使用的数据恰好也存储在这个页中此时就直接从这个内存中读取即可这就可以减少磁盘IO的次数从而提高查询效率且一个页中即使没有数据也会使用16KB的空间来存储且也会与索引中的B树的节点对应2.页的基本结构在MySQL中页的种类有很多最常用的就是用来存储数据的数据页和存储索引的索引页但是无论是哪种类型的页都会包含页头和页尾这两部分且主题用数据行来填充数据页的基本结构如下图2.1 页文件头和页文件尾关于这部分的内容现在只需要关注页头中的上一页页号和下一页页号即可因为每个页中的页头都记录了上一页页号和下一页页号通过这两个属性就可以将页与页之间连接了起来从而形成了双向链表2.2 页主体页主体部分是存储数据的主要部分每当创建一个新页时都会自动分配两个行一个是最小行另一个是最大行这两行并不存储真实的数据而是作为数据行链表的头和尾在页主体中每一个数据行包括最大行和最小行都有保存下一行数据行的偏移量区域next_record通过这个偏移量就可以将页主体中的所有数据行以单向链表的形式链接起来下图是一个新页的结构图当往一个新页中插入数据时也会往最小行和最大行之间插入对应的数据行当有更多的数据插入时就会按照插入数据的主键值的大小进行连接从而形成单向链表如下图可是由于数据行还是以单向链表的形式连接起来的这样查询的时间复杂度不还是O(N)所以MySQL在这一部分还做了一部分的优化也就是页目录2.3页目录在讲页目录之前首先要知道页主体中的数据行是会进行分组的最小行默认为一组且最大行永远在最后一组除了最小行这一组其他组中最多可以包含的8条数据行如果这超过8个数据行此时就会分裂出一个新的组如下图知道了分组的概念之后此时就来介绍页目录页目录就是用来提高查询效率的页目录中有一个叫槽的东西每当页主体中的数据行进行了分组之后页目录中就会创建一个槽槽的数量与组的数量是一致的槽中会指定每一组中的最后条记录同时保存这条数据行的主键值。有了槽之后查询一条记录的过程就变为假设我们要查找主键值为6的数据行查询步骤如下首先要找到这条记录所在的页然后通过主键值去找到对应的槽然后根据槽去找对应的分组接着就可以在分组中去查询这条记录的所以通过页目录中的槽在查询某一条记录时就在也不用一一遍历页主体中的所有数据行了。2.4数据页头数据页头中记录了当前页保存数据的相关信息如下图不详细介绍了3.B树在索引中的工作原理首先会根据要查询数据的主键值去B树中找到对应的索引页并将索引页加载到内存中在根据得到的索引页去找到要查询数据所在的数据页并将其加载到内存中最终在页中查询数据时会根据主键值去与页目录中存储的主键值去比较找到对应的槽由于槽和对应一个组所以根据槽很快就可以定位到该数据在页主体中的那一个分组中找到对应的分组后就可以在该组去取对应的数据举个例子如下图假设要查找id为5的记录完整的过程如下首先判断B树根节点的索引记录也就是索引页1根据57就可以判断id5的记录在左子树中然后找到索引页2根据id在索引页2中找到id5的索引记录然后根据索引记录去找到对应的数据页并将数据页加载到内存中接着就去对应的数据页去对应的记录即可总结图如下4.计算三层树高的B树可以存放多少条记录理论上的一个数据页的默认大小为16KB假设数据页中的一条记录的大小为1KB那么一个数据页中就可以存储16条记录一个索引页中存的是主键值和子节点的引用假设主键类型为bigint类型大小为8byte下一页地址的大小为6byte则此时一天索引记录占14byte此时一个索引页中可以存储1024*16/141170条记录则理论上一个三层B树在理论上可以存1170*1170*1621902400条记录总结如下图