B+ tree implemented in Java

B+树相关介绍

B+树是一棵多叉排序树，即每个非叶子节点可以包含多个子节点，其整体结构呈扁平化，所以其非常适配于数据库和操作系统的文件系统中。且B+树能够保持数据的稳定有序，插入和删除都拥有较稳定的对数时间复杂度。

B+树的特性：以 m 阶为例，m 表示内部节点即非叶子节点可以包含的最大子节点个数 maximumNum
<ul>若一个内部节点有 \(n(n  right) {                flag = false;                break;            }            if (left = entry.key) {                values.add(entry.value);            }        }        leafNode = leafNode.rightSibling;    }    return values;}[/code]插入操作

B+树的插入操作仅在叶子节点进行：

• 若为空树，则创建一个叶子节点，该叶子节点同时也是根节点，插入操作结束；
  
• 根据插入的 key 值，找到应该在的叶子节点插入；
  
  
  • 若插入后叶子节点个数符合要求即小于m，则插入结束
    
  • 若插入后叶子节点个数不符合要求即大于等于m，将该节点分裂成两半，则判断当前叶子节点是否为根节点
    
    
    • 若当前叶子节点为根节点，则构建一个新的root节点，指向分裂后的两个子节点
      
    • 若当前叶子节点不为根节点，则在父节点处添加一个新的子节点，新子节点则存储原节点一半的值，并循环向上判断中间节点是否满足要求
      
    
    
  
  

1. package bplustree;
3. public abstract class Node {
4.     InternalNode parent;    // 父节点
5.        
6.     public Node() {}
7.    
8.     public abstract boolean isValid();          // 判断删除节点后各B+树节点是否满足要求
9.     public abstract boolean isAvailable();      // 判断B+树节点是否可以分裂节点给其他节点
10.     public abstract boolean isMergeable();      // 判断B+树节点是否可以和其他节点合并
11. }

复制代码

删除操作

B+树的删除操作仅在叶子节点进行：

• 若删除后，叶子节点中的索引个数仍然满足要求即大于等于Math.ceil(m / 2)时，将该叶子节点的其他索引左移一位，删除结束；
  
• 若删除后，叶子节点中的索引个数不满足最低要求，则查询左右兄弟节点：
  
  
  • 若左/右兄弟节点中索引个数大于Math.ceil(m / 2)，则从左/右兄弟节点中移动一个索引项到当前叶子节点中，并修改父节点的索引值，删除结束
    
  • 若左/右兄弟节点中索引个数等于Math.ceil(m / 2)，则将左/右节点与当前节点合并，修改父节点的索引记录，并向上逐级判断内部节点是否因为页合并导致索引项不满足最低要求，删除结束
    
  
  

1. public class InternalNode extends Node{
2.     int maxChildNodes;                   // 子节点个数最大值 m，m为阶数
3.     int minChildNodes;                   // 除根节点及叶子节点外，子节点个数最小值 ceil(m / 2)
4.    
5.     int curNodesNum;                     // 内部节点当前的子节点个数
6.     InternalNode leftSibling;            // 左兄弟节点
7.     InternalNode rightSibling;           // 右兄弟节点
8.     Integer[] keys;                      // 内部节点当前的索引值，最多有 m - 1 个
9.     Node[] childPointers;                // 内部节点当前的子节点，最多有 m 个
10. }

复制代码

参考文章：
1. B+树

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！