B树 解析与源码

2021年5月3日 71点热度 0条评论 来源: 傲然君

概念

B树,是普遍运用于文件系统和数据库的一种多叉(即,每个非叶子结点可以有多个孩子)平衡查找树

数据库索引为什么采用B树/B+树结构?

数据库索引存储在磁盘上,当数据库的数据量比较大时,索引可能高达几G,甚至更多。所以在利用索引查找时,不会一次性把整个索引加载到内存,而是每次只加载一个磁盘页(这里的磁盘页对应索引树的结点)。

  1. 若索引树采用二叉树结构,则一个页面只能存放一个值。因此在最坏的情况下,查找一个值的磁盘IO次数 = 索引树的高度。
  2. 由1可看出,磁盘IO次数由索引树的高度决定。因此,为了减少磁盘IO次数,需要把原本“瘦高”的树结构转变成“矮胖”的树结构。B树和B+树就是这样一种数据结构。对于B树和B+树,每个结点包含的关键字数目取决于磁盘页的大小。

B树的特性

一棵m阶B树(m>=3),或是空树,或是具有如下几个特征的树:

  1. 若根结点不是叶子结点,则 2 <= 根结点的孩子数 <= m;(根结点至少包含一个关键字)
  2. 除根结点和叶子结点外,ceil(m/2) <= 其它结点的孩子数 <= m,其包含的关键字数 = 它的孩子数-1;(ceil(x):返回大于或者等于x的最小整数)
  3. 所有叶子结点都出现在同一层,ceil(m/2)-1 <= 结点包含的关键字数目 <= m - 1;
  4. 每个结点中的关键字从小到大排列,并且非叶子结点的k-1个关键字,正好是它k个孩子包含的关键字的值域分划(即,父结点中的第i个关键字(如果存在的话) < 第i个孩子中的所有关键字 < 父结点中的第i+1个关键字(如果存在的话)。

B树的高度

对于一个m(m>=3)阶B树,假设关键字总数目为n,高度为h:

  1. 根结点至少有2个孩子(根结点至少有一个关键字),因此第二层至少有两个结点;
  2. 除根和叶子结点外,其他结点至少有t=ceil(m/2)个孩子(取最小时,除根结点外,其他结点包含的关键字个数为t-1)。因此,第三层至少有2t个结点(第二层每个结点包含的关键字个数为t-1),第四层至少有2t2个结点(第三层每个结点包含的关键字个数为t-1),…,第h-1层至少有2t(h-3)个结点(第h-2层每个结点包含的关键字个数为t-1);
  3. 将所有结点包含的关键字相加:

由此可知:

  • 在B树上增删改查的磁盘IO次数为为O(logtn),CPU时间为O(mlogtn)。
  • 在关键字总数目不变的情况下,结点包含的关键字越多,B树的高度越小。这也是为什么SQL Server中应尽量以窄键建立聚集索引。因为键越小,结点可容纳的关键字越多,B树的高度越小,从而提升了查询性能。

性能分析

  • n个关键字的平衡二叉排序的高度(lgn)比B树的高度约大lgt倍。
  • 若作为在内存中使用的表结构,B树不一定比平衡二叉树好,尤其当m较大时更是如此。
    这是因为B树增删改查的CPU时间: O(mlogtn)=0(lgn·(m/lgt))。
    而m/lgt>1,因此当m较大时,O(mlogtn)比平衡二叉排序树的CPU时间O(lgn)大得多。故,若B树仅作为在内存中使用,则应取较小的m。(通常取最小值m=3,此时B树每个内部结点孩子数目可为2或3,这种3阶的B-树称为2-3树)。

插入操作

对于一个m阶的B树,新关键字一般是插入在叶子结点层,通过检索可以确定新关键字应插入的叶子结点。

  • 将关键字直接按升序插入该结点,若插入后,结点中关键字总个数 <= m-1,则插入结束;
  • 若插入后,结点中关键字总个数 > m-1,则需将结点进行“分裂”。即:
    1)为该结点新增一个相邻的右结点;
    2)以中间关键字为界,将该结点内关键字一分为二。将大于中间关键字的一半移动到新结点,中间关键字移动到父结点中;
    3)将该结点一半的孩子结点移动到新结点,将新结点添加到父结点的孩子结点中(具体来说,是作为父结点新加关键字的右孩子结点);
    4)修改新结点的孩子结点的父结点;
    5)由于父结点新增了一个关键字,故应继续判断父结点中关键字个数是否超过限制。若父结点中的关键字数目 > m-1,则重复1)- 4)分裂父结点。

删除操作

**情形一:**被删关键字Key所在结点node为非叶子结点时,则
1、找到Key在结点node中的位置idx。即:node->key[idx]为将被删除的关键字;
2、找到以结点child = node->child[idx]为根节点的子树中的最大关键字Key2(结点node2),并用Key2填充Key的位置,即:node->key[idx] = Key2。(node2必定为某一个叶子节点,Key2必定为child最后一个孩子的最后一个孩子…的最后一个孩子的最后一个关键字)
3、由于node2为叶子节点,因此node2移出了一个关键字后,问题转化为情形二。

**情形二:**被删关键字Key所在结点node为叶子结点时,将Key直接从node删除
1、若删除后,node中关键字的个数 >= Min - 1,则删除操作完成;
2、若删除后,node中关键字的个数 < Min - 1,则B树的特性已被破坏。处理情况:

  • 1)若node的左(右)相邻结点中关键字的个数 > Min - 1时,则将兄弟结点中的最大(小)关键字上移到父节点,然后将父节点中的关键字下移到node;

  • 2)若node的左(右)相邻结点中关键字的个数 = Min - 1时,则将node和左(右)相邻结点合并为一个新的结点,并将父结点中夹在node和左(右)相邻结点之间的关键字移动到新结点。
    若移出一个关键字后,父结点中关键字个数 >= Min - 1,则删除操作完成,否则按步骤2对父结点进行操作,并依次类推直至根结点。

    注:若Min=ceil(m/2)

实现

1、结点结构定义

/// B树结点结构定义
struct SBTree_Node
{
	int nKeyNum;			/// 结点存储的关键字的个数
	int *pKey;				/// 结点存储的关键字			创建结点时,会一次性分配nMaxNumOfKey+1个元素空间(多分配1个空间 用于分裂)
	SBTree_Node *pParent;	/// 指向父结点的指针
	SBTree_Node **pChid;	/// 指向孩子结点的指针数组	创建结点时,会一次性分配nMaxNumOfKey+2个指针空间(多分配1个空间 用于分裂)
};

2、B树结构定义

/// B树结构定义
struct SBTree
{
	int nMaxNumOfKey;		/// 每个结点可包含的关键字的最大个数
	int nMinNumOfKey;		/// 每个结点可包含的关键字的最小个数 根结点包含的关键的最小个数为1
	int nSplitIndex;        /// 分裂索引   分裂时,该位置上的关键字会提升到父结点中
	SBTree_Node *pRoot;		/// 根结点
};

3、构建一个空树

/// 构建一个空树
/// @param	nRank			[in]	B树的阶层
bool createBTree(int nRank, SBTree *&pBTree)
{
	if (nRank < 3)
	{
		return false;	/// B树的最小阶层为3
	}

	pBTree = (SBTree *)malloc(sizeof(SBTree));

	pBTree->nMaxNumOfKey = nRank - 1;
	if (nRank % 2)
	{
		pBTree->nMinNumOfKey = nRank / 2 + 1 - 1;
	}
	else
	{
		pBTree->nMinNumOfKey = nRank / 2 - 1;
	}

	pBTree->nSplitIndex = (nRank + 1) / 2 - 1;
	pBTree->pRoot = NULL;

	return true;
}

4、构建结点

/// 创建一个结点
SBTree_Node *createNode(SBTree *pBTree)
{
	SBTree_Node *pNode = (SBTree_Node *)malloc(sizeof(SBTree_Node));

	pNode->nKeyNum = 0;
	pNode->pKey = (int *)malloc((pBTree->nMaxNumOfKey + 1) * sizeof(int));
	pNode->pChid = (SBTree_Node **)malloc((pBTree->nMaxNumOfKey + 2) * sizeof(SBTree_Node *));

	memset(pNode->pKey, NULL, (pBTree->nMaxNumOfKey + 1) * sizeof(int));
	memset(pNode->pChid, NULL, (pBTree->nMaxNumOfKey + 2) * sizeof(SBTree_Node *));
	
	pNode->pParent = NULL;
	
	return pNode;
}

5、插入操作

/// 插入操作
bool insert(SBTree *pBTree, int nKey)
{
	SBTree_Node *pNode = pBTree->pRoot;

	/// 创建根结点
	if (NULL == pNode)
	{
		pNode = createNode(pBTree);
		pNode->nKeyNum = 1;
		pNode->pKey[0] = nKey;
		pNode->pParent = NULL;

		pBTree->pRoot = pNode;
		return true;
	}

	int nKeyIndex = 0;

	/// 查找结点的插入位置
	while (pNode)
	{
		for (nKeyIndex = 0; nKeyIndex < pNode->nKeyNum; nKeyIndex++)
		{
			if (nKey == pNode->pKey[nKeyIndex])
			{
				return true;	/// 关键字已经存在 无需插入
			}
			else if (nKey < pNode->pKey[nKeyIndex])
			{
				break;
			}
		}

		if (pNode->pChid[nKeyIndex] != NULL)
		{
			pNode = pNode->pChid[nKeyIndex];
		}
		else
		{
			break;
		}		
	}

	/// 将关键字移位
	/// 关键字插入位置为 pNode->pKey[nKeyIndex-1]
	for (int nIndex = pNode->nKeyNum; nIndex > nKeyIndex; nIndex--)
	{
		pNode->pKey[nIndex] = pNode->pKey[nIndex-1];
	}
	pNode->pKey[nKeyIndex] = nKey;
	pNode->nKeyNum++;

	/// 分裂结点
	if (pNode->nKeyNum > pBTree->nMaxNumOfKey)
	{
		return bTree_splite(pBTree, pNode);
	}

	return true;
}
/// 分裂结点
bool bTree_splite(SBTree *pBTree, SBTree_Node *pNode)
{
	int nKeyNumOfCurrentNode = 0;

	while (pNode->nKeyNum > pBTree->nMaxNumOfKey)
	{
		nKeyNumOfCurrentNode = pNode->nKeyNum;

		///1、创建一个新的结点
		SBTree_Node *pNewNode = createNode(pBTree);

		///2、将原结点一半的关键字、孩子结点移动到结点
		memcpy(pNewNode->pKey, pNode->pKey + pBTree->nSplitIndex + 1, (nKeyNumOfCurrentNode - pBTree->nSplitIndex - 1) * sizeof(int));
		memcpy(pNewNode->pChid, pNode->pChid + pBTree->nSplitIndex + 1, (nKeyNumOfCurrentNode - pBTree->nSplitIndex) * sizeof(SBTree_Node *));

		pNewNode->nKeyNum = nKeyNumOfCurrentNode - pBTree->nSplitIndex - 1;
		pNewNode->pParent = pNode->pParent;

		pNode->nKeyNum = pBTree->nSplitIndex;

		///3、将 pNode->pKey[pBTree->nSplitIndex] 提升到父结点
		if (NULL == pNode->pParent)
		{
			///3.1、已经到达根结点
			/// 创建根结点 并 修改根结点内元素
			pNode->pParent = createNode(pBTree);

			pNode->pParent->nKeyNum = 1;
			pNode->pParent->pKey[0] = pNode->pKey[pBTree->nSplitIndex];

			pNode->pParent->pChid[0] = pNode;
			pNode->pParent->pChid[1] = pNewNode;
			pNode->pParent->pParent = NULL;

			/// 修改第二层结点的父结点
			pNewNode->pParent = pNode->pParent;

			/// 修改 B树的根结点
			pBTree->pRoot = pNode->pParent;
		}
		else
		{
			///3.2、父结点不为NULL
			/// 检索关键字插入位置
			int nIndex = pNode->pParent->nKeyNum;
			for (; nIndex > 0; nIndex--)
			{
				if (pNode->pParent->pKey[nIndex - 1] > pNode->pKey[pBTree->nSplitIndex])
				{
					pNode->pParent->pKey[nIndex] = pNode->pParent->pKey[nIndex - 1];	///移动关键字
					pNode->pParent->pChid[nIndex + 1] = pNode->pParent->pChid[nIndex];	///移动关键字的孩子结点
				}
				else
				{
					break;
				}
			}

			/// 将关键字插入父结点
			pNode->pParent->pKey[nIndex] = pNode->pKey[pBTree->nSplitIndex];
			pNode->pParent->nKeyNum++;

			/// 为父结点添加新的孩子结点
			pNode->pParent->pChid[nIndex + 1] = pNewNode;
			pNewNode->pParent = pNode->pParent;
		}

		///4、原结点一半的关键字、孩子都移到了新结点 重置原结点后一半的关键字和孩子
		memset(pNode->pKey + pBTree->nSplitIndex, NULL, (nKeyNumOfCurrentNode - pBTree->nSplitIndex) * sizeof(int));
		memset(pNode->pChid + pBTree->nSplitIndex + 1, NULL, (nKeyNumOfCurrentNode - pBTree->nSplitIndex) * sizeof(SBTree_Node *));

		///5、修改新结点还孩子结点的父结点
		for (int nIndex = 0; nIndex < pNewNode->nKeyNum + 1; nIndex++)
		{
			if (pNewNode->pChid[nIndex] != NULL)
			{
				pNewNode->pChid[nIndex]->pParent = pNewNode;
			}
		}

		///6、继续遍历当前结点的父结点
		pNode = pNode->pParent;
	}

	return true;
}

6、删除操作

/// 删除指定的关键字
/// 检索待删除关键字所在的结点
bool bTree_delete(SBTree *pBTree, int nKey)
{
	SBTree_Node *pNode = pBTree->pRoot;

	while (pNode)
	{
		int nIndex = 0;

		for (; nIndex < pNode->nKeyNum; nIndex++)
		{
			if (nKey == pNode->pKey[nIndex])
			{
				/// 检索到关键字所在的结点
				return _bTree_delete(pBTree, pNode, nIndex);
			}
			else if (nKey < pNode->pKey[nIndex])
			{
				break;
			}
		}

		pNode = pNode->pChid[nIndex];
	}

	return false;
}
/// 删除结点 pNode 中索引位置为 nIdex 的关键字
///
/// 若 pNode 为叶子结点,则直接删除关键字
/// 若 pNode 为非叶子结点,则用 pNode->pKey[nIndex] 中序遍历的直接前序 填充 pNode->pKey[nIndex]
///						  该中序遍历的直接前序必定为 pNode->pChid[nIndex] 最后一个孩子的最后一个孩子的...最后一个孩子的最后一个关键字
/// 
/// 若 pNode 或 pNode->pKey[nIndex] 中序遍历的直接前序所在的结点 删除一个关键字后,剩余关键字个数 >= B树的结点关键字最小个数,则删除操作结束
/// 否则,需要向相邻兄弟借一个关键字或与相邻兄弟合并为一个新的结点
bool _bTree_delete(SBTree *pBTree, SBTree_Node *pNode, int nIndex)
{
	SBTree_Node *pChildNode = pNode->pChid[nIndex];

	if (pNode->pChid[0])
	{
		///1、pNode 不是叶子结点

		///1.1、找到 pChildNode 最后一个孩子的最后一个孩子....的最后一个孩子的最后一个关键字
		while (pChildNode && pChildNode->pChid[pChildNode->nKeyNum])
		{
			pChildNode = pChildNode->pChid[pChildNode->nKeyNum];
		}

		///1.2、使用以 pNode->pChid[nIndex] 为根结点的子树中的最大关键字 填充 pNode 中 nIndex 位置
		/// pChildNode 必定是叶子结点
		pNode->pKey[nIndex] = pChildNode->pKey[pChildNode->nKeyNum - 1];

		pChildNode->pKey[pChildNode->nKeyNum - 1] = 0;
		pChildNode->nKeyNum--;

		pNode = pChildNode;
	}
	else
	{
		///2、pNode 本身就是叶子结点 则删除的关键字不一定是最后一个关键字 因此需要紧凑关键字
		for (int nKeyIndex = nIndex; nKeyIndex < pNode->nKeyNum - 1; nKeyIndex++)
		{
			pNode->pKey[nKeyIndex] = pNode->pKey[nKeyIndex + 1];			
		}

		pNode->pKey[pNode->nKeyNum - 1] = 0;
		pNode->nKeyNum--;
	}
	
	if (pNode->nKeyNum < pBTree->nMinNumOfKey)
	{
		///3、叶子结点删除一个关键字后 已破坏 B树的特性
		/// 需要向相邻兄弟借一个关键字或者与相邻合并为一个新的结点
		bTree_BorrowOneKeyOrMergeNode(pBTree, pNode);
	}

	return true;
}
/// 结点pNode删除一个关键字后的处理情况:
/// 1、从相邻兄弟借一个关键字
/// 2、与相邻兄弟合并为一个新的结点,父结点中位于 pNode 和兄弟结点之间的关键字 需要移动到新结点
bool bTree_BorrowOneKeyOrMergeNode(SBTree *pBTree, SBTree_Node *pNode)
{
	///1、若pNode为根结点
	if (NULL == pNode->pParent)
	{
		if (pNode->nKeyNum == 0)
		{
			/// 说明前一步 发生结点合并,pNode 移除了一个关键字给下层新结点
			/// 删除关键字后 0个孩子结点或两个孩子结点已合并为一个新的结点
			if (pNode->pChid[0])
			{
				/// 将第二层提升为根结点
				pNode->pChid[0]->pParent = NULL;
				pBTree->pRoot = pNode->pChid[0];
			}
			else
			{
				/// 空树
				pBTree->pRoot = NULL;
			}

			/// 释放原先的根结点
			free(pNode);
		}

		return true;
	}

	/// 若最开始删除的关键字Key位于非叶子结点中 则此处的pNode必定为其父结点的最后一个孩子结点
	/// 否则pNode在其父结点的孩子结点中顺序不定
	/// 故,此处需要先确定pNode为其父结点的第几个孩子结点
	/// 
	/// 2、查找pNode为其父结点的第几个孩子结点
	int nIndexOfNode = 0;
	for (; nIndexOfNode < pNode->pParent->nKeyNum + 1; nIndexOfNode++)
	{
		if (pNode->pParent->pChid[nIndexOfNode] == pNode)
		{
			break;
		}
	}

	if (nIndexOfNode >= pNode->pParent->nKeyNum + 1)
	{
		return false;
	}

	/// 3、向前(后)兄弟结点借一个关键字
	else if (nIndexOfNode > 0 && pNode->pParent->pChid[nIndexOfNode - 1]->nKeyNum > pBTree->nMinNumOfKey)
	{
		/// 3.1、向前一个兄弟结点借一个关键字
		SBTree_Node *pBrotherNode = pNode->pParent->pChid[nIndexOfNode - 1];

		for (int nIndex = pNode->nKeyNum; nIndex > 0; nIndex++)
		{
			pNode->pKey[nIndex] = pNode->pKey[nIndex - 1];
			pNode->pChid[nIndex + 1] = pNode->pChid[nIndex];		
		}
		pNode->pChid[1] = pNode->pChid[0];

		/// 用父结点中位于pNode和前一个兄弟结点之间的关键字填充pNode的第一个关键字
		pNode->pKey[0] = pNode->pParent->pKey[nIndexOfNode - 1];
		pNode->nKeyNum++;

		/// 将前一个兄弟结点的最后一个孩子作为pNode的第一个孩子
		pNode->pChid[0] = pBrotherNode->pChid[pBrotherNode->nKeyNum];
		if (pNode->pChid[0])
		{
			pNode->pChid[0]->pParent = pNode;
		}

		/// 用前一个兄弟结点中的最后一个关键字填充父结点中移除的关键字
		pNode->pParent->pKey[nIndexOfNode - 1] = pBrotherNode->pKey[pBrotherNode->nKeyNum - 1];

		pBrotherNode->pKey[pBrotherNode->nKeyNum - 1] = 0;
		pBrotherNode->nKeyNum--;
		pBrotherNode->pChid[pBrotherNode->nKeyNum] = NULL;
		
		return true;
	}
	else if (nIndexOfNode < pNode->pParent->nKeyNum && pNode->pParent->pChid[nIndexOfNode + 1]->nKeyNum > pBTree->nMinNumOfKey)
	{
		/// 3.2、向后一个兄弟结点借一个关键字
		SBTree_Node *pBrotherNode = pNode->pParent->pChid[nIndexOfNode + 1];

		/// 用父结点中位于pNode和后一个兄弟结点之间的关键字填充pNode的第一个关键字
		pNode->pKey[pNode->nKeyNum] = pNode->pParent->pKey[nIndexOfNode];
		pNode->nKeyNum++;

		/// 将后一个兄弟结点的第一个孩子作为pNode的最后一个孩子
		pNode->pChid[pNode->nKeyNum] = pBrotherNode->pChid[0];
		if (pNode->pChid[pNode->nKeyNum])
		{
			pNode->pChid[pNode->nKeyNum]->pParent = pNode;
		}
		
		/// 用后一个兄弟结点中的第一个关键字填充父结点中移除的关键字
		pNode->pParent->pKey[nIndexOfNode] = pBrotherNode->pKey[0];

		/// 将后一个兄弟结点中的关键字和孩子往前移动一位
		for (int nIndex = 1; nIndex < pBrotherNode->nKeyNum; nIndex++)
		{
			pBrotherNode->pKey[nIndex - 1] = pBrotherNode->pKey[nIndex];
			pBrotherNode->pChid[nIndex - 1] = pBrotherNode->pChid[nIndex];
		}
		pBrotherNode->pChid[pBrotherNode->nKeyNum - 1] = pBrotherNode->pChid[pBrotherNode->nKeyNum];

		pBrotherNode->pKey[pBrotherNode->nKeyNum - 1] = 0;
		pBrotherNode->nKeyNum--;
		pBrotherNode->pChid[pBrotherNode->nKeyNum] = NULL;

		return true;
	}

	/// 4、与前(后)一个兄弟合并为一个新的关键字
	else
	{
		SBTree_Node *pLeftNode = NULL;
		SBTree_Node *pRightNode = NULL;
		int nIndexOfParentKey = 0;

		if (nIndexOfNode > 0)
		{
			pLeftNode = pNode->pParent->pChid[nIndexOfNode - 1];
			pRightNode = pNode;
			nIndexOfParentKey = nIndexOfNode - 1;
		}
		else
		{
			pLeftNode = pNode;
			pRightNode = pNode->pParent->pChid[nIndexOfNode + 1];
			nIndexOfParentKey = nIndexOfNode;
		}

		/// 合并结点 pLeftNode 和 pRightNode,父结点索引位置为 nIndexOfParentKey 的关键字 需移动到新结点
		/// 
		/// 此时 pLeftNode 和 pRightNode 即可均为叶子或非叶子结点
		/// 
		/// 若均为非叶子结点,则前一步骤必定发生了结点合并,同时新合并的结点必定为 pLeftNode 或 pRightNode 的子结点
		/// 假设为 pLeftNode,则 pLeftNode 在移除一个关键字给新结点的同时,关键字右侧的孩子结点也消失了(孩子结点中的关键字已经合并到新节点)
		/// 因此当合并 pLeftNode 和 pRightNode时,首先将父结点位于 pLeftNode 和 pRightNode 之间的关键字Key 移到 pLeftNode 后,该关键字其实并没有右孩子结点,
		/// 因此合并时,pRightNode 的第一个孩子结点即为合并后关键字Keyd 的右孩子结点
		/// 
		/// 即,若 pLeftNode 和 pRightNode 非叶子结点,则两者合并后,必定满足:结点个数 = 关键字个数 + 1
		return bTree_MergeNode(pBTree, pLeftNode, pRightNode, nIndexOfParentKey);
	}

	return true;
}
/// 合并结点 pLeftNode 与 pRightNode,nIndexOfParentKey 为父结点中位于 pLeftNode 与 pRightNode 之间的关键字
/// 
/// 此时 pLeftNode 和 pRightNode 即可均为叶子或非叶子结点
/// 
/// 若均为非叶子结点,则前一步骤必定发生了结点合并,同时新合并的结点必定为 pLeftNode 或 pRightNode 的子结点
/// 假设为 pLeftNode,则 pLeftNode 在移除一个关键字给新结点的同时,关键字右侧的孩子结点也消失了(孩子结点中的关键字已经合并到新节点)
/// 因此当合并 pLeftNode 和 pRightNode时,首先将父结点位于 pLeftNode 和 pRightNode 之间的关键字Key 移到 pLeftNode 后,该关键字其实并没有右孩子结点,
/// 因此合并时,pRightNode 的第一个孩子结点即为合并后关键字Keyd 的右孩子结点
/// 
/// 即,若 pLeftNode 和 pRightNode 非叶子结点,则两者合并后,必定满足:结点个数 = 关键字个数 + 1
bool bTree_MergeNode(SBTree *pBTree, SBTree_Node *pLeftNode, SBTree_Node *pRightNode, int nIndexOfParentKey)
{
	/// 将父结点中的关键字移到子结点
	pLeftNode->pKey[pLeftNode->nKeyNum] = pLeftNode->pParent->pKey[nIndexOfParentKey];
	pLeftNode->nKeyNum++;

	/// 将 pLeftNode 与 pRightNode 合并为一个新结点 pLeftNode
	memcpy(pLeftNode->pKey + pLeftNode->nKeyNum, pRightNode->pKey, pRightNode->nKeyNum *sizeof(int));
	memcpy(pLeftNode->pChid + pLeftNode->nKeyNum, pRightNode->pChid, (pRightNode->nKeyNum + 1)*sizeof(SBTree_Node *));

	for (int nIndex = 0; nIndex < pRightNode->nKeyNum + 1; nIndex++)
	{
		if (pRightNode->pChid[nIndex])
		{
			pRightNode->pChid[nIndex]->pParent = pLeftNode;
		}
	}

	pLeftNode->nKeyNum += pRightNode->nKeyNum;

	/// 移动父结点内部关键字和孩子结点
	for (int nIndex = nIndexOfParentKey + 1; nIndex < pLeftNode->pParent->nKeyNum; nIndex++)
	{
		pLeftNode->pParent->pKey[nIndex - 1] = pLeftNode->pParent->pKey[nIndex];
		pLeftNode->pParent->pChid[nIndex] = pLeftNode->pParent->pChid[nIndex + 1];
	}
	///pLeftNode->pParent->pChid[pLeftNode->pParent->nKeyNum - 1] = pLeftNode->pParent->pChid[pLeftNode->pParent->nKeyNum];

	pLeftNode->pParent->pKey[pLeftNode->pParent->nKeyNum - 1] = 0;
	pLeftNode->pParent->pChid[pLeftNode->pParent->nKeyNum] = NULL;
	pLeftNode->pParent->nKeyNum--;

	/// 释放右结点
	free(pRightNode);

	if (pLeftNode->pParent->nKeyNum < pBTree ->nMinNumOfKey)
	{
		/// 父结点移除一个关键字后 破坏了B树的特性
		/// 因此父结点需要向其相邻的兄弟结点借一个关键字或与之合并为一个新的结点
		return bTree_BorrowOneKeyOrMergeNode(pBTree, pLeftNode->pParent);
	}
	
	return true;
}

结果展示

依次插入关键字:
492,172,383,59,123,27,67,135,335,211,362,368,421,386,426,429,777,567,690,530,540,649,736,763,793,886,782,862,915,926

1、B树的阶层为3时:
插入操作:

删除关键字386:

删除关键字383:

2、B树的阶层为5时:
插入操作:

删除关键字926:

删除关键字567:

删除关键字540:

    原文作者:傲然君
    原文地址: https://blog.csdn.net/u010601662/article/details/79180053
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。