2014阿里实习生面试题——MySQL如何实现索引的

这是2014阿里实习生北京站二面的一道试题：

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，比如MyISAM和InnoDB存储引擎。

MyISAM索引实现：

MyISAM存储引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现：

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是：InnoDB的数据文件本身就是索引文件。

第二个与MyISAM索引的不同是：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

其实，数据库索引的实现可以采用红黑树，B-Tree树数据结构。

但是为什么实际上采用的B+Tree呢？

这要从计算机存储原理和操作系统相关知识说起。因为数据表的索引比较大，不能常驻内存，所以以文件形式存储在磁盘中。所以当查询数据的时候就需要I/O操作。高效率查询的目标是较少I/O次数。一次I/O一般读取一页（一般为4k）大小的数据(局部性原理)。如此，在B-树中，每当申请一个新结点时，就以页的大小来申请。也就是说一次I/o可以读取一个一个结点（包含很多key）的数据；而在红黑树结构结构中，逻辑相邻的结点物理上不一定相邻，就是说，读取同等的数据需要多次I/O。所以选择B-树效率更好。

那为何最终选了B+树呢？

因为B+树内节点去掉了data域，因此可以拥有更大的出度，就是说一个结点可以存储更多的内结点，那么I/O效率更高。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

聚集索引与非聚集索引之分：

InnoDB是聚集索引，因为它的B+树的叶结点包含了完整的数据记录。而MyISAM方式B+树的叶结点只是存储了数据的地址，故称为非聚集索引。

索引使用策略及优化

MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。