《数据结构》课程设计说明书B+树查找的实现

1、武汉理工大学数据结构课程设计说明书b+树查找的实现摘要.1引言.1.1 b+树的定义.1.2 b+树的举例.2需求分析.2.1 系统应具备的功能.2.2 测试计划.3数据结构设计. 3.1结点类. 3.2 方便操作的队列.3.3将叶子结点链在一起的链表.4算法设计. 4.1 b+树插入算法. 4.1.1 插入算法设计. 4.1.2插入代码的实现. 4.1.2.1 将元素插入到树中. 4.1.2.2搜索整个树，找到插入的位置. 4.1.2.3 将关键字以及其子树插入this结点. 4.1.2.4若结点个数过多分裂该节点. 4.2 b+树删除算法. 4.2.1删除算法设计. 4.2.2删除代码的实

2、现. 4.2.2.1从b+树中删除关键字. 4.2.2.2搜索该删除的位置返回结点指针. 4.2.2.3在this中删除某关键字. 4.2.2.4若关键字太少，合并. 4.3 b+树查找. 4.3.1查找算法的设计. 4.3.2查找代码的实现. 4.3.2.1基于叶子链的查找. 4.3.2.2基于根的查找. 4.4 b+树的显示. 4.4.1 b+树显示设计. 4.4.2 b+树显示代码的实现. 4.4.2.1打印整个树. 4.4.2.2 打印某结点. 4.5 其他函数. 4.5.1 时间随机创建b+树. 4.5.2创建完整个树后把叶子结点链起来. 4.6 main函数的实现.5设计体会以及技

3、术讨论.6参考文献.7结束语.摘要：b+树是一种树数据结构，常见于数据库与档案系统之中。b+树能够使资料保持有序，并拥有均匀的对数处理时间的插入和删除动作。建立一棵b+树，实现b+树的查找等相关操作，输出结果；关键字：b+树，插入，删除，查找，输出1引言 实时数据库系统是开发实时控制系统、数据采集系统、cims系统等的支撑软件。其中，数据库系统大部分基于b+树来实现。b+树是为文件系统而提出一种b-树的变型树，是一种平衡的多路查找树，在文件系统中有所应用。主要用作文件的索引。利用它查找信息快速，方便数据以及文件的管理。创建b+树，实现其基本插入，删除，两种查找，输出。 1.1 b+树的定义b树

4、是应文件系统所需而出的一种b-树的变型树。一棵m阶的b树和m阶b-树的差异在于： 1有n棵子树的结点中含有n个关键字。 2所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 3所有的非终端结点可以看成是索引部分，结点中仅含其子树（结点）中的最大（或最小）关键字。 通常在b树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。 1.2 b+树的举例2需求分析：2.1 系统应具备的功能 1 创建一棵b+树 2 实现b+树的插入结点操作3 实现b+树的删除结点操作4 实现b+树的两种查找，输出结果5 实现b+树的显示操作2.

5、2 测试计划时间随机产生几棵b+树，然后显示结果，实现数据的插入，删除，两种查找等操作，并显示结果。3 数据结构设计：3.1结点类class btreepublic:int n; /该节点所含关键字的个数 大于等于2btree *father;static int number;/阶数 大于等于3static btree *root;btree();int *data;btree *down;static bool inserttree(int t);/在树中插入tstaticbtree* searchinsert(int t);/搜索插入到某节点bool insertpoint(int t,

6、btree *p);/在节点插入void split(int t,btree *p); /分裂static void treedel(int t);void delpoint(int t);static btree*searchdel(int t);/搜索删除某节点void combine();static deep; /深度static void deletetree();int *x; /存储各层的结点数int btree:number=4;int btree:deep=0;btree *btree:root=null;btree:btree() /创建一个节点data=new intnu

7、mber;down=new btree*number;for(int i=0;inumber;i+)datai=0;downi=null;father=null;n=0;3.2 方便操作的队列为了实现显示，链接操作自定义了一种特殊的队列，该队列以btree指针和结点深度为队列元素，入队正常操作，出队时判断是否为叶子结点，如果不是叶子结点则把它的全部孩子结点入队；class duipublic :btree * data200; /元素int num200; /该元素是第几层的int tp,tl;/tp为队头，tl为队尾dui()tp=0;tl=0;btree* pop();void push(

8、btree*,int);bool empty(); ;btree* dui:pop()/出队int t;t=tp;tp=(tp+1)%200;if(numt!=btree:deep-1)/不为叶子节点for(int i=0;in;i+)push(datat-downi,numt+1);return datat; void dui:push(btree *i,int j)datatl=i;numtl=j;tl=(tl+1)%200;xj+;bool dui:empty()if(tp=tl)return 1;else return 0;dui qu; /全局的队列3.3将叶子结点链在一起的链表st

9、ruct node btree* q; node *next;node *head=null;/全局的叶子结点链的头结点4算法设计 4.1 b+树插入算法 4.1.1 插入算法设计b-树的生成从空树开始，逐个插入关键字而得。关键字的个数必须至少为m/2-1，每次插入总在最底层某个终端结点添加一个关键字，如果该结点关键字个数小于m-1则直接插入，如果发现新插入关键字后，关键字总数超过m-1个则结点需要分裂，做法如下： (a)假设结点p中已经含有m-1个关键字，再插入一个关键字之后(插入总要保持关键字数组的大小有序，从小到大排好序)，可以将p分裂为p和p，其中p含有的信息为m/2-1(m表示大于m

10、的最小整数)，p含有的信息为m-m/2 (m表示大于m的最小整数)。然后将关键字km/2和指向p的指针则一起插入到p的双亲结点中去。 (b)检查双亲结点，如果双亲结点出现(a)的情况，则回到步骤a继续执行。直到插入满足条件为止，树的深度增加过程是随着插入而自下而上生长的过程。 4.1.2插入代码的实现 4.1.2.1 将元素插入到树中bool btree: inserttree(int t)/将t插入树中btree *p=btree:searchinsert(t);if(1=p-insertpoint(t,null)return 1;else return 0;4.1.2.2搜索整个树，找到插

11、入的位置，若插入的关键字大于root的最大关键字需该祖辈的关键字btree* btree:searchinsert(int t)/搜索t的该插入的位置，返回指针if(root=null)root=new btree;deep=1;return root;btree *p;p=root;if(troot-dataroot-n-1) /大于最大关键字要改父节点的关键字while(p-down0!=null)p-datap-n-1=t;p=p-downp-n-1;return p;while(p-down0!=null)int i;for(i=0;in&tp-datai;i+);p=p-downi;

12、return p;4.1.2.3 将关键字以及其子树插入this结点bool btree:insertpoint(int t,btree *p)/把元素t和它所指的子树插入this结点中int i,j;for(i=n-1;i=0&datait;i-);if(i=0&t=datai) return 0; /相同不做操作if(n+1number)split(t,p);return 1 ;for(j=n-1;ji;j-) /插入元素和指针dataj+1=dataj;downj+1=downj;datai+1=t;downi+1=p;if(p!=null)p-father=this;n+;return

13、 1;4.1.2.4若结点个数过多分裂该节点void btree:split(int t,btree *p)/*t,p分别是多余的节点地址，关键字，分裂this节点*/int i,j;if(this=root)deep+;root=new btree;btree *pt=new btree;for(i=0,j=0;idataj)pt-datai=dataj;if(downi!=null)downi-father=pt;pt-downi=downj;j+;elsept-datai=t;t=99999999;if(p!=null)p-father=pt;pt-downi=p;pt-father=r

14、oot;pt-n=(number+1)/2;root-data0=pt-data(number+1)/2-1;root-down0=pt;for(i=0;idataj)datai=dataj;downi=downj;j+;elsedatai=t;downi=p;t=99999999;father=root;n=number-(number+1)/2+1;root-n=2;root-data1=datanumber-(number+1)/2;root-down1=this;elsebtree *pt=new btree;for(i=0,j=0;idataj)pt-datai=dataj;if(d

15、ownj!=null)downj-father=pt;pt-downi=downj;j+;elsept-datai=t;t=99999999;if(p!=null)p-father=pt;pt-downi=p;pt-father=father;pt-n=(number+1)/2;for(i=0;idataj)datai=dataj;downi=downj;j+;elsedatai=t;t=99999999;downi=p;n=number-(number+1)/2+1;father-insertpoint(pt-datapt-n-1,pt);4.2 b+树删除算法 4.2.1删除算法设计 b-

16、树删除算法分析，注意删除可以在b-树的任意关键字而不是局限于叶结点的关键字： (a)从根结点开始，根结点至少有1个关键字，将根结点记录为p，将被删除的关键字b所在的结点为q，如果一开始p等于q，说明删除发生在根结点，转入步骤(c)，否则必须先试探路径上结点的关键字个数，如果p到q必须经过的p的某个孩子结点r时，如果该孩子结点的关键字的个数等于m/2-1时，则转入步骤(b)，然后将孩子结点的地址赋给p，直到发现p的孩子为即将被删除的关键字所在的结点q，转入步骤(c)； (b)r结点如果存在与自己相邻的兄弟结点，该兄弟结点记为s，如果s是r的右兄弟并且结点s的关键字数目大于m/2-1，则将r和s两

17、兄弟之间存在一个关键字a(位于他们的双亲结点p中)移动到r的最右边并且a的右孩子指向s最左边关键字的左孩子，s最左边的关键字移动到p中原来关键字a的位置，我们称之为先向右兄弟借位，当然如果s是r的左兄弟并且结点s的关键字数目大于m/2-1时r也可以采用向左兄弟s先借位的算法。而如果r的相邻兄弟结点关键字数目没有大于m/2-1时，仍然任意选定一个相邻兄弟结点s，并且从双亲结点p取关键字a，a须满足的条件是a相邻的两个指针域指向的正是结点r和s，将r，a，s进行合并，同时将p中a所在的位置删除，合并其相邻的两个指针域为一个，返回。 (以上(b)的做法为了避免的情况是：当被删关键字所在结点需要从其双

18、亲借位时，双亲出现关键字数目等于m/2-1而需要进一步进行借位操作，它的做法是从根到被删除关键字所在结点的路径上，中间结点的关键字个数预先从m/2-1增加到m/2个) (c)对于含有被删除关键字b的结点q，有如下三种大的判别情况： q已经是树的根并且是b-树种唯一一个结点，直接删除关键字b即可； 如果结点q不是b-树的根，但是是b-树的叶子结点，继续进行判断，如果q结点中含有的关键字的数量大于m/2-1则直接进行删除关键字b即可，算法结束；如果q结点中含有的关键字数量等于m/2-1时，还要判断，如果q的相邻兄弟结点的关键字数量存在关键字数量大于m/2-1的相邻兄弟，则进行借位，然后删除关键字b

19、，算法结束；如果q的相邻兄弟结点的关键字数量均等于m/2-1，则删除b之后，需要从叶子结点的双亲进行借位并同与q的相邻兄弟结点直接进行合并(与q合并的兄弟结点和q同属于一个双亲结点的孩子并且他们为所借关键字的相邻两个指针域所指的结点)，此时不必再担心双亲结点出现违规的现象，因为步骤(a)和(b)的做法已经进行了预先避免。算法结束； 如果结点q不是b-树的根，也不是b-树的叶子结点，则q是b-树的中间结点，对中间结点中关键字b的删除操作，需要先把此关键字b与它的直接后继(即是在b树中所有关键字组成的序列，比b大与b相邻的关键字)对换位置，关键字b的直接后继位于b的相邻右指针所指的子树中的最左位置

20、，也是该子树中的最小关键字的位置，互换后b位于叶子结点，直接转步骤。4.2.2删除代码的实现 4.2.2.1从b+树中删除关键字void btree:treedel(int t)if(root=null)cout空树root-dataroot-n-1)cout无该元素delpoint(t);4.2.2.2搜索该删除的位置返回结点指针btree* btree:searchdel(int t)btree *p;p=root;while(p-down0!=null)int i;for(i=0;in&tp-datai;i+);if(t=p-datai)goto loop; /要改父节点的值p=p-do

21、wni;return p;loop:int y=0;while(p-datay!=t)y+;/查找所在的结点btree *q=p-downy;while(q-down0!=null)q=q-downq-n-1;int a=q-dataq-n-2; /q到达底端p-datay=a;p=p-downy;while(p-down0!=null)p-datap-n-1=a;p=p-downp-n-1;return p;4.2.2.3在this中删除某关键字void btree:delpoint(int t)/在this处删除tint i;for(i=0;idatai;i+);if(t!=datai)c

22、out无该元素endl;return ; /无该元素，结束;for(;in-1;i+)datai=datai+1;downi=downi+1;n-;if(nn=0)deep-;btree *p=root;root=null;delete p;elseif(root-n=1&root-down0!=null)btree *p=root;root=root-down0;delete p;deep-;return;int i;for(i=0;in;i+)if(father-downi=this)break;if(0=i)btree *p;int j;p=father-down1;if(p-n=(nu

23、mber+1)/2)int a;a=datan-1;for(j=0;jn;j+)datan=p-dataj;downn+=p-downj;if(p-downj!=null)p-downj-father=this;father-down1=this;father-delpoint(a);delete p;elsefather-data0=p-data0;datan=p-data0;downn+=p-down0;if(p-down0!=null)p-down0-father=this;for(j=0;jn-1;j+)p-dataj=p-dataj+1;p-downj=p-downj+1;p-n-;

24、elsebtree *p;int j;p=father-downi-1;if(p-n=(number+1)/2)int a;a=p-datap-n-1;for(j=0;jdatap-n=dataj;p-downp-n+=downj;if(downj!=null)downj-father=p;father-downi=p;father-delpoint(a);delete this;elsefather-datai-1=p-datap-n-2;p-n-;for(j=n;j0;j-)dataj=dataj-1;n+;data0=p-datap-n;4.3 b+树查找4.3.1查找算法的设计在b+树

25、中可以采用两种查找方式,一种是直接从最小键值开始进行顺序查找,另一种就是从b+树的根结点开始进行随机查找。这种查找方式与b-树的查找方法相似,只是在分支结点上的键值与查找值相等时,查找并不结束,要继续查到叶结点为止,此时若查找成功,则按所给指针取出对应记录即可。因此,在b+树中,不管查找成功与否,每次查找都是经过了一条从树根结点到叶子结点的路径。4.3.2查找代码的实现4.3.2.1基于叶子链的查找void searchlink(int t)if(head=null)cout空树endl;return;node *p=head;int n=0;while(p!=null)n+;for(int

26、i=0;iq-n&tp-q-datai;i+);if(t=p-q-datai)coutsuccess!它在第btree:deep层的第n个结点里endl;break;elseif(tq-datai)coutfail!无该结点值next;if(p=null)coutfail!无该结点值endl;4.3.2.2基于根的查找void searchroot(int t)if(btree:root=null)cout空树btree:root-databtree:root-n-1)cout无改结点值down0!=null)for(int i=0;in&tp-datai;i+);p=p-downi;for(

27、int i=0;in&tp-datai;i+);if(t=p-datai)coutsuccess!存在该结点值endl;else coutfail!不存在该结点值！endl;void searchlink(int t)if(head=null)cout空树endl;return;node *p=head;int n=0;while(p!=null)n+;for(int i=0;iq-n&tp-q-datai;i+);if(t=p-q-datai)coutsuccess!它在第btree:deep层的第n个结点里endl;break;elseif(tq-datai)coutfail!无该结点值n

28、ext;if(p=null)coutfail!无该结点值endl;4.4 b+树的显示4.4.1 b+树显示设计定义一个显示结点的函数，利用特殊队列，遍历整个b+树，打印所以结点;4.4.2 b+树显示代码的实现4.4.2.1打印整个树void printtree(btree *q)if(q=null)cout空树endl;return;int i,j;for(i=0;ibtree:deep;i+)xi=0;qu.push(q,0);for(i=0;ibtree:deep;i+)cout第i+1层:endl;for(j=0;jxi;j+)print(qu.pop();coutendl;4.4.

29、2.2 打印某结点void print(btree *p)for (int i=0; i n; i+)coutsetw(4)datai;cout | ;4.5 其他函数4.5.1 时间随机创建b+树void create(int m)btree:deletetree();srand(unsigned)time(null);for(int i=0;idown0!=null);node *p1,*p2;head=p1=new node;p1-q=tree;while(!qu.empty()p2=new node;p2-q=qu.pop();p1-next=p2;p1=p2;p1-next=null

30、;46 main函数的实现void main()int choice;dosystem(cls);cout*endl;cout* 欢迎进入b+树演示程序，请选择相应功能。 *endl;cout* 1。随机建立一棵b+树； *endl; cout* 2。在b+树中利用叶子链一个数； *endl;cout* 3。在b+树中利用根查找一个数； *endl;cout* 4。在b+树中插入一个数； *endl;cout* 5。在b+树中删除一个数； *endl;cout* 6。显示整个b+树； *endl;cout* 0。退出程序； *endl;cout*endl;cout请选择：choice;int m;switch (choice)case 1:system(cls);cout您选择的是创建b+树end