如何做网站怎么赚钱吗,购物建设网站,九洋建设官方网站,网站建设对企业的帮助B树(B-tree)
B树(B-tree)是一种自平衡的多路查找树#xff0c;主要用于磁盘或其他直接存取的辅助存储设备
B树能够保持数据有序#xff0c;并允许在对数时间内完成查找、插入及删除等操作 这种数据结构常被应用在数据库和文件系统的实现上
B树的特点包括#xff1a; B树为…B树(B-tree)
B树(B-tree)是一种自平衡的多路查找树主要用于磁盘或其他直接存取的辅助存储设备
B树能够保持数据有序并允许在对数时间内完成查找、插入及删除等操作 这种数据结构常被应用在数据库和文件系统的实现上
B树的特点包括 B树为了表示节点个数 通常称为 M阶树 1.M阶树每个结点至多有M棵子树(M2) 2.每个非根节点至少有 M/2向上取整个孩子至多有M个孩子。 3.每个叶子节点至少有 M/2-1 个关键字至多有M-1个关键字并以升序排列 4.所有叶子节点都在同一层 5.非叶子节点的关键字个数等于其孩子数减一 6.所有叶子节点不含有任何信息
按照子节点数 y非根节点至少有 M/2向上取整个孩子至多有M个孩子 M 3 2 y 3, 因此称为:2-3树 M 4 2 y 4, 因此称为:2-3-4树 M 5 3 y 5, 因此称为:3-5树 M 7 4 y 7, 因此称为:4-7树
B树的高度对于含有n个关键字的m阶B树其高度为O(log n) 这种数据结构通过减少定位记录时所经历的中间过程从而加快存取速度 与自平衡的二叉查找树不同B树为系统大块数据的读写操作做了优化
下面先看 B树节点的定义
class BTNodeT where T : IComparableT
{private BTNodeT parentNode; // 父节点private ListT keyList; // 关键字向量private ListBTNodeT childList; // 子节点向量其长度总比key多一
}B树每个节点存储的关键字是从小到大有序的keyList 是从小到大排序的 B树 关键字个数 比 子节点 个数少 1 个为什么 因为 关键字 和 子节点 可以理解为这么样一个排序,假设一个 5 阶树的一个节点
childList[0]keyList[0]childList[1]keyList[1]childList[2]可以看到 子节点 和 关键字 是交替出现的并且 子节点 比 关键字 个数多 1 个
并且还有一个隐藏的信息 1.子树中所有关键字的值比其右侧的关键字都小 2.子树中所有关键字的值比其左侧的关键字都大 什么意思呢 1.childList[0] 子树下所有节点的关键字) 小于 keyList[0] 2. keyList[0] 小于 (childList[1] 子树下所有节点的关键字)
看下图 一个 5阶树 Node0 包含 三个关键字(25,39,66)四个子节点(Node1Node2Node3Node4) 25 对应 keyList[0] 39 对应 keyList[1] 66 对应 keyList[2]
Node0 包含 两个关键字 (5, 13) 25 Node1 包含 两个关键字 25 (28, 30) 39 Node2 包含 两个关键字 39 (40, 55) 66 Node3 包含 两个关键字 66 (67, 68, 90)
B树在操作 插入、删除的过程中往往会导致 上溢节点个数大于 B树限制 下移节点个数小于 B树限制 需要通过一系列操作将树恢复平衡
B树操作逻辑 查询 number 1.根节点作为当前节点 2. number 顺次与当前节点的关键字作比较 如果 number keyList[index]则 number 一定在 childList[index]令当前节点 childList[index] 循环执行 2 如果 number keyList[index]则 在关键字中找到 了number查询完成返回节点 如果 number keyList[index], index如果 index childList.Count查找失败返回否则继续循环执行 2 比较下一个 关键字 keyList[index]
我在查询操作逻辑中隐含保留了一个 hot 节点这个 hot 节点是最接近 number 的节点如果查询成功则 hot 不再起作用如果查询失败在 插入操作中 是有用处的
插入 number 1.先执行查询操作如果查询到节点则说明已经存在不再添加返回 2.查询逻辑中 保存的 hot 节点是最接近 numbe 的节点我们将 number 插入到hot节点 3.令 number 与 keyList 中的数据比较 如果 keyList[i] number 将 number 插入到 keyList第 i 1 位置然后 childList 第 i 2 位置插入一个空节点 如果 keyList 中的关键字 number将 number 插入到 keyList 第 0 个位置然后 childList 第 1 个位置插入一个空节点 4. 如果 hot 节点发生上溢做分裂处理
C#代码实现如下 B树节点定义 /// summary/// B-树节点定义/// /summary/// typeparam nameT/typeparamclass BTNodeT where T : IComparableT{private BTNodeT parentNode; // 父节点private ListT keyList; // 关键字向量private ListBTNodeT childList; // 子节点向量其长度总比key多一public BTNode(){keyList new ListT();childList new ListBTNodeT();childList.Insert(0, null);}public BTNode(T t, BTNodeT lc, BTNodeT rc){parentNode null;keyList.Insert(0, t);// 左右孩子childList.Insert(0, lc);childList.Insert(1, rc);if (null ! lc){lc.parentNode this;}if (null ! rc){rc.parentNode this;}}public BTNodeT ParentNode{get { return parentNode; }set { parentNode value; }}private ListT KeyList{get { return keyList; }set { keyList value; }}public int KeyCount{get { return KeyList.Count; }}public void InsertKey(int index, T key){KeyList.Insert(index, key);}public T GetKey(int index){return KeyList[index];}public void RemoveKeyAt(int index){KeyList.RemoveAt(index);}public void SetKey(int index, T key){KeyList[index] key;}private ListBTNodeT ChildList{get { return childList; }set { childList value; }}public void InsertChild(int index, BTNodeT node){ChildList.Insert(index, node);if (null ! node){node.parentNode this;}}public BTNodeT GetChild(int index){return ChildList[index];}public void AddChild(BTNodeT node){InsertChild(ChildList.Count, node);}public BTNodeT RemoveChildAt(int index){BTNodeT node ChildList[index];ChildList.RemoveAt(index);return node;}public void SetChild(int index, BTNodeT node){ChildList[index] node;}public int ChildCount{get { return ChildList.Count; }}}B树实现 /// summary/// B-树/// /summary/// typeparam nameT/typeparamclass BTreeT where T : IComparableT{private int _order; // 介次protected BTNodeT _root; // 跟节点protected BTNodeT _hot; // search() 最后访问的非空节点位置public BTree(int order){_order order;}public BTNodeT Root{get { return _root; }set { _root value; }}/// summary/// 查找/// /summarypublic BTNodeT Search(T t){BTNodeT v Root; // 从根节点触发_hot null;while (null ! v){int index -1;for (int i 0; i v.KeyCount; i){int compare v.GetKey(i).CompareTo(t);if (compare 0){index i;if (compare 0){break;}}}// 若成功则返回if (index 0 v.GetKey(index).CompareTo(t) 0){return v;}_hot v;// 沿引用转至对应的下层子树并载入其根v v.ChildCount (index 1) ? v.GetChild(index 1) : null;}// 若因 null v 而退出,则意味着抵达外部节点return null; // 失败}/// summary/// 插入/// /summarypublic bool Insert(T t){BTNodeT node Search(t);if (null ! node){return false;}int index -1;for (int i 0; i _hot.KeyCount; i){int compare _hot.GetKey(i).CompareTo(t);if (compare 0){index i;if (compare 0){break;}}}_hot.InsertKey(index 1, t); // 将新关键码插至对应的位置_hot.InsertChild(index 2, null); // 创建一个空子树指针SolveOverflow(_hot); // 如发生上溢需做分裂return true;}/// summary/// 删除/// /summarypublic bool Remove(T t){BTNodeT node Search(t);if (null node){return false;}int index -1;for (int i 0; i node.KeyCount; i){if(node.GetKey(i).CompareTo(t) 0){index i;break;}}// node 不是叶子节点if (null ! node.GetChild(0)){BTNodeT u node.GetChild(index 1); // 在右子树中一直向左即可while (null ! u.GetChild(0)){u u.GetChild(0); // 找到 t 的后继必需于某叶节点}// 至此node 必然位于最底层且其中第 r 个关键码就是待删除者node.SetKey(index, u.GetKey(0));node u; // 并与之交换位置index 0;}node.RemoveKeyAt(index);node.RemoveChildAt(index 1);SolveUnderflow(node); // 如有必要需做旋转或合并return false;}/// summary/// 上溢:因插入而上溢后的分裂处理/// /summaryprivate void SolveOverflow(BTNodeT v){if (_order v.ChildCount){return; //递归基当前节点并未上溢}int s _order / 2; //轴点此时应有_order key.Count child.Count - 1BTNodeT u new BTNodeT(); //注意新节点已有一个空孩子for (int j 0; j _order - s - 1; j){ //v右侧_order-s-1个孩子及关键码分裂为右侧节点uBTNodeT node v.GetChild(s 1);v.RemoveChildAt(s 1);u.InsertChild(j, node); //逐个移动效率低T key v.GetKey(s 1);v.RemoveKeyAt(s 1);u.InsertKey(j, key); //此策略可改进}BTNodeT node2 v.GetChild(s 1);v.RemoveChildAt(s 1);u.SetChild(_order - s - 1, node2); //移动v最靠右的孩子if (null ! u.GetChild(0)) //若u的孩子们非空则{for (int j 0; j _order - s; j) //令它们的父节点统一{u.GetChild(j).ParentNode u; //指向u}}BTNodeT p v.ParentNode; //v当前的父节点pif (null p){_root p new BTNodeT();p.SetChild(0, v);v.ParentNode p;} //若p空则创建之int index -1;for (int i 0; i p.KeyCount; i){int compare p.GetKey(i).CompareTo(v.GetKey(0));if (compare 0){index i;if (compare 0){break;}}}int r 1 index; //p中指向u的指针的秩T key2 v.GetKey(s);v.RemoveKeyAt(s);p.InsertKey(r, key2); //轴点关键码上升p.InsertChild(r 1, u); u.ParentNode p; //新节点u与父节点p互联SolveOverflow(p); //上升一层如有必要则继续分裂——至多递归O(logn)层}/// summary/// 下溢:因删除而下溢后的合并处理/// /summary/// param namenode/paramprivate void SolveUnderflow(BTNodeT v){if ((_order 1) / 2 v.ChildCount) return; //递归基当前节点并未下溢BTNodeT p v.ParentNode;if (null p){ //递归基已到根节点没有孩子的下限if (v.KeyCount 0 null ! v.GetChild(0)){//但倘若作为树根的v已不含关键码却有唯一的非空孩子则/*DSA*/_root v.GetChild(0);_root.ParentNode null; //这个节点可被跳过v.SetChild(0, null); //release(v); //并因不再有用而被销毁} //整树高度降低一层return;}int r 0;while (p.GetChild(r) ! v){r;}//确定v是p的第r个孩子——此时v可能不含关键码故不能通过关键码查找//另外在实现了孩子指针的判等器之后也可直接调用Vector::find()定位/*DSA*/// 情况1向左兄弟借关键码if (0 r){ //若v不是p的第一个孩子则BTNodeT ls p.GetChild(r - 1); //左兄弟必存在if ((_order 1) / 2 ls.ChildCount){ //若该兄弟足够“胖”则/*DSA*/v.InsertKey(0, p.GetKey(r - 1)); //p借出一个关键码给v作为最小关键码T key ls.GetKey(ls.KeyCount - 1);ls.RemoveKeyAt(ls.KeyCount - 1);p.SetKey(r - 1, key); //ls的最大关键码转入pBTNodeT node ls.GetChild(ls.ChildCount - 1);ls.RemoveChildAt(ls.ChildCount - 1);//同时ls的最右侧孩子过继给v//作为v的最左侧孩子v.InsertChild(0, node);return; //至此通过右旋已完成当前层以及所有层的下溢处理}} //至此左兄弟要么为空要么太“瘦”// 情况2向右兄弟借关键码if (p.ChildCount - 1 r){ //若v不是p的最后一个孩子则BTNodeT rs p.GetChild(r 1); //右兄弟必存在if ((_order 1) / 2 rs.ChildCount){ //若该兄弟足够“胖”则/*DSA*/v.InsertKey(v.KeyCount, p.GetKey(r)); //p借出一个关键码给v作为最大关键码T key rs.GetKey(0);rs.RemoveKeyAt(0);p.SetKey(r, key); //rs的最小关键码转入pBTNodeT node rs.GetChild(0);rs.RemoveChildAt(0);v.InsertChild(v.ChildCount, node);//同时rs的最左侧孩子过继给vif (null ! v.GetChild(v.ChildCount - 1)) //作为v的最右侧孩子{v.GetChild(v.ChildCount - 1).ParentNode v;}return; //至此通过左旋已完成当前层以及所有层的下溢处理}} //至此右兄弟要么为空要么太“瘦”// 情况3左、右兄弟要么为空但不可能同时要么都太“瘦”——合并if (0 r){ //与左兄弟合并/*DSA*/BTNodeT ls p.GetChild(r - 1); //左兄弟必存在T key p.GetKey(r - 1);p.RemoveKeyAt(r - 1);ls.InsertKey(ls.KeyCount, key);p.RemoveChildAt(r);//p的第r - 1个关键码转入lsv不再是p的第r个孩子BTNodeT node v.GetChild(0);v.RemoveChildAt(0);ls.InsertChild(ls.ChildCount, node);//v的最左侧孩子过继给ls做最右侧孩子while (v.KeyCount 0){ //v剩余的关键码和孩子依次转入lsT key2 v.GetKey(0);v.RemoveKeyAt(0);ls.InsertKey(ls.KeyCount, key2);BTNodeT node2 v.GetChild(0);v.RemoveChildAt(0);ls.InsertChild(ls.ChildCount, node2);}//release(v); //释放v}else{ //与右兄弟合并/*DSA*/// printf( ... case 3R\n);BTNodeT rs p.GetChild(r 1); //右兄弟必存在T key p.GetKey(r);p.RemoveKeyAt(r);rs.InsertKey(0, key); p.RemoveChildAt(r);//p的第r个关键码转入rsv不再是p的第r个孩子BTNodeT node v.GetChild(v.ChildCount - 1);v.RemoveChildAt(v.ChildCount - 1);rs.InsertChild(0, node);if (null ! rs.GetChild(0)){rs.GetChild(0).ParentNode rs; //v的最左侧孩子过继给ls做最右侧孩子}while (v.KeyCount 0){ //v剩余的关键码和孩子依次转入rsT key2 v.GetKey(v.KeyCount - 1);v.RemoveKeyAt(v.KeyCount - 1);rs.InsertKey(0, key2);BTNodeT node2 v.GetChild(v.ChildCount - 1);v.RemoveChildAt(v.ChildCount - 1);rs.InsertChild(0, node2);if (null ! rs.GetChild(0)){rs.GetChild(0).ParentNode rs;}}//release(v); //释放v}SolveUnderflow(p); //上升一层如有必要则继续分裂——至多递归O(logn)层}/// summary/// 层序遍历获取所有节点切是按照每一层节点返回/// /summary/// param namenode/param/// returns/returnspublic ListListBTNodeT TraverseLevelList(BTNodeT node){ListListBTNodeT listResult new ListListBTNodeT();if (null node){return listResult;}QueueBTNodeT queue new QueueBTNodeT();queue.Enqueue(node);while (queue.Count 0){int count queue.Count;ListBTNodeT list new ListBTNodeT();while(count 0){--count;node queue.Dequeue();if (null node){continue;}list.Add(node);for (int i 0; i node.ChildCount; i){queue.Enqueue(node.GetChild(i));}}listResult.Add(list);}return listResult;}/// summary/// 层序遍历获取所有节点/// /summary/// param namenode/param/// returns/returnspublic ListBTNodeT TraverseLevel(BTNodeT node){ListBTNodeT list new ListBTNodeT();if (null node){return list;}QueueBTNodeT queue new QueueBTNodeT();queue.Enqueue(node);while (queue.Count 0){node queue.Dequeue();if (null node){continue;}list.Add(node);for (int i 0; i node.ChildCount; i){queue.Enqueue(node.GetChild(i));}}return list;}}
