1. B树(B-树)

B树系列常用作查找使用（外查找）

其他常见的查找搜索结构

B树使用场景：
数据量很大，无法直接讲数据放入内存中，这些数据在磁盘上。

B树的结构中，树中的节点保存的是数据在磁盘中的位置。
在这里插入图片描述
但是如果B树是类似AVL树，红黑树或哈希表的话，涉及大量的访问磁盘操作，效率太低。

B树采用的是优化AVL树的方式提高效率

将普通的AVL树进行压缩（单层存更多），二叉树变成多叉树。
一个节点有多个关键字和其映射的值

B树的规则

一棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

根节点至少有两个孩子
每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数（分支节点，孩子比关键字多一个，eg：10阶B树，每个分支节点最少包含5个孩子，4个关键字。最多包含10个孩子，9个关键字）
每个叶子节点都包含k-1个关键字，其中 ceil(m/2) ≤ k ≤ m
所有的叶子节点都在同一层
每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分
每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。（关键字按照升序排列，同时保证A0<K1<A1<K2<A2）(多叉搜索树)

B树插入过程

eg：三阶B树插入关键字（53, 139, 75, 49, 145, 36, 50, 47, 101）

节点最多保存2个关键字，最少保存1个关键字。根节点单独看

根节点最多可以保存2个关键字，为了简化插入操作，开辟三个关键字大小，当插入后发现已经满了时再进行分裂。同时多开辟一个空间也有助于在插入时进行排序。
如果节点满了，分裂右边一半关键字个数的一般给兄弟节点。提取中位数给父亲，没有父亲就创建新的根节点
继续插入49等后续关键字。

此时节点又满了，需要进行分裂。
继续插入50和47这两个关键字。
最后插入101，导致叶子节点满，需要进行分裂

这次分裂会导致两次连续分裂
第一次分裂导致根节点满
在这里插入图片描述
继续分裂根节点，产生新的根节点

插入完毕

特点

B树天然平衡，B树是先横向扩展，再竖直生长。所以B树天然平衡
新插入的节点一定在叶子插入，叶子节点没有孩子，不影响关键字和孩子的关系
叶子节点满了，分裂出一个兄弟，提取中位数，向父亲插入一个值和孩子
根节点分裂会增加一层
对于B树的每一个节点，这个节点的孩子个数比关键字个数多一个。

C++模拟实现B树插入与中序遍历

#pragma once
#include<iostream>

template<class K, size_t M>
struct BTreeNode {
	//多开辟一个空间方便插入
	K _keys[M];
	BTreeNode<K, M>* _subs[M + 1];
	BTreeNode<K, M>* _parent;//这个节点的父节点
	size_t _n;//记录实际存储关键字个数
	BTreeNode() {
		for (size_t i = 0; i < M; i++) {
			_keys[i] = K();
			_subs[i] = nullptr;
		}
		_subs[M] = nullptr;
		_n = 0;
		_parent = nullptr;
	}
};

//数据如果存在磁盘上，K是磁盘地址
template<class K, size_t M>
class BTree {
	typedef BTreeNode<K, M> Node;
public:
	//查找要插入的叶子节点对应的下标
	std::pair<Node*, int>Find(const K& key) {
		Node* par = nullptr;
		Node* cur = _root;
		while (cur) {
			//在一个节点中查找
			size_t i = 0;
			while (i < cur->_n) {
				if (key < cur->_keys[i]) {
					//_key[size]的左孩子
					break;
				}
				else if (key > cur->_keys[i]) {
					i++;
				}
				else {
					return std::make_pair(cur, i);
				}
			}
			par = cur;//记录cur的父节点
			cur = cur->_subs[i];
		}
		return std::make_pair(par, -1);
	}
	bool Insert(const K& key) {
		if (_root == nullptr) {
			_root = new Node;
			_root->_keys[0] = key;
			_root->_n++;
			return true;
		}
		std::pair<Node*,int> ret = Find(key);
		if (ret.second >= 0) {
			//不允许冗余
			return false;
		}
		//如果没有找到，Find函数返回要插入的叶子节点
		Node* cur = ret.first;
		K newKey = key;
		Node* child = nullptr;
		while (true) {
			InsertKey(cur, newKey, child);
			if (cur->_n == M) {
				//这个节点满了，需要分裂
				size_t mid = M / 2;
				//node中有[mid+1,M-1]的数据
				Node* node = new Node;
				size_t pos = 0;
				//同时还要拷贝孩子节点
				for (int i = mid + 1; i < M; i++) {
					node->_keys[pos] = cur->_keys[i];
					node->_subs[pos] = cur->_subs[i];
					if (cur->_subs[i] != nullptr) {
						//更新父节点
						cur->_subs[i]->_parent = node;
					}
					pos++;
					cur->_keys[i] = K();//方便观察
					cur->_subs[i] = nullptr;
				}
				//最后一个子节点拷贝
				node->_subs[pos] = cur->_subs[M];
				if (cur->_subs[M] != nullptr) {
					//更新父节点
					cur->_subs[M]->_parent = node;
				}
				cur->_subs[M] = nullptr;
				node->_n = pos;
				cur->_n -= pos + 1;//还要提取一个节点作为这两个节点的父节点

				K midKey = cur->_keys[mid];
				cur->_keys[mid] = K();//方便调试观察

				//向cur->parent插入cur->_keys[mid]和node节点
				if (cur->_parent == nullptr) {
					//分裂根节点
					_root = new Node;
					_root->_keys[0] = midKey;
					_root->_subs[0] = cur;
					_root->_subs[1] = node;
					_root->_n = 1;
					cur->_parent = _root;
					node->_parent = _root;
					break;
				}
				newKey = midKey;
				child = node; 
				cur = cur->_parent;//while循环插入
			}
			else {
				//节点没有满，插入结束
				return true;
			}
		}
		return true;
	}

	//中序遍历
	void Inorder() {
		_Inorder(_root);
	}
private:
	void _Inorder(Node* root) {
		if (root == nullptr) {
			return;
		}
		for (size_t i = 0; i < root->_n; i++) {
			_Inorder(root->_subs[i]);
			std::cout << root->_keys[i] << " ";
		}
		//最后还剩余一个右子树
		_Inorder(root->_subs[root->_n]);
	}

	void InsertKey(Node* cur, const K& key, Node* child) {
		int endPos = cur->_n - 1;
		while (endPos >= 0) {
			if (key < cur->_keys[endPos]) {
				//挪动key和右孩子
				cur->_keys[endPos + 1] = cur->_keys[endPos];
				cur->_subs[endPos + 2] = cur->_subs[endPos + 1];
				endPos -= 1;
			}
			else {
				break;
			}
		}
		cur->_keys[endPos + 1] = key;
		cur->_subs[endPos + 2] = child;
		if (child != nullptr) {
			child->_parent = cur;
		}
		cur->_n += 1;
	}
	Node* _root = nullptr;
};

测试代码：

#include"BTree.h"

int main() {
	int arr[] = { 53, 139, 75, 49, 145, 36, 50, 47, 101 };
	BTree<int, 3>bTree;
	for (auto& e : arr) {
		bTree.Insert(e);
	}
	bTree.Inorder();
	return 0;
}