【mysql 索引结构】innodb索引结构B+树

为什么Mysql中Innodb的索引结构采取B+树？

开头，我们先回忆一下，B树和B+树的结构以及特点，如下所示:
B树：

注意一下B树的两个明显特点

• 树内的每个节点都存储数据
• 叶子节点之间无指针相邻

B+树：

注意一下B+树的两个明显特点

• 数据只出现在叶子节点
• 所有叶子节点增加了一个链指针

针对上面的B+树和B树的特点，我们做一个总结
(1)B树的树内存储数据，因此查询单条数据的时候，B树的查询效率不固定，最好的情况是O(1)。我们可以认为在做单一数据查询的时候，使用B树平均性能更好。但是，由于B树中各节点之间没有指针相邻，因此B树不适合做一些数据遍历操作。

(2)B+树的数据只出现在叶子节点上，因此在查询单条数据的时候，查询速度非常稳定。因此，在做单一数据的查询上，其平均性能并不如B树。但是，B+树的叶子节点上有指针进行相连，因此在做数据遍历的时候，只需要对叶子节点进行遍历即可，这个特性使得B+树非常适合做范围查询。

因此，我们可以做一个推论:没准是Mysql中数据遍历操作比较多，所以用B+树作为索引结构。而Mongodb是做单一查询比较多，数据遍历操作比较少，所以用B树作为索引结构。
（3）那么为什么Mysql做数据遍历操作多？而Mongodb做数据遍历操作少呢？
因为Mysql是关系型数据库，而Mongodb是非关系型数据。由于关系型数据库和非关系型数据的设计方式上的不同。导致在关系型数据中，遍历操作比较常见，因此采用B+树作为索引，比较合适。而在非关系型数据库中，单一查询比较常见，因此采用B树作为索引，比较合适。