【数据结构】B-树概念 解决你对概念的疑惑（B-树的阶和度的关系）

目录

概念

对于变量（k,m）的解释

m代表阶数

阶和度的区别

k代表key，反映了节点的元素个数以及节点的孩子个数

节点的元素个数

k的取值范围

对于概念5的解释

为什么使用B-树

B-树的查找

---

概念

m阶B-树的具有一下几个特征

        1.跟节点至少有两个子女。

        2.每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m（这里m/2是向上取整）

        3.每个叶子结点都包含k-1个元素，其中m/2<=k<=m（这里m/2是向上取整）

        4.所有叶子结点位于同一层

        5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分

对于变量（k,m）的解释

这里k和m的定义并不是很明确，接下来将会解释一下这几个变量

m代表阶数

阶和度的区别

这里阶和度并不是一个概念

        首先我们可以先看一下两者的概念

                阶：m阶是代表每个节点最多有m个分支（子树）

                树的度：为m代表这棵树度最大的节点为m

                节点的度：代表当前节点有几个孩子

B-树的阶是先有阶数，然后根据阶数来构建树的

而树的度是树构建完成后根据树来决定度是多少的

比如我们想建立一个5阶B-树

这颗树为一棵5阶B-树，完全符合概念，但是这棵树的度只有4

严格来讲，这两个名词的概念完全不同

k代表key，反映了节点的元素个数以及节点的孩子个数

节点的元素个数

节点的元素个数就是指这个节点能够存储几个数据

也就是说对于红框中的数据个数

k的取值范围

我们根据定义可以看出，对一棵m阶的B-树来讲，这棵树的k为m/2取上界到m

对于一棵4阶B-树来说，这棵树的k为2到4之间，每个节点的元素只能在1到3之间，中间节点只能有2到4个孩子

对于一棵5阶B-树来说，这棵树的k为3到5之间，每个节点的元素只能在2到4之间，中间节点只能有3到5个孩子

对于图中的节点，节点的元素为3，节点有4个孩子，满足B-树的条件

对于概念5的解释

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分

这句话比较抽象难懂，但是可以通过举例来解释

对于元素的顺序，是按照如图所示的箭头来排序的，对于一个节点，节点内部的元素是按照从小到大的顺序排列的，他的第一个元素肯定大于最左边的孩子节点，并且小于左边第二个孩子节点的第一个节点，第二个元素肯定在左边第二个节点的元素和左边第三个元素之间的

由此可以的出，节点的第k-1个元素（元素从0开始，k从1开始）肯定在左边第k个节点元素和左边第k-1个元素大小之间的

为什么使用B-树

        在计算机的逻辑中，数据是存储在磁盘中的，当需要调用数据的时候，我们需要将磁盘中的数据加载到内存中，然后供CPU进行操作，在内存中对数据的处理速度是远高于磁盘IO的速度的，所以速度损耗一般发生在磁盘的IO速度上

        而树的一个节点就对应着一个磁盘页，而查询次数最坏情况下就是树的高度

        所以为了查询速度，我们要尽可能的减少磁盘的IO次数，从而变成在内存中的处理，这样可以大大提高查询速度，这样我们就可以通过降低树的高度，然后往同一个磁盘页中加入在不超过磁盘容量的基础上尽可能多的数据，这样就可以提高效率

        也就是通过在同一个节点多存放几个元素来达到树的高度变矮的操作，所以就需要用到B-树

B-树的查找

主要分为两步

        第一步与当前节点中的数据进行对比，判断是不是在当前节点中，如果不在的话判断要进入当前节点的哪一个子树

        第二步进入子树

比如要查询的数值为5

首先会在根节点进行查找对比

 第二次查找对比

 第三次查找对比

参考文章

B树详解 - 简书

漫画：什么是B-树？