从零开始学数据结构系列之第五章《B树了解以及定义》

本文主要是介绍从零开始学数据结构系列之第五章《B树了解以及定义》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

B树

下面的视频可以看一下，有助于理解下B树
七海讲数据结构-平衡树&B树【七海Nana7mi】

B树的定义

B-tree 即 B树，B 即 Balanced，平衡的意思。

B树 是一颗多路平衡查找树。

​   B树是所有结点的平衡因子均为0的多路平衡查找树。

​   B树是一种自平衡的树，一个节点可以拥有2个以上的子节点，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。

​   它与自平衡二叉查找树不同，B树的每个节点可以包含大量的关键字信息和分支，便于降低自己的高度，让自己更胖更矮，更加适用于读写相对大的数据块的存储系统，例如磁盘，可以减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

​   **在B树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。**因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，在这点名批评红黑树，但是由于节点没有被完全填充，可能浪费了一些空间。

B树的优势如下：

​   使关键字保持排序顺序以进行顺序遍历
​   使用分层索引来最大程度地减少磁盘读取次数
​   使用部分完整的块来加快插入和删除
​   使用递归算法使索引保持平衡
总之，B树操作不是很复杂，用途很广泛，正道的光，照在了数据结构的路上

一颗m阶的B树定义如下：

• 每一个节点最多有 m 个子节点
• 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ （向上取整）个子节点
• 如果根节点不是叶子节点，那么它至少有两个子节点
• 有 k 个子节点的非叶子节点拥有 k − 1 个键
• 所有的叶子节点都在同一层，叶子节点不包含任何关键字信息
• 除根节点外的所有非叶结点至少有棵子树，即至少含有个关键字

那怎么理解上面这五个的定义呢？

  首先这个m是什么意思呢，那这个 m 的话就是我们B树的阶数，例如我 m 等于五的时候，我这个就叫五阶 B 树。如果 m 等于三的话，那它就叫三阶 B 树。那有些地方的话可能也不叫阶而叫度，那具体叫法的话还是因教程而异，我们这里的话统一叫阶

1. 每一个节点最多有 m 个子节点

   1. m>=2,m=2时是二叉搜索树，那我们的二叉搜索数是不是相当于我们二阶 B树，每一个它的 m 是等于二，那我们它最多是有 m 个子节点，也就是2个子节点

2. 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ （向上取整）个子节点

   1. 那我们向上取整是什么意思呢？
      1. 例如我 n 等于五，那么五除以二的话是等于2.5，我们向上取整的话，那它这个最后的值是取3，那这个的话就是向上取整的意思
   2. 那我们对非叶子节点要怎么理解？
      1. 那 b 树的话本质上也是树，那它是逆向生长的，最顶端是它的根。那我们这样想的话，那最底端的话就是它的叶子节点，也是可以理解为它的最后一层，简单的话，我们可以看下面的图示，那可以看下图，而子的话，我们个这个可以理解成二叉平衡树。那二叉平衡树的最底端的话，那就是它的叶子节点。那除于我们蓝色框以外的话，那就是我们的非叶子节点

3. 如果根节点不是叶子节点，那么它至少有两个子节点

   1. 那这句话是什么意思呢？那这句话的根本目的就是为了防止 B 树 进行一个失衡，因为根据定义的话，我们 b 树本质上是一个平衡搜索树。如果它的非根子节点少于两个的话，那它的话就可以相当于一条斜着的那种链，那这样的话就会导致它本身就是失衡，导致计算机搜索便利数据的话呃时间冗长，所以的话这样的话会和它根本的定义产生冲突。所以我们如果根节点不是子节点的话，那么它的至少有两个子节点

4. 有 k 个子节点的非叶子节点拥有 k − 1 个键

   1. 非叶子节点的那一节点有k-1个键，他就有k棵子树

5. 所有的叶子节点都在同一层，叶子节点不包含任何关键字信息

   1. 我们的叶子节点最终指向的都是空。那这如果我们遍历到空的话，也就意味着我们在这棵 b 树上查找不到想要的数据，所以这就很好的造成了不用再额外的判断。如果找不到任何关键字信息，要怎么办
   2. 可以视为外部结点或类似于二分查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空
   3. 同理，我们的叶子节点，也就是我们最终存放的那个位置。为什么要在同一层？是因为它本质上也是一个平衡树，所以我们要最大程度的存放它的数据，所以要造成所有子节点要在同一层

6. 除根节点外的所有非叶结点至少有棵子树，即至少含有个关键字

   1. 那这样的话，例如我们五阶 b 数的话，那它最少是有两棵子树，最多含有4个子树。如果是三阶的话，那就是一个最少有一个子树，最多有两个子树
   2. 本质来说，也是为了防止它的一个失衡

那总的来说为什么这些个定义呢？

​ 那最终原因本质上还是来讲的话，就是为了防止它B树的一个失衡

---

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》
60【第四章】《迪杰斯特拉算法了解》
61【第四章】《Dijkstra 迪杰斯特拉算法图解》
62【第四章】《Dijkstra 迪杰斯特拉算法总代码》
63【第四章】《弗洛伊德(floyd)算法简介》
64【第四章】《弗洛伊德算法详解》
65【第四章】《弗洛伊德代码详解》
66【第四章】《拓扑排序之AOV网》
67【第四章】《拓扑排序介绍及其方法》
68【第四章】《拓扑排序代码详解》
69【第四章】《什么是关键路径》
70【第四章】《什么是关键路径二》
71【第四章】《关键活动与最早路径实现思想》
72【第四章】《关键活动与最早路径实现思想写法二》
73【第四章】《关键路径总代码讲解写法一》
74【第四章】《关键路径总代码讲解写法二》
75【第五章】《顺序查找》
76【第五章】《顺序查找-带哨兵》
76【第五章】《二分查找》

这篇关于从零开始学数据结构系列之第五章《B树了解以及定义》的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---