一棵m阶B树,或者是空树,或者满足如下特性
1. 树中每个节点最多有m棵子树,且至多有m-1个关键字
2.若根节点不是叶子节点,那么至少两棵子树,至少一个关键字
3.除了根节点以外的节点,每个非叶节点至少有m/2向上取整棵子树
4.所有叶子节点(在B树中视为外部结点)都在同一个层面上
5.各个结点内关键字按照升序或者降序排列
B树所有结点都包含信息
B树的插入,如果一个结点插入后关键字个数为m,那就需要进行分裂,如果影响到了根节点,会使得B树高度加一
分裂的具体过程,将中间的数提到上面即可,然后两边结点进行分裂
最多需要3h+1次IO操作(影响到根节点)
B树的删除,如果一个结点删除后关键字个数小于最少个数,那么就需要进行合并
删除的步骤:
1. 直接删除关键字(如果删除后没有破坏B树的性质)
2. 破坏了,兄弟够借,就是将兄弟的一个元素放到父亲,然后父节点的一个元素降落下来
3.兄弟不够借,那就将父亲的一个结点和自己的兄弟合并起来
在B+树中
1.每个关键字对应一棵子树
2.每个结点的关键字范围是m/2向上取整<=n<=m
3.叶子结点包含全部关键字,叶子结点包含信息,非叶子结点索引只包含对应子树最大关键字和指向该子树的指针
B+树的非叶子结点仅起到索引作用,查找成功需要查找到叶子结点,即每次查找长度都相同(保证查找公平性)
B+树支持顺序查找,所有叶子结点类似于一个链表结构
B树和B+树都能够有效支持随机查找