B树核心知识点总结

B树是一棵平衡树，即各子树高度一致，且每个节点中存放的关键字数量t通常远大于2（通常是1000左右）。

B树是一棵有根树（设为T.root），所有节点具有如下性质：

1）每个节点node具有如下属性：

node.n，存储node中的关键字数量；

node.n个关键字本身node.key1，node.key2，…，node.keyn以非降序方式存放；

node.leaf是一个布尔值，标示当前节点是否是叶子节点；

2）每个内部节点（非叶子节点）node包含指向node.n+1个孩子节点的指针：node.c1,…,node.cn+1；

3）关键字node.keyi对各个子树中的关键字加以分割，假设其左右孩子分别为node.ci、node.ci+1，则node.ci中的所有关键字不大于node.keyi，node.ci+1的所有关键字不小于node.keyi；

4）每个叶子节点具有相同的深度；

5）每个节点保护的关键字个数有规定的取值范围，由B树的度d（>=2）决定：

除根节点外，其它节点至少有d-1个关键字，即除根节点外，所有节点至少包含d个孩子节点。如果树非空，根节点至少有个关键字。（注释：这里没有说根节点只有一个关键字）

每个节点之多包含2d-1个关键字。因此，一个内部节点，至多有2d个节点，当一个节点恰好有2d-1个节点时，则称此节点是满的（非常重要，插入删除操作需要关注的重点）

6）B树的高度h满足：h<=logd((n+1)/2)。

查询操作

查询操作的执行时间分为两部分：1）内存类遍历时间O(t)；2）读写磁盘次数为O(h)，设读取一次磁盘的时间为T，则总时间为：O(ht)+TO(h)。

插入操作

分析BTreeInsert，读取磁盘的次数为O(h)，分裂B树的次数也为O(h)，即写磁盘的次数也为O(h)，因此读写总次数为O(h)。

B树删除

实际的时间复杂度通常可以认为是O(log n)，这里的n是树中元素的数量。

【广告时间：阿里云小站官方上云，近期优惠就用阿里云ECS云服务器。】