DS高阶：B树系列_问题 d: ds b-树构建及查找

一、常见的搜索结构

1、顺序查找     时间复杂度：O(N)

2、二分查找     时间复杂度：O(logN)

        要求：（1）有序 （2）支持下标的随机访问

3、二叉搜索树（BS树）       时间复杂度：O(logN)——>O(N)

        若接近有序的数据插入到BS中，会导致退化成单支树，时间复杂度退化为O(N)

4、平衡搜索树 （AVL树和RB树）   时间复杂度：O(logN)

       在BS的基础上，通过一些规则加以限制，通过旋转来限制高度,维持logN的时间复杂度

5、哈希    时间复杂度：O(1)

        底层是散列表，要注意解决哈希冲突。综合效率优于平衡搜索树

        以上结构适合用于数据量相对不是很大，能够一次性存放在内存中（内查找），进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。（B树系列   解决外查找的问题）

         根据上面的分析，我们知道B树系列是为了解决外查找的问题而生的，但是你可能会有这样的疑惑：虽然高度下降了，但是由于我的一个节点存储这多个关键字信息，那么我即使找到这个节点，不也是要遍历关键字信息，效率真的能提高么？？

        答：在磁盘中的搜索来说，定位的效率低，但是如果准确定位到了（节点），后面效率就会很高（顺序遍历节点中的关键字），这个跟磁盘的底层结构有关，具体可以参照下面的文献去理解。

二、B树的概念

      1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(后面有一个B的改进版本B+树、B*树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。一棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

（1）根节点至少有两个孩子

（2）每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数

（3）每个叶子节点都包含k-1个关键字，其中 ceil(m/2) ≤ k ≤ m

（4）所有的叶子节点都在同一层

（5）每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划
分
 （6）每个结点的结构为：（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。

 （7）实际中M通常会设计得比较大（比如1024）

以上规则可能还有点抽象，我们通过分析B树的插入来剖析具体的过程

三、B树的插入过程分析

       为了简单起见，假设M = 3. 即三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三个部分，因此节点应该有三个孩子，为了后续实现简单期间，节点的结构如下：

注意孩子比关键字多一个，并且为了防止越界的问题，我们多开一个空间

 用序列{53, 139, 75, 49, 145, 36, 50,47,101}构建B树的过程如下

（1）插入53

（2）插入139

（3）插入75

（4）进行分裂

 这里可以解释为什么ceil(m/2) ≤ k ≤ M  

假设M是偶数  比如是10  那么后面5个给兄弟，中位数给父亲，自己还剩下4个，兄弟会多一个

假设M是奇数  比如是11  那么后面5个给兄弟，中位数给父亲，自己还剩下5个，正好一样多

（5）插入49 

 分析以下，当B树有多个叶子节点的时候，如何去选取我们要插入的叶子节点。

答：B树的逻辑是 左-根-左-根-左-根……-右，我们先忽略掉后面这个右子树，把它抽象成一个节点对应一个左子树，在拓展兄弟的时候是向右拓展的，所以我们找的是要左（小）的找。  举个例子，49比75小，那么必然在75左孩子那边，此时可以直接往下走，但是如果139比75大，那么此时不能直接到下一层，而是先往后找，直到找到一个比自己大的节点（如果后面没有，就是当前节点）的左孩子去找。

（6）插入145

（7）插入36

（8）进行分裂 

（9）插入50

（10）插入47

 （11）插入101

（12）继续分裂

 （13）二次分裂

 四、B树简单模拟实现

4.1 B树的节点设计

template<class K,size_t M> 
struct BTreeNode
{
	BTreeNode()
	{
		for (size_t i = 0; i < M; ++i)
		{
			_keys[i] = K();  //K的默认构造
			_subs[i] = nullptr;
		}
		_subs[M] = nullptr;
		_parent = nullptr;
		_n = 0;
	}
	//关键字永远比孩子少一个  为了方便插入，我们多开一个空间 预防边界情况
	K _keys[M]; //M-1个关键字
	BTreeNode<K, M>* _subs[M + 1];// 孩子的集合 M个孩子
	BTreeNode<K, M>* _parent;//父亲节点  方便插入的时候向上回溯
	size_t _n; //实际存了多少节点
};
template<class K, size_t M>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:
 
private:
	Node* _root=nullptr;
};

1、K代表K类型，一般是表示地址，当然也可以是KV模型

2、M表示这是M路多叉树

3、_subs表示孩子节点的集合，_keys表示关键字的集合，为了防止边界情况的判断，统一多开一个空间。

4、_n表示一共个有效的关键字

5、_parent是父亲节点，维护父亲的原因是我们需要向上传中位数，如果不维护一个父亲节点，会比较难实现，但是增加了一个指针，同时也要十分注意去维护这个指针（容易忽略）。

4.2 B树的查找

       在B树不允许键值冗余的情况下，如果我们想插入一个节点，那么我们要保证B树没有该节点，因此我们在实现插入之前，先实现一个查找的函数

pair<Node*, int> Find(const K& key)  //查找这个节点以及对应关键字的下标
{
	Node* cur = _root;
	Node* parent = nullptr;//如果没找到， 把父亲节点带回来
	while (cur) //因为i每次都要重头开始算
	{
		size_t i = 0; 
		while (i < cur->_n)
		{
			if (key < cur->_keys[i]) break; //keys[i]的左孩子根他的下标是相等的
			else if (key > cur->_keys[i]) ++i;     //左才会往下跳  比右小i++
			else return make_pair(cur, i);
		}
		//但是有可能走到空都不会结束  找不到就往自己的孩子去跳
		parent = cur;
		cur = cur->_subs[i];
	}
	return make_pair(parent, -1);
}

1、返回值pair<Node*,int> 前一个返回对应的节点，后一个表示对应节点中的下标。

2、parent指针的意义：因为我们在插入之前必须要调用这个查找函数，并且必须插入到相应的叶子节点中去。那么我们可以顺便通过这个返回值返回我们要插入的叶子节点。这样在insert函数中接受find函数的返回值的时就可以直接拿到待插入的叶子节点。

3、因为拓展都是往右拓展的，所以我们必须要确保比key当前元素小，我们才能跳到下一层去找他的左孩子，并且每次都要从第一个位置开始找，如果比当前元素大的话，那么先往后找，而不是直接往该节点的右孩子找！！

4.3 插入key的过程

         我们多开一块空间的目的先进行无脑插入，然后再去检查该节点是否满了，如果满了再进行分裂调整，但是我们有些时候可能不光要插入key，还要插入新增的节点。

//每次循环往cur插入newkey和child
void InsertKey(Node* node, const K& key, Node* child)
{
	int end = node->_n - 1;
	while (end >= 0)  //如果我比你小，你就往后挪   类似插入排序逻辑
	{
		if (key < node->_keys[end]) //挪动key 还要挪动右孩子
		{
			node->_keys[end + 1] = node->_keys[end];
			node->_subs[end + 2] = node->_subs[end+1];
			--end;
		}
		else break; //找到了就放
	}
	node->_keys[end + 1] = key;
	node->_subs[end + 2] = child;
	if (child)  child->_parent = node; // 一定要记得反向链接维护parent指针
	++node->_n;
}

1、只有多次分裂的时候才会出现需要链接新增的节点，如果只有一次分裂的话，child就是nullptr，所以在反向链接的时候要注意！！！

2、在插入关键字的时候，我们按照插入排序的逻辑从后开始往前找，不断将比自己大的元素往后挪，挪动的时候要别忘了把他的右子树也跟着往后挪动。

3、end必须设置成int而不能是size_t，因为是从后往前找的，所以end是有可能会出现负数的。

4.4 B树的插入整体实现

bool Insert(const K& key)
{
	if (_root == nullptr) //如果我为空 那我就让自己成为新的根
	{
		_root = new Node;
		_root->_keys[0] = key;
		++_root->_n;  
		return true;
	}
	//如果不为空  开始执行插入逻辑
 
	pair<Node*, int> ret = Find(key);
	if (ret.second>=0) return false;
	//如果没有找到，find顺便带回了要插入的叶子节点
	Node* cur = ret.first;
	//每次循环往cur插入newkey和child
	
	K newKey = key;
	Node* child = nullptr;
	while (1)
	{
		InsertKey(cur, newKey, child);
		//情况1 没满， 直接结束
		if (cur->_n < M) return true;
 
		Node* brother = new Node;
		//分裂一半[mid+1,M-1]给兄弟  找到中间那个值
		size_t mid = M / 2;
		size_t i = mid + 1;
		size_t j = 0;
		for (; i < M; ++i, ++j)
		{
			//拷贝key和key的左孩子
			brother->_keys[j] = cur->_keys[i]; 
			brother->_subs[j] = cur->_subs[i]; //节点也拷过去
			//与父亲建立连接
			if (cur->_subs[i])  cur->_subs[i]->_parent = brother;
		
			//清理一下方便观察
			cur->_keys[i] = K();
			cur->_subs[i] = nullptr;
		}
		// 还有最后一个右孩子拷过去
		brother->_subs[j] = cur->_subs[i];
		if (cur->_subs[i])  cur->_subs[i]->_parent = brother; //孩子如果不是空  那么父亲就得更新一下
		cur->_subs[i] = nullptr;
 
		brother->_n = j;
		cur->_n -= (brother->_n + 1);//因为还要把中位数往上放
 
		K midKey = cur->_keys[mid];
		cur->_keys[mid] = K();//方便观察
		//转化成往cur的parent去插入 cur->[mid]和 brother
		// 说明刚刚分裂是根节点
		if (cur->_parent == nullptr)
		{
			_root = new Node; //最坏情况 我的父亲是空，那就造一个新的根出来
			_root->_keys[0] = midKey;
			_root->_subs[0] = cur;
			_root->_subs[1] = brother;
			_root->_n = 1;
			//链接起来
			cur->_parent = _root;
			brother->_parent = _root;
			break;
		}
		else //如果父亲不是空，还可以向上调整
		{
			// 转换成往parent->parent 去插入parent->[mid] 和 brother
			newKey = midKey;
			child = brother;
			cur = cur->_parent;
		}
	}
	return true;
}

1、如果什么也没有，那么自己就成为新的树。

2、通过find函数去找B树中是否存在这个关键字，如果存在就结束，不存在，那就把返回的pair中的first（待插入的叶子节点）提取出来。

3、因为有可能会涉及到多次分裂，所以我们要将插入的函数写在循环里面（通过cur、newkey、child来帮助我们迭代 ），然后每次插入之后就去判断是否还要进行分裂。如果没满就结束，如果满了就分裂。

4、分裂一半的key和节点（要注意节点的反向链接）给自己的兄弟，然后清理一下数据方便我们调试观察，最后有一个右孩子还得再拷贝一次。

5、传中位数的时候，如果cur没有父亲，那么就直接造一个父亲出来。如果cur有父亲，就更新一下cur、newkey、child，继续往上迭代去走。将问题转化成往父亲节点插入中位数和一个brother节点。

4.5 B树的中序遍历验证

       他的整体逻辑是左、根、左、根、左、根……右  所以我们可以将前两个过程抽出来，然后最后再单独处理右。走一个中序遍历的逻辑实现有序。

	void _InOrder(Node* cur)
	{
		if (cur == nullptr)  return;
		// 左 根  左 根  ...  右
		size_t i = 0;
		for (; i < cur->_n; ++i)
		{
			_InOrder(cur->_subs[i]); // 左子树
			cout << cur->_keys[i] << " "; // 根
		}
		_InOrder(cur->_subs[i]); // 最后的那个右子树
	}
 
	void InOrder()
	{
		_InOrder(_root);
	}

 附上测试用例：

void testBtree()
{
	BTree<int, 3> t;
	int a[] = { 53, 139, 75, 49, 145, 36, 101 };
	for (auto e : a)  t.Insert(e);
	t.InOrder();
}
 

 4.6 整体的代码

#pragma once
#include<iostream>
using namespace std;
 
//K表示存的地址  M表示最多有几个分支
template<class K,size_t M> 
struct BTreeNode
{
	BTreeNode()
	{
		for (size_t i = 0; i < M; ++i)
		{
			_keys[i] = K();  //K的默认构造
			_subs[i] = nullptr;
		}
		_subs[M] = nullptr;
		_parent = nullptr;
		_n = 0;
	}
	//关键字永远比孩子少一个  为了方便插入，我们多开一个空间 预防边界情况
	K _keys[M]; //M-1个关键字
	BTreeNode<K, M>* _subs[M + 1];// 孩子的集合 M个孩子
	BTreeNode<K, M>* _parent;//父亲节点  方便插入的时候向上回溯
	size_t _n; //实际存了多少节点
};
 
 
template<class K, size_t M>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:
	pair<Node*, int> Find(const K& key)  //查找这个节点以及对应关键字的下标
	{
		Node* cur = _root;
		Node* parent = nullptr;//如果没找到， 把父亲节点带回来
		while (cur) //因为i每次都要重头开始算
		{
			size_t i = 0; 
			while (i < cur->_n)
			{
				if (key < cur->_keys[i]) break; //keys[i]的左孩子根他的下标是相等的
				else if (key > cur->_keys[i]) ++i;     //左才会往下跳  比右小i++
				else return make_pair(cur, i);
			}
			//但是有可能走到空都不会结束  找不到就往自己的孩子去跳
			parent = cur;
			cur = cur->_subs[i];
		}
		return make_pair(parent, -1);
	}
 
	//每次循环往cur插入newkey和child
	void InsertKey(Node* node, const K& key, Node* child)
	{
		int end = node->_n - 1;
		while (end >= 0)  //如果我比你小，你就往后挪   类似插入排序
		{
			if (key < node->_keys[end]) //挪动key 还要挪动右孩子
			{
				node->_keys[end + 1] = node->_keys[end];
				node->_subs[end + 2] = node->_subs[end+1];
				--end;
			}
			else break; //找到了就放
		}
		node->_keys[end + 1] = key;
		node->_subs[end + 2] = child;
		if (child)  child->_parent = node; // 要记得向上连接
		++node->_n;
	}
 
	bool Insert(const K& key)
	{
		if (_root == nullptr) //如果我为空 那我就让自己成为新的根
		{
			_root = new Node;
			_root->_keys[0] = key;
			++_root->_n;  
			return true;
		}
		//如果不为空  开始执行插入逻辑
 
		pair<Node*, int> ret = Find(key);
		if (ret.second>=0) return false;
		//如果没有找到，find顺便带回了要插入的叶子节点
		Node* cur = ret.first;
		//每次循环往cur插入newkey和child
		
		K newKey = key;
		Node* child = nullptr;
		while (1)
		{
			InsertKey(cur, newKey, child);
			//情况1 没满， 直接结束
			if (cur->_n < M) return true;
 
			Node* brother = new Node;
			//分裂一半[mid+1,M-1]给兄弟  找到中间那个值
			size_t mid = M / 2;
			size_t i = mid + 1;
			size_t j = 0;
			for (; i < M; ++i, ++j)
			{
				//拷贝key和key的左孩子
				brother->_keys[j] = cur->_keys[i]; 
				brother->_subs[j] = cur->_subs[i]; //节点也拷过去
				//与父亲建立连接
				if (cur->_subs[i])  cur->_subs[i]->_parent = brother;
			
				//清理一下方便观察
				cur->_keys[i] = K();
				cur->_subs[i] = nullptr;
			}
			// 还有最后一个右孩子拷过去
			brother->_subs[j] = cur->_subs[i];
			if (cur->_subs[i])  cur->_subs[i]->_parent = brother; //孩子如果不是空  那么父亲就得更新一下
			cur->_subs[i] = nullptr;
 
			brother->_n = j;
			cur->_n -= (brother->_n + 1);//因为还要把中位数往上放
 
			K midKey = cur->_keys[mid];
			cur->_keys[mid] = K();//方便观察
			//转化成往cur的parent去插入 cur->[mid]和 brother
			// 说明刚刚分裂是根节点
			if (cur->_parent == nullptr)
			{
				_root = new Node; //最坏情况 我的父亲是空，那就造一个新的根出来
				_root->_keys[0] = midKey;
				_root->_subs[0] = cur;
				_root->_subs[1] = brother;
				_root->_n = 1;
				//链接起来
				cur->_parent = _root;
				brother->_parent = _root;
				break;
			}
			else //如果父亲不是空，还可以向上调整
			{
				// 转换成往parent->parent 去插入parent->[mid] 和 brother
				newKey = midKey;
				child = brother;
				cur = cur->_parent;
			}
		}
		return true;
	}
 
	void _InOrder(Node* cur)
	{
		if (cur == nullptr)  return;
		// 左 根  左 根  ...  右
		size_t i = 0;
		for (; i < cur->_n; ++i)
		{
			_InOrder(cur->_subs[i]); // 左子树
			cout << cur->_keys[i] << " "; // 根
		}
		_InOrder(cur->_subs[i]); // 最后的那个右子树
	}
 
	void InOrder()
	{
		_InOrder(_root);
	}
 
 
private:
	Node* _root=nullptr;
};
 
 
void testBtree()
{
	BTree<int, 3> t;
	int a[] = { 53, 139, 75, 49, 145, 36, 101 };
	for (auto e : a)  t.Insert(e);
	t.InOrder();
}

 4.7 B树的性能分析

       对于一棵节点为N度为M的B-树，查找和插入需要$log{M-1}N$~$log{M/2}N$次比较，这个很好证明：对于度为M的B-树，每一个节点的子节点个数为M/2 ~(M-1)之间，因此树的高度应该在要
$log{M-1}N$和$log{M/2}N$之间，在定位到该节点后，再采用二分查找的方式可以很快的定位
到该元素。
         B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则$log_{M/2}N$ <=4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。

4.8 B树的删除过程分析 

 1、删除36

 2、删除40

3、删49 

 4、删150

5、删160 

 五、B树系列

5.1 B+树

       B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

（1）分支节点的子树指针与关键字个数相同（相当于去掉了左边的子树，相比B树取消了孩子和关键字的包含关系，而是一一对应）

（2）分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间（和B树一致）
（3） 所有叶子节点增加一个链接指针链接在一起（这样就可以直接找到叶子节点，不一定需要从根去找了！！）
（4）所有关键字及其映射数据都在叶子节点出现（1、分支节点和叶子节点有重复的值，分支节点存的是叶子节点的索引->key.2、父亲中存的是孩子节点中的最小值做索引）

和B树规则区别总结：

1、简化B树孩子比关键字多一个的规则，变成了相等（一一对应）。

2、而key value都存在叶子节点上，一方面是节省空间，一方面是方便遍历查找所有值

B+树的特性：
1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
2. 不可能在分支节点中命中（因为只存k而没有存kv）。
3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层

5.2 B+树的插入过程分析

 用序列{53, 139, 75, 49, 145, 36, 50,47,101}构建B+树的过程如下：

1、插入53

2、插入139

 3、插入75

4、插入49

 5、分裂

6、插入145

 7、插入36

8、插入50 

9、分裂

 10、插入47

11、插入101

 12、分裂

13、二次分裂

和B树插入的区别：

1、一开始创建的是两层，一层做根，一层做分支

2、父亲节点存的是孩子节点中的最小值做索引，如果最小值更新了，那么往上的索引值都要全部更新

3、孩子不再是比key多一个（包含关系），而是和key相等（一一对应关系）

4、分裂的时候，不再是把中位数往上拿，而是把分裂出来的兄弟节点的最小值往上拿 

5.3 B*树

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
为什么B*树的非叶子节点需要指向兄弟节点的指针呢？而B+树不需要呢？ 究竟想达到什么目的？

B+树的分裂：
        当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*树的分裂：
        当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。（所以B*树的关键字和孩子数量->[2/3M——M]）
      所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

5.3 B树系列总结

B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；
B*树：一棵更丰满的，空间利用率更高的B+树。