视频地址：7.5B树 - YouTube

阅读本章需要知识储备

B树诞生背景

由于多差查找树会导致不平衡，让查找效率不搞，因此就设置一套平衡机制来提高多叉树的查找效率，这就有了B树。B树是二叉搜索树的扩展。用空间复杂度换取时间复杂度。二叉搜索树是在内存中内存空间有限，而cpu查找内存速度快，所以二叉树就用时间换取空间。

B树定义

B树 B即Balanced，平衡的意思。在国内有经常将两者都写作B-树的情形， 是一种平衡的多路查找树（因此满足左 值<根值<右值的特性），2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。

满足以下规则就是B树:

规则一:m(m>=2)叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同（绝对平衡）。
规则二:m(m>=2)叉查找树中，规定除了根节点外（它有两个），任何结点至少有[m/2|个分叉，即至少含有[m/2|-1关键字

备注一：一棵树刚开始插入第一元素，它就根部，此时无法满足规则二。例如5叉树要求任何结点至少有3个分叉，即至少含有2关键字。但是把第一关键字插入根后，这是根结点无法满足规则二，因此要排除根。

—棵m阶B树或为空树，或为满足如下特性的m叉树:
1）树中每个结点至多有m棵子树，最多含有m-1个关键字("要满足查找树前驱和后继，所以两棵子树指针夹着一个关键字(value)，）

2)若根结点不是终端结点，则至少有两棵子树(因为要求绝对平衡)。
3)除根结点外(规则二)，每个结点至少有[m/2]个子树，至少含有(m/2)-1个关键字。

23树是个B数特例，实际用的B数一般都是一个结点几十上百个元素的

4)所有非叶结点的结构如下︰

  因为两个指针夹着一个关键字（前驱和后驱）所以指针比关键字（value）多一个。

5）所有的叶子（null指针）结点出现在同一层次上，不带信息（null指针）。(就像是折半查找判断树中查找失败的结点)

B树核心特性归纳成以下：

B树的查找操作

B树是多路查找树，二叉排序树是二路查找, B树是多路查找，所以它是二叉排序树的拓展
因此，B树的查找操作和二叉排序树的查找操作非常类似。
查找过程∶

①先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。
②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。
Eg:如果Key比第一个关键字K,还小，则去Po指针所指向的子树中查找，如果比最后一个关键字K,还
大，则去P,指针所指向的子树中查找。

 B树的插入操作

 重点是结点分裂

 n/2 向上取整。3/2=2 因此30作为新结点，20 和50作为子结点。

B树的删除操作

重点是结点合并

1)如果删除的关键字在终端结点上(最底层非叶子结点):
①结点内关键字数量大于[m/2]-1，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。
②结点内关键字数量等于[m/2]-1，并且其左右兄弟结点中存在关键字数量大于[m/2]-1的结点，则去兄弟阶段中借关键字。

③结点内关键字数量等于[m/2]-1，并且其左右兄弟结点中不存在关键字数量大于[m/2]-1的结点，则需要进行结点合并。

 2）如果删除的关键字不在终端结点上(最底层非叶子结点)︰需要先转换成在终端结点上，再按照在终端结点上的情况来分别考虑对应的方法。

 B树的应用

读取操作耗时比较长的外部设备（毫秒级别）的种的数据，例如磁盘 u盘。

 2-3树、2-3-4树

2-3树、2-3-4树是查找树,是B树的特例

因此满足左<根<右的特性。

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构。二叉树、链表、数组、队列、栈是内存中的数据结构