毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 论文 >> 正文

SWFCDB的研究与探索 第7页

更新时间:2009-6-4:  来源:毕业论文
SWFCDB的研究与探索 第7页
5 自主知识产权数据库—重点难点
5.1 B+树索引
B+树是稠密层次索引的一种形式,具有动态重组的能力[5],因此能够保证其中间结点介于M/2和M之间(M为B树的阶)。要实现B+树,实现动态重组,插入和删除B+树结点时,就必须文护其结点的平衡性,这就是实现B+树算法的难点。
这里把B+树的中间结点叫做索引结点,而终端结点叫做叶子结点。对于5阶B+树,每个结点最多有4个关键字,5个指向子树的指针,而B+树的平衡因子为50%,因此每个结点中至少有2个关键字(根结点除外)。
5.1.1 插入平衡
插入平衡分为文护叶子结点平衡和文护索引结点平衡。
 
图 5 1
如图图 5 1所示为一个只有2层的B+树,现在将G插入树中,显然将插入EFHI所在的结点中,但是该结点中的关键字数达到了最大值4,因此叶子结点将会分裂,分裂后的图如图 5 2 所示
 
图 5 2
现在在图 5 2 的基础上再插入M,显然M将插入KPQZ所在的结点中,但是其父结点中的关键字达到了最大关键字数目,这时必然导致索引结点的分裂,并产生新的根结点,如图 5 3 所示。
 
图 5 3
5.1.2 删除平衡
相比插入平衡,删除平衡要复杂得多。
如果删除某结点的一个关键字,如果删除该关键字后该结点关键字数目大于或等于5/2(向上取整)-1,则不影响其平衡性,删除完成。
如果被删除关键字所在结点中的关键字数目等于5/2(向上取整)-1,而和该结点相邻的兄弟结点关键字数目大于5/2(向上取整)-1,则将该相邻兄弟结点中的一个关键字旋到该结点中(如果相邻结点是左兄弟,则将左兄弟中的最大关键字右旋入该结点;如果相邻节点是右兄弟,则将右兄弟中的最大关键字左旋入该结点)。如删除图 5 3 中的关键字K后,关键字I将右旋入关键字K所在结点,删除后如图 5 4所示。
 
图 5 4
如果待删除关键字所在的结点中的关键字数目等于 5/2(向上取整)-1,而和它相邻的兄弟结点有关键字数目也等于 5/2(向上取整)-1,则将待删除关键字所在结点和兄弟结点合并。这种合并必然导致其父节点(索引结点)中的关键字数减1,如果父结点中的关键字数目(未删除结点前)等于 5/2(向上取整)-1,则导致父结点的平衡因子在50%以下,因此必须处理索引结点的平衡。
现在先在图 5 4的基础上顺序插入X,Y,M,N,L,S,T,R。插入后的B+树结点图如图 5 5所示。删除关键字T,Z后,T,Z所在的结点均等于5/2(向上取整)-1,满足平衡因子50%,删除结束。现在删除关键字R,此时R所在的结点关键字数目
 
图 5 5
等于5/2(向上取整)-1,删除R后该结点的关键字数目小于5/2(向上取整)-1,而其左兄弟的关键字数目等于5/2(向上取整)-1(如果大于5/2(向上取整)-1,则执行右旋操作),将执行叶子结点合并操作,叶子结点合并后(如果父结点的关键字数目大于或等于5/2(向上取整)-1,则删除结束),其父结点的关键字数目也小于5/2(向上取整)-1,因此父节点要执行索引结点合并操作。删除R关键字后的B+树结点图如图 5 6所示。
 
图 5 6
文护叶子结点的平衡采用了左(右)兄弟右(左)旋一关键字和合并叶子结点的方法,同样文护索引结点也需采用以上两方法。在删除R关键字的过程中,涉及到了索引结点的合并,下面删除关键字D将涉及到索引结点的左旋。关键字D所在结点的关键字数目等于5/2(向上取整)-1,则删除D后关键字数目小于5/2(向上取整)-1,同样叶子结点合并后,此时索引结点的关键字数目小于5/2(向上取整)-1,这时应该执行索引结点的合并或旋转,但是D所在结点的父结点此时只有右兄弟,且其关键字数目达到了结点所能容纳的最大值,因此不能执行索引结点的合并,而执行索引结点的左旋操作。删除关键字D后B+树结点如图 5 7所示。
 
图 5 7
5.1.3 B+树算法难点总结
B+树算法的难点是文护结点在插入和删除关键字后的结点平衡性。插入平衡通过叶子结点分裂和索引结点分裂来实现,而删除平衡则通过叶子结点的左(右)旋转,叶子结点合并和索引结点的左(右)旋转,索引结点合并来实现。与B树(B-树)相比,B+树在插入算法上要简单,而在删除算法上要复杂。以上两节的介绍只是说明算法的基本原理,而在具体的算法设计中,则更应该考虑更多的实现细节。如:合并索引结点时应该将合并的结点指向新的父结点;插入关键字时,如果结点分裂,产生新的结点,如果预先生成的B+树结点空间都用完了,则应该生成若干新的结点空间;删除关键字时,如果有结点的合并,则应该回收结点空间等。
目前B+树算法采用的关键字类型为字符类型,可通过模版类思想[9]将其扩充为支持其他类型和自定义类型,如果为自定义类型,则需重载“ < ”运算符。
5.2 完成端口(IOCP)
完成端口采用了重叠I/O的机制,下面比较下完成端口与其他I/O模型产生性能差异的原因。
默认情况下,每个socket 在系统底层都有一个发送和接收缓冲区。当发送数据时,实际上是把数据复制到发送数据缓冲区中,然后用WSASend()发送,并返回。但是如果发送缓冲区已满,则WSASend()中指定的缓冲区就会被锁定到系统的非分页内存池中,函数返回WSA_IO_PENDING,说明目前网络忙,一旦网络空闲时,数

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一页

SWFCDB的研究与探索 第7页下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©751com.cn 辣文论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。