【数据结构】B树

1 B树介绍

B树（英语：B-tree），是一种在计算机科学自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉搜索树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快访问速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

那为什么要使用 B-树呢（或者说为啥要有 B-树呢）？

要解释清楚这一点，我们假设我们的数据量达到了亿级别，主存当中根本存储不下，我们只能以块的形式从磁盘读取数据，与主存的访问时间相比，磁盘的 I/O 操作相当耗时，而提出 B-树的主要目的就是减少磁盘的 I/O 操作。大多数平衡树的操作（查找、插入、删除，最大值、最小值等等）需要 O(ℎ) 次磁盘访问操作，其中 ℎ 是树的高度。但是对于 B-树而言，树的高度将不再是logn(其中 n是树中的结点个数），而是一个我们可控的高度 ℎ （通过调整 B-树中结点所包含的键【你也可以叫做数据库中的索引，本质上就是在磁盘上的一个位置信息】的数目，使得 B-树的高度保持一个较小的值）。一般而言，B-树的结点所包含的键的数目和磁盘块大小一样，从数个到数千个不等。由于B-树的高度 h 可控（一般远小于logn ），所以与 AVL 树和红黑树相比，B-树的磁盘访问时间将极大地降低。

平衡二叉排序树是利用插入的成本缓解查找效率---------->红黑树来解决（最长子树不超过最短子树的2倍。数据量大的时候，树会很深，查找次数变多）----------->B树（多叉，多路查找树）

动画显示树调整的网站：Data Structure Visualization

2 B树特点

B树是一种平衡的多叉树，通常我们说m阶的B树，它必须满足如下条件：

• 每个节点最多有m个子节点。
• 每一个非叶子节点（除根节点）最少有[m/2]个子节点。
• 如果根节点不是叶子节点，那么它至少有两个子节点。
• 有k个子节点的非叶子节点拥有k-1个键，且升序排列，满足k[i] < k[i + 1]
• 每个节点至多包含2*k-1个键。
• 所有的叶子节点都在同一层。
• 像其他平衡的二叉搜索树一样，搜索插入和删除的时间复杂度是O(logn)
• 每个节点的结构是：

其中：

n记录这个节点关键字的个数；

P0存储的是第一个孩子的地址，P1存储的是第二个孩子的地址，以此类推。。。。。。

K1是第一个关键字，K2是第二个关键字，以此类推。。。。。。

B树中一个节点的子节点数目的最大值，用m表示，假如最大值为4，则为4阶，如下图

性质：

• 每个节点最多有m个子节点。
• 每一个非叶子节点（除根节点）最少有[m/2]个子节点。
• 如果根节点不是叶子节点，那么它至少有两个子节点。
• 有k个子节点的非叶子节点拥有k-1个键，且升序排列，满足k[i] < k[i + 1]
• 每个节点至多包含2*k-1个键。
• 所有的叶子节点都在同一层。
• 满足n叉排序树

3 B树的增删改查

磁盘预读

内存跟磁盘发生数据交互的时候，一般情况下有一个最小的逻辑单元，称之为页,datapage

页一般由操作系统决定是多大，一般是4k或者8k，我们在数据交互时，可以取页的整数倍来进行读取。

电脑的文件都是datapage的整数倍

每个节点放在磁盘块里，用B树做索引，这个磁盘大小是16k

三层数据。

对比B树和B+树

有一个很重要的不同是：B+树的数据都存在叶子节点上。

3.3 B树的查找

查找简单，将查找放到前面。。。。。。

B树的查找操作与二叉排序树（BST）极为类似，只不多B树中的每个结点包含多个关键字。假设待查找的关键字为K，从根结点开始，递归向下进行查找。对每一个访问的非叶子结点，如果结点包含待查找的关键字K，则返回结点指针；否则，递归到该结点的恰当子代（该子代结点中的关键字均在比K更大的关键字之前）。如果抵达了叶子结点且没有找到K则返回 null。

如图，简化画出来。查找关键字F为例进行说明

第一步：访问根结点P，发现关键字F小于P ，则查找结点P的左孩子。

第二步：访问结点 P 的左子结点【C、G、L】 ，对于一个结点中包含多个关键字时，顺序进行访问，首先与关键字C进行比较，发现比C大；然后与关键字G进行比较，发现比G小，则说明待查找关键字F位于关键字C和关键字G之间的子代中。

第三步：访问关键字C和关键字G之间的子代，该子代结点包含三个关键字【D、E、F】，进行顺序遍历，比较关键字D和F，F比D大

顺序访问关键字E，F比E大：

顺序访问关键字F，发现与待查找关键字相同，查找成功。则返回结点【D、E、F】的指针。

接下来定义一个B树的节点

// B 树的节点
class BTreeNode {
public:
    vector<int> keys;               // 存储节点的键
    int degree;                     // 节点的度（最大子节点数量）
    vector children;    // 存储子节点的指针
    bool leaf;                      // 标志节点是否为叶节点
 
    // 构造函数
    BTreeNode(int degree, bool leaf);
 
    // 遍历节点
    void traverse();
 
    // 在节点及其子树中搜索给定的键
    BTreeNode* search(int key);
 
    // 在非满节点中插入键
    void insertNonFull(int key);
 
    // 分裂满子节点
    void splitChild(int i, BTreeNode* y);
};
 
// BTreeNode 类构造函数实现
BTreeNode::BTreeNode(int degree, bool leaf) {
    this->degree = degree;
    this->leaf = leaf;
    keys.reserve(2 * degree - 1);  // 为键分配内存
    children.reserve(2 * degree);  // 为子节点指针分配内存
}
 
// 从左到右遍历节点的键，并在需要时递归遍历子树
void BTreeNode::traverse() {
    int i;
    for (i = 0; i < keys.size(); i++) {
    	// 不是叶子节点，即中间节点，递归遍历子树
        if (leaf == false) {
        	children[i]->traverse();
		}
		// 打印键值
        cout << " " << keys[i];
    }
    // 不是叶子节点，即中间节点，递归遍历最后一个子树
    if (leaf == false) {
    	children[i]->traverse(); 
	}
}
 
// 在节点及其子树中搜索给定的键
BTreeNode* BTreeNode::search(int key) {
    int i = 0;
    while (i < keys.size() && key > keys[i]) {
    	i++;
	}
    // 键在当前节点中找到
    if (keys[i] == key) {
    	return this;
	}
    // 当前节点为叶节点且未找到键
    if (leaf == true) {
    	return nullptr;
	}
	// 递归搜索子树
    return children[i]->search(key);
}

这段代码笔者使用chatGPT生成的

（1）节点有个属性是节点的度，即每个节点最多有m个子节点。

（2）traverse函数是：左到右遍历节点的键，并在需要时递归遍历子树

（3）search函数是：在节点及其子树中搜索给定的键

// 在节点及其子树中搜索给定的键
BTreeNode* BTreeNode::search(int key) {
    int i = 0;
    // 因为一个节点存储的数据是有序的
    while (i < keys.size() && key > keys[i]) {
    	i++;
	}
    // 键在当前节点中找到
    if (keys[i] == key) {
    	return this;
	}
    // 当前节点为叶节点且未找到键
    if (leaf == true) {
    	return nullptr;
	}
	// 递归搜索子树
    return children[i]->search(key);
}

（4）insertNonFull和splitChild先略过

然后是B树代码

// B 树
class BTree {
public:
    BTreeNode* root;    // B 树的根节点
    int degree;         // B 树的度
 
    // 构造函数
    BTree(int degree);
 
    // 遍历整棵树
    void traverse();
 
    // 在树中搜索给定的键
    BTreeNode* search(int key);
 
    // 向树中插入键
    void insert(int key);
};
 
// BTree 类的实现
BTree::BTree(int degree) {
    root = nullptr;
    this->degree = degree;
}
 
// 遍历整棵树
void BTree::traverse() {
    if (root != nullptr) {
    	root->traverse();
	}
}
 
// 在树中搜索给定的键
BTreeNode* BTree::search(int key) {
    return (root == nullptr) ? nullptr : root->search(key);
}

整棵B树的查找

// 在树中搜索给定的键
BTreeNode* BTree::search(int key) {
    return (root == nullptr) ? nullptr : root->search(key);
}

3.2 B树的插入

一个新插入的关键字K，总是被插入到叶子结点。

与二叉排序树的插入操作类似，从根结点开始，向下遍历直到叶子结点，到达叶子结点，将关键字K插入到相应的叶子结点。

与 BST 不同的是，通过最小度定义了一个结点可以包含关键字的个数的一个取值范围，所以在插入一个关键字时，就需要确认插入关键字之后结点是否超出结点本身最大可容纳的关键字个数。

如何判断在插入一个关键字 k 之前，一个结点是否有可供当前结点插入的空间呢？

3.2 B树的删除

参考：

[1] https://zh.wikipedia.org/zh-hans/B%E6%A0%91

[2] 图解：什么是B树？（心中有 B 树，做人要虚心）一文读懂B-树 - 知乎 (zhihu.com)

[3] B 树 - OI Wiki (oi-wiki.org)

[4] 终于把B树搞明白了(四)_B树的删除操作_哔哩哔哩_bilibili

[5] notes/docs/B树和B+树详解.md at master · wardseptember/notes · GitHub