\(11.2\)\(B\)树

1.\(B\)树的引入

  导致\(BST\)最坏运行时间的原因是：每次insert操作，我们都选择在叶子上进行，这导致了树的高度的增加。因此，一个自然的想法是：能否在不增加树的高度的前提下插入节点。

  为了达到这个目的，我们可以在一个叶子中插入多个节点，这样就不会导致叶子高度的增加了。

  但如果无限制地在一个叶子中插入，那么这个叶子就会退化成一个链表了。因此，我们可以对单个叶子能够装入节点的数量设置限度(\(limit\))，例如\(4\)。当叶子中节点个数超过\(4\)个时，就通过弹出中间的节点，把这个叶子分开(\(split\))。

2.\(2-3\)搜索树

  一棵\(2-3\)搜索树是满足如下条件的树：

• 空的(\(empty\))。
• 一个叶子存储一个节点，同时有两个链接(\(link\))，和\(BST\)类似。
• 一个叶子存储二个节点，同时有三个链接。设二个节点分别为\(x,y\)，则三个链接所指向的其它叶子分别满足\(a_i\leq x,x\leq a_i\leq y,a_i\leq y\)。

3.查找流程

  \(2-3\)搜索树查找节点的流程如下：

4.插入流程

  \(2-3\)搜索树插入节点的流程如下：

1. 我们仍然一直在左叶子进行插入操作。
2. 将节点插入对应的叶子时，如果该叶子的节点个数大于\(3\)，则弹出中间靠左的节点(如果是奇数个节点就直接弹出中间的)，然后相应地重新排列子树。
3. 重复上述步骤，直到找到一个有空位的父节点或者遍历到根节点。

  一些插入情况对应的图示如下：

  分开叶子的图示如下：