终于弄清楚B-树原来就TM是B树了，今天终于看懂了（看到了）B树与B+树的简单原理，可以回答为啥MySQL数据库使用B+树存储索引的问题了。这篇文章不再赘述B树/B+树的概念、结构等原理，主要讲一讲这两者的关系与区别，以及为什么关系型数据库（如MySQL）使用B+树存储索引而非关系型数据库（如MongoDB）使用B树作为存储索引的数据结构。
首先讲讲B树作为数据结构存储的优点
众所周知，使用传统的平衡二叉树（如AVL树、红黑树）来作为查找数据结构的查询性能非常赞。存储少量数据时，使用AVL树来做索引当然很棒，因为数据直接读入内存操作，效率很高。但是当存储海量数据时，一次性将所有数据读入内存不现实，因此需要在磁盘内直接进行查找，这意味着磁盘IO的操作为查找性能带来了挑战。因此，降低IO次数便是存储海量数据索引的一个亟需解决的问题。对于二叉树而言，由于层数较高，达到了logN层（N为节点个数，也就是数据的个数，因为二叉树一个节点只存出一个数据），因此，查找一个数据的IO次数也达到了logN的级别。而B树采用多叉的结构，目标是将树的层数压缩在3（通常来说），从而大大减少了磁盘的IO次数，增加了查找效率。
所以说，B树作为数据结构存储数据的目的是为了压缩树的高度，从而减少在海量数据查找情况下，降低磁盘IO的次数，从而从真实世界的时间概念上进行优化。（也就是说此时不能从算法时间复杂度来作唯一考量了。）
B树与B+树的区别
细节上的区别也不在此篇赘述，主要讲讲作为存储结构，最大的区别就在于，B树直接将数据存储在索引的指针指向上，即，树中的节点直接存储数据；而B+树则在所有非叶子节点上只存放索引，而只有在叶子节点上才真正存储数据，并且在树的最后一层上，每个数据按序拥有指针（即所有叶子节点构成链表结构，数据的索引具有连续性和有序性）。也正是因此，B+树的结构支持区间查找，可以很好地利用磁盘的预读机制，即B+树相对于B树增加了区间访问性。
除此之外，由于B+树的非叶子节点只存储索引副本，而不存储真实的数据，因此，对于相同大小的磁盘块，B树能存储的索引较小，而B+树能存储更多的索引，因此每个节点能索引的范围更大也更精确，从而更好地减小磁盘的IO次数。
该说说MongoDB和MySQL了
大家知道，MongoDB作为一种非关系型数据库（也是聚合型数据库），使用的存储结构是B树；而MySQL作为一种关系型数据库，使用的是B+树，Why is 这样？
MongoDB
从聚合性数据库这个字眼就能看出，这种类型的数据库很好地迎合了B树的聚合特性（索引与数据直接绑定存储在一个节点里）。而且，B树的查找效率最好可以达到O(1)（即在根节点就查找到），如此也很好地迎合了非关系型数据库对性能要求高（但数据模型要求简单）的需求。简单来说，B树查找到了索引，也即立马获取到了数据。
MySQL
B+树查询效率稳定，固定在logN（log底数很大，因此logN并不大），因为所有数据都在叶子节点中，也即树的最后一层上，所以查询效率稳定。更重要的是，关系型数据库具有很普遍的区间访问需求，而B树不支持区间访问，B+树也能很好地利用磁盘预读机制迎合关系型数据库区间访问的需求。另外，由于B+树的每个节点的索引范围更大更精确，因此也更适合外部存储（减少磁盘IO次数）。
讲完了。