数据结构课件第九章查找和

1、当查找的文件较大，且存放在磁盘等直接存取设备中时，为了减少查找过程中对磁盘的读写次数，提高查找效率，基于直接存取设备的读写操作一般以“页”为当查找的文件较大，且存放在磁盘等直接存取设备中时，为了减少查找过程中对磁盘的读写次数，提高查找效率，基于直接存取设备的读写操作一般以“页”为的特征B-树又称基本B树,(多路平衡查找树),由R.Bayer(贝尔和)于1970年提出，是构造大型件系统索引结构的一种数据结构类型。它适合在磁盘直接存取设备上组织动态的查找表9.2.3B-树和B一棵m(m3)阶的B-树，或为，或是具有下列性质的m叉树树中每个结点的子树数目一棵m(m3)阶的B-树，或为，或是具有下列性

2、质的m叉树树中每个结点的子树数目2；非叶结点形式如下所示：数目其中，n为结点中key()的个数ki(lin)为key，且kiki+1，每个ki的位置还有；指针rep，指向key为iPi(0in)为指向本结点子树的指针，子树上所有key与ki、ki+1均满足排序性，即： kiPi所指子树上的key50,查找56652312查找失败11B-树的查找例9-6在一棵3阶B-4665T查找根查找根查6550,查找56652312查找失败11B-树的查找B-树的类型结构#definem/定义B-树的阶typedefstructbtnode /B-树结点/key数目structbtnodeB-树的类型结构#

3、definem/定义B-树的阶typedefstructbtnode /B-树结点/key数目structbtnode/指向本结点的父结点keytype/存放本结点中key（k1 retype*repm; /存放与key指针structbtnode/指向本结点子树的指针/结点及指针说明符typedef/查找结果Btreeg; /一次查找的非叶点/key相应序号/查找结果标志B-树的查找B-树的查找算法resultBTsearch(BtreeT,keytype/在根指针为T的B-树上，查找key为k所在位置i,j,n; B-树的查找算法resultBTsearch(BtreeT,keytype/

4、在根指针为T的B-树上，查找key为k所在位置i,j,n; , ; if(T=NULL)return(NULL,0,0); /空树返回p=T; /p为当前查找结点的指针，q为p之父n=p-/取结点中key的个数if(kp-/k大于p结点所有key时 p=p-j=n+1;/找k的位置/查找成功，返回k在p中的第j个位置 p=p-break;/查找相应子树/查找失败，k时，应在q结点第j位置B-树的查找B-树的查找效率取决于以下两：包含k的结点在B-树中所在的层数结点中ki的个数nB-树一般存B-树的查找效率取决于以下两：包含k的结点在B-树中所在的层数结点中ki的个数nB-树一般存入外存，而查找

5、某结点需要一个从外存向内存的存取过程，所以k所在结点的层数h越大，对外存的次就越多。而对外存的存取时间远大于在内存中key的查找时间，故是影响B-树查找效率的决定。也就是说，在B-树中进行查找时，其查找时间主要花费在搜索结点外存）上，即主要取决于B-树的深度B-树的查找算法分析问：含N个关键字的m阶B-树可能达到的最大深度H为多少？反过来问： 深度为H的B-树中至少含有多少个结点？先推导每一层1234H+1 含最少结问：含N个关键字的m阶B-树可能达到的最大深度H为多少？反过来问： 深度为H的B-树中至少含有多少个结点？先推导每一层1234H+1 含最少结个个2m/2 ：假设 m 阶 B-树的

6、深度为 H+1，由第 H+1 层为叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1N+12(m/2)H-H-1log m/2 (N+1)/2) Hlogm/2(N+1)/2)+12(m/22(m/22 H-1 总结：在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过B-树的查找算法分析生成B-树是一个“”过程。即初始B-树为空，逐步key=k，形成所需的树结构。每次结点终端结点中添加一个关键字。都是在最低层的某个非算法思路：调用查找算法BTsearch( T, k) ，确定k所属结点，返回（q, i , 若q中key生成B-树是一个“”过程。

7、即初始B-树为空，逐步key=k，形成所需的树结构。每次结点终端结点中添加一个关键字。都是在最低层的某个非算法思路：调用查找算法BTsearch( T, k) ，确定k所属结点，返回（q, i , 若q中key数Cnnparent) /取q的父结点mB-树的生成算法描述/q为根 = (p-k1=ki; p-TB-树的算法描述/q为根 = (p-k1=ki; p-TB-树的生成Km2-1q删除key=k，算法思路如下：（1）调用查找算法BTsearch( T, k) ，确定k所属结点，返回（q, 删除key=k，算法思路如下：（1）调用查找算法BTsearch( T, k) ，确定k所属结点，返

8、回（q, i , m/2，删（2） 若k落在最底层非终端结点，从q中删除k。若q中key后，其key数至少-1，仍保持m阶的特性，删除工作完成；若删除后其key数小于-1，则要进行“合并”运算：即将父结点中一个key拉下，（3）若k不位于最底层非终端结点，将k互换到最底层非终端结点，然后调用步骤（2）进行删除。合并的实现只删除最下层非终端结点中的关键字的情形，有三种可能：被删除关键字所在的结点中关键字的数目不小于m/2 ，则需要从该结点中删去该关键字Ki和相应指针Ai，树的其他都不变。合并的实现只删除最下层非终端结点中的关键字的情形，有三种可能：被删除关键字所在的结点中关键字的数目不小于m/2

9、 ，则需要从该结点中删去该关键字Ki和相应指针Ai，树的其他都不变。T删除2合并的实现只删除最下层非终端接种的关键字的情形，有三种可能：被删除关键字所在的结点中关键字的数目等于m/2-1，而与结点相邻的右兄弟（或左兄弟）结点中的关键字数目大合并的实现只删除最下层非终端接种的关键字的情形，有三种可能：被删除关键字所在的结点中关键字的数目等于m/2-1，而与结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于m/2-1则需要将其兄弟结点中的最小（或最大的）关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。T删除合并的实现只删除最下层非终端接种的

10、关键字的情形，有三种可能：被删除关键字所在的结点中关键字的数目等于m/2-1，而与结点相邻的右兄弟（或左兄弟）结点中的关键字数目大合并的实现只删除最下层非终端接种的关键字的情形，有三种可能：被删除关键字所在的结点中关键字的数目等于m/2-1，而与结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于m/2-1则需要将其兄弟结点中的最小（或最大的）关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。T删除合并的实现只删除最下层非终端接种的关键字的情形，有三种可能：被删除关键字所在的结点和其相邻的兄弟结点中关键字的数目都等于m/2-1，假设该结点有

11、左兄弟，且其左兄弟结点地址由双亲结点中的指针Ai所指，则再删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字ki一起，合并到Ai所指兄弟结点中。删除T合并的实现只删除最下层非终端接种的关键字的情形，有三种可能：被删除关键字所在的结点和其相邻的兄弟结点中关键字的数目都等于m/2-1，假设该结点有左兄弟，且其左兄弟结点地址由双亲结点中的指针Ai所指，则再删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字ki一起，合并到Ai所指兄弟结点中。删除T例9-在下图的3阶B-树中，分别删除k=10、52、56、46TT2例9-在下图的3阶B-树中，分别删除k=10、5

12、2、56、46TT2B+树是B-树的变型，目的在于有效地组织文件的索引结构。 （1）B+树结点形式：其中，n为key及子树个数；ki(lin)为key，且为指向本结点子树的指针，子树上B+树是B-树的变型，目的在于有效地组织文件的索引结构。 （1）B+树结点形式：其中，n为key及子树个数；ki(lin)为key，且为指向本结点子树的指针，子树上所有key与ki、ki+1均满足排序性，即：ki-1 Pi所指子树上的key 所有的叶子结点包含了全部关键字的信息。所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大(或最小)关键字。n例9-9一棵3阶B+Ta索引bc通常在B+树上，有两个

13、头指针，一个指向根结点；另一个指向关键字最小的叶子结点。可以对B+树进行两种查找算法。RRRRRRRRR2322222例9-9一棵3阶B+Ta索引bc通常在B+树上，有两个头指针，一个指向根结点；另一个指向关键字最小的叶子结点。可以对B+树进行两种查找算法。RRRRRRRRR2322222B+树查找算法在B+树中可以采用两种查找方式（1）顺序查找：类似单链表的查找。直接在数据层进行查找。（B+树查找算法在B+树中可以采用两种查找方式（1）顺序查找：类似单链表的查找。直接在数据层进行查找。（2）随机查找：类似B-树的查找。不同的是搜索到索引层的key与k相等时，还得继续搜索下去，直到数据层为止。例9-查找k=70。查找根a，因7080，取相应c结点；虽中有70,但还得搜索下去，直到找到数据层的70，取出相TabcRRRRRRRR例9-查找k=70。查找根a，因7080，取相应c结点；虽中有70,但还得搜索下去，直到找到数据层的70，取出相TabcRRRRRRRRR222与B-树的 操作相似，B+树的 也从叶子结点开始，当与B-树的 操作相似，B+树的 也从叶子结点开始，当后结点中的键值个数大于