平衡二叉排序树便于动态查找，因此用平衡二叉排序树来组织索引表是一种可行的选择。当用于大型数据库时，所有数据及索引都存储在外存，因此，涉及到内、外存之间频繁的数据交换，这种交换速度的快慢成为制约动态查找的瓶颈。若以二叉树的结点作为内、外存之间数据交换单位，则查找给定关键字时对磁盘平均进行㏒㏒次访问是不能容忍的，因此，必须选择一种能尽可能降低磁盘I/OI/O次数的索引组织方式。树结点的大小尽可能地接近页的大小。
B树主要用于文件系统中，在B树中，每个节点的大小为一个磁盘的页，节点中锁包含的关键字及其子节点的数目取决于页的大小。一个度为m的B树，称为m阶B树，定义如下：
（1）一个m阶B树，或者是空树，或者满足一下性质的m叉树；
（2）根节点或者是叶子，或者至少有两颗子树，至多是m棵子树；
（3）除根节点外，所有非终端节点至少是「m/2
（向上取整）棵子树，至多是m棵子树；
（4）所有叶子节点都在树的同一层上。
下图为B树的一个例子：
1，B树的数据结构，根据以上的信息，定义B树的数据结构如下：
//节点数据结构的定义
typedef struct BTNode
{
int
keynum;
//节点信息的数量，不包含key[0]节点
struct
BTNode *parent; //父节点
int
key[M+1];
//节点信息数组，第一个节点没用。
struct
BTNode
*ptr[M+1];//子节点信息
}BTNode;
2，B树的查找
查找的基本思想是：
（1）从树的根节点T开始，在节点中利用遍历或折半查找给定的值，如果找到，则返回节点指针和在节点中的位置；如果没有，则到（2）
（2）与节点中的Key进行比较，找到给定值左右Key中间的指针，去其子树中查找
（3）重复执行1,2两步，直到找到。如果直到叶子节点，仍未找到，则返回0，并返回最后搜索的叶子节点。（此节点是给定值需要插入的位置）
3，B树的插入
插入新节点的基本思想如下：
（1）在B树查找关键字，如果找到，则不插入；否则，执行（2）
（2）将给定值插入到叶子节点中，如果：
a，叶子的节点数
b，叶子的节点数=m-1：插入节点，并将节点分裂。分裂的方式是将该节点拆分成两个节点，然后，将中间节点插入到父节点当中，拆分后的两个节点，分别作为插入到父节点的中间节点的左右子。如果中间节点插入到父节点后，仍然需要分裂，则继续分裂，直到根节点。如果仍然需要分裂，则新建一个根节点，将分裂后的两个节点分别作为新根节点的两个子节点。
例如如下图：
代码如下：
#include
#include
#include
#include
using namespace std;
// 定义B-tree 的阶数，一般是根据磁盘磁盘页的大小而定
#define M
5
// 节点数据结构的定义
typedef struct BTNode
{
int keynum; //节点信息的数量，不包含 key[0] 节点
struct BTNode
*parent; // 父节点
int key[M+1]; //节点信息数组，第一个节点没用。
struct BTNode *ptr[M+1];// 子节点信息
}BTNode;
//B-tree 的搜索函数
// 参数T ： B-Tree的根节点， K ：要查找的信息
//p ：如果找到 K，则 p 为所在的节点，如果没有找，则 p 为最后一次查找的节点
//p 传的是指针的引用
// 返回值为 0，为未找到；为其他值，为在节点中的位置
int BT_search(BTNode
*T, int K,
BTNode *&p)
{
BTNode
*q;
int i;
p=q=T;
while (q!=NULL)
{
p=q;
// 在节点内查找，此处可以用二分法查找
for (i=1;
i<=q->keynum; i++)
{
if (q->key[i]==K)
return i;
else if (K >
q->key[i])
continue ;
else
break ;
}
q=q->ptr[i-1];
}
return 0;
}
// 分裂函数，当一个节点中信息数过多
// 需要分裂节点
// 参数p 为传引用
// 拆分后，分为 p和返回值 q 两个节点
BTNode
*split(BTNode *&p)
{
BTNode
*q;
int mid;
int j,
k;
q=(BTNode
*)malloc( sizeof (BTNode));
mid=(M+1)/2;
q->ptr[0]=p->ptr[mid];
if (q->ptr[0] != NULL)
q->ptr[0]->parent=q;
// 从mid 位置拆分， mid 值上调到父节点
//
mid 后为一部分， mid前为一部分
for (j=1,
k=mid+1; k<=M; k++)
{
q->key[j]=p->key[k];
q->ptr[j]=p->ptr[k];
if (q->ptr[j] != NULL)
q->ptr[j]->parent=q; // 注意此处拆分后，要修改父节点信息。
j++;
}
q->keynum=M-mid;
p->keynum=mid-1;
q->parent=p->parent;
return q;
}
// 插入节点，参数 T为父节点， K 为插入信息
void insert_BTree(BTNode
*&T, int K)
{
int i;
BTNode
*p=NULL, *s1=NULL, *s2=NULL;
if (!BT_search(T, K, p))
{
while (p!=NULL)
{
p->key[0]=K;
for (i=p->keynum; Kkey[i];
i--)
{
p->key[i+1]=p->key[i];
p->ptr[i+1]=p->ptr[i];
}
i+=1;
p->key[i]=K;
p->ptr[i]=s2;
p->ptr[i-1]=s1;
if (++(p->keynum) < M)
break ;
else
{
s2=split(p);
s1=p;
K=p->key[p->keynum+1];
p=p->parent;
}
if (p==NULL)
{
p=(BTNode
*)malloc( sizeof (BTNode));
p->keynum=1;
p->key[1]=K;
p->ptr[0]=s1;
s1->parent=p;
p->ptr[1]=s2;
s2->parent=p;
p->parent=NULL;
T=p;
break ;
}
}
}
}
// 深度遍历函数，用于检验 b-tree 正确性。
void mid_order(BTNode *T)
{
int i;
queue
q;
BTNode
*p=T;
if (p!=NULL)
{
q.push(p);
while (!q.empty())
{
p=q.front();
for (i=0;
i<=p->keynum; i++)
{
if (p->ptr[i] != NULL)
q.push(p->ptr[i]);
if (i!=p->keynum)
cout<<p->key[i+1]<< "
" ;
}
q.pop();
cout<<endl;
}
}
}
int main()
{
int n;
cin>>n;
int i;
int num;
BTNode
*T=NULL;
BTNode
*p;
for (i=0;
i
{
if (T==NULL)
{
T=(BTNode
*)malloc( sizeof (BTNode));
T->keynum=1;
T->key[1]=i;
T->ptr[0]=NULL;
T->ptr[1]=NULL;
T->parent=NULL;
}
else
{
insert_BTree(T,
i);
}
}
mid_order(T);
return 0;
}
加载中，请稍候......
加载中…
(2013-07-16 18:03:14)