# Disk-based B+ Tree

**Repository Path**: vierundsechzig/bptree_disk_based

## Basic Information

- **Project Name**: Disk-based B+ Tree
- **Description**: No description available
- **Primary Language**: C++
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-05-06
- **Last Updated**: 2021-06-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 图书管理系统

## 介绍
这是一个图书管理系统，其数据采用外存版本的B+树索引，能够尽可能地减少IO次数，提升读取速度。

### 核心算法伪代码描述

说明：

1. 若 node 为一个 B+树节点，则 node.key 表示它的关键字数组，node.children 表示它的 子节点数组。
2. position(a, e)中，a 为升序排序的数组。它返回的是 e 应当被插入的位置。该位置上 的数值不小于 e，而前一个位置上的数值小于 e。

#### B+树的查询

```
// 若 e 存在，则 L 表示 e 位于的叶节点，返回值为它在该节点关键字数组中的下标。若e 不存在，则 L 表示若 e 要被插入到树中，它应当被插入到哪个叶节点，返回值表示它应当被 插入的该叶节点的关键字数组中的位置。
FUNCTION FIND(Node* T, Key e, Node* L)
	Node* node = T;
	WHILE node 不是叶节点 DO
		index = position(node->key, e);
		node = node->children[index];
	WEND
	RETURN position(node->key, e);
END FUNCTION
```

时间复杂度：O(log n)

空间复杂度：O(1)

#### B+树的插入

```
// 将 e 插入至 T 中。返回值表示插入是否成功。
FUNCTION INSERT(Node* T, Key e)
	IF T 为空 THEN
		新建一个节点，记录该节点的信息，并将 B+树的根节点指针和第一个叶节点指针指向它;
		RETURN TRUE;
	ELSE 
		Node* L;
		index = FIND(T, e, L);
		IF L->key[index] == e THEN
			RETURN FALSE;
		ELSE 
			将 e 插入到 L->key 的适当位置; 
			IF e 比 T 各关键字都大 THEN
				将 e 的值赋给各祖先节点的关键字数组最后一个元素;
			END IF
			WHILE L 不是根节点 AND L 的子节点数超过 B+树阶数 DO
				将 L 分裂为两个，一半的关键字归于其中一个节点，剩余的关键字归于另外一个节点;
				IF L 为叶节点 THEN
					修改这两个分裂节点的后继节点指针，其中一个指向另一个分裂节点，另一个指向原 L 节点的后继节点;
				ELSE 
					将原 L 中的子节点指针一半归于其中一个节点，剩余的归于另外一个节点；同时，修改原 L 节点子节点的父指针域，确保它们指向新的父节点;
				END IF
				修改 L 父节点的关键字数组和子节点指针数组：L 对应的关键字和子节点指针位置分为二，记录 L 分裂后节点的最大关键字值，并将子节点指针指向它们;
				L = L->PARENT;
			WEND 
			IF 根节点的子节点数超过 B+树阶数 THEN
				根节点一分为二，并创建新的节点，该节点的两个子节点指针指向分裂的节点，关键字为这些节点的最大关键字，并将 B+树的根节点指针指向新建的节点;
			END IF
			RETURN TRUE
		END IF
	END IF
END FUNCTION
```
时间复杂度：O(log n)

空间复杂度：O(1)

#### B+树的删除

```
// 删除 T 中的 e。返回值表示插入是否成功。
FUNCTION DELETE(Node* T, Key e)
	Node* L;
	index = FIND(T, e, L);
	IF L->key[index]不存在 OR L->key[index] != e THEN
		RETURN FALSE;
	ELSE
		将 e 从 L 中删去;
		IF e 是 T 中唯一关键字 THEN
			根结点指针和第一个子节点指针均变为空指针;
			RETURN TRUE;
		END IF
		IF e 是 L 中的最大关键字 THEN
			则修改 L 各祖先节点的关键字信息，使之正确;
		END IF
		WHILE L 不是根节点 AND L 的节点数没达到 B+树的最小要求 DO
			IF 邻居节点的关键字数正好为 B+树的最小要求 THEN
				合并 L 和邻居节点;
				IF L 是叶节点 THEN
					修改合并后节点的后驱结点指针，使之正确;
				ELSE 
 					修改 L 和邻居节点的子节点的父节点指针，使之正确;
				END IF
				将父节点中 L 和邻居节点对应位置的关键字和子节点指针合并;
			ELSE 
				将邻居节点中的一个关键字指针移动到 L 中;
				IF L 不是叶节点 THEN
					将邻居节点中该关键字对应位置的子节点指针移动到 L 中;
					将该子节点指针指向的子节点指针指向 L;
				END IF
				修改 L 父节点中邻居节点和 L 对应位置的关键字值，使之正确;
			END IF 
			L = L->PARENT;
		WEND 
		IF 根节点不是叶节点且只有一个子节点 THEN
			将根节点指针指向根节点的子节点;
			删除原根节点;
		END IF
		RETURN TRUE;
	END IF
END FUNCTION
```

时间复杂度：O(log n)

空间复杂度：O(1)

### 总结

这个项目的完成度其实不太好，验收的时候bug多，不过B+树逻辑没有出问题。所以这次项目主要的作用是让我掌握了B+树的原理和操作，并用代码实现出来，而且是外存版本的，对I/O复杂度理解更为深刻。

## 运行环境
在AMD64架构的Windows操作系统上编译运行。Linux移植尚未成功，会出现输入输出的故障。


## 安装教程

cmake后在cmake-build-debug目录下运行software_library.exe即可。

## 使用说明

运行后有菜单，根据菜单提示输入字符即可。其中有个选项是遍历B+树，它会把B+树节点信息按层次打印出来。程序初始已有几本书的库存，可以查看此时的B+树结构。

## 演示截图

下图展示列出所有图书功能。

![alt display](screenshots/bptreelist.png)

下图展示遍历B+树功能，Position为节点在文件中的位置，Degrees表示该节点的子结点数，Key List为键值列表，每个节点有n个键值和n个指针，n为当前节点度数，非叶节点的指针为子结点指针，叶结点的指针为文件记录指针。

![alt traverse](screenshots/bptreetraverse.png)

下图为插入一个记录。

![alt add](screenshots/bptreeadd.png)

下图为删除一个记录。

![alt delete](screenshots/bptreedel.png)