B树——思路、及C语言代码的实现

文章由LinuxBoy分享于2019-04-01 07:04:25热评（677）

B树——思路、及C语言代码的实现

0.序

　　本人现读本科大二，这学期学习数据结构，老师为我们的期末作业布置一道任选题，而我一直以来都有听说B树是一棵挺神奇的树，所以我选择了它，当然更重要的原因是因为B树的难度最高，我喜欢做有挑战性的工作。同时，我听我基友说他热衷于将自己所学所想分享到博客园上，故才有了这样一篇文章。希望我能够在写博客的同时学习到更多东西，同时也能帮助到其他遇到或者即将遇到雷同问题的初学者们。

1.关于B树

　　B树是一种称之为查找树的树，与之类似的有查找二叉树，平衡二叉树，除此之外，还有各种B树的兄弟姐妹B+树、B-树、B*树等，他们共同的特点就是都是按照一定的顺序规律存储的。B树的应用也是很广泛的，B树是几乎所有数据库的默认索引结构，也是用的最多的索引结构。B树是一种多叉树，根据其最多叉的数目可以直接称为M阶B树。根据算法导论上叙述，还可按B树每个节点最少的分支确定一棵B树的阶，但是这样的话B树的阶便必须为偶数。我个人是使用根据最大分支的数目确定B树的阶的。

　　下图就是某一棵B树，每一个结点中都包含有数个数据元素，而同时一定会有数据元素的个数加一个的子树。

　　一棵M阶B树或为空树，或为满足下列特性的M叉树：

（1）树中每个结点最多含有M棵子树；

（2）若根结点不是叶子结点，则至少有2棵子树；

（3）除根结点之外的所有非终端结点至少有[m/2]棵子树；

（4）每个非终端结点中包含的信息keynum，ptr[0],key[1],ptr[1],key[2],ptr[2],……key[keynum],ptr[keynum];

　　其中，key为关键字，且关键字按升序排序，ptr为指向子树的根结点指针

2.思路及实现

　　B树的接口主要是插入（包括空树插入一个元素）和删除操作，而插入和删除操作不可避免的都会用到查找操作，而查找的主要思路比较简单，主要是利用B树是一种排序树的原理，可以很快找到要插入位置或者要删除结点。这里的关键是注意返回内容包括查找结果所在结点，以及该元素所在位置，这是为了方便接下来的操作比较简单。

插入：

　　通过对B树进行遍历，找出要插入的结点以及结点位置，如果找到的key值在B树当中已经存在，则说明插入失败，否则，就可以进行插入操作。这里可以先不管是否超出M阶树的上限要求，因为我们在定义的时候会故意留下一个位置，可以存放多余的一个元素，插入之后，通过判断是否达到M阶树上限要求，再进行递归的分裂操作。

/***
* @name Status insertBTree(BTree &T, Record e)
* @description 插入实现元素的插入
* @return 成功返回OK,如果存在则返回FALSE，否则返回ERROR
* @notice
***/
Status insertBTree(BTree &T, Record e)
{
BTree p;
int index, temp;
Status find_flag;
if (NULL == T)//考虑B树为空树的情况
{
T = (BTree)malloc(BTLEN);
if (NULL == T) return OVERFLOW;
T->keynum = 1;
T->parent = NULL;
for (index = 0;index <= m; ++index)
{
T->ptr[index] = NULL;
T->key[index] = 0;
}
T->key[1] = e.key;
return OK;
}
find_flag = findBTree(T, p, temp, e.key);//寻找插入节点
if (find_flag == TRUE)
{
return FALSE;
}
if (find_flag == FALSE)
{ //不管怎样先直接插入
p->keynum++;
for (index = p->keynum;index > temp;--index)
{
p->key[index] = p->key[index - 1];
p->ptr[index] = p->ptr[index - 1];
}
p->ptr[temp] = NULL;
p->key[temp] = e.key;
if (p->keynum == m) //这种情况得分裂
{
splitBTree(p);
}
renewParent(T);
return OK;
}
return ERROR;
}

更多详情见请继续阅读下一页的精彩内容：

推荐文章：

B树——思路、及C语言代码的实现