模拟实现B-树详解

1. 根节点至少有两个孩子；
2. 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字，并且以升序排列；
3. 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子；
4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间；

5.B-树通过节点的分裂和合并操作来保持树的平衡，所有叶子节点都位于同一层。

B-树的插入分析

以M=3为例，每个节点中存储两个数据，两个数据可以将区间分割为三部分，即最多有两个关键字，三个孩子。

但是为了方便，对于每个节点，当插入第三个关键字时不分裂，在插入第三个关键字之后再分裂，可以想象成每个节点最多有三个关键字，最多有四个孩子。即：

下面以插入序列【53,139,75,49,145,36,101】为例构建B树：

【1】插入53

【2】插入139

【3】插入75

【4】引发分裂

【5】插入49和145

【6】插入36

【7】引发分裂

【8】插入101

【9】引发分裂

【10】再次引发分裂

B-树插入总结

1. 如果树为空，直接插入新节点中，该节点为树的根节点
2. 树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
3. 检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)
4. 按照插入排序的思想将该元素插入到找到的节点中
5. 检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足
6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：
        申请新节点
        找到该节点的中间位置
        将该节点中间位置右侧的元素以及其孩子搬移到新节点中
        将中间位置元素以及新节点往该节点的双亲节点中插入，即继续4
7. 如果向上已经分裂到根节点的位置，插入结束

模拟实现B-树

基本结构

Pair.java

public class Pair <K,V>{ private K key; private V val; public Pair(K key, V val) { this.key = key; this.val = val; } public K getKey() { return key; } public void setKey(K key) { this.key = key; } public V getVal() { return val; } public void setVal(V val) { this.val = val; } }

MyBtree.java

public class MyBtree { static class BTRNode { public int[] keys;//关键字 public BTRNode[] subs;//孩子 public BTRNode parent;//存储当前孩子节点的父亲节点 public int usedSize;//记录当前节点中关键字的数量 public BTRNode () { //说明一下：这里多给一个 是为了好进行分裂 this.keys = new int[M]; this.subs = new BTRNode[M+1]; } } public static final int M = 3; public BTRNode root;//当前B树的根节点 }

寻找插入位置

为什么返回 Pair<BTRNode,Integer>？

是因为，find函数要实现的功能是

【1】看看B-树中是否存在和要插入元素相等的元素，如果存在相等元素，则返回所在位置

【2】为要插入的元素找到合适的位置

如果只是返回BTRNode，无论是上面哪种情况，结果都是非空，无法进行区分。

如果只是返回-1和非负值，只知道B-树是否存在和要插入元素相同的元素，并不知道要将元素插入到哪个地方。

如果返回 Pair<BTRNode,Integer>，便可解决上述问题，既能知道B-树是否存在和要插入元素相同的元素，又知道要将元素插入到哪个地方。

private Pair<BTRNode,Integer> find(int key) { BTRNode cur = root; BTRNode parent = null; while (cur != null) { int i = 0; while (i < cur.usedSize) { if(cur.keys[i] == key) { //返回一个当前找到的节点 和 当前这个数据在节点当中的下标 return new Pair<>(cur,i); }else if(cur.keys[i] < key) { i++; }else { break; } } parent = cur; cur = cur.subs[i]; } return new Pair<>(parent,-1); }

插入元素

1.首先判断B-树根节点是否为空，如果为空，直接插入即可，并且B-树元素个数++；

2.如果B-树根节点不为空，首先看看B-树中是否存在和要插入元素相等的元素，如果存在，则插入结束，不对要插入元素进行插入

3.如果B-树根节点不为空，且B-树中不存在和要插入元素相等的元素，就可以在找到的合适的插入位置进行插入，然后判断是否要对B-树进行分裂，如果要对B-树进行分裂，则进行分裂操作。

public boolean insert(int key) { //1、如果B树为空的时候 if(root == null) { root = new BTRNode(); root.keys[0] = key; root.usedSize++; return true; } //2、当B树不为空的时候，我们需要查看当前B树当中 是否存在我的Key Pair<BTRNode,Integer> pair = find(key); //判断 这里获取到的val值 是不是-1 来确定 当前是否存在该key if(pair.getVal() != -1) { return false; } //3、说明不存在这个key 我们要进行插入 BTRNode parent = pair.getKey(); int index = parent.usedSize-1; for (; index >= 0;index--) { if(parent.keys[index] >= key) { parent.keys[index+1] = parent.keys[index]; }else { break; } } parent.keys[index+1] = key; parent.usedSize++; //为什么不处理 孩子呢 因为你每次插入都是再叶子节点，所以叶子节点都是null if(parent.usedSize < M) { //没有满 return true; }else { //满了-》分裂 split(parent); return true; } }

分裂节点

1.首先把要分裂节点的父节点进行记录保存，并创建新节点

2.然后开始挪动数据，包括关键字和孩子，需要考虑更新挪动后的孩子节点的父节点

3.其次更新新节点的关键字个数，以及分裂节点的关键字个数

4.然后判断分裂节点的父节点是否为空

5.如果为空，就创建新节点，挪动数据并更新新节点的关键字个数

6.如果不为空，继续挪动数据并更新分裂节点的父节点的关键字个数

7.然后判断分裂节点的父节点是否需要分裂

8.如果需要分裂，继续重复执行上述1~7步骤，直到不再需要分裂为止。

private void split(BTRNode cur) { BTRNode newNode = new BTRNode(); //1. 先存储当前需要分裂节点的父节点 BTRNode parent = cur.parent; //2. 开始挪数据 int mid = cur.usedSize >> 1; int i = mid+1; int j = 0; for( ; i < cur.usedSize;i++) { newNode.keys[j] = cur.keys[i]; newNode.subs[j] = cur.subs[i]; //处理刚刚拷贝过来的孩子节点的父亲节点 为新分裂的节点 if(newNode.subs[j]!=null) { newNode.subs[j].parent = newNode; } j++; } //多拷贝一次孩子 newNode.subs[j] = cur.subs[i]; if(newNode.subs[j]!=null) { newNode.subs[j].parent = newNode; } //更新当前新节点的有效数据 newNode.usedSize = j; //这里的-1 指的是 将来要提到父亲节点的key cur.usedSize = cur.usedSize - j - 1; //特殊：处理根节点的情况 if(cur == root) { root = new BTRNode(); root.keys[0] = cur.keys[mid]; root.subs[0] = cur; root.subs[1] = newNode; root.usedSize = 1; cur.parent = root; newNode.parent = root; return; } //更新当前新的节点的父亲节点 newNode.parent = parent; //开始移动父亲节点 int endT = parent.usedSize-1; int midVal = cur.keys[mid]; for (; endT >= 0 ; endT--) { if(parent.keys[endT] >= midVal) { parent.keys[endT+1] = parent.keys[endT]; parent.subs[endT+2] = parent.subs[endT+1]; }else { break; } } parent.keys[endT+1] = midVal; //将当前父节点的孩子节点 新增为newNode parent.subs[endT+2] = newNode; parent.usedSize++; if(parent.usedSize >= M) { split(parent); } }

中序遍历

private void inorder(BTRNode root){ if(root == null) return; for(int i = 0; i < root.usedSize; ++i){ inorder(root.subs[i]); System.out.println(root.keys[i]); } inorder(root.subs[root.usedSize]); }

完整代码

Pair.java

public class Pair <K,V>{ private K key; private V val; public Pair(K key, V val) { this.key = key; this.val = val; } public K getKey() { return key; } public void setKey(K key) { this.key = key; } public V getVal() { return val; } public void setVal(V val) { this.val = val; } }

MyBtree.java

public class MyBtree { static class BTRNode { public int[] keys;//关键字 public BTRNode[] subs;//孩子 public BTRNode parent;//存储当前孩子节点的父亲节点 public int usedSize;//记录当前节点中关键字的数量 public BTRNode () { //说明一下：这里多给一个 是为了好进行分裂 this.keys = new int[M]; this.subs = new BTRNode[M+1]; } } public static final int M = 3; public BTRNode root;//当前B树的根节点 public boolean insert(int key) { //1、如果B树为空的时候 if(root == null) { root = new BTRNode(); root.keys[0] = key; root.usedSize++; return true; } //2、当B树不为空的时候，我们需要查看当前B树当中 是否存在我的Key Pair<BTRNode,Integer> pair = find(key); //判断 这里获取到的val值 是不是-1 来确定 当前是否存在该key if(pair.getVal() != -1) { return false; } //3、说明不存在这个key 我们要进行插入 BTRNode parent = pair.getKey(); int index = parent.usedSize-1; for (; index >= 0;index--) { if(parent.keys[index] >= key) { parent.keys[index+1] = parent.keys[index]; }else { break; } } parent.keys[index+1] = key; parent.usedSize++; //为什么不处理 孩子呢 因为你每次插入都是再叶子节点，所以叶子节点都是null if(parent.usedSize < M) { //没有满 return true; }else { //满了-》分裂 split(parent); return true; } } private void split(BTRNode cur) { BTRNode newNode = new BTRNode(); //1. 先存储当前需要分裂节点的父节点 BTRNode parent = cur.parent; //2. 开始挪数据 int mid = cur.usedSize >> 1; int i = mid+1; int j = 0; for( ; i < cur.usedSize;i++) { newNode.keys[j] = cur.keys[i]; newNode.subs[j] = cur.subs[i]; //处理刚刚拷贝过来的孩子节点的父亲节点 为新分裂的节点 if(newNode.subs[j]!=null) { newNode.subs[j].parent = newNode; } j++; } //多拷贝一次孩子 newNode.subs[j] = cur.subs[i]; if(newNode.subs[j]!=null) { newNode.subs[j].parent = newNode; } //更新当前新节点的有效数据 newNode.usedSize = j; //这里的-1 指的是 将来要提到父亲节点的key cur.usedSize = cur.usedSize - j - 1; //特殊：处理根节点的情况 if(cur == root) { root = new BTRNode(); root.keys[0] = cur.keys[mid]; root.subs[0] = cur; root.subs[1] = newNode; root.usedSize = 1; cur.parent = root; newNode.parent = root; return; } //更新当前新的节点的父亲节点 newNode.parent = parent; //开始移动父亲节点 int endT = parent.usedSize-1; int midVal = cur.keys[mid]; for (; endT >= 0 ; endT--) { if(parent.keys[endT] >= midVal) { parent.keys[endT+1] = parent.keys[endT]; parent.subs[endT+2] = parent.subs[endT+1]; }else { break; } } parent.keys[endT+1] = midVal; //将当前父节点的孩子节点 新增为newNode parent.subs[endT+2] = newNode; parent.usedSize++; if(parent.usedSize >= M) { split(parent); } } private Pair<BTRNode,Integer> find(int key) { BTRNode cur = root; BTRNode parent = null; while (cur != null) { int i = 0; while (i < cur.usedSize) { if(cur.keys[i] == key) { //返回一个当前找到的节点 和 当前这个数据在节点当中的下标 return new Pair<>(cur,i); }else if(cur.keys[i] < key) { i++; }else { break; } } parent = cur; cur = cur.subs[i]; } return new Pair<>(parent,-1); } private void inorder(BTRNode root){ if(root == null) return; for(int i = 0; i < root.usedSize; ++i){ inorder(root.subs[i]); System.out.println(root.keys[i]); } inorder(root.subs[root.usedSize]); } }

代码测试

public static void main(String[] args) { MyBtree myBtree = new MyBtree(); int[] array = {53, 139, 75, 49, 145, 36,101}; for (int i = 0; i < array.length; i++) { myBtree.insert(array[i]); } myBtree.inorder(myBtree.root); }

运行结果：

B-树的删除

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。

3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

下面以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key,最少有2个key。

a）原始状态

b）在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束。

c）在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。

删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。

d）在上述情况下接着32，结果如下图。

当删除后，当前结点中只key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

当前结点key的个数满足条件，故删除结束。

e）上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。

同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

同理，对于当前结点而言只能继续合并了，最后结果如下所示。

合并后结点当前结点满足条件，删除结束。

B-树的优点

1.减少磁盘I/O操作：B-树的设计目标是减少磁盘I/O操作，提高存取速度。由于磁盘访问速度远慢于CPU处理速度，因此减少磁盘访问次数可以显著提高性能。
2.自平衡性：B-树在插入和删除操作时会自动进行节点的分裂和合并，以保持树的平衡性。这种自平衡性确保了B-树在查找、插入和删除操作中的高效性。
3.支持大量数据：B-树能够很好地处理大规模数据，因为它通过增加节点的子节点数量来降低树的高度，从而减少了查找过程中需要遍历的节点数。

B-树的应用场景

1.数据库索引：B-树常被用作数据库系统的索引结构，以加快数据的读取速度。例如，MySQL、PostgreSQL等数据库系统都基于B-树或其变种实现数据索引。
2.文件系统：B-树可以在文件系统中用于管理目录和文件，如Unix文件系统中的索引节点（Inode）就是以B-树为基础结构实现的。
3.GIS（地理信息系统）：GIS数据需要用到空间索引算法查询与分析空间数据，B-树作为为空间数据设计的一种索引结构，可用于GIS数据库中的数据索引。
4.路由表：B-树可用于构建路由表，快速定位目标路由器地址。

B+树

B+树是B-树的变形，也是一种多路搜索树：

1. 其定义基本与B-树相同，除了：
2. 非叶子节点的子树指针与关键字个数相同
3. 非叶子节点的子树指针p[i]，指向关键字值属于【k[i]，k[i+1])的子树
4. 为所有叶子节点增加一个链指针
5. 所有关键字都在叶子节点出现

B+树的搜索与B-树基本相同，区别是B+树只有达到叶子节点才能命中(B-树可以在非叶子节点中命中)，其性能也等价与在关键字全集做一次二分查找。
B+树的特性：

1. 所有关键字都出现在叶子节点的链表中(稠密索引)，且链表中的节点都是有序的。
2. 不可能在非叶子节点中命中。
3. 非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储数据的数据层。
4. 更适合文件索引系统

概念图：

B+树的优势

1.降低磁盘I/O次数：由于B+树的非叶子节点不保存数据，且叶子节点之间通过指针相连，这使得在查找数据时，可以一次性加载更多的关键字到内存中，从而减少磁盘I/O次数。
2.提高查询效率：B+树的叶子节点之间通过指针相连，形成了有序链表，这使得范围查询变得非常高效。
3.适用于大数据集：B+树的高度较低，对于大数据集来说，可以减少查找、插入和删除操作所需的时间复杂度。

B+树的应用场景

1.数据库索引：在关系型数据库中，B+树被广泛用于索引数据，以提高查询效率。
2.文件系统：在文件系统中，B+树用于存储和管理文件和目录，保证文件的快速查找和高效顺序访问。
3.缓存管理：在计算机系统中，B+树可用于管理缓存数据，因为它能够快速索引和更新数据，同时保证数据的一致性和可靠性。

B+树与B树的区别

1.关键字存储位置：B+树的所有关键字都存储在叶子节点中，且叶子节点之间通过指针相连；而B树的关键字则可能存储在非叶子节点中。
2.内部节点结构：B+树的内部节点仅包含其子树中的最大（或最小）关键字作为索引；而B树的内部节点则可能包含多个关键字和相应的子树指针。
3.查询效率：由于B+树的叶子节点之间通过指针相连，形成了有序链表，这使得范围查询在B+树中更加高效。

B*树

B树是B+树的一种变体，它在B+树的基础上进行了优化。

特点

1.节点结构：B树保留了B+树的基本结构，即所有关键字都存储在叶子节点中，且叶子节点之间通过指针相连形成有序链表。但B树在非根和非叶子节点中增加了指向兄弟的指针，这一特点使得B*树在节点分裂和合并时更加灵活。
2.关键字数量：B树定义了非叶子节点关键字个数至少为(2/3)M，即块的最低使用率为2/3（其中M为节点的最大关键字数），这比B+树的1/2更高。这意味着B*树在分配新节点方面的概率更低，空间使用率更高。
3.分裂与合并：当B树的节点满时，会分配一个新的节点，并将数据根据一定的规则进行分裂。在分裂过程中，B树会尽量保持节点的平衡，以维持树的整体性能。同样，在删除关键字导致节点关键字数量不足时，B*树也会通过合并节点或借用兄弟节点的关键字来保持树的平衡。

概念图

B*树的优势

1.更高的空间使用率：由于B树定义了更高的块最低使用率，因此在相同条件下，B树能够存储更多的关键字，从而提高了空间使用效率。
2.更好的平衡性：B*树通过增加指向兄弟的指针和更严格的节点分裂与合并规则，使得树在插入和删除操作时能够更好地保持平衡，减少了树的高度，提高了查询效率。
3.更低的磁盘I/O次数：由于B*树在存储结构上的优化，使得在进行大量数据的查询、插入和删除操作时，能够减少磁盘I/O次数，提高操作效率。