# BPlusTree

**Repository Path**: xiaopengyuyu/BPlusTree

## Basic Information

- **Project Name**: BPlusTree
- **Description**: B+树简单实现。
- **Primary Language**: Java
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-01-06
- **Last Updated**: 2026-01-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# BPlusTree（Java）

一个纯内存的 B+ 树实现（泛型 Key/Value），支持 `insert` / `search` / `delete` 三种基本操作。项目以少量 Java 源文件组成，便于阅读与学习（未引入构建工具、未使用 `package` 声明）。

## 功能

- 插入：`BTree#insert(TKey key, TValue value)`
- 查询：`BTree#search(TKey key)`
- 删除：`BTree#delete(TKey key)`
- 自动维护平衡：节点溢出时分裂、节点下溢时向兄弟借 key 或融合

## 快速开始

### 编译

在仓库根目录执行：

```bash
javac *.java
```

### 使用示例

项目未包含 `main` 入口；你可以在任意位置新建一个 `Main.java`（与这些文件同目录）来验证：

```java
public class Main {
  public static void main(String[] args) {
    BTree<Integer, String> tree = new BTree<>();
    tree.insert(1, "a");
    tree.insert(2, "b");
    System.out.println(tree.search(2)); // b
    tree.delete(1);
  }
}
```

然后运行：

```bash
javac Main.java && java Main
```

## 目录说明（仓库根目录）

- `.git/`：Git 版本控制元数据（由 Git 自动维护，通常无需手动修改）。
- `.idea/`：IntelliJ IDEA 项目配置（可选；不影响命令行编译）。

## 代码文件说明

- `BTree.java`：对外的 B+ 树 API，持有根节点并实现插入/查询/删除入口。
- `BTreeNode.java`：节点抽象基类与 `TreeNodeType` 枚举；提供溢出/下溢处理框架、兄弟指针维护等通用逻辑。
- `BTreeInnerNode.java`：内部节点实现（保存索引 key 与 child 指针），负责在父子间 push-up key、借 key、融合等结构调整。
- `BTreeLeafNode.java`：叶子节点实现（保存 key 与 value），负责叶子层面的插入/删除、分裂，以及与兄弟节点的借 key/融合。
- `LICENSE.md`：MIT License。

## 可配置项

## 节点“阶”（order）在哪里控制？

当前实现的节点容量（可理解为此项目里“阶”的控制点）由两个常量决定：

- `BTreeInnerNode.INNERORDER`
- `BTreeLeafNode.LEAFORDER`

你只需要修改上述常量并重新编译，即可改变内部节点/叶子节点何时触发“溢出分裂”和“下溢借键/融合”。

### 这两个常量在代码里如何生效

实现中会为“插入时允许临时超出 1 个 key”的场景预留一个额外槽位，因此数组长度通常是 `order + 1`（而不是 `order`）：

- 内部节点（`BTreeInnerNode.java`）
  - `keys = new Object[INNERORDER + 1]`
  - `children = new Object[INNERORDER + 2]`
  - 解释：正常情况下内部节点最多容纳 `INNERORDER` 个 key（对应最多 `INNERORDER + 1` 个孩子）。当插入导致 key 数达到 `INNERORDER + 1` 时，`BTreeNode#isOverflow()` 会判定溢出并执行分裂；分裂过程中需要临时多一个 child 指针，所以 `children` 预留到 `INNERORDER + 2`。
- 叶子节点（`BTreeLeafNode.java`）
  - `keys = new Object[LEAFORDER + 1]`
  - `values = new Object[LEAFORDER + 1]`
  - 解释：正常情况下叶子节点最多容纳 `LEAFORDER` 个 key/value；插入时允许临时达到 `LEAFORDER + 1`，随后触发分裂。

### 溢出/下溢阈值如何计算

阈值逻辑位于 `BTreeNode.java`：

- 溢出（触发分裂）：`keyCount == keys.length`
  - 内部节点：当 `keyCount == INNERORDER + 1` 时溢出
  - 叶子节点：当 `keyCount == LEAFORDER + 1` 时溢出
- 下溢（触发借键/融合）：`keyCount < (keys.length / 2)`（整数除法）
  - 内部节点：`keys.length = INNERORDER + 1`，阈值为 `floor((INNERORDER + 1) / 2)`
  - 叶子节点：`keys.length = LEAFORDER + 1`，阈值为 `floor((LEAFORDER + 1) / 2)`
- 可借出 key（兄弟节点“能借键”）：`keyCount > (keys.length / 2)`

说明：这些阈值是“本项目实现的定义”，与某些教材/实现中对 B/B+ 树阶的严格数学定义可能不完全一致；如果你希望严格匹配特定定义，需要同步调整 `isUnderflow()` / `canLendAKey()` 的计算方式。

## 说明与限制

- 仅内存结构：不包含持久化、日志、恢复等能力。
- 未提供范围查询 API；但节点实现维护了左右兄弟指针，可在此基础上扩展遍历。


## 参考链接
- [原仓库链接](https://github.com/linli2016/BPlusTree.git)