什么是B-树、B树、B+树、B*树？
首先，B-tree树即B树。B即Balanced平衡，因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，这是个非常不好的直译，很容易让人产生误解，人们可能会以为B-树和B树是两种树。
1、B树
1.1、B树产生的背景
不管是二叉树、二叉查找树还是平衡二叉树，它们都有诸多限制，比如：
每个结点只能存储一个元素。
结点的度至多为2，即使是平衡二叉树，在存储百万、千万级别的数据量时，也会导致树的深度特别大，而深度大就会影响查找效率。
这里提一下平衡二叉树的缺点：
- 由于平衡二叉树需要左旋和右旋来调整树的结构，因此在频繁插入和删除的场景下，每插入或删除一个结点，都极有可能导致树的不平衡，性能也会大打折扣。红黑树（后面会介绍）就是来解决这个问题的。
前面讲的几种数据结构，都是纯内存操作，但是当数据量特别大（如数据库中千万级别的数据表、磁盘中的上万个文件等），内存都存不下了怎么办？在这种情况下，需要用外存（硬盘）来存储，而对数据的处理则需要不断地从硬盘调入调出。
此时，时间复杂度的计算就会发生变化，因为还要额外考虑对硬盘的访问次数和单次访问时间等。
为了降低对硬盘的访问次数，需要设计新的数据结构。前面讲的几种树，结点都只能存一个元素，因此，当元素非常多的时候，要么结点的度非常大，要么树的深度非常大，这两种情况都会导致对硬盘的访问次数偏大。如果每个结点能存多个元素，那么树的总结点数就会大大减少，对磁盘的访问次数也会相应的大大减少。
由于有如上限制，为此引入了多路查找树的概念。
多路查找树：结点的度可以大于2，并且每一个结点可以存储多个元素。由于是查找树，所以结点之间存在某种特定的排序关系。
1.2、B树的基本概念
B树是一种平衡的多路查找树。
其实B树和多路查找树是一个意思，网上很多资料也是这样认为的，但是也可以认为多路查找树和B树不是一个意思，因为多路查找树不一定是平衡的。
B树的阶：所有结点中的最大孩子数。其实跟树的度一个意思。
一个m阶B树的属性：
如果根结点不是叶子结点，则其至少有两颗子树。
[m/2]<=k<=m，[m/2]为向上取整，比如9阶B树，5<=k<=9。每一个非根分支结点都有k个孩子和k-1个元素；叶子结点有k-1个元素。
所有叶子结点在同一层（平衡）。
所有分支结点有下列信息数据：(n,A0,K1,A1,K2,A2,...,Kn,An)，n是结点存储的元素个数，Ai表示子树，Ki表示元素，而从A0到An的值是从小到大排序的，这跟二叉查找树的性质一样。
