B树，B+树，B*树（无代码）
B树：
应用场景：文件索引系统
在B树中，一个节点有m个地址域，m-1个数据域。这使得B树变得又矮又胖。树高的降低使得查找效率大大提升，但也使得代码变得复杂。
一棵m阶的B树需要满足：
1.每个节点最多有m个孩子
2.“除根节点和叶子节点”之外，其他每个节点至少有[ceil(m/2)]个孩子。（ceil函数取上限）对应一半的孩子。
3.“除根节点外”每个节点的关键字个数n必须满足：[ceil(m/2)]<=n<=m-1
注：m-1个数据域就有m个范围，例如1，2就有小于1，1到2，大于2三个范围，每个范围对应一个地址域
注：叶子节点和根节点不要求孩子数量，根节点不要求关键字数量
以5阶B树举例，每个节点最多5个孩子，除根节点和叶节点，每个节点至少3个孩子，除根结点外每个节点2到4个关键字。
插入时的节点上溢：对于一棵 m 阶 的B树，每个节点最多只能存储 m-1 个关键字。所以，当一个节点试图存储第 m 个关键字时，就必须进行分裂。这种情况我们称之为节点上溢 (Overflow)。
第一步：我们找到中间关键字，并把它插到溢出节点的父亲节点中。
第二步：我们将位于中间关键字左侧的所有关键字放入一个新的左子节点L中，同理放入一个新的右子节点R中。原来的节点被L和R替代。
第三步：父节点中，原来指向节点N的那个指针被移除，被替代为L和R
如果不断的分裂上溢最终使根节点也需要上溢，此时会创建一个全新的根节点，这个根节点只包含那个中间关键字，这也是B树高度增加的唯一方式。
删除时的节点下溢：下溢指的是：在一个节点删除一个关键字后，该节点的关键字数量少于B树规定的下限（⌈m/2⌉ - 1个关键字）。
情况一：如果要删除的关键字k就在叶子节点中
情况二：如果要删除的关键字k不在叶子节点中
第一步：找到k的直接前驱/后继 k'
第二步：用k'取代k，问题转化为删除直接前驱/后继中的k'，可以证明，k的直接前驱/后继必定位于叶子节点中，此时情况二归于情况一
情况一处理：
如果叶子节点也发生下溢，分为策略1和策略2
策略1：如果L的左右兄弟有一个富裕（大于最低下限），通过旋转来解决问题。
策略2：如果左右兄弟都不富裕，则“L”可以和“一个兄弟”以及“父节点中分割L和兄弟的关键字”直接合并。原来的L和兄弟节点被丢弃。由于我们从父节点中拿走了一个关键字，可能导致父节点也下溢。
如果下溢一直传递到根节点，导致根节点需要和它的子节点合并。合并后，根节点变空，新节点成为根。这是B树高度降低的唯一方式。
为什么B树在磁盘I/O上具有巨大优势
核心：B树的设计，完美地匹配了磁盘“读取缓慢，但一次能读很多”的物理特性，它通过“化零为整”的方式，最大限度地减少了与磁盘交互的次数。
问题的根源：磁盘I/O最耗时的部分是寻道（移动磁头到正确位置）。每一次I/O操作，无论你只读1个字节还是4KB，大部分时间都花在了这个物理动作上。减少磁盘I/O，是提升性能的王道。
传统二叉树的弊端：以AVL树和红黑树为例，它们每个节点都只存一个关键字，导致树又高又瘦。树高和最坏情况下磁盘I/O的次数相等，这样的代价是无法接受的。
B树的设计：在数据库或文件系统中，一个B树节点的大小通常被设计为与一个磁盘块/页（如4KB, 8KB）的大小相匹配。使树高及磁盘I/O次数急剧降低。
B+树：
B+树和B树主要的不同在：
1.于B+树的非叶节点存储的关键字不包括除了“索引”以外的其他信息，即使你在非叶子节点找到了目标节点，你也无法获取该节点的其他信息。（B树可以，因为B树的关键字存储的是完整的节点）
2.B+树的叶子节点包括所有的关键字的完整节点的信息，你只有可能在B+树的叶子节点查找到所需要的信息。
B+树这样设计的好处：
使B树的非叶节点能够存储更多的关键字，能够进一步的压缩树高，提高查询的效率，且性能极其稳定
B*树：一棵B*树相比B树的主要优化的地方在于，B*树对节点分裂和合并的策略有所不同。（B*树和B+树可以结合，二者不冲突）
对于B树和B+树，一旦节点满了之后，它会立刻进行一分为二的分裂，使分裂后的两个新节点，只满足二分之一的最低要求填充率
而B*树会看自己的兄弟是否有多余空间，然后把自己的部分关键字分享或移动给兄弟节点，使两个节点的填充率趋于均匀。
如果兄弟节点满了，此时，万不得已才进行分裂，但分裂方式为2分为3，使最低填充率从B树的1/2达到2/3。
B*树和B+树的取舍：由于B+树提供的简化模型和“足够好”的性能，以及其在范围查询上的巨大优势，使得它在数据库等领域成为了事实上的标准。B*树的实现复杂性，使得其带来的空间利用率提升在很多场景下并不足以弥补其开发和维护成本。