超链接到网站怎么做视频文件,品牌网站建设解决方,网站传送门怎么做,中国传媒大学声明目录
B树的主要特性#xff1a;
B树的操作#xff1a;
B树的优点#xff1a;
为什么要发明出B-树#xff1f;
B树的概念和原理剖析
原理图讲解(部分讲解在图中)
初始化结点#xff1a;
处理数据数量计算(了解)
底层代码实现(加深理解) 前些日子我们学了AVl树
B树的操作
B树的优点
为什么要发明出B-树
B树的概念和原理剖析
原理图讲解(部分讲解在图中)
初始化结点
处理数据数量计算(了解)
底层代码实现(加深理解) 前些日子我们学了AVl树红黑树感受到了搜索树在底层和实际应用的广泛和其规则的复杂性今天我们继续学习一下原理也是搜索树的B-树。
B树是一种自平衡的树数据结构常用于实现数据库和文件系统的索引。它的设计目的是保持数据有序并允许高效的插入、删除和搜索操作。B树的特点是它的节点可以包含多个子节点而不是像二叉树那样每个节点只有两个子节点。这样可以减少树的高度从而减少查找和更新操作的时间复杂度。
B树的主要特性 有序性B树中的所有节点按升序排列这使得查找非常高效。每个节点包含一个键值的有序列表以及指向其子节点的指针。 多子节点与二叉树不同B树中的每个节点可以有多个子节点。节点中的键值和子节点之间有一定的关系子节点中的值总是介于父节点键值之间。 平衡性B树是平衡树它通过在插入和删除时重新分布节点的键值确保树的所有叶节点都位于同一层级上。因此查找的时间复杂度始终为 O(log n)其中 n 是树中的键值总数。 分支因子B树的分支因子通常称为阶数order决定了每个节点可以有多少个子节点。一个阶数为 mmm 的 B 树意味着每个节点最多可以有 m−1m-1m−1 个键和 mmm 个子节点。 高效磁盘访问由于每个节点可以存储多个键和指针B树减少了对磁盘的访问次数。因此B树在数据库管理系统和文件系统中广泛应用特别适用于处理大量需要存储在外存如硬盘上的数据。
B树的操作 查找查找操作从根节点开始逐层深入通过比较键值找到目标元素。每次查找时最多需要访问树的高度层数这使得查找效率较高。 插入插入时首先通过查找找到应插入的位置然后将新键值插入到合适的节点中。如果节点已满节点会被拆分部分键值上移到父节点中。 删除删除操作更为复杂如果直接删除某节点会导致树失衡因此可能需要将相邻节点的键值重新分配或者将节点合并以保持树的平衡性。
B树的优点
高效的插入、删除、查找操作特别是在处理大量数据时。保证树的高度始终较低从而减少操作的复杂度。适用于外存系统的索引结构因为它减少了对磁盘的访问次数。
常见的改进版本包括 B(B加)树它在叶节点中包含所有的数据并使用顺序链表链接叶节点从而提高了范围查询的效率。
为什么要发明出B-树
其实B-树最初被发明出来是为了解决磁盘上读取数据普遍较慢的问题。B-树即使用于内查找也适用于外查找。 这里有人就有意见了呀为什么别的数据结构不行偏偏要选择B-呢 首先由于磁盘数据过多假设需要查找磁盘里10亿个值我们可以看到以上图不同的数据结构的时间复杂度可以看出最优的就是哈希和平衡二叉树的那两个AVl树比红黑树相对选择条件更严格所以选择AVl树那也需要logn次也就是说10亿个数据就是30次可以查完虽然已经很短了但是磁盘的访问速度太慢了30次还是显得太多了。
那使用哈希表行不行呢虽然时间复杂度为o1但是由于会产生负面的哈希冲突问题所以比较难以处理多个数据重复映射到同一个位置比较麻烦
由于磁盘一般不存在空间不足的问题所以即便使用位图和布隆过滤器也是没有用的。
下面有更清晰的解释可供参考 所以最大的问题就是磁盘自己本身访问数据太慢了需要将次数降至个位数才行于是由于之前的搜索二叉树都是二叉的(一个根最多只有2个孩子节点)所以这里要想提高速率只能降低树的高度增加根节点的孩子个数(变成多叉)。
就这样B树就诞生了
B树的概念和原理剖析
1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树 (后面有一个B的改进版本B树然后有些地方的B树写的的是B-树注意不要误读成B减树)。一 棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质
1. 根节点至少有两个孩子//为了增加叉数而设置的
2. 每个分支节点都包含k-1个关键字和k个孩子其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数
3. 每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m
4. 所有的叶子节点都在同一层
5. 每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划 分 6. 每个结点的结构为nA0K1A1K2A2… KnAn其中Ki(1≤i≤n)为关键 字且Ki。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的 关键字均小于Ki1。 n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。 解析开始我们可以看到这个B树的规则还是比较复杂的。先理清楚几个概念
关键字就是每一层的节点个数(相当于根)
孩子就是每个关键字所引出的节点(相当于根的子节点)
从2和3规则可以看出B树是多叉搜索树如果阶数m为10那关键字最少为4最多为9孩子最少为5最多为10并且可以看出每层的关键字的个数总比其孩子节点少1说明有一个孩子必定同时是两个相邻的关键字的孩子。
第5条规则体现了其仍为搜索树需要按从大到小排列关键字才可以在后面分裂后通过取中位数的方式取到新的关键字(根)
说到分裂由于规则3每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m所以每行的关键字个数最多为阶数-1当插入的关键字的个数等于阶数m时就需要进行分裂分裂具体是怎么样的后面会体现。
原理图讲解(部分讲解在图中) 由于我们这边设的阶数为m 3但是我们必须给每行的关键字m个空间因为如果只给2个(对于m 3来说每行关键字最多为2)就无法判断是否关键字等于m是否需要分裂因为第3个数无法插入了多开一个空间方便判断磁盘很大的不差那一个空间
刚开始插入时由于还没有明显的头结点需要通过不断插入关键字来完成第一次分裂产生这也比较符合先利用已经开辟好的空间的逻辑 当第一次分裂完成后会产生一个新的单个头节点之后我们在插入节点的时候必须从叶子节点开始插入这样才不会剖坏之前已经插入的节点的位置因为B树仍然是搜索树。从上图也证明了一个结点可能会成为两个根的孩子的理论所以B树中根节点的个数不是其孩子的两倍因为根据图可以看出有些孩子被重复利用了且根节点是通过子节点分裂产生的。
分裂引起的根的移动需要连同着其孩子节点一起移动。种种异样表明B树的设计完全是为了插入数据的方便不是为了保持平衡而设计的所以和其他的搜索树不太一样。
这里关键是画图出来一下展示我画的图 初始化结点
根据规则6和演示图解就可以很轻松的得出每个结点的构造。 由于每个结点是有可能形成多叉的且一个结点可能会成为两个根的孩子所以一个结点会先有一个存放关键字的数组然后为了访问其孩子还需要一个存有指向此根的全部孩子的指针数组(这里不是单纯的左右指针那么简单了因为孩子有点多)另外根据上图还需要一个变量n统计关键字的个数(就是当层的结点数)由于我们之前的搜索树都还有一个指向其父亲结点的指针所以这里也可以考虑加入。
struct BTreeNode { //K _keys[M - 1]; //BTreeNodeK, M* _subs[M]; // 为了方便插入以后再分裂多给一个空间 K _keys[M];//关键字(本行节点) BTreeNodeK, M* _subs[M1];//子节点(快速连串访问体现树结构 BTreeNodeK, M* _parent;//父亲节点体现原本三叉链的本质结构 size_t _n; // 记录实际存储多个关键字
};
处理数据数量计算(了解)
实际情况运用B树时阶层通常会很大(B树阶层越大处理的节点数(关键字)就越多数据量就越大)所以我们以下定义形成一个1023阶层的4层的B树。
根据规则那么每个分支的关键字数最多就为m - 1 1023其孩子为m等于1024根据下图的逐层推算可以得出每行的关键字和孩子节点的个数。可以看出B树成功的通过压缩了高度同时存储了更多的数据 底层代码实现(加深理解)
欲知后事如何请听下文分解持续关注博主以解锁B树更多秘密
