本文简单介绍B树和B+树的概念，以及它们有何区别，还有各自的适用场景。
一. B树
- B树的定义
B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。最坏查找情况是查完整个树的深度。
- B树的特点
如下中的M表示阶数：
- 根节点至少有两个子节点
- 每个节点有M-1个key，并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 除根节点外的其它节点至少有M/2个子节点
- B树示意图
下图是一个M=4阶的B树：
二. B+树
- B+树的特点
B+树是对B树的一种变形树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
- B+树示意图
三. B树和B+树的区别
B树和B+树的区别示意图：
- 本身数据结构上的区别
A. 关键字数量不同：B+树分支结点M个关键字，叶子节点也有M个；B树分支结点则存在 k-1 个关键码
B. 数据存储位置不同：B+树数据存储在叶子结点上；B树存储在每个结点上
C. 查询不同：B+树是从根节点到叶子节点的路径；B树是只需要找到数据就可以
D. 分支节点存储信息不同：B+树存索引信息；B树存的是数据关键字
- 性能上的区别
A. B+树的层级更少：相较于B树B+树的每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
B. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
C. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
D. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
E. B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
四. 应用场景
- B树和B+树存在的意义
二叉查找树的时间复杂度是Ｏ(logN)，效率已经足够高。为什么出现B树和B+树呢？当大量数据存储在磁盘上，进行查询操作时，需要先将数据加载到内存中（磁盘IO操作），而数据并不能一次性全部加载到内存中，只能逐一加载每个磁盘页（对应树的一个节点），并且磁盘IO操作很慢，平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。为了减少磁盘IO的次数，就需要降低树的深度，那么就引出了B树和B+树：每个节点存储多个元素，采用多叉树结构。这样就提高了效率，比如数据库索引，就是存储在磁盘上，采用的就是B+树的数据结构。
- B树应用场景
B树大量应用在数据库和文件系统当中。
它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数。B树算法减少定位记录时所经历的中间过程，从而加快存取速度。
- B+树应用场景
B+树应用于数据库的索引中，例如MySQL使用B+树作为索引。
