B-树(查询、插入、删除)

1 B-树简介

B-树是一种树状数据结构，它保持数据的排序，并允许在 对数平摊时间 内进行搜索、插入和删除。与自平衡二叉搜索树不同，它是针对读和写大数据块的系统进行优化的。它最常用于数据库和文件系统。

B-树是一种特殊的自平衡搜索树，其中每个节点可以包含一个以上的键，并且可以有两个以上的子节点。它是二叉搜索树的一种推广形式。它也被称为高度平衡的 m路树。

B-树的重要性质:

1. 对于每个节点 x，键是按递增顺序存储的。

2. 在每个节点中，都有一个布尔值x.leaf，如果x是一个叶子，则该值为真。

3. 如果n是树的阶，每个内部节点最多可以包含n - 1个键，以及指向每个子节点的指针。

4. 除根节点外，每个节点最多可以有n个子节点，且至少有n/2个子节点。

5. 所有的叶子都有相同的深度(即树的高度h)。因此，它确保了B-树避免了不平衡树的问题。

6. 根节点至少有 2 个子节点，并且包含至少1个键。

7. 如果n为1，那么对于任意高度为h且最小度为t>=2的n键B-树，

文章来源: wenyusuran.blog.csdn.net，作者：文宇肃然，版权归原作者所有，如需转载，请联系作者。

原文链接：wenyusuran.blog.csdn.net/article/details/123678645