学生做网站教程,美容美发培训,dedecms 网站 经常无法连接,莱芜金点子广告信息港一、概述
1. 历史
B树(B-Tree)结构是一种高效存储和查询数据的方法#xff0c;它的历史可以追溯到1970年代早期。B树的发明人Rudolf Bayer和Edward M. McCreight分别发表了一篇论文介绍了B树。这篇论文是1972年发表于《ACM Transactions on Database Systems》中的#xff…一、概述
1. 历史
B树(B-Tree)结构是一种高效存储和查询数据的方法它的历史可以追溯到1970年代早期。B树的发明人Rudolf Bayer和Edward M. McCreight分别发表了一篇论文介绍了B树。这篇论文是1972年发表于《ACM Transactions on Database Systems》中的题目为“Organization and Maintenance of Large Ordered Indexes”。
这篇论文提出了一种能够高效地维护大型有序索引的方法这种方法的主要思想是将每个节点扩展成多个子节点以减少查找所需的次数。B树结构非常适合应用于磁盘等大型存储器的高效操作被广泛应用于关系数据库和文件系统中。
B树结构有很多变种和升级版例如B树、B*树和SB树等。这些变种和升级版本都基于B树的核心思想通过调整B树的参数和结构提高了B树在不同场景下的性能表现。
总的来说B树结构是一个非常重要的数据结构为高效存储和查询大量数据提供了可靠的方法。它的历史可以追溯到上个世纪70年代而且在今天仍然被广泛应用于各种场景。 2. B的含义
B树的名称是由其发明者Rudolf Bayer提出的。Bayer和McCreight从未解释B代表什么人们提出了许多可能的解释比如Boeing、balance、between、broad、bushy和Bayer等。但McCreight表示越是思考B-trees中的B代表什么就越能更好地理解B-trees。 3. 特性
一棵B-树具有以下性质
特性1每个节点x具有
属性n表示节点x中key的个数属性leaf表示节点是否是叶子节点节点key可以有多个以升序存储
特性2每个非叶子节点中的孩子数是n 1、叶子节点没有孩子
特性3最小度数t节点的孩子数称为度和节点中键数量的关系如下
最小度数t键数量范围21 ~ 332 ~ 543 ~ 7......n(n-1) ~ (2n-1)
其中当节点中键数量达到其最大值时即3、5、7··· 2n - 1需要分裂
特性4叶子节点的深度都相同 问题1B-树为什么有最小度数的限制
答B树种有最小度数的限制是为了保证B树的平衡特性。
在B树中每个节点都可以有多个子节点这使得B树可以存储大量的键值但也带来了一些问题。如果节点的子节点数量太少那么就可能导致B树的高度过高从而降低了B树的效率。此外如果节点的子节点数量太多那么就可能导致节点的搜索、插入和删除操作变得复杂和低效。
最小度数的限制通过限制节点的子节点数量来平衡这些问题。在B树种每个节点的子节点数量都必须在一定的范围内即t到2t之间其中t为最小度数 4. B-树与2-3树、2-3-4树的关系
可以这样总计它们之间的关系
2-3树是最小度数为2的B树其中每个节点可以包含2个或3个子节点2-3-4树是最小度数为2的B树的一种特殊情况其中每个节点可以包含2个、3个或4个子节点B树是一种更加一般化的平衡树可以适应不同的应用场景其节点可以包含任意数量的键值节点的度数取决于最小度数t的设定。 二、实现
1. 定义节点
static class Node {boolean leaf true;int keyNumber;int t;int[] keys;Node[] children; public Node(int t) {this.t t;this.keys new int[2 * t - 1];this.children new Node[2 * t];}Overridepublic String toString() {return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));}
}
leaf表示是否是叶子节点keyNumber为keys中有效key数目t为最小度数它决定了节点中key的最小、最大数目分别是t - 1 和 2t - 1keys存储此节点的keychildren存储此节点的childtoString只是为了方便调试和测试非必须实际keys应当改为entries以便同时保存key和value刚开始简化实现 2. 多路查找
为上面节点添加get方法 /*** 多路查找* param key* return*/public Node get(int key) {int i 0;while(i keyNumber) {if(keys[i] key) {return this;}if(keys[i] key) {break;}i;}// 执行到此时keys[i] key 或 ikeyNumberif(leaf) {return null;}// 非叶子节点情况return children[i].get(key);} 3. 插入key和child
为上面节点类添加insertKey和insertChild方法 /*** 向keys指定索引处插入key* param key* param index*/public void insertKey(int key, int index) {System.arraycopy(keys, index, keys, index 1, keyNumber - index);keys[index] key;keyNumber;}/*** 向children指定索引处插入child* param child* param index*/public void insertChild(Node child, int index) {System.arraycopy(children, index, children, index 1, keyNumber - index);children[index] child;}
作用是向keys数组或children数组指定index处插入新数据注意
①由于使用了静态数组并且不会在新增或删除时改变它的大小因此需要额外的keyNumber来指定数组内有效key的数目
插入时keyNumber删除时减少keyNumber的值即可
②children不会单独维护数目它比keys多一个
③如果这两个方法同时调用注意它们的先后顺序insertChild后调用因为它计算复制元素时用到了keyNumber 4. 定义树
public class BTree {final int t;final int MIN_KEY_NUMBER;final int MAX_KEY_NUMBER;Node root;public BTree() {this(2);}public BTree(int t) {this.t t;MIN_KEY_NUMBER t - 1;MAX_KEY_NUMBER 2 * t - 1;root new Node(t);}
} 5. 插入 /*** 新增* param key*/public void put(int key) {doPut(root, key, null, 0);}private void doPut(Node node, int key, Node parent, int index) {// 1. 查找本节点的插入位置iint i 0;while(i node.keyNumber) {if(node.keys[i] key) {// 更新return;}if(node.keys[i] key) {break; // 找到插入位置即为此时的i}i;}// 2. 如果节点是叶子节点可以直接插入了if(node.leaf) {node.insertKey(key, i);// 上限}// 3. 如果节点是非叶子节点需要在children[i]处继续递归插入else {doPut(node.children[i], key, node, i);// 上限}if(isFull(node)) {split(node, parent, index);}}boolean isFull(Node node) {return node.keyNumber MAX_KEY_NUMBER;}
首先查找本节点中的插入位置i如果没有空位key被找到应该走更新的逻辑目前什么没做
接下来分两种情况
如果节点是叶子节点可以直接插入了如果节点是非叶子节点需要在children[i]处继续递归插入
无论哪种情况插入完成后都可能超过节点keys数目限制此时应当执行节点分裂
参数中的parent和index都是给分裂方法用的代表当前节点父节点和分裂节点都是第几个孩子
判断依据为
boolean isFull(Node node) {return node.keyNumber MAX_KEY_NUMBER;
} 6. 分裂 /*** 分裂* param left 要分裂的节点* param parent 分裂节点的父节点* param index 分裂节点是第几个孩子*/private void split(Node left, Node parent, int index) {// 分裂节点为根节点if(parent null) {Node newRoot new Node(t);newRoot.leaf false;newRoot.insertChild(left, 0);this.root newRoot;parent newRoot;}// 1. 创建right节点把left节点中t之后的key和child移动过去Node right new Node(t);// 新增节点是否是叶子节点与待分裂节点一致right.leaf left.leaf;System.arraycopy(left.keys, t, right.keys, 0, t - 1);// 如果分裂节点为非叶子节点if(!left.leaf) {System.arraycopy(left.children, t, right.children, 0, t);}right.keyNumber t - 1;left.keyNumber t - 1;// 2. 中间的keyt - 1处插入到父节点int mid left.keys[t - 1];parent.insertKey(mid, index);// 3. right节点作为父节点的孩子parent.insertChild(right, index 1);}
分为两种情况
①如果parent null表示要分裂的是根节点此时需要创建新根原来的根节点作为新根的0孩子
②否则
创建right节点分裂后大于当前left节点的把t以后的key和child都拷贝过去t - 1处的key插入到parent的index处index指left作为孩子时的索引right节点作为parent的孩子插入到index1处 7. 删除
case 1当前节点是叶子节点没找到
case 2当前节点是叶子节点找到了
case 3当前节点是非叶子节点没找到
case 4当前节点是非叶子节点找到了
case 5删除后key数目 下限不平衡
case 6根节点 Node节点类添加一些方法 /*** 向keys指定索引处插入key* param key* param index*/public void insertKey(int key, int index) {System.arraycopy(keys, index, keys, index 1, keyNumber - index);keys[index] key;keyNumber;}/*** 向children指定索引处插入child* param child* param index*/public void insertChild(Node child, int index) {System.arraycopy(children, index, children, index 1, keyNumber - index);children[index] child;}/*** 移除指定index处的key* param index* return*/int removeKey(int index) {int t keys[index];System.arraycopy(keys, index 1, keys, index, --keyNumber - index);return t;}/*** 移除最左边的key* return*/public int removeLeftmostKey() {return removeKey(0);}/*** 移除最右边的key* return*/public int removeRightmostKey() {return removeKey(keyNumber - 1);}/*** 移除指定index处的child* param index* return*/public Node removeChild(int index) {Node t children[index];System.arraycopy(children, index 1, children, index, keyNumber - index);children[keyNumber] null; // help GCreturn t;}/*** 移除最左边的child* return*/public Node removeLeftmostChild() {return removeChild(0);}/*** 移除最右边的child* return*/public Node removeRightmostChild() {return removeChild(keyNumber);}/*** index 孩子处左边的兄弟* param index* return*/public Node childLeftSibling(int index) {return index 0 ? children[index - 1] : null;}/*** index 孩子处右边的兄弟* param index* return*/public Node childRightSibling(int index) {return index keyNumber ? null : children[index 1];}/*** 复制当前节点的所有key和child到target* param target*/public void moveToTarget(Node target) {int start target.keyNumber;if(!leaf) {for (int i 0; i keyNumber; i) {target.children[start i] children[i];}}for (int i 0; i keyNumber; i) {target.keys[target.keyNumber] keys[i];}}
删除代码 /*** 删除key* param key*/public void remove(int key) {doRemove(null, root, 0, key);}private void doRemove(Node parent, Node node, int index, int key) {int i 0;// 在有效范围内while(i node.keyNumber) {if(node.keys[i] key) {break;}i;}// 情况1找到i代表待删除key的索引// 情况2没找到i代表到第i个孩子继续查找if (node.leaf) { // 当前节点是叶子节点if(!found(node,key, i)) { // case 1 没找到return;} else { // case 2 找到了node.removeKey(i);}} else { // 当前节点不是叶子节点if(!found(node,key, i)) { // case 3 没找到// 到孩子节点继续查找doRemove(node, node.children[i], i, key);} else { // case 4 找到了// 1. 找后继keyNode s node.children[i 1]; // 当前节点的后一个孩子while(!s.leaf) {// 直到叶子节点取最左边的s s.children[0];}int skey s.keys[0];// 2. 替换待删除keynode.keys[i] skey;// 3. 删除后继keydoRemove(node, node.children[i 1], i 1, skey);}}// 删除后key数目小于下限if(node.keyNumber MIN_KEY_NUMBER) {// 调整平衡 case 5 case 6balance(parent, node, index);}}/*** 是否找到key* param node* param key* param i* return*/private boolean found(Node node, int key, int i) {return i node.keyNumber node.keys[i] key;}/*** 调整平衡* param parent 父节点* param x 待调整节点* param i 索引*/private void balance(Node parent, Node x, int i) {// case 6 根节点if(x root) {if(root.keyNumber 0 root.children[0] ! null) {root root.children[0];}return;}// 获取左右两边的兄弟Node left parent.childLeftSibling(i);Node right parent.childRightSibling(i);if(left ! null left.keyNumber MIN_KEY_NUMBER) {// case 5-1 左边富裕右旋// a) 父节点中前驱key旋转下来x.insertKey(parent.keys[i - 1], 0);if(!left.leaf) {// b) 左边的兄弟不是叶子节点把最右侧的孩子过继给被调整的节点x.insertChild(left.removeRightmostChild(), 0);}// c) 删除左边兄弟的最右节点移到父节点旋转上去parent.keys[i - 1] left.removeRightmostKey();return;}if(right ! null right.keyNumber MIN_KEY_NUMBER) {// case 5-2 右边富裕左旋// a) 父节点中后去key旋转下来x.insertKey(parent.keys[i], x.keyNumber);if(!right.leaf) {// b) 右边的兄弟不是叶子节点把最左侧的孩子过继给被调整的节点x.insertChild(right.removeLeftmostChild(), x.keyNumber 1);}// c) 删除右边兄弟的最左节点移到父节点旋转上去parent.keys[i] right.removeLeftmostKey();return;}// case 5-3 两边都不富裕向左合并if(left ! null) {// 向左兄弟合并// 将待删除节点从父节点移除parent.removeChild(i);// 从父节点合并一个key到左兄弟left.insertKey(parent.removeKey(i - 1), left.keyNumber);// 将待删除节点的剩余节点和孩子移到到左边x.moveToTarget(left);} else {// 没有左兄弟向自己合并// 把它的右兄弟移除parent.removeChild(i 1);// 父节点移除一个key插入到待删除节点x.insertKey(parent.removeKey(i), x.keyNumber);// 将右兄弟合并过来right.moveToTarget(x);}} 8. 完整代码
package com.itheima.datastructure.BTree;import java.util.Arrays;public class BTree {static class Node {int[] keys; // 关键字Node[] children; // 孩子int keyNumber; // 有效关键字数目boolean leaf true; // 是否是叶子节点int t; // 最小度数public Node(int t) { // t 2this.t t;this.children new Node[2 * t];this.keys new int[2 * t - 1];}public Node(int[] keys) {this.keys keys;}Overridepublic String toString() {return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));}/*** 多路查找* param key* return*/public Node get(int key) {int i 0;while(i keyNumber) {if(keys[i] key) {return this;}if(keys[i] key) {break;}i;}// 执行到此时keys[i] key 或 ikeyNumberif(leaf) {return null;}// 非叶子节点情况return children[i].get(key);}/*** 向keys指定索引处插入key* param key* param index*/public void insertKey(int key, int index) {System.arraycopy(keys, index, keys, index 1, keyNumber - index);keys[index] key;keyNumber;}/*** 向children指定索引处插入child* param child* param index*/public void insertChild(Node child, int index) {System.arraycopy(children, index, children, index 1, keyNumber - index);children[index] child;}/*** 移除指定index处的key* param index* return*/int removeKey(int index) {int t keys[index];System.arraycopy(keys, index 1, keys, index, --keyNumber - index);return t;}/*** 移除最左边的key* return*/public int removeLeftmostKey() {return removeKey(0);}/*** 移除最右边的key* return*/public int removeRightmostKey() {return removeKey(keyNumber - 1);}/*** 移除指定index处的child* param index* return*/public Node removeChild(int index) {Node t children[index];System.arraycopy(children, index 1, children, index, keyNumber - index);children[keyNumber] null; // help GCreturn t;}/*** 移除最左边的child* return*/public Node removeLeftmostChild() {return removeChild(0);}/*** 移除最右边的child* return*/public Node removeRightmostChild() {return removeChild(keyNumber);}/*** index 孩子处左边的兄弟* param index* return*/public Node childLeftSibling(int index) {return index 0 ? children[index - 1] : null;}/*** index 孩子处右边的兄弟* param index* return*/public Node childRightSibling(int index) {return index keyNumber ? null : children[index 1];}/*** 复制当前节点的所有key和child到target* param target*/public void moveToTarget(Node target) {int start target.keyNumber;if(!leaf) {for (int i 0; i keyNumber; i) {target.children[start i] children[i];}}for (int i 0; i keyNumber; i) {target.keys[target.keyNumber] keys[i];}}}Node root; // 根节点int t; // 树中节点最小度数final int MIN_KEY_NUMBER; // 最小key数目final int MAX_KEY_NUMBER; // 最大key数目public BTree() {this(2);}public BTree(int t) {this.t t;root new Node(t);MAX_KEY_NUMBER 2 * t - 1;MIN_KEY_NUMBER t - 1;}/*** key是否存在* param key* return*/public boolean contains(int key) {return root.get(key) ! null;}/*** 新增* param key*/public void put(int key) {doPut(root, key, null, 0);}private void doPut(Node node, int key, Node parent, int index) {// 1. 查找本节点的插入位置iint i 0;while(i node.keyNumber) {if(node.keys[i] key) {// 更新return;}if(node.keys[i] key) {break; // 找到插入位置即为此时的i}i;}// 2. 如果节点是叶子节点可以直接插入了if(node.leaf) {node.insertKey(key, i);// 上限}// 3. 如果节点是非叶子节点需要在children[i]处继续递归插入else {doPut(node.children[i], key, node, i);// 上限}if(isFull(node)) {split(node, parent, index);}}boolean isFull(Node node) {return node.keyNumber MAX_KEY_NUMBER;}/*** 分裂* param left 要分裂的节点* param parent 分裂节点的父节点* param index 分裂节点是第几个孩子*/private void split(Node left, Node parent, int index) {// 分裂节点为根节点if(parent null) {Node newRoot new Node(t);newRoot.leaf false;newRoot.insertChild(left, 0);this.root newRoot;parent newRoot;}// 1. 创建right节点把left节点中t之后的key和child移动过去Node right new Node(t);// 新增节点是否是叶子节点与待分裂节点一致right.leaf left.leaf;System.arraycopy(left.keys, t, right.keys, 0, t - 1);// 如果分裂节点为非叶子节点if(!left.leaf) {System.arraycopy(left.children, t, right.children, 0, t);}right.keyNumber t - 1;left.keyNumber t - 1;// 2. 中间的keyt - 1处插入到父节点int mid left.keys[t - 1];parent.insertKey(mid, index);// 3. right节点作为父节点的孩子parent.insertChild(right, index 1);}/*** 删除key* param key*/public void remove(int key) {doRemove(null, root, 0, key);}private void doRemove(Node parent, Node node, int index, int key) {int i 0;// 在有效范围内while(i node.keyNumber) {if(node.keys[i] key) {break;}i;}// 情况1找到i代表待删除key的索引// 情况2没找到i代表到第i个孩子继续查找if (node.leaf) { // 当前节点是叶子节点if(!found(node,key, i)) { // case 1 没找到return;} else { // case 2 找到了node.removeKey(i);}} else { // 当前节点不是叶子节点if(!found(node,key, i)) { // case 3 没找到// 到孩子节点继续查找doRemove(node, node.children[i], i, key);} else { // case 4 找到了// 1. 找后继keyNode s node.children[i 1]; // 当前节点的后一个孩子while(!s.leaf) {// 直到叶子节点取最左边的s s.children[0];}int skey s.keys[0];// 2. 替换待删除keynode.keys[i] skey;// 3. 删除后继keydoRemove(node, node.children[i 1], i 1, skey);}}// 删除后key数目小于下限if(node.keyNumber MIN_KEY_NUMBER) {// 调整平衡 case 5 case 6balance(parent, node, index);}}/*** 是否找到key* param node* param key* param i* return*/private boolean found(Node node, int key, int i) {return i node.keyNumber node.keys[i] key;}/*** 调整平衡* param parent 父节点* param x 待调整节点* param i 索引*/private void balance(Node parent, Node x, int i) {// case 6 根节点不平衡if(x root) {if(root.keyNumber 0 root.children[0] ! null) {root root.children[0];}return;}// 获取左右两边的兄弟Node left parent.childLeftSibling(i);Node right parent.childRightSibling(i);if(left ! null left.keyNumber MIN_KEY_NUMBER) {// case 5-1 左边富裕右旋// a) 父节点中前驱key旋转下来x.insertKey(parent.keys[i - 1], 0);if(!left.leaf) {// b) 左边的兄弟不是叶子节点把最右侧的孩子过继给被调整的节点x.insertChild(left.removeRightmostChild(), 0);}// c) 删除左边兄弟的最右节点移到父节点旋转上去parent.keys[i - 1] left.removeRightmostKey();return;}if(right ! null right.keyNumber MIN_KEY_NUMBER) {// case 5-2 右边富裕左旋// a) 父节点中后去key旋转下来x.insertKey(parent.keys[i], x.keyNumber);if(!right.leaf) {// b) 右边的兄弟不是叶子节点把最左侧的孩子过继给被调整的节点x.insertChild(right.removeLeftmostChild(), x.keyNumber 1);}// c) 删除右边兄弟的最左节点移到父节点旋转上去parent.keys[i] right.removeLeftmostKey();return;}// case 5-3 两边都不富裕向左合并if(left ! null) {// 向左兄弟合并// 将待删除节点从父节点移除parent.removeChild(i);// 从父节点合并一个key到左兄弟left.insertKey(parent.removeKey(i - 1), left.keyNumber);// 将待删除节点的剩余节点和孩子移到到左边x.moveToTarget(left);} else {// 没有左兄弟向自己合并// 把它的右兄弟移除parent.removeChild(i 1);// 父节点移除一个key插入到待删除节点x.insertKey(parent.removeKey(i), x.keyNumber);// 将右兄弟合并过来right.moveToTarget(x);}}}B站视频链接基础算法-175-B树-remove-演示2_哔哩哔哩_bilibili
