btree

b树

特性

1. 所有叶子结点在同一层
2. b树的最小度为t，度就是结点子树的个数
3. t - 1 <= len(elements) <= 2t - 1
4. t <= len(children) <= 2t
5. 结点len(children) = len(elements) + 1
6. 所有结点的key都是按递增顺序排序，关键字k1和k2之间的子树包含的所有关键字k1<key<k2
7. b树增长和收缩都是从root开始
8. 查询，插入，删除时间复杂度都是O(logn)

插入操作

所有插入的元素最终都会落在叶子结点，从根结点开始向下寻找合适的结点，途经的结点如果len(key)==2t-1，必须分裂成两个结点，中间key上移到父结点合适位置，分裂后的结点分别获得原始结点前半和后半的key以及child。

插入1，创建根结点

        | 1 |

插入2、3，无需分裂

        | 1 | 2 | 3 |

插入4，创建新的根结点，分裂原来的根结点作为叶子结点

        | 2 |
       /     \
    | 1 |   | 3 | 4 |

插入5

         | 2 |
       /     \
   | 1 |    | 3 | 4 | 5 |

插入6，分裂叶子结点，上移元素4到父结点

        | 2 | 4 |
      /     |     \
   | 1 |  | 3 |  | 5 | 6 |

插入7

        | 2 | 4 |
       /    |     \
   | 1 |  | 3 |  | 5 | 6 | 7 |

插入8，分裂上移元素6

        | 2 | 4 | 6 |
      /     |   |     \
  | 1 |  | 3 | | 5 |  | 7 | 8 |

插入9，分裂根结点，继续遍历，插入元素到叶子结点

               | 4 |
            /        \
       | 2 |         | 6 |
     /      \       /     \
 | 1 |    | 3 |   | 5 |   | 7 | 8 | 9 |

删除操作

从根结点向下寻找需要删除的key，途经的结点，假设要找的key在子树y上，y结点的key个数必须大于t-1，如果它有key个数大于t-1的临近兄弟z，从z获取一个key给当前结点，当前结点分配一个key给y结点。如果y没有key个数大于t-1的临近兄弟，合并兄弟，当前结点拿出一个key作为合并后的结点的中间key。 如果被删除的key在叶子结点，直接删除。 如果被删除的结点在非叶子结点，从key的左子树找到前驱key，判断左子树根结点长度是否大于等于t，满足条件则用前驱key替换要删除的key，再从左子树中删除前驱key，不满足条件从右子树找后继key，如果左子树右子树都不满足条件，合并左右子树，然后直接删除key。

b树

               | 4 |
            /        \
       | 2 |         | 6 |
     /      \       /     \
 | 1 |    | 3 |   | 5 |   | 7 | 8 | 9 |

删除9

        | 2 | 4 | 6 |
      /     |   |     \
  | 1 |  | 3 | | 5 |  | 7 | 8 |

删除8

        | 2 | 4 | 6 |
      /     |   |     \
  | 1 |  | 3 | | 5 |  | 7 | 

删除7

        | 2 | 4 |
       /    |     \
   | 1 |  | 3 |  | 5 | 6 | 

删除6

        | 2 | 4 |
       /    |     \
   | 1 |  | 3 |  | 5 |

删除5

       | 2 |
      /     \
   | 1 |   | 3 | 4 |

删除4

       | 2 |
      /     \
   | 1 |   | 3 |

删除3

       | 1 | 2 |

删除2

       | 1 |