高效检索，往往依赖索引。首先先明确索引的概念。
MySQL索引使用的数据结构是B+树。
B+树有以下特点：
- B+树是一棵搜索树，树中元素是有序的。
- B+树是B树的变体。优势在于硬盘IO次数更少（因为中间节点只是指针，不保存其他数据，所以一个节点能存储更多元素，使得整棵树更胖更矮），而且便于范围查找。
- B+树往往很大，不能完全存放于内盘，需要存放于硬盘，所以IO次数决定效率。
- 一个节点可以包含多个元素，减小树的高度，这样一次硬盘IO能读过较多元素，能减少IO次数。
- 根节点至少有两个值。
- 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
- 父节点的元素是孩子结点中最大（或最小）的元素。所以根节点的最大元素是整棵树的最大元素。
- 每个一个父结点的元素都会出现在孩子结点中，所以叶子节点中包含树中所有元素。
- 所有的叶子结点都位于同一层。
- 每个叶子节点包含指向下个叶子节点的指针，形成一个有序链表。
- 只有叶子节点包含数据库中的数据（卫星数据），其他节点都是索引。
- 聚集索引存在的是一条记录，非聚集索引存放的是主键。
单行查找：
先看B树的单行查找：
通过上图可知，B树通过找到银行指针去文件中找到相关记录。
再看下B+树，从树根开始，逐层找到叶子节点。比如查找元素3。
第一次磁盘IO
第二次磁盘IO
第三次磁盘IO
范围查找：查找3 - 11的元素。
如果是B树，需要中序遍历。
如果是B+树，只需要沿着叶子链表搜索即可。
找到下限3
最后对比下MySQL不同存储引擎之间的索引：
参考：北京大学计算机教学课件，以及
漫画：什么是 B+ 树？
