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
Last updated