MySQL高级——MySQL中BTree索引结构与检索原理

一、BTree索引结构

二、BTree索引初始化介绍

• 一颗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并不真实存在于数据表中。

三、BTree索引查找过程

• 如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO。在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计；
• 通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，
• 通过磁盘块3的P2指针的磁盘地址把磁盘块8由磁盘加载到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。
• 真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。