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] 下一页