B-树的实现

发表于 2018-05-22 更新于 2024-09-22 分类于数据结构

我们常看到的查找树都是二叉树，如二叉查找树，AVL树、伸展树等，但还有一种常用的查找树不是二叉树。这种树叫B-树，是一种多叉树。

阶为M的B-树是一棵具有下列结构特性的树
树的根或者是一片树叶，或者其儿子数在2和M之间。（根可以是叶子节点，不是的话，儿子数就要在2-M之间）
除根外，所有非树叶节点的儿子树在┌M/2┐和M之间。
所有的树叶都在相同的深度上。

这是一棵4阶的树，可以仔细观察下。之后的插入操作都会以这棵树为demo。

应符合以下条件

不管什么结点，都至多有
M -1个关键字，

M 棵子树（假如可以有子树的话）；
根结点如果不是叶子结点的话，那么至少有两棵子树，即至少1个关键词；
除根以外的所有结点（包括树叶），至少有┌M/2┐-1个关键字；（┌M/2┐是取上整，└M/2┘是取下整）
根据上面也不难想到非叶子结点的关键字个数=指向儿子的指针个数-1；

有两种比较流行的B-树，一种是实际数据只存储在树叶上，还有一种是允许存储在内部节点上，如二叉查找树中所做的那样。在这里我使用的是第二种，内部节点也可以存储值。

B-树有两个比较关键的操作，插入及删除，比较麻烦。

插入的过程

现在想要插入15 49 42 15 48 16 4 30 17 43 20 9 25 7 21 22 ，并且是设定为4阶树，也就是一个节点最多四个孩子，三个关键字。

前三个节点插入比较简单，按顺序插入即可，此时根节点也是叶子节点。插入的时候先不管是否会超出m阶树的上限要求，因为定义时我们也会额外开辟一些空间。

第四个值15，首先查找到已经有这个值了，那么便不进行插入。插入第五个值48，发现这个节点已经有4个关键字了，已经超过了要求。那么需要进行分裂。分裂操作是插入操作过程中一个最重要的操作，因为这是处理“冲突”（即结点中的数据元素大于B树规则中要求的最大个数）的一个通用的处理方式，这种方式必须要对所有的情况都适用，而分裂是解决这一问题一种方法。分裂需要父节点腾出一个key和一个child的位置，然后在需要分裂的节点里取出中间元素放进父节点腾出的key里。需要分裂的节点被一分为二，分别作为父亲的儿子。

第六个节点16插进去没有问题，下一个插入节点4，发现需要分裂。将中间元素16放进父节点。

继续插入30,17，43，插入43后需要继分裂

插,20,9无问题，25的时候需要再次分裂

42移动到父节点之后，父节点的关键字数量也超过了限制，那么父节点也需要进行一次分裂，将中间元素抽出来当做新的父节点，如下图

插入7，继续分裂

插入21，无问题，插入22，进行分裂。

分裂完之后，发现它的父节点需要继续分裂

最终所有节点插入完成。也就是这篇文章第一张图片的那棵树。

删除的过程

为了更好的演示删除的过程，这里的B-树选择阶为5的。之前的定义提到过，M阶的B-树的非根节点，至少有┌M/2┐-1个关键字，M为5代入，至少有2个关键字。那么为什么要求是至少有┌M/2┐-1个呢？这个从插入开始说起，当某个节点插到第五个关键字时，这时候就需要分裂了，前一半两个关键字，后一半两个关键字，刚好都是最小的2个关键字，中间一个给父亲。假如M是偶数为6，插入第六个关键字的时候需要分裂，前一半有三个关键字，后一半有两个关键字，┌M/2┐-1仍为2，很巧妙。不管M是多少，在分裂的时候，都能恰好满足至少有┌M/2┐-1个关键字这个条件。┌M/2┐-1代码的写法是(m + 1) / 2 - 1 。

删除分两种情况。第一种删除的是叶子节点，如果删除之后，关键字数量还能满足要求，则结束，否则调用合并函数，合并函数是先尝试向兄弟节点借一个关键字，如果兄弟也不够了的话，就合并。
第二种是删除内部节点，找到子树中最大的一个关键字替换它（一定是叶子节点），然后对那个叶子节点执行删除，回到第一种情况。
文字不是非常理解没关系，下面上图。

这是一个5阶的B树，我们先删除0，去掉0之后，叶子节点仍然满足要求，删除结束。

我们接着删除12，我们要从这个节点的子树里找到一个关键字代替它，有两种方法，用比12小的最大关键字或比12大的最小关键字代替12(也就是前驱或者后继)，然后删掉那个儿子中的关键字，如下图。

在这两种方法里，代码实现的是第一种方式。第一种，删除11后，发现叶子节点只有一个10（图见上图中的第一种），关键字个数少于2个，此时应该合并，合并同样也有两种方式，和前一个兄弟节点合并或者后一个兄弟节点合并。

代码实现的是第一种，和前一个兄弟合并。接着我们删除9，尝试向前一个兄弟借个关键字，发现要是它借了，它也就不满足了，这时候我们就需要合并节点了，如下图。

现在我们来皮一下，直接删除根节点21。按照之前说到的，先找到比它小的最大关键字，一定在叶子节点里面，最大为20，替换根节点21后，然后删除叶子节点中的20。

发现叶子节点不满足条件了，向兄弟借一个关键字后变成下图。

接着删除17，兄弟无法帮助你，只能再次合并，结果如下。

父节点借出一个后，自己也不够了，需要对父节点再次进行合并，结果如下。

至此，删除操作的各种情况就都讲完了。在编写代码的时候，有一种特殊情况需要注意，对下面这种情况进行删除2的时候，正常合并结果如下。

因为根节点的关键字最少可以为1，所以一直没有对根进行合并，也没人能和根合并。。。遇到这种把根都删到没有关键字的时候，就需要重新设置根为原来根的第一个儿子了，代码里有体现。

代码实现

代码有一个欠缺的地方，大部分函数返回值都是void，无法得知函数的执行状态，更好的做法是设置一个状态结构体，返回值是状态，success，fail，error等、

类的定义

static const int m = 4;    //m阶
class BTree {
public:
	int keynum;
	int key[m + 1];				//关键字数组，多开辟一个，从1开始  0号未用， key[m]是临时空间
	BTree * parent;				//父节点指针
	BTree child[m + 1];			//孩子结点指针数组，多开辟一个  child[m]是临时空间

	//这里还涉及一个问题，如何判断一个节点是否是叶子节点，叶子节点的child[0]必定为空
	//非叶子节点的child[0]不为空
	BTree() {
		keynum = 0;
		for (int& k : key)
			k = -999;
		parent = NULL;
		for (BTree n : child) n = NULL;
	}
};

/这个结构体是查询节点返回的结果
如果，isquery是true，表明找到了这个节点，即node
如果，isquery是false，表明没有这个节点，失败于某个终端结点上，即node
如果找到了这个节点，p是在关键字中的位置，如果没有找到，返回的是应该插入的位置，例如叶子节点 1 3 5 ，寻找 4，返回的是3，方便插入。（都从1开始计数）/
struct Result {
	BTree *node;
	bool isquery;
	int p;
};

查询操作，非递归和递归都写了一遍，非递归的是没出现过问题，递归的测试了十来个数据，暂时没出现问题。

非递归查询

/*非递归查询节点*/
Result* findBTree(BTree* root, int k)
{
	Result* result = new Result();
	if (root == NULL)
	{
		return NULL;
	}
	BTree *r = root;
	int index = 1;
	int nowKey = r->key[index];
	while (r != NULL)
	{
		index = 1;
		while (index <= r->keynum)	//遍历所有关键字
		{
			if (r->key[index] == k)
			{
				//找到该节点
				result->isquery = true;
				result->p = index;		//该关键字在节点的位置
				result->node = r;
				return result;
			}
			if (k > r->key[index])
			{
				/*如果相等，则说明，r里面的最后一个关键字都没有k大*/
				if (index == r->keynum)
				{
					/*r已经是叶子节点了*/
					if (r->child[index] == NULL)
					{
						//没有该节点
						result->isquery = false;
						result->node = r;
						result->p = index + 1;
						return result;

					}
					/*还有儿子，遍历儿子*/
					r = r->child[index];
					break;
				}
				/*还没到最后一个关键字，继续遍历这个r*/
				index++;
				nowKey = r->key[index];
				continue;
			}
			/*比上一个大，比这一个小，应该遍历它的儿子，如果有儿子的话*/
			if (k < r->key[index])
			{
				/*是叶子节点，没儿子，无查找的节点*/
				if (r->child[index - 1] == NULL)
				{
					result->isquery = false;
					result->node = r;
					result->p = index;
					return result;
				}
				r = r->child[index - 1];
				break;
			}
		}

	}
}

递归查询

/*递归查询节点*/
Result * findTree2(BTree* root, int val)
{
	Result *result = new Result;
	if (!root) {
		return NULL;
	}

	//如果比第一个关键字小，检索第一个儿子
	if (val < root->key[0] && root->child[0])
	{
		return findNode(root->child[0], val);
	}
	//如果比最后一个关键字大，检索最后一个儿子
	if (val > root->key[root->keynum - 1] && root->child[root->keynum])
	{
		return findNode(root->child[root->keynum], val);
	}
	//单独判读最后一个key
	if (val == root->key[root->keynum - 1])
	{
		result->node = root;
		result->isquery = true;
		result->p = root->keynum - 1;
		return result;
	}
	//在最边上两个关键字中间
	for (int i = 0; i < root->keynum - 1; i++) {
		if (val == root->key[i])
		{
			result->node = root;
			result->isquery = true;
			result->p = i;
			return result;
		}
		else if (val > root->key[i] && val < root->key[i + 1]) {
			return findNode(root->child[i + 1], val);
		}
	}
	//没有这个值，返回父节点，也就是某个最低层的非终端结点上
	result->node = root->parent;
	result->isquery = false;
	return result;
}

插入节点，在这边犯了一个弱智错误，判断是否需要分裂的时候少写一个=，折腾了一段时间，需要细心...

/*插入节点*/
void insertBTree(BTree* &root, int val)
{
	/*考虑B-树为空的情况*/
	if (root == NULL)
	{
		root = new BTree();
		root->key[1] = val;
		root->keynum = 1;
		return;
	}
	/*查找这个节点*/
	Result *r = findBTree(root, val);
	BTree* p = r->node;
	if (r->isquery)
	{
		//查找到了这个节点,无需插入
		return;
	}
	else
	{
		p->keynum++;				//不管怎么样，先往叶子节点里面插入
		for (int index = p->keynum; index > r->p; index--)
		{
			p->key[index] = p->key[index - 1];	//关键之往后挪一格
			p->child[index] = p->child[index - 1];	//儿子也是一样，既然叶子节点儿子都为空，那这一行就无所谓了。
		}
		p->key[r->p] = val;
		p->child[r->p] = NULL;

		/*需要分裂*/
		if (p->keynum == m)
		{
			splitBTree(p);
		}
	}
	return;
}

分裂

/*分裂*/
void splitBTree(BTree*  T)
{
	BTree* t1, *t2;
	int index, index_1;
	/*已经传递到根节点了，根也需要分裂*/
	if (T->parent == NULL)
	{
		t1 = new BTree();
		t2 = new BTree();
		t1->keynum = m / 2;
		t2->keynum = m - m / 2 - 1;
		t1->parent = T;
		t2->parent = T;

		/*初始化t1*/
		for (index = 0; index <= m / 2; index++)
		{
			t1->key[index] = T->key[index];

			/*不是叶子节点，就还需要重新分配子树*/
			if (T->child[index] != NULL)
			{
				t1->child[index] = T->child[index];
				T->child[index]->parent = t1;		//还需要更新子树的父节点
			}
		}

		/*初始化t2*/
		t2->child[0] = T->child[m / 2 + 1];
		for (index = m / 2 + 2; index <= m; index++)
		{
			t2->key[index - m / 2 - 1] = T->key[index];

			if (T->child[index] != NULL)
			{
				t2->child[index - m / 2 - 1] = T->child[index];
				T->child[index]->parent = t2;
			}

		}
		T->keynum = 1;
		T->child[0] = t1;
		T->child[1] = t2;
		T->key[1] = T->key[m / 2 + 1];
		for (index = 2; index <= m; index++)
		{
			T->child[index] = NULL;
			T->key[index] = -999;
		}
		return;
	}
	else
	{
		/*查询这个节点在父节点中的位置，（从0开始）*/
		index = whichSon(T);
		for (index_1 = T->parent->keynum; index_1 > index; index_1--)
		{
			T->parent->key[index_1 + 1] = T->parent->key[index_1];
			T->parent->child[index_1 + 1] = T->parent->child[index_1];
		}
		T->parent->keynum++;
		T->parent->key[index + 1] = T->key[m / 2 + 1];
		/*t2为新的节点*/
		t2 = T->parent->child[index + 1] = new BTree();
		t2->keynum = m - (m / 2 + 1);
		t2->parent = T->parent;
		/*因为没有key[0]，所以要单独初始化child[0]，不用for一起初始化*/
		t2->child[0] = T->child[m / 2 + 1];
		/*初始化t2*/
		for (index = m / 2 + 2; index <= m; index++)
		{
			t2->child[index - m / 2 - 1] = T->child[index];
			t2->key[index - m / 2 - 1] = T->key[index];
		}

		T->keynum = m / 2;
		for (index = (m / 2) + 1; index <= m; ++index)  //初始化T
		{
			T->child[index] = NULL;
			T->key[index] = -999;
		}
		/*父亲也需要分裂，递归*/
		if (T->parent->keynum == m)
		{
			splitBTree(T->parent);
		}
		return;
	}
	
}

返回该节点是父节点的第几个儿子（从 0 开始计数）

/*查询T是父节点的第几个孩子(从0开始计数)  失败返回-1*/
int whichSon(BTree* T)
{
	int index = -1;
	if (T == NULL)
		return -1;
	for (index = 0; index <= T->parent->keynum; index++)
	{
		if (T == T->parent->child[index])
			return index;
	}
	return -1;
}

寻找当前节点所有儿子中最大的关键字

/*寻找当前节点所有儿子中最大的关键字*/
Result* findMax(BTree* T)
{
	if (T == NULL) return NULL;
	BTree *p = T;
	while (p->child[p->keynum] != NULL)
		p = p->child[p->keynum];
	Result *r = new Result();
	r->isquery = true;
	r->node = p;
	r->p = p->keynum;
	return r;
}

合并节点

void borrowBNode(BTree* &root, BTree *T)
{
	int mynum, bronum, index;
	BTree* b;
	BTree* f = T->parent;
	/*考虑父节点不存在的情况，理论上是不会出现这种情况*/
	if (f == NULL)
	{											
		return;
	}
	/*找到当前节点是父节点的第几个儿子（从0开始 */
	mynum = whichSon(T);
	if (mynum == 0)
		bronum = 1;
	else
		bronum = mynum - 1;
	b = f->child[bronum];

	/*如果兄弟帮不了你，即它给你一个关键字，它就不满足条件了*/
	if (b->keynum == (m + 1) / 2 - 1)
	{
		/*和兄弟合并*/
		/*如果我是第一个节点*/
		if (bronum > mynum)
		{
			/*交换T和b的值，再进行合并，保证b是T父节点的前一个儿子*/
			BTree *tmp = T;
			T = b;
			b = tmp;
			int tmpp = bronum;
			bronum = mynum;
			mynum = tmpp;
		}

		/*现在b一定是在T前面，T合并到b里*/
		b->keynum++;
		b->key[b->keynum] = f->key[mynum];
		b->child[b->keynum] = T->child[0];
		for (index = 1; index <= T->keynum; index++)
		{
			b->keynum++;     
			b->key[b->keynum] = T->key[index];
			b->child[b->keynum] = T->child[index];
		}
		/*调整父节点*/
		for (index = mynum; index <= f->keynum; index++)
		{
			f->key[index] = f->key[index + 1];
			f->child[index] = f->child[index + 1];
		}
		f->keynum--;
		f->key[0] = -999;
		/*父节点不是根节点，且不满足条件，也需要调用合并函数*/
		if (f->keynum <= (m + 1) / 2 - 2 && f->parent != NULL)
		{
			borrowBNode(root, f);
		}
		/*根节点已经删的没有关键字了，重新设置根节点*/
		if (root->keynum == 0)
		{
			if (root->child[0] != NULL)
				root = root->child[0];
		}
	}
	/*如果兄弟可以帮你*/
	else
	{
		/*如果我是第一个节点*/
		if (bronum > mynum)
		{
			T->keynum++;
			T->key[T->keynum] = f->key[bronum];
			T->child[T->keynum] = b->child[0];
			f->key[bronum] = b->key[1];
			b->child[0] = b->child[1];
			for (index = 1; index <= b->keynum; index++)
			{
				b->child[index] = b->child[index + 1];
				b->key[index] = b->key[index + 1];
			}
			b->keynum--;
		}
		/*如果我不是第一个节点*/
		else
		{
			T->child[1] = T->child[0];
			for (index = 1; index <= T->keynum; index++)
			{
				T->key[index + 1] = T->key[index];
				T->child[index + 1] = T->child[index];
			}
			T->child[0] = b->child[b->keynum];
			T->key[1] = f->key[mynum];
			f->key[mynum] = b->key[b->keynum];
			T->keynum++;
			b->child[b->keynum] = NULL;
			b->key[b->keynum] = -999;
			b->keynum--;

		}

	}
}

删除节点

/*删除节点*/
void deleteBTree(BTree* &root, int val)
{
	int index;
	if (root == NULL)
		return ;
	Result* r = findBTree(root, val);
	/*没查询到这个节点*/
	if (!r->isquery)
		return ;
	BTree* p = r->node;
	/*如果是叶子节点*/
	if (r->node->child[0] == NULL)
	{
		for (index = r->p; index <= p->keynum; index++)
		{
			p->key[index] = p->key[index + 1];
		}
		p->key[p->keynum] = -999;
		p->keynum--;
		/*叶子节点关键字数量不够。既是树叶同时又是根的话就不需要合并了，只需要关键字数大于1就行了*/
		if (p->keynum <= (m + 1) / 2 - 2 && p->parent != NULL)
		{
			/*借兄弟节点*/
			borrowBNode(root, p);
		}
		return ;
	}
	/*如果是内部节点*/
	else
	{
		/*找到儿子里的最大节点，替换要删除的节点*/
		Result *re = findMax(p->child[r->p - 1]);
		BTree *q = re->node;
		p->key[r->p] = q->key[re->p];
		q->key[re->p] = -999;
		q->keynum--;
		/*如果叶子节点关键字数量不够*/
		if (q->keynum <= (m + 1) / 2 - 2)
		{
			/*借兄弟节点*/
			borrowBNode(root, q);
		}
		return ;
	}
}

附上cpp代码点击下载

参考
《数据结构与算法分析》
https://www.cnblogs.com/QG-Hothoren/p/4564721.html
https://www.cnblogs.com/nullzx/p/8729425.html