mysql中的b-tree实现在哪个源码文件中？

如果查找数据29，那么首先会把硬盘块由磁盘加载到内存此时发生一次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，显然成本非常非常高。

为什么Mysql考虑使用B+树，而不是B树，其实我们可以先了解下B树和B+树的特点来看下。

※ 树的每个结点都会存储数据

※ 单次查询不一定要遍历到树的根部，平均查询时间会比较快

※ 非叶子节点不存储数据，只存储（冗余）索引，索引包含主键和指针

※ 叶子节点才真正存储数据

※ 每个叶子节点互相链表相连，保证了范围查询的时效性(页之间用双向链表连接，数据间用单项链表链接)

InnoDB最小存储单位是页，叶子节点和非叶子节点最小单位都是页，页大小Mysql 默认设定16384字节，约为16KB。

我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节

我们一个页中能存放多少这样的索引元素，其实就代表有多少指针，即16384/14=1170

高度为2的B+树能存放1170×16=18720

高度为3的B+树能存放1170×1170×16 = 21902400

InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。

在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO *** 作即可查找到数据。

---