# B树

maple tree是B树的优化形式，为了更好的理解maple tree，这里先对B树做一个铺垫学习。

## B树的性质

B树是平衡搜索树的一种，对于一个m阶B树它的性质有：

* 平衡：所有的叶子节点都在一层
* 有序：节点内有序，左子树都小于它，右子树都大于它
* 多路：**最多**m-1个元素，根节点**最少**1个元素，其余节点**最少**(m/2上取整 - 1)个元素

而这些性质都是在树的操作上保证的。下面就看看B树的插入和删除操作

## 插入操作

先找到需要插入的node，此时一定是叶子节点。 插入后，如果节点没有上溢出，则结束。如果上溢出，则进行拆分动作，将多处的元素插入父节点。 再判断父节点。

下面用一张图来观察拆分动作。

假设执行插入后，节点有5个元素，已经上溢出。这时候就要执行拆分，以中间元素B为分割点拆分。

```
                            idx
                      +---+ +---+
                      | A | | C |
                      +---+ +---+
                     |     |     |
                     c0    c1    c2
                           /
                       /
                   /
               /
        +---+ +---+ +---+ +---+ +---+
        | X | | Y | | B | | J | | K |
        +---+ +---+ +---+ +---+ +---+
       |     |     |     |     |     |
       c10   c11   c12   c20   c21   c22
```

拆分后，B元素上移到父节点，而右半部分作为子树也插入父节点。

```
                            idx
                      +---+ +---+ +---+
                      | A | | B | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c'    c2
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+ +---+                       +---+ +---+
        | X | | Y |                       | J | | K |
        +---+ +---+                       +---+ +---+
       |     |     |                     |     |     |
       c10   c11   c12                   c20   c21   c22
```

## 删除操作

先找到需要删除的元素，如果该元素不在叶子节点，则找到其后继，并替换。总之确保是在叶子节点上做删除操作。 如果删除后，节点没有下溢出，那么删除操作完成。 此时再判断节点的兄弟，如果兄弟节点元素超过一半，那么就借一个过来。如果兄弟元素也不过，则合并。 如果是合并的，那么就往上走一层，看父节点是否下溢出。

### 借元素

我们先看看从兄弟节点上借元素的情况。

此时左子树的元素下溢出，我们要做的是把父节点上的元素拿来放到最后，然后把右子树的第一个孩子也拿过来。 然后右子树的第一个元素上移到父节点上。

```
                            idx
                      +---+ +---+ +---+
                      | A | | B | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c2    c3
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+ +---+                       +---+ +---+ +---+ +---+
        | X | | Y |                       | J | | K | | L | | M |
        +---+ +---+                       +---+ +---+ +---+ +---+
       |     |     |                     |     |     |     |     |
       c10   c11   c12                   c20   c21   c22   c23   c24
```

最后的结果是这样。

```
                            idx
                      +---+ +---+ +---+
                      | A | | J | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c2    c3
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+ +---+ +---+                 +---+ +---+ +---+
        | X | | Y | | B |                 | K | | L | | M |
        +---+ +---+ +---+                 +---+ +---+ +---+
       |     |     |     |               |     |     |     |
       c10   c11   c12   c20             c21   c22   c23   c24
```

### 合并兄弟

合并兄弟的操作实际是拆分操作的反向操作。

此时，左子树已经下溢出，其兄弟也没有足够的元素。 就需要把父节点的元素拉下来放到最后，然后把兄弟也加到后面。

```
                            idx
                      +---+ +---+ +---+
                      | A | | B | | C |
                      +---+ +---+ +---+
                     |     |     |     |
                     c0    c1    c2    c3
                           /     \
                       /             \
                   /                     \
               /                             \
        +---+                             +---+ +---+
        | X |                             | J | | K |
        +---+                             +---+ +---+
       |     |                           |     |     |
       c10   c11                         c20   c21   c22
```

最后的结果就像这样。

```
                            idx
                      +---+ +---+
                      | A | | C |
                      +---+ +---+
                     |     |     |
                     c0    c1    c3
                           /
                       /
                   /
               /
        +---+ +---+ +---+ +---+
        | X | | B | | J | | K |
        +---+ +---+ +---+ +---+
       |     |     |     |     |
       c10   c11   c20   c21   c22
```