分析上面的过程，发现需要 3 次磁盘 IO 操作和 3 次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。
B+ 树B+ 树：是应文件系统所需而产生的一种 B 树的变形树。
一棵 m 阶的 B+ 树和 m 阶的 B 树的异同点在于：
1、每个节点的指针上限为 2d 而不是2d+1。
2、所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。（B 树的叶子节点并没有包括全部需要查找的信息）
3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字，不存储 data。（B 树的非终节点也包含需要查找的有效信息）
为什么说 B+ 树比 B 树更适合做数据库索引？
1）B+ 树的磁盘读写代价更低
B+ 树的内部结点并没有存储关键字具体信息。因此其内部结点相对 B 树更小。
如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。
2) B+ 树的查询效率更加稳定
由于非终端结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，进而每一个数据的查询效率相当。
几种树的对比
以上，为了介绍索引内容，我们花费了大量的篇幅介绍了几种数据结构模型，特别是树的相关概念。
另外，涉及到树的添加和删除元素，操作更加复杂，本文篇幅有限（其实是小编也搞不太明白），这里就不再展开。
有兴趣的，强烈建议钻研下参考链接里的内容。
好了，下面我们来看 MySQL 中的 InnoDB 引擎的索引是如何实现的。
MySQL 的索引模型说了这么多，终于到索引出场了。
索引就是这种神奇伟大的存在。索引相当于数据库的表数据之外新建的数据结构，该数据结构的数据段中存储着字段的值以及指向实际数据记录的指针。
数据库表的索引从数据存储方式上可以分为聚簇索引和非聚簇索引（又叫二级索引）两种。
1、聚簇索引
表数据按照索引的顺序来存储的，也就是说索引项的顺序与表中记录的物理顺序一致。
对于聚簇索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。 在一张表上最多只能创建一个聚集索引，因为真实数据的物理顺序只能有一种。
聚簇集是指实际的数据行和相关的键值都保存在一起。
注意：数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。
如果主键不是自增 id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。
聚簇索引的二级索引：叶子节点不会保存引用的行的物理位置,而是保存了行的主键值
2、非聚集索引
表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，其行数量与数据表行数据量一致。
聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。一般情况下主键会默认创建聚簇索引，且一张表只允许存在一个聚簇索引。
这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。
下面，我们可以看一下 MYSQL 中 MyISAM 和 InnoDB 两种引擎的索引结构。
MyISAM索引实现MyISAM 引擎使用 B+ 树作为索引结构，叶节点的 data 域存放的是数据记录的地址，就是非聚集索引。
下图是 MyISAM 索引的原理图：
