1 B树

每个节点都存储key和data，所有节点组成这棵树，并且叶子节点指针为null。

2 B+树

只有叶子节点存储data，叶子节点包含了这棵树的所有键值，叶子节点不存储指针。

后来，在B+树上增加了顺序访问指针，也就是每个叶子节点增加一个指向相邻叶子节点的指针，这样B+树成了数据库系统实现索引的首选数据结构。

原因有很多，最主要的是这棵树矮胖。一般来说，索引很大，往往以索引文件的形式存储的磁盘上，索引查找时产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的时间复杂度。树高度越小，I/O次数越少。

那为什么是B+树而不是B树呢，因为它内节点不存储data，这样一个节点就可以存储更多的key。

3 MyISAM和InnoDB对索引的实现方式

在MySQL中，最常用的两个存储引擎是MyISAM和InnoDB，它们对索引的实现方式是不同的。

• MyISAM
  key存的是索引值，data存的是数据地址。索引是索引，数据是数据。索引放在XX.MYI文件中，数据放在XX.MYD文件中，所以也叫非聚集索引。
  
• InnoDB
  key存的是索引值，data存的是数据本身。索引也是数据。数据和索引存在一个XX.IDB文件中，所以也叫聚集索引。
  
• 两种存储引擎的区别：

1. MyISAM是非事务安全的，而InnoDB是事务安全的

2. MyISAM锁的粒度是表级的，而InnoDB支持行级锁

3. MyISAM支持全文类型索引，而InnoDB不支持全文索引

4. MyISAM相对简单，效率上要优于InnoDB，小型应用可以考虑使用MyISAM

5. MyISAM表保存成文件形式，跨平台使用更加方便

6. MyISAM管理非事务表，提供高速存储和检索以及全文搜索能力，如果在应用中执行大量select操作可选择

7. InnoDB用于事务处理，具有ACID事务支持等特性，如果在应用中执行大量insert和update操作，可选择。

8. B+树中只有叶子节点会带有数据记录，而B树则所有节点都指向数据记录的行号，在内部节点出现的索引项不会再出现在叶子节点中。

9. B+树中所有叶子节点都是通过指针连接在一起，而B树不会。

• B+树的优点：

1. 非叶子节点不会带上数据记录，这样，一个块中可以容纳更多的索引项，一是可以降低树的高度，减少查找时间。二是一个内部节点可以定位更多的叶子节点。
2. 叶子节点之间通过指针来连接，范围扫描将十分简单，而对于B树来说，则需要在叶子节点和内部节点不停的往返移动。

• B树的优点：
  对于在内部节点的数据，可直接得到，不必根据叶子节点来定位。

参考
https://blog.csdn.net/zhuanzhe117/article/details/78039692