B树是一种自平衡多路搜索树,能够保持数据有序。它能够使搜索,插入和删除在O(log n)的时间复杂度内完成。我们描述一颗B树时需要指定它的阶数,阶数表示了一个结点最多有多少个孩子结点,一般用字母m表示阶数。当m取2时,就是我们常见的二叉搜索树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html
B树具有以下特点:
B树中每个节点至少有两个子节点,至多有2 * 阶数个子节点。 B树中所有从根节点到叶节点的路径长度相同或者相差不超过1。 B树中每个非终端节点至少有[Math.ceil(阶数/2)-1]个子节点。 B树搜索,插入和删除的时间复杂度为O(h),其中h是B树的高度。由于B树的高度与节点个数logN成正比,因此B树的时间复杂度为O(logN)。 B树中存储的节点个数在每个节点层次上至少增加一倍,因此B树的节点个数在每增加一层高度时至少增加一倍。所以B树的高度与logN成正比。 B树支持范围查询,可以在O(logN + M)的时间内返回数据值在[a, b]之间的所有节点,其中M为查询结果中的节点个数。
B树的优点:
由于每个节点可以有多个子节点,因此B树的高度较小,这使得搜索更加高效。 B树的节点个数至少是阶数的一半,这使得B树非常稳定,即使在进行大量插入和删除操作后,B树的高度也不会变得太高或太矮。 由于每个节点包含多个元素,因此B树中较少的节点就可以包含大量的数据。这使得B树非常适合管理大量的数据。B树是许多数据库系统中最常用的索引结构,因为它可以在保持有序的同时进行高效的插入、删除和搜索操作。
B树的操作
一,B树的搜索过程
B树的搜索操作
搜索B树的过程与二叉查找树类似。我们始终沿着指向子节点的指针向下遍历,直到到达叶节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html
例如,我们以查找0005号节点为例,查找的流程大体如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html
首先拿到根节点【0004和0008】,与0005进行比较,因为0005大于0004,小于0008,所以需要到0004的右子树的节点继续查找(二分法规则,左小右大,左边放小于当前节点值的子节点、右边放大于当前节点值的子节点); 将0005节点与0006节点进行比较,因为0005小于0006,所以应该到0006左边的树中进行查找; 将0005节点与0005节点进行比较,刚好相等,于是就找到了目标节点
B树的平衡是通过拆分节点来实现的。当插入或删除操作后,如果某个节点的子节点个数小于阶数的一半或者大于阶数,就需要进行节点的拆分或者合并来保持B树的平衡,这种调整被称为树的重组。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html
B树的插入操作
插入操作首先需要找到要插入的新键的插入位置。一旦找到插入位置,就需要进行以下步骤:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html
如果该节点的子节点个数小于阶数,则直接将新键插入到该节点中。 否则,需要将该节点拆分为两个节点,并将键的值从中间拆分开。新键插入到适当的节点中。 如果在第1步或第2步中,新节点的父节点的子节点个数达到最大值,就需要继续向上拆分直到根节点。 如果在第3步中,根节点的子节点也达到最大值,则需要创建一个新的根节点,并将原来的根节点拆分,新键插入到新根节点中。
B树的删除操作
删除操作也需要先找到要删除的键的位置。删除操作可以分为三种情况:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html
删除的节点在叶节点:直接删除该键即可。 删除的节点有一个子节点:用子节点替代该节点。 删除的节点有两个子节点:用后继节点或者前驱节点替代该节点。后继节点是该节点中键值大于该节点键值的最小的节点。前驱节点是该节点中键值小于该节点键值的最大的节点。
B树的节点的合并操作如下:
如果一个节点的子节点个数小于阶数的一半,则需要与相邻的兄弟节点进行合并。 将该节点和其中一个相邻的兄弟节点合并,兄弟节点的子节点变为被合并节点的子节点。 被合并节点的父节点的子节点个数减一。如果父节点的子节点个数小于阶数的一半,就需要继续向上合并。 合并到根节点时,如果根节点只剩下一个子节点,就需要将整个B树减去一层高度,也就是删除根节点,将其唯一的子节点变为新的根节点。
最后我们看文章中B树的特点中的红色字体部分:B树中每个非终端节点至少有[Math.ceil(阶数/2)-1]
个子节点, 那这个是为什么呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4547.html