深圳做网站比较好天涯,网站建设考核,事业单位网站建设方案策划书,网站有备案是正规的吗写目录 一、B树的基本概念1.引入2.B树的概念 二、B树的实现1.B树的定义2.B树的查找3.B树的插入操作4.B树的删除5.B树的遍历6.B树的高度7.整体代码 三、B树和B*树1.B树2.B*树3.总结 一、B树的基本概念
1.引入
我们已经学习过二叉排序树、AVL树和红黑树三种树形查找结构#x… 写目录 一、B树的基本概念1.引入2.B树的概念 二、B树的实现1.B树的定义2.B树的查找3.B树的插入操作4.B树的删除5.B树的遍历6.B树的高度7.整体代码 三、B树和B*树1.B树2.B*树3.总结 一、B树的基本概念
1.引入
我们已经学习过二叉排序树、AVL树和红黑树三种树形查找结构但上述结构适用于数据量相对不是很大能够一次性放进内存中进行数据查找的场景。如果数据量非常大比如由100G数据无法一次放进内存中那就只能放在磁盘上了。此时想要搜索数据就需要将存放关键字及其映射的数据的地址放到内存中的搜索树的节点中那么要访问数据时先取这个地址去磁盘访问数据。 但是由于磁盘访问的速度很慢对于上述树形查找结构来说就是需要logN次的IO这是一个很难接受的结果。 那么如何加速对数据的访问呢
提高IO的速度SSD相比传统机械硬盘是快了不少但还是没有得到本质性的提升降低树的高度——多路平衡查找树
2.B树的概念
B树是一种平衡的多叉树。一颗m阶(m2)的B树是一棵的m路平衡搜索树它可以是空树或者满足以下性质
根节点至少有两个孩子。每个分支节点都包含k-1个关键字和k个孩子其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数。每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m。所有的叶子节点都在同一层。每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分。每个结点的结构为nA0K1A1K2A2… KnAn其中Ki(1≤i≤n)为关键字且KiKi1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki1。 n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。
二、B树的实现
1.B树的定义
为了方便学习我们在这里先将m设为3这时每个结点能存2个关键字和3个孩子。不过为了方便后续插入分别额外多开了一个空间。
templateclass K, size_t M
struct BTreeNode
{K _keys[M]; // 用于存储关键字BTreeNodeK, M* _subs[M 1]; // 用于存储孩子BTreeNodeK, M* _parent; size_t _n; // 存储当前孩子的数量BTreeNode(){for (size_t i 0; i M; i){_keys[i] K();_subs[i] nullptr;}_subs[M] nullptr;_parent nullptr;_n 0;}
};2.B树的查找
查找的具体步骤应该是先进入根结点如果等于data1则返回如果小于data1则进入child1如果大于data1则i此时i指向data2若小于data2则进入child2若大于data2则进入child3。
pairNode*, int Find(const K key)
{Node* parent nullptr;Node* cur _root;while (cur){size_t i 0;while (i cur-_n) // 在当前结点进行查找{if (key cur-_keys[i]) // 如果小于则进入与当前下标相同的孩子{break;}else if (key cur-_keys[i]) //如果大于则i{i;}else{return make_pair(cur, i); // 找到了就返回当前结点以及该关键字所在的位置}}parent cur;cur cur-_subs[i];}return make_pair(parent, -1); //找不到返回父结点
}3.B树的插入操作
用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下 插入过程总结
如果树为空直接插入新节点中该节点为树的根节点树非空找待插入元素在树中的插入位置(注意找到的插入节点位置一定在叶子节点中)检测是否找到插入位置(假设树中的key唯一即该元素已经存在时则不插入)按照插入排序的思想将该元素插入到找到的节点中检测该节点是否满足B-树的性质即该节点中的元素个数是否等于M如果小于则满足如果插入后节点不满足B树的性质需要对该节点进行分裂 申请新节点找到该节点的中间位置将该节点中间位置右侧的元素以及其孩子搬移到新节点中将中间位置元素以及新节点往该节点的双亲节点中插入即继续4 如果向上已经分裂到根节点的位置插入结束
// 插入操作中用到的函数
void InsertKey(Node* node, const K key, Node* child) // 插入新关键字
{int end node-_n - 1;while (end 0){if (key node-_keys[end]){node-_keys[end 1] node-_keys[end];node-_subs[end 2] node-_subs[end 1];--end;}else{break;}}node-_keys[end 1] key;node-_subs[end 2] child;if (child){child-_parent node;}node-_n;
}
// B树的插入
bool Insert(const K key)
{if (_root nullptr) //如果根结点为空{_root new Node;_root-_keys[0] key;_root-_n;return true;}pairNode*, int ret Find(key); // 借助查找操作来判定是否存在要插入的值if (ret.second 0) // 如果不存在则可以找到要进行插入的位置{return false;}Node* parent ret.first;K newKey key;Node* child nullptr;while (1){InsertKey(parent, newKey, child); // 先利用插入排序的方法进行插入if (parent-_n M) // 如果没有破坏B树的性质则返回true{return true;}else // 否则进行分裂操作{size_t mid M / 2;Node* brother new Node;size_t i mid 1;size_t j 0;for (; i M; i) // 把一半的数据分给新建的兄弟结点{brother-_keys[j] parent-_keys[i];brother-_subs[j] parent-_subs[i];if (parent-_subs[i]){parent-_subs[i]-_parent brother;}j;// 拷走重置一下方便观察parent-_keys[i] K();parent-_subs[i] nullptr;}brother-_subs[j] parent-_subs[i];if (parent-_subs[i]){parent-_subs[i]-_parent brother;}parent-_subs[i] nullptr;brother-_n j;parent-_n - (brother-_n 1);K midKey parent-_keys[mid];parent-_keys[mid] K();if (parent-_parent nullptr) // 如果没有父结点则新建{_root new Node;_root-_keys[0] midKey;_root-_subs[0] parent;_root-_subs[1] brother;_root-_n 1;parent-_parent _root;brother-_parent _root;break;}else // 有父结点则将插入排序的参数修改然后回到循环开始插入{newKey midKey;child brother;parent parent-_parent;}}}return true;
}B树插入的代码实现非常复杂需要十分细心要注意对结点的维护。
4.B树的删除
B树的删除分为3种情况
直接删除关键字若删除当前关键字后仍然满足B树定义则直接删除该关键字。兄弟够借若再删除一个关键字就会破坏B树定义并且左右兄弟的关键字个数大于等于ceil(m/2)则需要调整该结点、右或左兄弟结点及其父结点父子换位法以达到新的平衡。兄弟不够借若左、右兄弟结点的关键字个数都不足以被借则将关键字删除后与左或右兄弟结点及父结点的关键字进行合并。
由于B树的删除用代码实现非常复杂就不多讲了。
5.B树的遍历
B树的遍历就不难了与查找的过程类比即可。
void _InOrder(Node* cur)
{if (cur nullptr)return;// 左 根 左 根 ... 右size_t i 0;for (; i cur-_n; i){_InOrder(cur-_subs[i]); // 左子树cout cur-_keys[i] ; // 根}_InOrder(cur-_subs[i]); // 最后的那个右子树
}void InOrder()
{_InOrder(_root);
}6.B树的高度
B树的效率取决于B树的高度因为磁盘存取次数与高度成正比。 若n1则对任意一颗包含n个关键字、高度为h、阶数为m的B树
若让每个结点中的关键字个数达到最多则容纳同样多关键字的B树的高度达到最小。因为B树种每个结点最多有m棵子树m-1个关键字所以在一颗高度为h的m阶B树中关键字的个数应满足 n ( m − 1 ) ( 1 m m 2 . . . m h − 1 ) m h − 1 n(m-1)(1mm^2...m^{h-1})m^h-1 n(m−1)(1mm2...mh−1)mh−1因此有 h l o g m ( n 1 ) hlog_m(n1) hlogm(n1)若让每个结点中的关键字个数达到最少则容纳同样多关键字的B树高度达到最大。第一层至少有1个结点第二层至少有两个结点除根结点外的每个非叶结点至少有ceil(m/2)棵子树则第三层至少有2ceil(m/2)个结点……第h1层至少有 2 ( c e i l ( m / 2 ) ) h − 1 2(ceil(m/2))^{h-1} 2(ceil(m/2))h−1个结点注意到第h1层是不包含任何信息的叶结点。对于关键字个数为n的B树叶结点即查找不成功的结点为n1由此有 n 1 2 ( c e i l ( m / 2 ) ) h − 1 n12(ceil(m/2))^{h-1} n12(ceil(m/2))h−1即 h l o g c e i l ( m / 2 ) ( ( n 1 ) / 2 ) 1 hlog_{ceil(m/2)}((n1)/2)1 hlogceil(m/2)((n1)/2)1。
7.整体代码
#include iostream
using namespace std;templateclass K, size_t M
struct BTreeNode
{K _keys[M];BTreeNodeK, M* _subs[M 1];BTreeNodeK, M* _parent;size_t _n;BTreeNode(){for (size_t i 0; i M; i){_keys[i] K();_subs[i] nullptr;}_subs[M] nullptr;_parent nullptr;_n 0;}
};templateclass K, size_t M
class BTree
{typedef BTreeNodeK, M Node;
public:pairNode*, int Find(const K key){Node* parent nullptr;Node* cur _root;while (cur){size_t i 0;while (i cur-_n) // 在当前结点进行查找{if (key cur-_keys[i]) // 如果小于则进入与当前下标相同的孩子{break;}else if (key cur-_keys[i]) //如果大于则i{i;}else{return make_pair(cur, i); // 找到了就返回当前结点以及该关键字所在的位置}}parent cur;cur cur-_subs[i];}return make_pair(parent, -1); //找不到返回父结点}void InsertKey(Node* node, const K key, Node* child) // 插入新关键字{int end node-_n - 1;while (end 0){if (key node-_keys[end]){node-_keys[end 1] node-_keys[end];node-_subs[end 2] node-_subs[end 1];--end;}else{break;}}node-_keys[end 1] key;node-_subs[end 2] child;if (child){child-_parent node;}node-_n;}bool Insert(const K key){if (_root nullptr) //如果根结点为空{_root new Node;_root-_keys[0] key;_root-_n;return true;}pairNode*, int ret Find(key); // 借助查找操作来判定是否存在要插入的值if (ret.second 0) // 如果不存在则可以找到要进行插入的位置{return false;}Node* parent ret.first;K newKey key;Node* child nullptr;while (1){InsertKey(parent, newKey, child); // 先利用插入排序的方法进行插入if (parent-_n M) // 如果没有破坏B树的性质则返回true{return true;}else // 否则进行分裂操作{size_t mid M / 2;Node* brother new Node;size_t i mid 1;size_t j 0;for (; i M; i) // 把一半的数据分给新建的兄弟结点{brother-_keys[j] parent-_keys[i];brother-_subs[j] parent-_subs[i];if (parent-_subs[i]){parent-_subs[i]-_parent brother;}j;// 拷走重置一下方便观察parent-_keys[i] K();parent-_subs[i] nullptr;}brother-_subs[j] parent-_subs[i];if (parent-_subs[i]){parent-_subs[i]-_parent brother;}parent-_subs[i] nullptr;brother-_n j;parent-_n - (brother-_n 1);K midKey parent-_keys[mid];parent-_keys[mid] K();if (parent-_parent nullptr) // 如果没有父结点则新建{_root new Node;_root-_keys[0] midKey;_root-_subs[0] parent;_root-_subs[1] brother;_root-_n 1;parent-_parent _root;brother-_parent _root;break;}else // 有父结点则将插入排序的参数修改然后回到循环开始插入{newKey midKey;child brother;parent parent-_parent;}}}return true;}void _InOrder(Node* cur){if (cur nullptr)return;// 左 根 左 根 ... 右size_t i 0;for (; i cur-_n; i){_InOrder(cur-_subs[i]); // 左子树cout cur-_keys[i] ; // 根}_InOrder(cur-_subs[i]); // 最后的那个右子树}void InOrder(){_InOrder(_root);}
private:Node* _root nullptr;
};void TestBtree()
{int a[] { 53, 139, 75, 49, 145, 36, 101 };BTreeint, 3 t;for (auto e : a){t.Insert(e);}t.InOrder();
}三、B树和B*树
1.B树
B树是B树的变形是在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又在B树的基础上做了以下几点改进优化
分支节点的子树指针与关键字个数相同分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1])区间之间所有叶子节点增加一个链接指针链接在一起所有关键字及其映射数据都在叶子节点出现 B树的特性
所有关键字都出现在叶子结点的链表中且链表中的结点都是有序的。不可能在分支结点中命中。分支结点相当于是叶子结点的索引叶子结点才是存储数据的数据层。
B树的分裂 当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增 加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向 兄弟的指针。
2.B*树
B*树是B树的变形在B树的非根和非叶子节点再增加指向兄弟节点的指针。
B*树的分裂 当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结 点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如 果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父 结点增加新结点的指针。 所以B*树分配新结点的概率比B树要低空间使用率更高
3.总结
通过以上介绍大致将B树B树B*树总结如下
B树有序数组平衡多叉树B树有序数组链表平衡多叉树B*树一棵更丰满的空间利用率更高的B树。 文章转载自： http://www.morning.skrrq.cn.gov.cn.skrrq.cn http://www.morning.hrtwt.cn.gov.cn.hrtwt.cn http://www.morning.kzcz.cn.gov.cn.kzcz.cn http://www.morning.dmjhp.cn.gov.cn.dmjhp.cn http://www.morning.bklhx.cn.gov.cn.bklhx.cn http://www.morning.tgfsr.cn.gov.cn.tgfsr.cn http://www.morning.csjps.cn.gov.cn.csjps.cn http://www.morning.qfgxk.cn.gov.cn.qfgxk.cn http://www.morning.qjxxc.cn.gov.cn.qjxxc.cn http://www.morning.zlxkp.cn.gov.cn.zlxkp.cn http://www.morning.rckmz.cn.gov.cn.rckmz.cn http://www.morning.ldwxj.cn.gov.cn.ldwxj.cn http://www.morning.dyfmh.cn.gov.cn.dyfmh.cn http://www.morning.fbrshjf.com.gov.cn.fbrshjf.com http://www.morning.lwwnq.cn.gov.cn.lwwnq.cn http://www.morning.tgpgx.cn.gov.cn.tgpgx.cn http://www.morning.gbybx.cn.gov.cn.gbybx.cn http://www.morning.wmfmj.cn.gov.cn.wmfmj.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.xoaz.cn.gov.cn.xoaz.cn http://www.morning.xgkxy.cn.gov.cn.xgkxy.cn http://www.morning.drggr.cn.gov.cn.drggr.cn http://www.morning.nwpnj.cn.gov.cn.nwpnj.cn http://www.morning.rkxqh.cn.gov.cn.rkxqh.cn http://www.morning.bqwrn.cn.gov.cn.bqwrn.cn http://www.morning.xjmyq.com.gov.cn.xjmyq.com http://www.morning.gjwkl.cn.gov.cn.gjwkl.cn http://www.morning.gjxr.cn.gov.cn.gjxr.cn http://www.morning.qwnqt.cn.gov.cn.qwnqt.cn http://www.morning.bmlcy.cn.gov.cn.bmlcy.cn http://www.morning.bloao.com.gov.cn.bloao.com http://www.morning.rhwty.cn.gov.cn.rhwty.cn http://www.morning.pdwny.cn.gov.cn.pdwny.cn http://www.morning.rzcbk.cn.gov.cn.rzcbk.cn http://www.morning.cwcdr.cn.gov.cn.cwcdr.cn http://www.morning.rqbr.cn.gov.cn.rqbr.cn http://www.morning.qhmgq.cn.gov.cn.qhmgq.cn http://www.morning.jqcrf.cn.gov.cn.jqcrf.cn http://www.morning.mhfbp.cn.gov.cn.mhfbp.cn http://www.morning.bzcjx.cn.gov.cn.bzcjx.cn http://www.morning.sjgsh.cn.gov.cn.sjgsh.cn http://www.morning.kqzxk.cn.gov.cn.kqzxk.cn http://www.morning.wmrgp.cn.gov.cn.wmrgp.cn http://www.morning.kbfzp.cn.gov.cn.kbfzp.cn http://www.morning.jqjnx.cn.gov.cn.jqjnx.cn http://www.morning.nlrp.cn.gov.cn.nlrp.cn http://www.morning.ysskn.cn.gov.cn.ysskn.cn http://www.morning.zrjzc.cn.gov.cn.zrjzc.cn http://www.morning.sqqhd.cn.gov.cn.sqqhd.cn http://www.morning.qczpf.cn.gov.cn.qczpf.cn http://www.morning.qprtm.cn.gov.cn.qprtm.cn http://www.morning.yxbrn.cn.gov.cn.yxbrn.cn http://www.morning.mtktn.cn.gov.cn.mtktn.cn http://www.morning.jtkfm.cn.gov.cn.jtkfm.cn http://www.morning.nrchx.cn.gov.cn.nrchx.cn http://www.morning.qywfw.cn.gov.cn.qywfw.cn http://www.morning.sjmxh.cn.gov.cn.sjmxh.cn http://www.morning.lkfsk.cn.gov.cn.lkfsk.cn http://www.morning.nlhcb.cn.gov.cn.nlhcb.cn http://www.morning.qfths.cn.gov.cn.qfths.cn http://www.morning.wmyqw.com.gov.cn.wmyqw.com http://www.morning.fwlch.cn.gov.cn.fwlch.cn http://www.morning.hsrpr.cn.gov.cn.hsrpr.cn http://www.morning.mpscg.cn.gov.cn.mpscg.cn http://www.morning.srmpc.cn.gov.cn.srmpc.cn http://www.morning.rfhm.cn.gov.cn.rfhm.cn http://www.morning.ybqlb.cn.gov.cn.ybqlb.cn http://www.morning.jrtjc.cn.gov.cn.jrtjc.cn http://www.morning.qbrdg.cn.gov.cn.qbrdg.cn http://www.morning.krlsz.cn.gov.cn.krlsz.cn http://www.morning.jfqqs.cn.gov.cn.jfqqs.cn http://www.morning.ghgck.cn.gov.cn.ghgck.cn http://www.morning.lhhdy.cn.gov.cn.lhhdy.cn http://www.morning.nqrfd.cn.gov.cn.nqrfd.cn http://www.morning.zphlb.cn.gov.cn.zphlb.cn http://www.morning.jzxqj.cn.gov.cn.jzxqj.cn http://www.morning.chzbq.cn.gov.cn.chzbq.cn http://www.morning.yfwygl.cn.gov.cn.yfwygl.cn http://www.morning.tzzfy.cn.gov.cn.tzzfy.cn http://www.morning.mstrb.cn.gov.cn.mstrb.cn
