数据结构关于B树说明及插入和分裂

本文主要是介绍数据结构关于B树说明及插入和分裂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注意：本文是我学习的一点总结，具体的代码并没有经过调试，是通过算法导论B树中的描述写成，但是增加了关于数据的链表，而不是
如算法导论中的一个数组，留于此用于以后的继续深入学习。

B树的定义和特点：
B树的阶实际上就是指向子树的最大指针个数
比如2-3树阶为3,2-3-4树阶为4
B树已经不是常规的树结构，多用于文件系统管理，每个节点可以有多个指向
孩子的指针，特点如下：
1、根要么为空树，要么至少有2个子树
2、假设M阶的B树，n个指向子树的指针
则：
Ceil(M/2)<=n<=M
n-1个关键字
则
ceil(M/2)-1<=n-1<=M-1
3、所有叶子结点在同一层次
4、设Pn为指针，Kn为关键字
KEYS=n P0K1P1K2P2K3P3..........
P0指向子树的所有值均小于K1
P1指向子树的所有值均大于K1
5、有K1<K2<K3<K4的顺序
如下就是一颗5阶4关键字的B树

B树的优势(可以说也是B+树的优势)：
由于在一些应用中比如数据库应用中，数据量肯能非常大，在这种情况一棵完全依赖内存的
树就不可取了，首先数据量过大使用AVL树或者红黑树得到的深度难以想象，二来不可能有
那么多的内存用于存放整个数据，实际上在数据库中往往是通过一个指针(并非内存中的指针)，
这个指针实际上是数据块的块号，如果我们只将B树的根结点缓存到内存中，那么我们根据
B树的查找原则将路径中的数据块存放到缓存，那么不仅性能大大提高，同时也减少了内存
的使用，一般物理磁盘的读取速度为毫秒级别，而内存硅存储的读取速度为纳秒级别，基本
上是5个数量级的差别。同时为了更大发挥磁盘读取的效率，一般来讲在数据库中B+树的根结
点为1个block.

B树的插入分裂：

1、如果叶子结点有足够的空间如果按照严格的定义就是

ciel(M/2)-1<=n-1<M-1 注意是小于M-1这样肯定小于

最大允许的关键字，那么就在找到的叶子结点进行插入

2、如果叶子结点关键字大于M-1，而双亲结点空间<M-1，则

分裂叶子结点，同时中间元素上移到双亲结点(我们以奇数

关键字为例)的相应位置,这样的移动的依据来自于

第四点：

KEYS=n P0K1P1K2P2K3P3..........

P0指向子树的所有值均小于K1

P1指向子树的所有值均大于K1

B树实际上也是一个有序树，按照这个规则上移后必然也满足

上面的规则，因为在一个节点中数据是有序排列我们设置是

升序。

3、如果双亲结点也处于M-1状态，那么双亲结点也需要分裂，其规则

如叶子结点一致，关于这一点演示如下：

考虑如下树(5阶,4关键字，注意5阶关子健最少2个最多4个)

插入55：

4、如果根结点也处于M-1状态，上面的情况就出现了B树索引高度加1的情况

演示如下：

考虑如下树(5阶,4关键字)插入84：

最后节点64分裂开来，树的高度由3变为了4

算法导论中的说明：
在算法导论中对b树的分裂做了一定的改动，也就是说在进行数据查找的时候
路过的结点，如果发现出现了等于最大关键的节点就进行分裂，这样虽然增加
了分裂的可能性，但是并不会增加太多因为增加的分裂次数只是一个常量而已
是一种方便的可行的编程方式。
并且进行了义一个中间量用于标示节点指针的中间位置，如果设置这个中间为
_BTREE_POINTER_M_,那么指针的个数最大始终为2*_BTREE_POINTER_M_为偶数，
而关键字个数始终为2*_BTREE_POINTER_M_-1为一个奇数，如果定义
BTREE_POINTER_M_=2 那么就是2-3-4树，这样对编程也带来了一定的方便，我们
也采用这种方式。而2-3树这样的定义是不能实现的。

代码（问题很多没调试过，算法导论描述编写而成）,这部分可以参考算法导论关于
B树的描述

点击(此处)折叠或打开

head.h
#define _BTREE_POINTER_M_ 2
#define _BTREE_POINTER_ (_BTREE_POINTER_M_ * 2) //2-3-4tree。
#define _BTREE_KEYS_ (_BTREE_POINTER_M_ * 2-1)
#define bool int
#define true 1
#define false 0
#define ALLOCBNODE (BTNodeP)calloc(1,sizeof(BTNode))
#define SIZENODE sizeof(DULNODE)
#define SIZELISTHEAD sizeof(LISTHEAD)
#define SIZEBTHead sizeof(BTHead)
typedef struct dulnode //node type of btree data
{
int data; //example
struct dulnode *prior;
struct dulnode *next;
} DULNODE,*DULNODEP;
typedef struct listhead ///node type of btree data header
{
DULNODEP head;
DULNODEP last;
DULNODEP current;
int length;
} LISTHEAD,*LISTHEADP;
typedef struct BTNode{
int keynum; // 结点中关键字的个数，keynum <= _BTREE_KEYS_
LISTHEADP keyhder; // 数据链表实现的头指针
struct BTNode* child[_BTREE_POINTER_]; // 孩子指针
bool isLeaf; // 是否是叶子节点的标志
int nodenum; // 节点计数
}BTNode,*BTNodeP;
typedef struct BTHead{
BTNodeP root_node; //指向B树的根结点
int max_node_num; // 当前节点个数计数
int btree_level; //B树的层次
}BTHead,*BTHeadP;

点击(此处)折叠或打开

#include<stdio.h>
#inlcude<stdlib.h>
//chain fun
bool initlist(LISTHEADP* p)
{
*p = (LISTHEADP)malloc(SIZELISTHEAD);
if(!*p)
{
return false;
}
else
{
memset(*p,0,SIZELISTHEAD);
(*p)->head = NULL;
(*p)->last = NULL;
(*p)->current = NULL;
(*p)->length = 0;
return true;
}
}
//inslast insert one node at last postion
void inslast(LISTHEADP h,DULNODEP s)
{
if(!(h->head)) //list is empty or not
{
h->head = s;
h->last = s;
h->current = s;
h->length++;
}
else
{
h->last->next = s;
s->prior = h->last;
h->last = s;
h->current = s;
h->length++;
}
}
void delfirst(LISTHEADP h) //delete first node current_point to next node
{
DULNODEP p;
if(!(h->head))
{
printf("error(1):delfirst() error list have no node!\n");
exit(1);
}
else if(!(h->head->next)) //only one node
{
free(h->head);
h->head = NULL;
h->current = NULL;
h->last = NULL;
h->length--;
}
else
{
p = h->head ;
h->head->next->prior = NULL;
h->head = h->head->next;
h->current = h->head;
h->length--;
free(p);
}
}
bool makenode(int datavalue,DULNODEP* p)
{
*p = (DULNODEP) malloc (SIZENODE);
if(!(*p))
{
return false;
}
else
{
memset(*p,0,SIZENODE);
(*p)->data = datavalue;
(*p)->next = NULL;
(*p)->prior = NULL;
return true;
}
}
static DULNODEP getelemp(const LISTHEADP h,int postion)
{
int i=0;
DULNODEP p;
if(postion > h->length || postion ==0 )
{
printf("error(2):getelemp() postion large than lenth or poastion = 0\n");
exit(2);
}
p = h->head;
while(i<postion-1)
{
i++;
p = p->next;
}
return p;
}
void dellast(LISTHEADP h) //delete last node current_point to prior node
{
DULNODEP p;
if(!(h->head))
{
printf("error(1):delfirst() error list have no node!\n");
exit(1);
}
else if(!(h->head->next)) //only one node
{
free(h->head);
h->head = NULL;
h->current = NULL;
h->last = NULL;
h->length--;
}
else
{
p = h->last ;
h->last->prior->next = NULL;
h->last = p->prior;
h->current = p->prior;
h->length--;
free(p);
}
}
static int findpos(LISTHEADP h,int k,int i)
{
DULNODEP p=NULL;
if(h->length == 0)
{return 1;}
else
{
p = h->last;
while(i>=1 && p->data > k) // exp : i = 1 one key if k<data frist insert else k>data return 2
{
if(i==1)
{
return i;
}
p = p->prior;
i--;
}
return i+1; // i+1=2 is insert after node 1
}
}
//addnode add one node after give postion
void addnode(DULNODEP inode,int postion,LISTHEADP h) //insert one elem after postion
{
DULNODEP p;
p = getelemp(h,postion);
if(!p->next) //last node?
{
p->next = inode;
inode->prior = p;
inode->next = NULL;
h->last = inode;
h->current = inode;
}
else
{
inode->prior = p;
inode->next = p->next;
p->next->prior = inode;
p->next = inode;
h->current = inode;
}
h->length++;
}
//insfirst insert one node at first postion
void insfirst(LISTHEADP h,DULNODEP s)
{
if(!(h->head)) //list is empty or not
{
h->head = s;
h->last = s;
h->current = s;
h->length++;
}
else
{
h->head->prior = s;
s ->next = h->head;
h->head = s;
h->current = s;
h->length++;
}
}
//btree fun
bool B_Tree_Inital(BTHeadP* p)
{
*p = (BTHeadP)malloc(SIZEBTHead);
if(!*p)
{
return false;
}
else
{
memset(*p,0,SIZEBTHead);
(*p)->root_node = NULL;
(*p)->max_node_num = 0;
(*p)->btree_level = 0;
return true;
}
}
void B_Tree_Create(BTNodeP* root,BTHeadP* p)
{
BTNodeP x = NULL;
if(!(x = ALLOCBNODE))
{
printf("B_Tree_Create error mem error(10)\n");
exit(10);
}
(*root) = x;
(*p)->root_node = (*root);//head pointer is root
(*p)->max_node_num++;
(*p)->btree_level++;
(x)->isLeaf = true;
(x)->keynum = 0;
(x)->nodenum = (*p)->max_node_num;
if(!(initlist(&(x->keyhder)));
{
printf("B_Tree_Create error mem error(11)\n");
exit(11);
}
}
void B_Tree_Split(BTNodeP* x,int i,BTNodeP* y,BTHeadP* p) //X是上层结点，y是X的一个满的子节点，i为y中间元素上浮到x中的位置
{
BTNodeP z = NULL;
DULNODEP zcnode = NULL; //btree node z's chain node pointer;
DULNODEP yfnode = NULL; //used find any node pointer;
int j=1;
if(!(z = ALLOCBNODE))
{
printf("B_Tree_Split error mem error(12)\n");
exit(12);
}
(*p)->max_node_num++;
z->isLeaf = (*y)->isLeaf;
z->keynum = _BTREE_POINTER_M_ - 1;
z->nodenum = (*p)->max_node_num++;
if(!(initlist(&(z->keyhder)));
{
printf("B_Tree_Split error mem error(13)\n");
exit(13);
}
yfnode = getelemp((*y)->keyhder,_BTREE_POINTER_M_+1);
for(j=1;j<=_BTREE_POINTER_M_-1;j++) //z first half key = y last half key this is very import
/*
--x--
--y-- --z--
*/
{
makenode(yfnode->data,&zcnode);
inslast(z->keyhder,zcnode);
yfnode = yfnode->next;
}
for(j=1;j<=_BTREE_POINTER_M_-1;j++)//delete y last half key beacuase the key is give to z
{
dellast((*y)->keyhder);
}
if(!((*y)->isLeaf)) // if node y is not leaf node,child pointer must change ,give half pointer to z ,but total pointer not change
{
for(j=1;j<=_BTREE_POINTER_M_;j++)
{
z->child[j-1] = (*y)->child[j-1+_BTREE_POINTER_M_];
(*y)->child[j-1+_BTREE_POINTER_M_] = NULL;
}
}
(*y)->keynum = _BTREE_POINTER_M_ - 1; //key change
for(j=(*x)->keynum+1;j>=i+1;j-- ) // 0 1 1 <insert new i=2 is before 2> 2 2 3 3 4 4 --> 0 1 1 new2 new2 3 3 4 4 5 5 i now is before i
{
(*x)->child[j] = (*x)->child[j-1];
}
(*x)->child[i] = z;
//find y last data is split data,use yfnode to store
makenode((*y)->keyhder->last->data,&yfnode);
//if sucess delete last y data
dellast((*y)->keyhder) ;
if(i == 1) //move key value
{
insfirst((*x)->keyhder,yfnode);
}
else
{
addnode(yfnode,i-1,(*x)->keyhder);
}
(*x)->keynum ++;
return yfnode->data;
}
void B_Tree_Insert_Nofull(BTNodeP* x,int k,BTHeadP* p)
{
int i ;
int pos;
int dataret;
DULNODEP np = NULL;
i = (*x)->keynum;
makenode(k,&np);
if((*x)->isLeaf) //if the x is leaf node ?
{
pos=findpos((*x)->keyhder,k,i);
if(pos == 1)
{
insfirst((*x)->keyhder,np);// pos == 1 insert at first
}
else
{
addnode(np,pos-1,(*x)->keyhder); //addnode is insert after pos so pos-1
}
(*x)->keynum++
}
else
{
pos=findpos((*x)->keyhder,k,i); //not leaf node find leaf node
if(((*x)->child)[pos-1]->keynum == _BTREE_KEYS_ ) // is child leaf node is full split it
{
dataret=B_Tree_Split(x,pos,&(((*x)->child)[pos-1]),p); //key real insert pos
if( k > dataret) //split sucess if k> B_TREE_SPLIS RETURN SPLIT DATA
{
pos=pos+1;
}
}
B_Tree_Insert_Nofull(&(((*x)->child)[pos-1]),k); //key pos is 1 2 3 4 5......pointer pos is 0 1 2 3 4....so pos-1
}
}
void B_Tree_Insert(BTHeadP* p,int k) //k is value to insert ,BtheadP has a pointer to b_tree_root
{
BTNodeP r = (*p)->root_node;
BTNodeP s = NULL;
if(r->keynum = _BTREE_KEYS_)
{
if(!(s = ALLOCBNODE))// new root node
{
printf("B_Tree_Insert error mem error(14)\n");
exit(14);
}
(*p)->max_node_num++;
(*p)->root_node = s;
(*p)->btree_level++;
s->isLeaf = FALSE;
s->keynum = 0;
s->child[0] = r;
s->nodenum = (*p)->max_node_num;
if(!(initlist(&(s->keyhder)));
{
printf("B_Tree_Insert error mem error(15)\n");
exit(15);
}
B_Tree_Split(&s,1,&r,&p);
B_Tree_Insert_Nofull(&s,k,p);
}
else
{
B_Tree_Insert_Nofull(&r,k,p);
}
}

关于B树的删除会涉及到更多的复杂的方面，比如普通删除，比如节点融合，B树高度的
降低等，我没有仔细的学习和研究。

可见B树B+树这种数据结构还是比较负载，如果加上很多很多的其他的链表或者数据结构
那么编写程序的难度非常大，我们使用数据库的DBA们应该为数据库软件的开发者们心存
敬畏，他们是天才的程序员。

来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/7728585/viewspace-2126929/，如需转载，请注明出处，否则将追究法律责任。

转载于:http://blog.itpub.net/7728585/viewspace-2126929/

这篇关于数据结构关于B树说明及插入和分裂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！