众所周知，MySQL选择的是B+Tree作为索引的数据结构，以及在5. 5版本之后InnoDB已经成为MySQL的默认引擎。而本文介绍B Tree与B+Tree的区别，InnoDB与MyISAM的区别，以此来回答出为什么选择B Tree和InnoDB存储引擎，希望对大家有所帮助。

多路平衡查找树

B Tree示例图

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程：

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree示例图

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

下面做一个推算：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

1、B+ Tree是B Tree的变种（进化），也就是说B Tree能解决的问题，B+ Tree也能解决（降低树的高度，增大节点存储数据量）

2、B+ Tree磁盘读写能力更强。因为B+ Tree的根节点和支节点不保存数据区，所以根节点和支节点同样大小的情况下，能够保存的关键字要比B Tree多。而叶子节点不保存子节点引用，能用于保存更多的关键字和数据。所以B+ Tree读写一次磁盘加载的关键字要比B Tree更多。

3、B+ Tree查询性能稳定。B+ Tree数据只保存在叶子节点，每次查询数据，查询IO次数一定是稳定的。B Tree则有可能直接从根节点命中返回，也有可能命中叶子节点返回。

InnoDB与MyISAM存储引擎存储数据库数据的文件不同。

InnoDB存储引擎有2个文件：Frm文件和Ibd文件。Frm文件是表的定义文件，而Ibd文件是数据和索引存储文件（数据以主键进行聚集索引，把真正的数据保存在叶子节点中）。

MyISAM存储引擎有3个文件：Frm文件、MYD文件和MYI文件。Frm文件是表的定义文件，MYD文件是数据文件（所有的数据保存在这个文件中），MYI文件是索引文件。

由上面可以看出，两者的区别就是InnoDB把数据和索引都放在一个文件中，而MyISAM则是有两个文件分开存储。

注意：通过索引文件和数据文件是否分离来分成聚集和非聚集索引。所以InnoDB存储引擎是聚集索引，而MyISAM存储引擎是非聚集索引。

InnoDB 主键索引：叶子节点的数据区保存的是真正的数据（要查询的数据）。主键索引树的叶子节点直接存储数据，所以叫做聚合索引。主键索引是从根节点一直扫描到叶子节点，从而找到对应主键的数据（数据保存在叶子节点的数据区）。

InnoDB辅助索引：叶子节点的数据区保存的是主键索引关键字的值。辅助索引是从根节点一直扫描到叶子节点，找到对应主键的值，再走主键索引。

而在MyISAM存储引擎中，主键索引和辅助索引是同级别的，没有主次之分。它们叶子节点的数据区保存的是数据的磁盘地址。两者都要根据这个地址从MYD数据文件中加载对应的数据。

1、InnoDB支持事务，MyISAM不支持。InnoDB对于每一条SQL语句都默认封装成事务，自动提交，所以会影响速度，最好把多条SQL语句放在begin和commit之间，组成一个事务。

2、InnoDB支持外键，MyISAM不支持。

3、InnoDB是聚集索引，使用B+ Tree作为索引结构，数据文件和索引文件绑在一起的，必须要有主键，通过主键索引效率更高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此主键不应该过大，因为主键太大，其它索引也都会很大。MyISAM是非聚集索引，也是使用B+ Tree作为索引结构，索引和数据文件是分开的，索引保存的是数据文件的指针（地址）。也就是说：InnoDB的B+树主键索引的叶子节点就是数据文件，辅助索引的叶子节点是主键的值；而MyISAM的B+树主键索引和辅助索引的叶子节点都是数据文件的地址指针。

4、InnoDB不保存表的具体行数，所以执行select count(*) from table时会全表扫描。而MyISAM用一个变量保存了整个表的行数，所以执行上述语句时只需要读出该变量即可。

5、InnoDB不支持全文索引，而MyISAM支持。所以在涉及全文索引领域的查询效率上MyISAM速度更快。但是在5.7之后的InnoDB支持全文索引了。

6、InnoDB支持表、行（默认）级锁，而MyISAM支持表级锁。

7、InnoDB表必须有唯一索引（如主键），用户没有指定的话会自己生产一个隐藏列Row_id来充当默认主键，而MyISAM可以没有。