其实从很久以前就打算写这篇总结了，这段时间也面试了不少同学，问到MySQL的时候，都是一直在用，但是当我问他们索引结构、引擎这些数据结构相关的问题的时候，能回答上来的就非常少了，起码从我角度而言，这个问题答好了，应该至少会给下一面的机会。
废话不多少，介绍下mysql的索引结构：
索引的本质
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是一种数据结构。
下面是一种可能的索引结构：第二列加索引，索引用二叉树这种数据结构实现。
虽然可以实现数据库索引的功能，但是mysql不会采用这种数据结构实现，它觉得二叉树太low了，实际上二叉树采用的是B-Tree(B+Tree)
B-Tree和B+Tree
什么是B-Tree(不要读成减，略low)B通常认为是Balance的简称
首先定义一条数据记录为一个二元组[key,data]，key为记录的键值，对于不同数据记录，key是互不相同的(为帮助理解的话，你把他当成主键好了)。data为数据记录除key外的数据(也就是这一条完整的记录)。
下图是一个高度为2，度为3的B-Tree：
什么是B+Tree
B-Tree有许多变种，其中最常见的是B+Tree，MySQL就普遍使用B+Tree实现其索引结构。
与B-Tree相比，B+Tree有以下不同点：
内节点不存储data，只存储key；叶子节点不存储指针，如下图所示：
红黑树、二叉树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，关键因素是磁盘IO的次数。
索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作，当表中的数据量比较大时，索引的大小也跟着增长，达到几个G甚至更多。当我们利用索引进行查询的时候，不可能把索引全部加载到内存中，只能逐一加载每个磁盘页，这里的磁盘页就对应索引树的节点。
从二叉树的查找过程了来看，树的高度和磁盘IO的次数都非常高，所以最坏的情况下磁盘IO的次数由树的高度来决定。
从前面分析情况来看，减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树，所以B-Tree就在这样伟大的时代背景下诞生了。
相同数量的key在B树中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。
一般来说，B+Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。
带有顺序访问指针的B+Tree
磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
B-Tree中一次检索最多需要h-1次I/O，综上所述，用B-Tree(B+Tree)作为索引结构效率是非常高的。
参考链接：