04树 + 堆 + 优先队列 + 图（D1_树（D6_B树（B）））

embedded/2025/2/7 2:52:31/

目录

一、学习前言

二、基本介绍

三、特性

1. 从概念上说起

2. 举个例子

四、代码实现

节点准备

大体框架

实现分裂

实现新增

实现删除

五、完整源码

一、学习前言

前面我们已经讲解过了二叉树、二叉搜索树（BST）、平衡二叉搜索树（AVL树）、红黑树，接下

爱就让我们了解下B树到底是什么？

二、基本介绍

在计算机科学中，B树是一种自平衡的树形数据结构，能够保持数据有序。

这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数量级的时间复杂度内

完成。

  • B树，其实是一颗特殊的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。
  • B树减少定位记录时所经历的中间过程，从而加快存取速度，其实B树主要解决的就是数据IO的问题。
  • 树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

总而言之，B树主要用于管理磁盘上的数据管理（减少磁盘IO次数），而之前说的AVL树与红黑树

适合用于内存数据管理。例如：存储一个100w的数据使用AVL存储，树高大约为20层（)，如果使用磁盘IO查询20次效率较低。

注意：常常面试官会问B树和B-树的区别，我们该如何回答？其实，B树和B-树是同一种数据结

构，如果不清楚的话，会被面试官忽悠！

三、特性

1. 从概念上说起

度degree：指树中节点孩子数

阶order：指所有节点孩子数中最大值

一棵 B-树具有以下性质

特性1：每个节点 x 具有

  • 属性 n，表示节点 x 中 key 的个数
  • 属性 leaf，表示节点是否是叶子节点
  • 节点 key 可以有多个，以升序存储

特性2：每个节点最多具有m个孩子，其中m叫做B-树的阶

特性3：除根结点与叶子节点外，每个节点至少有ceil(m/2)个孩子，根节点不是叶子节点时，最少

有两个孩子。叶子节点没有孩子

特性4：每个非叶子节点中的孩子数是 n + 1。而n的取值为ceil(m/2)-1<=n<=m-1。

特性5：最小度数t（节点的孩子数称为度）和节点中键数量的关系如下：

最小度数t

键数量范围

2

1 ~ 3

3

2 ~ 5

4

3 ~ 7

...

...

n

(n-1) ~ (2n-1)

其中，当节点中键数量达到其最大值时，即 3、5、7 ... 2n-1，需要分裂

特性6：叶子节点的深度都相同

2. 举个例子

一个m阶的B树特点如下：

  1. 所有叶子节点都在同一层级；
  2. 除了根节点以外的其他节点包含的key值数量在[m/2]-1到m-1的数据范围；
  3. 除了根节点和叶子节点外，所有中间节点至少有m/2个孩子节点；
  4. 根节点如果不是叶子节点的话，它必须包含至少2个孩子节点；
  5. 拥有n-1个key值非叶子节点必须有n个孩子节点；
  6. 一个节点的所有key值必须是升序排序的；

以上六点就是B树的全部特性

四、代码实现

节点准备

B树的节点属性，与其他树不太相同，首先是key可以有多个，因此要设置为数组，孩子节点也未

知，因此也要设置为数组。

本应该还存在一个value属性，这里简化掉，不添加该属性。

static class Node {boolean leaf = true; //是否是叶子节点int keyNumber; //有效keyint t; //最小度int[] keys; // keys数组Node[] children; //孩子节点数组public Node(int t) {this.t = t;this.keys = new int[2 * t - 1];this.children = new Node[2 * t];//最大孩子节点个数为为2*t}@Overridepublic String toString() {return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));}/*** 根据key获取对应节点** @param key* @return*/Node get(int key) {int i = 0;while (i < keyNumber) {//如果在该节点找到，那么直接返回即可if (keys[i] == key) {return this;}//说明要找的元素可能在children[i]中if (keys[i] > key) {break;}i++;}//如果是叶子节点，直接返回nullif (leaf) {return null;}return children[i].get(key);}/*** 指定位置插入元素** @param key* @param index*/void insertKey(int key, int index) {System.arraycopy(keys, index, keys, index + 1, keyNumber - index);keys[index] = key;keyNumber++;}/*** 向节点中插入孩子节点* @param child* @param index*/void insertChild(Node child, int index) {System.arraycopy(children, index, children, index + 1, keyNumber - index);children[index] = child;}
}

这里我采用了静态数组，因此需要多添加一个keyNumber参数来获取有效key的数量，如果使用

ArrayList，可以通过size方法获取，因此不需要添加这个属性。

大体框架

public class BTree {private Node root;private int t;//最小度数final int MAX_KEY_NUMBER;//最大key数量final int MIN_KEY_NUMBER;//最小key数量。用于分裂使用public BTree(int t) {this.t = t;root = new Node(t);MAX_KEY_NUMBER = 2 * t - 1;MIN_KEY_NUMBER = 2 * t;}static class Node {boolean leaf = true; //是否是叶子节点int keyNumber; //有效keyint t; //最小度int[] keys; // keys数组Node[] children; //孩子节点数组public Node(int t) {this.t = t;this.keys = new int[2 * t - 1];this.children = new Node[2 * t];//最大孩子节点个数为为2*t}@Overridepublic String toString() {return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));}/*** 根据key获取对应节点** @param key* @return*/Node get(int key) {int i = 0;while (i < keyNumber) {//如果在该节点找到，那么直接返回即可if (keys[i] == key) {return this;}//说明要找的元素可能在children[i]中if (keys[i] > key) {break;}i++;}//如果是叶子节点，直接返回nullif (leaf) {return null;}return children[i].get(key);}/*** 指定位置插入元素** @param key* @param index*/void insertKey(int key, int index) {System.arraycopy(keys, index, keys, index + 1, keyNumber - index);keys[index] = key;keyNumber++;}/*** 向节点中插入孩子节点** @param child* @param index*/void insertChild(Node child, int index) {System.arraycopy(children, index, children, index + 1, keyNumber - index);children[index] = child;}}
}

实现分裂

先说分裂规律，当新增一个节点后使节点中的key满足2t-1，那么该节点就会被分裂。

  • 创建一个新的节点，暂时称为right节点（分裂后会在被分裂节点的右边）
  • 被分裂节点把 t 以后的 key 和 child 都拷贝到right节点
  • t-1 处的 key 插入到 parent 的 index 处，index 指被分裂节点作为孩子时的索引
  • right 节点作为 parent 的孩子插入到 index + 1 处

图示如下：

红色部分的意思是当前节点是父结点中作为孩子的下标。黑色部分是key，小数字代表key的下标。

起始存在一个t为3的B树。那么最大key就为 2*3-1 。

此时作为父结点孩子下标为1的节点以及存在 4 个key，再添加一个key就会触发分裂。

现在，再添加一个新的key值 8 ，此时到达最大key数，触发分裂

此时分裂结束，分裂后结果如下

具体实现代码如下

private void split(Node parent, int index, Node split) {if (parent == null) {//说明分割根节点,除了需要创建right节点之外，还需要创建parent节点parent = new Node(t);parent.leaf = false;parent.insertChild(split, 0);root = parent;}Node right = new Node(t);//将被分裂节点的一部分key放入right节点中。System.arraycopy(split.keys, index, right.keys, 0, t - 1);//新建的节点与被分裂节点在同一层，因此leaf属性应该和被分裂节点一样right.leaf = split.leaf;right.keyNumber = t - 1;//如果被分裂节点不是叶子节点，也需要将孩子节点一并拷贝到right节点中if (!split.leaf) {System.arraycopy(split.children, t, right.children, 0, t);}split.keyNumber = t - 1;//将t-1节点放入父结点中int mid = split.keys[t - 1];parent.insertKey(mid, index);parent.insertChild(right, index + 1);
}

实现新增

  • 首先查找本节点中的插入位置 i，如果没有空位（key 被找到），应该走更新的逻辑。
  • 接下来分两种情况
    • 如果节点是叶子节点，可以直接插入了
    • 如果节点是非叶子节点，需要继续在 children[i] 处继续递归插入
  • 无论哪种情况，插入完成后都可能超过节点 keys 数目限制，此时应当执行节点分裂
  • 参数中的 parent 和 index 都是给分裂方法用的，代表当前节点父节点，和分裂节点是第几个孩子

具体实现代码如下

public void put(int key) {doPut(null, 0, root, key);
}private void doPut(Node parent, int index, Node node, int key) {int i = 0;while (i < node.keyNumber && node.keys[i] < key) {i++;}// TODO i<node.keyNumber是否多余？if (i < node.keyNumber && node.keys[i] == key) {return;}if (node.leaf) {node.insertKey(key, i);} else {doPut(node, i, node.children[i], key);}if (isFull(node)) {split(parent, index, node);}
}private boolean isFull(Node node) {return node.keyNumber == MAX_KEY_NUMBER;
}

实现删除

删除节点会存在下面几种情况

case 1：当前节点是叶子节点，没找到。直接返回null

case 2：当前节点是叶子节点，找到了。直接移除节点即可

case 3：当前节点是非叶子节点，没找到。递归寻找孩子节点是否存在该key

case 4：当前节点是非叶子节点，找到了。找到后驱节点交换key，并将交换后的key删除

case 5：删除后 key 数目 < 下限（不平衡）。需要进行调整

在兄弟节点中keyNumber数量充足的情况下可以通过旋转调整平衡。

图示如下：

现在要删除节点 2

删除之后，左侧孩子的key数量少于最小限度，因此需要进行一次左旋。

父结点 3 移动到左侧孩子节点中，右侧孩子节点中的第一个key 5 移动到父结点中，左旋结束。

但如果兄弟节点的key数量是最小限度，那么此时应该进行合并，而不是旋转。

合并时，我们通常选择将右侧的节点合并到左侧节点中去。

图示如下：

此时要删除key 3 ，右侧兄弟节点无法再向被删除节点提供key。

于是将右侧节点移除，同时将父结点的值与被移除节点的值都放在最初的左孩子节点中。

case 6：根节点当经过合并之后，根结点可能会存在为null的情况，此时让根节点中的 0 号孩子替

代掉根节点就好。

具体实现代码如下

/*** 移除指定元素** @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 && node.keys[i] < key) {i++;}if (node.leaf) {if (node.keys[i] == key) {//case 2:如果找到了并且是叶子节点node.removeKey(i);} else {//case 1:如果没找到并且是叶子节点return;}} else {if (node.keys[i] == key) {//case 4:如果找到了但不是叶子节点//找到后驱节点并交换位置Node child = node.children[i + 1];while (!child.leaf) {child = child.children[0];}int nextKey = child.keys[0];node.keys[i] = nextKey;//之所以不直接调用孩子节点的removeKey方法是为了避免删除后发生不平衡//child.removeKey(0);doRemove(node,child,i+1, nextKey);} else {//case 3:如果没找到但不是叶子节点doRemove(node,node.children[i],i, key);}}//如果删除后，节点中的key少于下限，那么需要进行调整if (node.keyNumber < MIN_KEY_NUMBER) {//平衡调整balance(parent,node,index);}
}/*** 调整B树** @param parent 父结点* @param node   被调整节点* @param index  被调整节点在父结点中的孩子数组下标*/
private void balance(Node parent, Node node, int index) {//case 6 根节点if (node == root) {if (node.keyNumber==0 && node.children[0]!=null){root = node.children[0];}return;}Node leftChild = parent.leftSibling(index);Node rightChild = parent.rightSibling(index);//如果左边孩子节点中的key值充足if (leftChild != null && leftChild.keyNumber > MIN_KEY_NUMBER) {//将父结点中的key赋值给nodenode.insertKey(parent.keys[index - 1], 0);if (!leftChild.leaf) {//如果左侧孩子不是一个叶子节点，在旋转过后，会导致keysNumber+1！=children。//因此将多出来的孩子赋值更多出来一个key的被调整节点node.insertChild(leftChild.removeRightmostChild(), 0);}//将左孩子中最右侧元素赋值给父结点parent.keys[index - 1] = leftChild.removeRightmostKey();return;}//如果右边充足if (rightChild != null && rightChild.keyNumber > MIN_KEY_NUMBER) {node.insertKey(parent.keys[index], node.keyNumber);if (!rightChild.leaf) {node.insertChild(rightChild.removeLeftmostChild(), node.keyNumber);}parent.keys[index] = rightChild.removeLeftmostKey();return;}//合并//如果删除节点存在左兄弟，向左合并if (leftChild != null) {//将被删除节点从父结点上移除parent.removeChild(index);//将父结点的被移除节点的前驱节点移动到左兄弟上leftChild.insertKey(parent.removeKey(index - 1), leftChild.keyNumber);node.moveToTarget(leftChild);} else {//如果没有左兄弟，那么移除右兄弟节点，并将右兄弟移动到被删除节点上。parent.removeChild(index+1);node.insertKey(parent.removeKey(index),node.keyNumber);rightChild.moveToTarget(node);}
}

五、完整源码

public class BTree {private Node root;private int t;//最小度数private final int MAX_KEY_NUMBER;private final int MIN_KEY_NUMBER;public BTree(int t) {this.t = t;root = new Node(t);MAX_KEY_NUMBER = 2 * t - 1;MIN_KEY_NUMBER = t-1;}static class Node {boolean leaf = true; //是否是叶子节点int keyNumber; //有效keyint t; //最小度int[] keys; // keys数组Node[] children; //孩子节点数组public Node(int t) {this.t = t;this.keys = new int[2 * t - 1];this.children = new Node[2 * t];//最大孩子节点个数为为2*t}@Overridepublic String toString() {return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));}/*** 根据key获取对应节点** @param key* @return*/Node get(int key) {int i = 0;while (i < keyNumber) {//如果在该节点找到，那么直接返回即可if (keys[i] == key) {return this;}//说明要找的元素可能在children[i]中if (keys[i] > key) {break;}i++;}//如果是叶子节点，直接返回nullif (leaf) {return null;}return children[i].get(key);}/*** 指定位置插入元素** @param key* @param index*/void insertKey(int key, int index) {System.arraycopy(keys, index, keys, index + 1, keyNumber - index);keys[index] = key;keyNumber++;}/*** 向节点中插入孩子节点** @param child* @param index*/void insertChild(Node child, int index) {System.arraycopy(children, index, children, index + 1, keyNumber - index);children[index] = child;}//移除指定元素int removeKey(int index) {int t = keys[index];System.arraycopy(keys, index + 1, keys, index, --keyNumber - index);return t;}//移除最左边的元素int removeLeftmostKey() {return removeKey(0);}//移除最右边的元素int removeRightmostKey() {return removeKey(keyNumber - 1);}//移除指定位置的孩子节点Node removeChild(int index) {//获取被移除的节点Node t = children[index];//将被移除节点的后面元素向前移动一位System.arraycopy(children, index + 1, children, index, keyNumber - index);//将之前最后一位的引用释放children[keyNumber] = null;//返回被引用元素return t;}//移除最左边的孩子节点Node removeLeftmostChild() {return removeChild(0);}//移除最右边的孩子节点Node removeRightmostChild() {return removeChild(keyNumber);}//移动指定节点到目标节点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 leftSibling(int index) {return index > 0 ? children[index - 1] : null;}//获取指定孩子节点的右边节点Node rightSibling(int index) {return index == keyNumber ? null : children[index + 1];}}/*** 查询key值是否在树中** @param key* @return*/public boolean contains(int key) {return root.get(key) != null;}/*** 新增节点** @param key*/public void put(int key) {doPut(null, 0, root, key);}//index的作用是，给分割方法提供参数private void doPut(Node parent, int index, Node node, int key) {//寻找插入位置int i = 0;while (i < node.keyNumber && node.keys[i] < key) {i++;}//如果找到了，直接更新if (node.keys[i] == key) {return;}//如果没找到，查看是否是叶子节点，如果不是，向下寻找if (node.leaf) {node.insertKey(key, i);} else {doPut(node, i, node.children[i], key);}if (isFull(node)) {split(parent, index, node);}}private boolean isFull(Node node) {return node.keyNumber == MAX_KEY_NUMBER;}/*** 分裂节点** @param parent* @param index 分割节点在父结点的孩子下标* @param split*/private void split(Node parent, int index, Node split) {if (parent == null) {//说明分割根节点,除了需要创建right节点之外，还需要创建parent节点parent = new Node(t);parent.leaf = false;parent.insertChild(split, 0);root = parent;}Node right = new Node(t);//将被分裂节点的一部分key放入right节点中。System.arraycopy(split.keys, t, right.keys, 0, t - 1);//新建的节点与被分裂节点在同一层，因此leaf属性应该和被分裂节点一样right.leaf = split.leaf;right.keyNumber = t - 1;//如果被分裂节点不是叶子节点，也需要将孩子节点一并拷贝到right节点中if (!split.leaf) {System.arraycopy(split.children, t, right.children, 0, t);for (int i =t;i<=split.keyNumber;i++){split.children[i]=null;}}split.keyNumber = t - 1;//将t-1节点放入父结点中int mid = split.keys[t - 1];parent.insertKey(mid, index);parent.insertChild(right, index + 1);}/*** 移除指定元素** @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 && node.keys[i] < key) {i++;}if (node.leaf) {if (node.keys[i] == key) {//case 2:如果找到了并且是叶子节点node.removeKey(i);} else {//case 1:如果没找到并且是叶子节点return;}} else {if (node.keys[i] == key) {//case 4:如果找到了但不是叶子节点//找到后驱节点并交换位置Node child = node.children[i + 1];while (!child.leaf) {child = child.children[0];}int nextKey = child.keys[0];node.keys[i] = nextKey;//之所以不直接调用孩子节点的removeKey方法是为了避免删除后发生不平衡//child.removeKey(0);doRemove(node,child,i+1, nextKey);} else {//case 3:如果没找到但不是叶子节点doRemove(node,node.children[i],i, key);}}//如果删除后，节点中的key少于下限，那么需要进行调整if (node.keyNumber < MIN_KEY_NUMBER) {//平衡调整balance(parent,node,index);}}/*** 调整B树** @param parent 父结点* @param node   被调整节点* @param index  被调整节点在父结点中的孩子数组下标*/private void balance(Node parent, Node node, int index) {//case 6 根节点if (node == root) {if (node.keyNumber==0 && node.children[0]!=null){root = node.children[0];}return;}Node leftChild = parent.leftSibling(index);Node rightChild = parent.rightSibling(index);//如果左边孩子节点中的key值充足if (leftChild != null && leftChild.keyNumber > MIN_KEY_NUMBER) {//将父结点中的key赋值给nodenode.insertKey(parent.keys[index - 1], 0);if (!leftChild.leaf) {//如果左侧孩子不是一个叶子节点，在旋转过后，会导致keysNumber+1！=children。//因此将多出来的孩子赋值更多出来一个key的被调整节点node.insertChild(leftChild.removeRightmostChild(), 0);}//将左孩子中最右侧元素赋值给父结点parent.keys[index - 1] = leftChild.removeRightmostKey();return;}//如果右边充足if (rightChild != null && rightChild.keyNumber > MIN_KEY_NUMBER) {node.insertKey(parent.keys[index], node.keyNumber);if (!rightChild.leaf) {node.insertChild(rightChild.removeLeftmostChild(), node.keyNumber);}parent.keys[index] = rightChild.removeLeftmostKey();return;}//合并//如果删除节点存在左兄弟，向左合并if (leftChild != null) {//将被删除节点从父结点上移除parent.removeChild(index);//将父结点的被移除节点的前驱节点移动到左兄弟上leftChild.insertKey(parent.removeKey(index - 1), leftChild.keyNumber);node.moveToTarget(leftChild);} else {//如果没有左兄弟，那么移除右兄弟节点，并将右兄弟移动到被删除节点上。parent.removeChild(index+1);node.insertKey(parent.removeKey(index),node.keyNumber);rightChild.moveToTarget(node);}}}


http://www.ppmy.cn/embedded/160183.html

相关文章

vscode软件操作界面UI布局@各个功能区域划分及其名称称呼

vscode软件操作界面UI布局@各个功能区域划分及其名称称呼

文章目录 abstract检查用户界面的主要区域官方文档关于UI的介绍 abstract 检查 Visual Studio Code 用户界面 - Training | Microsoft Learn 本质上&#xff0c;Visual Studio Code 是一个代码编辑器&#xff0c;其用户界面和布局与许多其他代码编辑器相似。 界面左侧是用于访…
阅读更多...
SQL进阶实战技巧：某芯片工厂设备任务排产调度分析 | 间隙分析技术应用

SQL进阶实战技巧：某芯片工厂设备任务排产调度分析 | 间隙分析技术应用

目录 0 技术定义与核心原理 1 场景描述 2 数据准备 3 间隙分析法 步骤1：原始时间线可视化
阅读更多...
Android学习21 -- launcher

Android学习21 -- launcher

1 前言 之前在工作中&#xff0c;第一次听到launcher有点蒙圈&#xff0c;不知道是啥&#xff0c;当时还赶鸭子上架去和客户PK launcher的事。后来才知道其实就是安卓的桌面。本来还以为很复杂&#xff0c;毕竟之前接触过windows的桌面&#xff0c;那叫一个复杂。。。 后面查了…
阅读更多...
【自动化办公】批量图片PDF自定义指定多个区域识别重命名，批量识别铁路货物运单区域内容改名，基于WPF和飞桨ocr深度学习模型的解决方案

【自动化办公】批量图片PDF自定义指定多个区域识别重命名，批量识别铁路货物运单区域内容改名，基于WPF和飞桨ocr深度学习模型的解决方案

项目背景介绍 铁路货运企业需要对物流单进行长期存档&#xff0c;以便后续查询和审计。不同的物流单可能包含不同的关键信息&#xff0c;通过自定义指定多个区域进行识别重命名&#xff0c;可以使存档的图片文件名具有统一的规范和明确的含义。比如&#xff0c;将包含货物运单…
阅读更多...
Kafka分区策略实现

Kafka分区策略实现

引言 Kafka 的分区策略决定了生产者发送的消息会被分配到哪个分区中&#xff0c;合理的分区策略有助于实现负载均衡、提高消息处理效率以及满足特定的业务需求。 轮询策略&#xff08;默认&#xff09; 轮询策略是 Kafka 默认的分区策略&#xff08;当消息没有指定键时&…
阅读更多...
上海路网道路 水系铁路绿色住宅地工业用地面图层shp格式arcgis无偏移坐标2023年

上海路网道路 水系铁路绿色住宅地工业用地面图层shp格式arcgis无偏移坐标2023年

标题和描述中提到的资源是关于2023年上海市地理信息数据的集合&#xff0c;主要包含道路、水系、铁路、绿色住宅区以及工业用地的图层数据&#xff0c;这些数据以Shapefile&#xff08;shp&#xff09;格式存储&#xff0c;并且是适用于ArcGIS软件的无偏移坐标系统。这个压缩包…
阅读更多...
深入探讨：服务器如何响应前端请求及后端如何查看前端提交的数据

深入探讨：服务器如何响应前端请求及后端如何查看前端提交的数据

深入探讨&#xff1a;服务器如何响应前端请求及后端如何查看前端提交的数据 一、服务器如何响应前端请求 前端与后端的交互主要通过 HTTP 协议实现。以下是详细步骤&#xff1a; 1. 前端发起 HTTP 请求 GET 请求&#xff1a;用于从服务器获取数据。POST 请求&#xff1a;用…
阅读更多...
Vue WebSocket简单应用 ws

Vue WebSocket简单应用 ws

webSocket应用 <template><div></div> </template><script> import { getToken } from "/utils/auth"; export default {data() {return {url: "",Socket: null, //socket对象lockReconnect: false, //锁定拒绝重连close: …
阅读更多...
最新文章

Copyright @ 2022~2023