2019-05-29

B/B+树

缘起

为了解决BST数据倾斜的问题，我们引入了AVL等平衡二叉树的结构. 但是对于海量数据的今天, 内存算法近乎不可能, 所以很多时候对数据进行检索的时候其实下一次要读取的数据其实尚在磁盘中. 而我们知道数据在磁盘中是以块（block）为单位存放的, 并且数据的读取要经历

柱面–>磁道–>块–>系统总线传输

上面的过程（参见【1】）. 其中前三个属于磁头定位要读取数据的过程，最为耗时（甚至可长达0.1s之久）. 所以对于海量数据的检索问题，我们必须要尽可能减少磁盘IO的次数. 因此降低树的高度势在必行——因为每次读取下一个树的节点就有可能是去磁盘通过IO文件读取数据. 所以原先的二路平衡查找拓广为多路平衡查找树势在必行. 这就是B系列的查找树（B、B+、B*）. 关于B树的前世今生以及B树的高维推广——R树（用于地图搜索）可参见【2】, 七月大神的博文.

分析

简单来讲，下面展示了B树的增删查三种操作. 查询的话没什么好说的，与BST完全类似. 只是定位到了节点之后，使用顺序表哨兵查找（而没有使用二分搜索，图简便嘛~ 因为定位到了节点之后，关键值数组元素个数优先，例如本例3阶B树的关键值数组至多2个元素, 二不二分其实和顺序哨兵查找没有太大性能差别了）检索到数据.

增加节点的话, 首先查询，如果查到了就不允许增加. 如果没查到，此时待插入的位置一定是叶子节点. 所以B树的增一定是从叶子节点开始增的. 而一旦关键值个数>=m(m是B树的阶数)，则爆了, 就要分裂. 关键值数组分裂成key[1,…,s-1]和key[s,…,M]，s=(M+1)/2, 分裂出来的尚没有父节点的指针和key[s]添加到父节点中去. 然后父节点可能再次分裂. 递推往上.

删除节点的话, 首先查询, 没查到，删除失败，查到了，先找到bst意义上该节点的后继（注意，该后继节点一定是叶子节点）. 然后将待删除的节点的值替换为该后继的值,然后删除该后继. 所以和新增操作一样，B树的删除操作也是从叶子节点开始的. 删除的话会导致节点个数减少以至于不满足B树节点的定义. 如果左右兄弟有的借（就是下面的borrow函数），就借一个过来（确切讲，是父节点下来一个关键值, 兄弟上去一个关键值），则这种减少不会向父亲传递. 否则的话, 也即左右兄弟都穷, 则就要向父亲借一个, 则就会使用合并操作（也就是下面的merge函数），然后这种减少再往祖父传播.

#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;


const int M = 3; // 本程序以 3阶B树为例子, m阶B树的定义是根节点至多m棵子树，至少2棵子树，但是非根节点至少m/2的向上取整棵子树，至多m棵子树

typedef struct BTNode
{
	int keynum, key[M+1]; // keynum是该节点中实际的键值的个数，key是该节点中的关键数组. 注意, 索引0不用于存储关键值,即关键值存储在 key[1,...,keynum],而ptr[0,...,keynum]是该节点的子树, 但是keynum<=M-1, 因为最多M棵子树. 所以keynum最多到M-1， 即key[1,...,M-1], 这样最多M棵子树, 并且子树是 ptr[0,...,M-1], 那么问题来了——为什么需要前后分别多出key[0]和key[M]呢? 因为下面插入节点的时候, 要先插入, 如果爆了，再分裂. 所以key[1,...,keynum]前后必须要各留出一个位置用于暂时安放插入元素, 这里keynum<=M-1, 所以key要开成[0,...,M],即key[M+1]
	BTNode *parent, *ptr[M+1]; // parent是父节点、ptr是子树的根节点数组（对于叶子节点, ptr中全部是0）, 其中ptr[i]指向的子树表示上面的值的范围是 (key[i],key[i+1]) 1<=i<keynum, 而对于ptr[0]指向的子树表示值<key[1], 对于ptr[keynum]，它表示值都 > key[keynum] 具体参见图1
	BTNode(int key):keynum(1),parent(0)
	{
		this->key[1] = key;
		memset(ptr,0,sizeof(ptr));
	}
	BTNode(){}
} BTNode, *BTree;

struct Result // 查找结果
{
	BTree ptr; // 指向B树节点的指针
	int i; //如果ok为false的话,则 ptr->key[i] < target < ptr->key[i+1](当1<=i<ptr->keynum) 或者 target < ptr->key[1]（当i=0） 或者 target >ptr->key[ptr->keynum](当i=ptr->keynum) 可以参见图1，如果ok为true的话, ptr->key[i] = target(1<=i<=keynum)
	bool ok; // 查没查到?
};

// 在B树节点p上寻找key, 寻找的结果信息封装在r中
void find(BTree p, int key, Result &r) // 注意, B树亦是BST类型的, 即p->key 是非降的数组
{
	p->key[0] = key; // 设置顺序查找哨兵， 防止r.i 不断的小下去, 设置哨兵之后, r.i最小只会小到0
	r.i = p->keynum;
	while(key < p->key[r.i]) r.i--;
	if (r.i && key==p->key[r.i]) r.ok = true; // 如果不是因为等于0才相等, 则就是找到了
	else r.ok = false;
}

Result search(BTree root, int key) // 在以root为根的B树中查找关键字key
{
	BTree p = root,q = 0; // p是移动指针, q指向p的父亲
	Result r;
	while (p)
	{
		q = p;
		find(p, key, r); // 在p上探索一番
		if (r.ok) // 如果找到了
		{
			r.ptr = p;
			return r;
		}
		p = p->ptr[r.i];
	} // while循环结束, 如果中间没有return的话, 说明p=0了, q是叶子节点, 则ptr 应该指向q，而且q上没有一个关键值和key相等的
	r.ptr = q;
	return r;
}

void split(BTree q, int s, BTree &p) // 将q->key[s+1],...,q->key[M]与q->ptr[s],...,q->key[M]移动到节点p去， 即q分裂 M-s个关键值到p去(p会新开辟), q分裂前是 q->key[1,...,M], 所以q剩下q->key[1,..,s]，p得到了q->key[s+1,...,M]
{
	p = new BTNode();
	p->keynum = M-s;
	p->parent = q->parent; // 因为p是从q分裂出来的, 所以p和q应该是同一个父亲.
	memcpy(p->key+1, q->key+(s+1), sizeof(int)*(M-s));
	for (int i= 0; i<=M-s; i++)
	{
		p->ptr[i] = q->ptr[i+s];
		if (p->ptr[i]) p->ptr[i]->parent = p; // 爹变了
	}
	q->keynum = s-1; // q的关键值个数变成了 s-1个，诶，等一下, p不是只分掉了s+1到M么? 那么q不应该是 1,...,s么? 其实不是, 因为分裂之后, 要将p插入到q的父节点上去, 而多一根指针就需要多一个关键值, 所以需要q[s]作为这个关键值插入到q的父节点上去. 但是B树节点中是不能重复的, 所以既然q[s]以后将作为父节点上的一个节点, 那自然不可能继续在原本的q上存在了
}

void insert(BTree q, int i, int x, BTree p) // 将关键值x与指向关键字都比x大的指针p插到q->key[i+1]位置上,即x和p插到q->key[i]的后面, 这只是封装了一个单纯的插入的小函数
{
	for (int j = q->keynum; j>i; j--)
	{
		q->key[j+1] = q->key[j];
		q->ptr[j+1] = q->ptr[j];
	}
	q->key[i+1] = x;
	q->ptr[i+1] = p;
	q->keynum++;
}

void insert(BTree &root, int key, BTree q, int i) // 往root为根的B树节点q(实际场景中就是叶子节点)的q->key[i]和 q->key[i+1]之间插入key
{
	bool ok = false; // 插入是否搞定了
	BTree p = 0;
	int x = key; // x会变
	while(!ok && q) // q亦会变
	{
		insert(q,i,x,p); // 将x和p插入到q->key[i]后面，即成为 q->key[i+1]与q->ptr[i+1]
		if (q->keynum < M) // 根据B树的定义, 节点最多M-1个关键值, 如果插入之后, 关键值的个数依旧没爆,则插入完成, 因为不需要分裂
		{
			ok = true;
		}
		else // 说明因为插入x与p导致q节点爆炸了(q->keynum>=M了), 则违法B树定义, 则就要分裂q节点
		{
			split(q, (M+1)/2, p); // q分裂M-(M+1)/2 个关键值到p 中去, p会新开辟，即 q[1,...,(M+1)/2] 保留在q中
			x = q->key[(M+1)/2]; // x位于q节点上（并没有分裂到p上去）并且x是q上最后那个节点
			q = q->parent; // q到其父节点去, 
			if (q) // 如果还有父节点的话, 则需要将这里分裂出来的p插入到q的父节点中去.(注意,目前新分裂出来的p尚没有父节点哩!)
			{
				Result r;
				find(q, x ,r); // 在q(已经往上走了一个节点)中寻找x, 查找的结果封装在r中.
				i = r.i; // 更新i,更新之后的i满足 q[i]<x<q[i+1],注意, 不会出现相等, 因为q[i]是原本的q(q已经变动到它的父节点上去了)的父节点上的值, 而这里x是原本q上的值, 而B树上节点的关键值是不一样的. 现在是想将p插入到原本q的父节点上去, 而根据图1知道多一根指针（ptr）就必须要多一个关键值, 所以原本q的父节点上新增哪个关键值呢? 就多原本q分裂之后的最后那个关键值就行了.
			}
		}
	} // ok是true或者 q已经变成空的了
	if (!ok) // 如果q变成空的了还不ok, 则意味着原本的根节点都分裂了, 即上面while循环最后加入的x 和 p 已经将原先的根节点撑爆了.然后原先的根节点分裂了, x是分裂出来的值（要作为新的根节点的），root是原先的根节点, p是分裂出来尚未找到父节点的节点
	{
		BTree newRoot = new BTNode; // 新的节点
		newRoot->keynum = 1; // 只有一个值, 就是x
		newRoot->key[1] = x;
		newRoot->parent = 0;
		newRoot->ptr[0] = root; // 原先的root和这里的p作为新的根节点的两棵子树
		newRoot->ptr[1] = p;
		root->parent = p->parent = newRoot;
		root = newRoot;
	} // 这个过程可以参见图2
}

void insert(BTree &root, int key) // 往 root为根的树中插入key值, 分成2步（对应三个insert重载） 1、找到插入的位置（如果存在，一定是叶子节点） 2、自底向上插入(中间的插入)，一旦节点爆了，就分裂，然后继续往上插，直至没爆，注意, B树插入节点爆了的话不是将多余的节点放进兄弟节点(如果兄弟有多余位置),而是分裂
{
	Result r = search(root, key);
	if (!r.ptr) // 如果root是空树(因为只有是空树, 则search中的while循环根本不会跑, 则r.ptr就是0)
	{
		root = new BTNode(key);
		return;
	}
	if (r.ok)
	{
		puts("关键字已存在, 插入失败");
		return;
	}
	insert(root,key,r.ptr, r.i); //关键字不存在，就要插入，注意, 如果关键字不存在的话, 那么r.ptr 就是叶子节点, 即B树插入新的节点都是从叶子节点开始的
}

void getSibling(BTree p, int tmp, BTree &lsibling, BTree &rsibling, int &index) // 本函数的目的是获取指向p节点左右孩子的指针, index表示p的父节点的key数组中小于p->key[1]的关键值(这里就是tmp)的最大索引
{ // 参见图3
	Result r;
	find(p->parent, tmp, r);
	index = r.i; // r.ok 一定是false. 并且r.i是p的父节点中比p->key[1](即这里的tmp)小的最大的那个关键值索引
	if (r.i == p->parent->keynum) rsibling = 0; // 如果搜索结果发现p的父节点中任意一个关键值都严格小于tmp的话, 则p是没有右兄弟的
	else rsibling = p->parent->ptr[r.i+1]; // 否则右兄弟就是它
	if (!r.i) lsibling = 0; // 如果p的父节点中所有的关键值都严格大于tmp的话(则p应该是p的父节点的第一根指针)
	else lsibling = p->parent->ptr[r.i-1]; // 否则左兄弟指针就是这个
}

void borrow(BTree p, BTree sibling, int index, char tag) // p所指向的节点向它的左兄弟或者右兄弟借一个关键字,tag='r'表示向右兄弟借，'l'表示向左兄弟借，index表示p的父节点中小于p->key[1]的元素的最大索引
{
	switch(tag)
	{
	case 'l':  // 参看 图4
		for (int i = p->keynum; i; i--) p->key[i+1] = p->key[i]; // p的关键值右移动一格，迎接从左孩子借来的关键值,（因为是BST，所以借来的关键值一定排在p的关键值的首位）
		for (int i = p->keynum; ~i; i--) p->ptr[i+1] = p->ptr[i]; // p的指针右移动一格, 迎接从左孩子借来的关键值身后的那一根指针.
		p->ptr[0] = sibling->ptr[sibling->keynum]; // 赋值指针
		if (p->ptr[0]) p->ptr[0]->parent = p; // 改爹了 原先爹是左孩子, 现在变成了p
		p->key[1] = p->parent->key[index]; // 父节点下来一个
		p->parent->key[index] = sibling->key[sibling->keynum]; // 左兄弟上去一个（所以父节点的元素个数压根没变, 不会影响父节点作为B树节点的定义，也就是这种借贷不会向上传播. 受影响的只有左兄弟，但好在左兄弟富裕,借的起）
		sibling->keynum--;
		p->keynum++;
		break;
	case 'r':
		p->key[++p->keynum] = p->parent->key[index+1]; // 父节点下来一个
		p->parent->key[index+1] = sibling->key[1]; // 右兄弟上去一个, 父节点的关键值个数没有受影响,不会传播
		for (int i=1; i < sibling->keynum; i++) sibling->key[i] = sibling->key[i+1]; // 因为右兄弟被借去一个, 所以要整体左移动
		p->ptr[p->keynum] = sibling->ptr[0]; // 接管
		if (p->ptr[p->keynum]) p->ptr[p->keynum]->parent = p; // 改爹了
		for (int i = 0; i< sibling->keynum; i++) sibling->ptr[i] = sibling->ptr[i+1]; // 指针左移动一个
		sibling->keynum--;
		break;
	}
}

void merge(BTree p, int index, BTree sibling, char tag) // 将p所指向的节点与它的左兄弟或者右兄弟外加父节点上的一个关键字（父节点少了一根指针,  从而也要少一个关键值）合并成一个新的节点,tag='r'表示与右兄弟合并,tag='l'表示与左兄弟合并,index表示p的父节点中小于p->key[1]的元素的最大索引
{
	int tmp;
	switch(tag)
	{
	case 'l': // 与左兄弟合并 确切讲, 是p外加p->parent->key[index]合并到p的左兄弟中去, 则p的左兄弟的关键字个数<(M-1)/2+1+(M-1)/2=M, 则合并后的节点的关键字个数至多M-1, 所以子树棵树<=M,符合B树节点的定义. 之所以考虑并入左子树, 是因为这样比较简单
		tmp = sibling->keynum; // 因为后面的 sibling->keynum 会发生变化, 所以这里临时记录一下
		sibling->key[++sibling->keynum] = p->parent->key[index];
		for (int i = 1; i<= p->keynum; i++) sibling->key[++sibling->keynum] = p->key[i]; // 将p的关键值并入左兄弟
		for (int i = 0; i<=p->keynum; i++) // 开始传送指针部分
		{
			sibling->ptr[++tmp] = p->ptr[i];
			if (p->ptr[i]) p->ptr[i]->parent = sibling; // 改爹
			for (int i = index; i<p->parent->keynum-1;i++) // p的父节点少掉了一个关键值又少掉了一根指针, 所以合并起来较方便
			{
				p->key[i] = p->key[i+1];
				p->ptr[i] = p->ptr[i+1];
			}
		}
		p->parent->keynum--;
		break;
	case 'r': // 与右兄弟合并, 确切讲，是右兄弟外加p->parent->key[index+1]并入p, 之所以采用这个顺序是因为追加比较简单，同理也是符合B树定义的. 
		tmp = p->keynum; // 因为后面会变
		p->key[++(p->keynum)] = p->parent->key[index+1]; // 父节点的一个关键值并入
		for (int i = 1; i <= sibling->keynum; i++)//将右兄弟的关键字写进p的尾部		
			p->key[++(p->keynum)]=sibling->key[i];
		for (int i = 0; i <= sibling->keynum; i++)		
		{
			p->ptr[++tmp]=sibling->ptr[i];//将右兄弟的指针部分移进p指向的节点
			if (sibling->ptr[i])			
				sibling->ptr[i]->parent=p;//修改移动过来的指针指向的节点的父亲属性			
		}
		for (int i = index+1; i <= p->parent->keynum-1; i++)//父节点少了一个关键字p->parent->key[index+1]与一根指针lORr,就需要将后续的递补上来
		{
			p->parent->key[i]=p->parent->key[i+1];
			p->parent->ptr[i]=p->parent->ptr[i+1];
		}
		p->parent->keynum--;//父节点少了一个关键字与一个指针
		break;
	}
}

void delNode(BTree &root, BTree p, int _index) // 删除以root为根的B树的节点p上的p->key[_index], 注意, 这个p是叶子
{
	int tmp = p->key[_index]; // 要删掉的值
	for (int i = _index+1; i<=p->keynum;i++) p->key[i-1] = p->key[i]; // 关键值向前移动一格
	for (int i = _index; i<=p->keynum; i++) p->ptr[i-1] = p->ptr[i]; // 指针向前移动一格
	p->keynum--; // 已经删除了p上_index位置的关键值 则因为要维护B树的定义
	BTree lsibling, rsibling, temp = 0;
	int index;
	while(p->parent && p->keynum < (M-1)/2) // 只要p不是根节点(根节点的子树棵数需要不少于2，和非根节点不同)并且p的关键值个数<(M-1)/2(则子树棵树<(M+1)/2,而这就是M/2的向上取整，从而不满足B树定义), 即只要非根节点删除导致不满足B树定义, 就要向左邻右舍借或者如果邻舍都是穷鬼的话 就要向父节点借了
	{
		getSibling(p, tmp, lsibling, rsibling, index); // 得到p的兄弟，和p的父亲的关键值中小于要删掉的值的最大索引
		if (rsibling && rsibling->keynum>=(M+1)/2) // 如果有右兄弟, 并且右兄弟的子树棵树>=M/2向上取整+1（关键值的个数+1=子树的棵树）的话, 则右兄弟富裕，可以问他接一个关键值，就不需要将此事告知父节点了,这里是先问右兄弟借, 其实先问左兄弟借也行
		{
			borrow(p, rsibling, index, 'r');
			break;
		}
		else if (lsibling && lsibling->keynum >= (M+1)/2) //如果右兄弟不给力， 但是有左兄弟，并且左兄弟也富裕, 则可以问左兄弟借一个关键值
		{
			borrow(p, lsibling, index, 'l');
			break;
		}
		else // 左右兄弟都是穷鬼, 即子树棵树都恰好是 (M+1)/2, 亦即关键值个数都恰好是 (M-1)/2
		{
			if (rsibling) // //如果右兄弟存在(但是右兄弟的关键字只有(M-1)/2个,不富余)的话,就与右兄弟合并,注意，确切讲是将右兄弟的东西并入到p所指向的节点中去了
			{
				merge(p, index, rsibling, 'r'); // p与右兄弟合并
				rsibling = 0; // 防止野指针
				temp = p; // 因为merge函数的处理是将右兄弟并入了p
			}
			else // //否则与左兄弟合并(注意，因为p不是根节点, 所以左右兄弟至少存在一个,不可能都不存在——哪怕是根节点只有2棵子树),确切讲是将p中的东西并入到左兄弟中去了		
			{
				merge(p, index, lsibling, 'l');
				p = 0; // 防止野指针
				temp = lsibling; // 因为merge函数的处理是将p并入了左兄弟
			}
			p = temp->parent; // 因为父节点少了一个元素+一根指针, 所以可能不满足B树节点的定义了. 所以父节点可能要进一步处理. 这就是如果左右邻居都穷的话, 就要问父节点借一个关键值，导致这种穷困会向父节点进行传播
		}
	} // while循环结束的方式是 1.变成根节点 2. p的关键值个数已经满足B树节点要求了
	if (!p->keynum) // 如果p变成了根节点, 并且根节点一个节点都没了(B树节点要求根节点至少2棵子树, 所以至少1个关键值), 如果一个关键值都没了, 则就不行(注意， 这里不要写p->keynum <(M-1)/2，因为如果没p->keynum 少到0也是符合B树要求的,换言之, 只有p->keynum为0才需要处理 )
	{
		root = temp; // temp是根节点的孩子, 但是因为它穷，向父节点（即根节点）借了一个关键值之后导致根节点都给减没了. 则temp就是新的根节点
		if (root) root->parent = 0; // 设置新晋根节点的父节点是NULL
	}
}


void del(BTree &root, int key) // 在以root为根的B树中删除关键字key, 想法其实和bst是一样的（B树本质也是bst）, 是先找到要删除的顶点, 然后与最左边的孩子的关键值的第一个交换一下, 则要删除的就是这个底层叶子节点了(最后都是叶子倒霉), 这个在bst、splay、AVL中都是这样删除的
{
	Result r = search(root, key);
	if (!r.ptr || !r.ok)
	{
		puts("该关键字不存在");
		return;
	}
	BTree p = r.ptr->ptr[r.i]; //  r.ptr->key[r.i] = key, 而 r.ptr->ptr[r.i] 为根节点的树上的值都是严格大于key的
	if(p)
	{
		while(p->ptr[0]) p = p->ptr[0]; // 到达最后底层的叶子节点
		r.ptr->key[r.i] = p->key[1]; // 将待删除的关键值替换为第一个关键值， 注意，这个关键值是顶替r.ptr->key[r.i]的(其实BST也是一样的)
		delNode(root, p, 1);
	}
	else delNode(root, r.ptr, r.i); // r.ptr是叶子, 则直接删掉该节点上的关键值的 r.i索引即可
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	BTree root = 0;
	int a[15]={45,24,53,90,3,12,50,61,70,100,30,26,85,70,7}; // 测试数据的图例参见图4之后的图示
	//测试Insert模块
	for (int i = 0; i < 15; i++)insert(root,a[i]);//最后生成的B树与严蔚敏书上有些出路..但是我纸上模拟了一下，我得到的结果依旧是对的（从而可以知道——不同的插入顺序得到的B树形态是不同的）	
	//测试Delete模块
	for (int i = 0; i < 15; i++)
	{
		del(root,a[i]);	
	}
	return 0;
}

从上面的代码结合下面的图示可以看出，B树所有的叶结点都处于相同的深度. 因此B树是平衡查找树.

大家广为熟知的mysql的存储引擎就是使用B+树实现的，其实B系列的树在内存算法中是没有太大优势的，可是一旦到了海量数据的外存算法，威力就显现出来了. 而且对于海量数据的B+树检索，因为根节点以及上面若干层的节点被反复query，所以基本这几个磁盘块一旦被读入内存，就一直驻在内存中了，不会重读IO的. 其实一般的数据库引擎一旦启动，这几个磁盘块就被主动换入内存页了.

下图演示了一个查找以职工号为关键字，职工号为38的记录的简单示意图，这里假设每个物理磁盘块仅能容纳3个索引，磁盘的I/O操作的基本单位是块（block),磁盘访问很费时，采用B+树有效的减少了访问磁盘的次数

注意, 对于mysql的B+树索引，和本文程序实现的不大一样. mysql的B+树索引大概长下面的样子

最显著的特点是底层叶子节点之间有一根双向链表连接，目的就是为了高效实现范围查询

但是上图显示的是一维的. 仅仅叶子节点存放输入点，内部节点等二左子树中的最大者（即内部节点存放的都是索引节点而已）. 所以mysql的B+树索引的构建是来一个数据，走二叉树定位到要插入的节点, 如果存在, 则不允许插入（这里是mysql索引的简化版——不允许重复数据）,如果不存在，则定位到叶子节点, 该插入插入，该分裂分裂

最后说一句, 同样的元素, 插入的顺序不同, 得到的B树结构未必一样.