Question

为什么Mysql用B+树做索引而不用B

Answer 1

先从数据结构的角度来答。
题主应该知道b-树和b+树最重要的一个区别就是b+树只有叶节点存放数据，其余节点用来索引，而b-树是每个索引节点都会有data域。
这就决定了b+树更适合用来存储外部数据，也就是所谓的磁盘数据。
从mysql（inoodb）的角度来看，b+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。
那么mysql如何衡量查询效率呢？磁盘io次数，b-树（b类树）的特定就是每层节点数目非常多，层数很少，目的就是为了就少磁盘io次数，当查询数据的时候，最好的情况就是很快找到目标索引，然后读取数据，使用b+树就能很好的完成这个目的，但是b-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘io次数（磁盘io一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，io次数增多，一次io多耗时啊！），而b+树除了叶子节点其它节点并不存储数据，节点小，磁盘io次数就少。这是优点之一。
另一个优点是什么，b+树所有的data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。
至于mongodb为什么使用b-树而不是b+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，上面所述的优点2需求就没那么强烈了，其次mysql由于使用b+树，数据都在叶节点上，每次查询都需要访问到叶节点，而mongodb使用b-树，所有节点都有data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于mysql（但侧面来看mysql至少平均查询耗时差不多）。
总体来说，mysql选用b+树和mongodb选用b-树还是以自己的需求来选择的。

Answer 2

B+ 树是对 B 树的一个小升级。大部分数据库的索引都是基于 B+ 树存储的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 树存储。
B+ 树最大的几个特点：
1. 非叶子节点只保留 KEY，放弃 DATA；
2. KEY 和 DATA一起，在叶子节点，并且保存为一个有序链表（正序，反序，或者双向）；
3. B+ 树的查找与 B 树不同，当某个结点的 KEY 与所查的 KEY 相等时，并不停止查找，而是沿着这个 KEY 左边的指针向下，一直查到该关键字所在的叶子结点为止。

Answer 3

先从数据结构的角度来答。 题主应该知道B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。 这就决定了B+树更适合用来存储外部数据，也就是所谓的磁盘数据。 从Mysql（Inoodb）的角...