个人简介免费模板下载,临沂网站优化如何,html素材免费下载,福田欧曼售后全国24小时服务电话文章目录 前言B树概念性质插入数据分析代码实现性能分析 B树概念特性插入数据分析应用 B*树概念B*树的分裂 总结B树系列的区别B树系列对比哈希和平衡搜索树 前言
前面我们所学习到的数据结构#xff0c;只能用来存储少量的数据#xff0c;因为内存大小是非常有限的#xff… 文章目录 前言B树概念性质插入数据分析代码实现性能分析 B树概念特性插入数据分析应用 B*树概念B*树的分裂 总结B树系列的区别B树系列对比哈希和平衡搜索树 前言
前面我们所学习到的数据结构只能用来存储少量的数据因为内存大小是非常有限的一般情况下也就几十个G面对海量数据时也就只能加载少部分数据到内存其它的都存在磁盘而与磁盘交换即IO速度是非常慢的
如下图以二叉平衡树为例树节点存的是磁盘中数据的地址当数据量非常庞大时这棵树的高度也就非常高而内存中为了存储更多的数据每个节点就不存储关键字只存储磁盘地址所以可能每到一层就需要进行一次磁盘IO所以就需要进行高度次磁盘IO效率很低 而使用哈希表效率虽然是O(1)但在一些极端场景下某个位置冲突很多导致访问次数剧增
B树
概念
为了解决前面所说的问题R.Bayer和E.mccreight提出了B树B树是一棵多叉平衡搜索树如下图B树中一个节点存储多个关键字这里的关键字一般也是磁盘地址磁盘查找效率低在于寻址慢而B树从两方面解决二叉平衡树的问题第一个是从二叉变多叉树的高度也就被降低了很多第二个是每个节点存储多个关键字及映射的值
性质
一颗M阶(m2)的B树是一颗平衡的M路平衡搜索树可以是空树性质如下
根节点至少有两个孩子
每个分支节点都包含k-1个关键字和k个孩子ceil(m/2) k mceil是向上取整函数
每个叶子节点都包含k-1个关键字ceil(m/2) k m
所有的叶子节点都在同一层
每个节点中的关键字从小到大排列节点中k-1个元素正好是k个孩子包含的元素的值域划分
每个节点的结构为(nA0K1A1K2A2… KnAn)Ki(1in)为关键字且Ki Ki 1 (1in-1)Ai(0in)为指向子树根节点的指针且Ai所指子树所有节点中的关键字均小于Ki 1n为节点中关键字的个数满足ceil(m/2)-1nm-1
插入数据分析
为了简单起见这里M3且将节点的孩子个数和关键字个数均在原来的基础上多加1个如下图 插入53、139、75如下图按照类似插入排序的方式保持关键字有序 上面关键字已经满了就需要进行分裂将关键字中的中位数提出来插入到新建的父节点中同时新建一个兄弟节点将一半关键字分给兄弟节点并将对应的一半孩子节点也分给兄弟最后父节点指向两个孩子节点 插入49145从根节点开始查找比它小就在左边节点比它大就往后继续走 插入36 插入101 综上所述可以看出B树的插入过程是一个自左向右自底向上的过程当节点关键字满了就分裂然后往上插入节点再满就再分裂依次类推
代码实现
为了便于分裂多给了一个孩子和一个关键字同时给一个父节点指针便于后面插入节点 给定一个根节点 查找关键字如果待插入的关键字小于当前节点的关键字就直接跳到当前节点的孩子节点如果是大于当前节点的关键字就继续往后走否则要找的关键字就在当前节点返回该节点和关键字在当前节点中的下标找完叶子节点都没有找到就说明不存在返回最后找的叶子节点和-1的下标的键值对 插入关键字类似于插入排序值得注意的是孩子节点的位置也需要变动同时如果有孩子节点还需要指向孩子节点而孩子节点指向父亲 插入数据操作首先要判断是不是第一个关键字如果是就创建一个新节点并将关键字插入其中即可 查找当前关键字是否存在存在就直接返回即可 因为可能会涉及自底向上的连续分裂所以需要多加一层死循环如果插入关键字后的节点没有满就直接返回即可 分裂节点首先要找到节点的中位数的下标然后创建兄弟节点分一半关键字和孩子节点给兄弟清空原节点已经不存在的关键字和孩子节点最后更新两个节点的关键字个数 当前节点没有根节点就创建新的根节点然后将原节点关键字的中位数插入到根节点同时根节点指向这两个孩子节点最后两个孩子节点指向父亲节点有根节点就将key更新为中位数原节点更新为它的父节点等待下次循环插入关键字 验证这棵树是否正确可以采用中序遍历的方式查看是否有序即可不过这无法判断指向父节点的指针的指向是否正确这就需要通过监视窗口去看了
性能分析
如下图磁盘IO的次数近似为以M为底N为真数的对数其中M为树的度N为关键字的个数
B树
概念
B树是B树的变形规则和B树基本类似但在B树的基础上进行了一些优化如下所示
分支节点的子树指针与关键字个数相同
分支节点的子树指针p[i]指向的关键字值大小在[k[i]k[i1]]之间
所有叶子节点增加一个链接指针链接在一起
所有关键字及其映射的数据都在叶子节点出现
如下图就是一颗B树分支节点与叶子节点有重复的值分支节点存的是叶子节点的索引父节点中存的是孩子节点中的最小值做索引
特性
所有关键字都出现在叶子节点的链表中且链表中的节点都是有序的
不可能在分支节点中命中
分支节点相对于是叶子节点的索引叶子节点才是存储数据的数据层
插入数据分析
插入53139754914536101
应用
B树应用于数据库索引
B*树
概念
B*树是B树的变形在非根和非叶子节点上再增加指向兄弟节点的指针如下图
B*树的分裂
当一个节点满时如果它的下一个兄弟节点未满则将一部分数据移到兄弟节点中再在原节点插入关键字最后修改父节点中兄弟节点的关键字如果兄弟也满了则在原节点与父节点之间增加新节点并各复制1/3的数据到新节点最后在父节点增加新节点的指针
总结
B树系列的区别
B树有序数组 平衡多叉树
B树有序数组链表 平衡多叉树
B*树更丰满的空间利用率更高的B树
B树系列对比哈希和平衡搜索树
B树系列有一些隐形坏处
空间利用率低消耗高
插入删除数据时分裂和合并节点必然要挪动数据
虽然高度更低但在内存中而言跟哈希和平衡搜索树是一个量级
结论B树系列在内存中体现不出优势
