B树与B+树的区别

我们先来看看Stack Overflow上面是怎么解释的（博主已经把回答copy下来了）：

The image below helps show the differences between B+ trees and B trees.

Advantages of B+ trees:

Because B+ trees don't have data associated with interior nodes, more keys can fit on a page of memory. Therefore, it will require fewer cache misses in order to access data that is on a leaf node.

因为B+树没有与内部节点相关的数据，所以更多的key可以安装在内存页上。因此，为了访问在叶节点上的数据，将需要更少的cache miss（高速缓存未命中）。

The leaf nodes of B+ trees are linked, so doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes. A B tree, on the other hand, would require a traversal of every level in the tree. This full-tree traversal will likely involve more cache misses than the linear traversal of B+ leaves.

B+树的叶节点是链接的，所以对树中的所有对象进行全扫描只需要一次线性遍历所有叶节点。另一方面，B树需要遍历树中的每一层。这种全树遍历可能会涉及比B+叶的线性遍历更多的高速缓存未命中。

Advantage of B trees:

Because B trees contain data with each key, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.

因为B树包含每个键的数据，所以频繁访问的节点可以更靠近根，因此可以更快地访问。

用简单的话说就是（不喜欢看英文解释的话可以从这里开始看）

在B树中，你可以将键和值存放在内部节点和叶子节点，但在B+树中，内部节点都是键，没有值。叶子节点同时存放键和值。

B+树的叶子节点由一条链相连，而B树的叶子节点各自独立。

使用B+树的好处

1. 由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。
2. B+树的叶节点由一条链相连，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间

使用B树的好处

B树可以在内部节点同时存储键和值，因此，把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率。这种特性使得B树在特定数据重复多次查询的场景中更加高效。

数据库为什么使用B+树而不是B树

B树相比二叉树虽好，但还是存在以下问题：

       1.每个节点中既要存索引信息，又要存其对应的数据，如果数据很大，那么当树的体量很大时，每次读到内存中的树的信息就会不太够。

       2.B树遍历整个树的过程和二叉树本质上是一样的，B树相对二叉树虽然提高了磁盘IO性能，但并没有解决遍历元素效率低下的问题。

       针对以上两个问题，B+树诞生了，B+树相比B树，本质上是一样的，区别就在与B+树的所有根节点都不带有任何数据信息，只有索引信息，所有数据信息全部存储在叶子节点里，这样，整个树的每个节点所占的内存空间就变小了，读到内存中的索引信息就会更多一些，相当于减少了磁盘IO次数，问题1就得到了解决。又由B树的性质可以得到，所有叶子节点都会在同一层，B+树会以一个链表的形式将所有叶子节点的信息全部串联起来，这样，想遍历所有数据信息只需要顺序遍历叶子节点就可以了，方便又高效，问题二就得到了解决。不仅如此，B+树还有一个相应的优质特性，就是B+树的查询效率是非常稳定的，因为所有信息都存储在了叶子节点里面，从根节点到所有叶子节点的路径是相同的。那么，我们最后再总结一下B+树的优点：

       （1) B+树的磁盘读写代价更低

              B+的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

       （2）B+树的数据信息遍历更加方便

                B+树只要遍历叶子节点就可以实现整棵树的遍历，而B树不支持这样的操作（或者说效率太低），而且在数据库中基于范围的查询是非常频繁的，所以数据库索引基本采用B+树

       （3) B+树的查询效率更加稳定

              由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。