第5章集合与查找

1、计算机学院计算机学院 软件工程系软件工程系n集合集合n静态查找静态查找n哈希表哈希表 n二叉查找树二叉查找树nb树和树和b树树1计算机学院计算机学院 软件工程系软件工程系2计算机学院计算机学院 软件工程系软件工程系3计算机学院计算机学院 软件工程系软件工程系集合运算集合运算a b 或 a+bababa b 或 a baba- -b4计算机学院计算机学院 软件工程系软件工程系5计算机学院计算机学院 软件工程系软件工程系#include const int defaultsize = 100;class set private: int * bitvector; /集合的位向量数组 int max

2、size; /最大元素个数public: set ( int maxsetsize = defaultsize ); set ( ) delete bitvector; 6计算机学院计算机学院 软件工程系软件工程系 void makeempty ( ) /置空 for ( int i = 0; i 0 ); /判参数合理否 bitvector = new int maxsize; /分配空间 assert ( bitvector != null ); for ( int i = 0; i = 0 & x = 0 & x maxsize ) bitvectorx = 0; return 1; r

3、eturn 0; 010计算机学院计算机学院 软件工程系软件工程系void set : operator = ( set& right ) /赋值 assert ( maxsize = right.maxsize ); for ( int i = 0; i maxsize; i+ ) /逐位传送 bitvectori = right.bitvectori;this0 1 1 1 0 0 0 0 0 0 0right0 1 1 1 0 0 0 0 1 1 011计算机学院计算机学院 软件工程系软件工程系set & set : operator + ( set& right ) /求并 asser

4、t ( maxsize = right.maxsize ); for ( int i = 0; i maxsize; i+ ) bitvectori = bitvectori | right.bitvectori; return *this;thisrightthis0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 1 1 0 1 0 1 1 1 012计算机学院计算机学院 软件工程系软件工程系set & set : operator * ( set & right ) /求交 assert ( maxsize = right.maxsize ); f

5、or ( int i = 0; i maxsize; i+) bitvectori = bitvectori &right.bitvectori; return *this;thisrightthis0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 1 0 0 0 0 0 0 1 013计算机学院计算机学院 软件工程系软件工程系set & set : operator - ( set & right ) /求差 assert ( maxsize = right.maxsize ); for ( int i = 0; i = 0 & x maxsize

6、); return bitvectorx;0 1 0 0 1 0 0 1 0 0 0 9315计算机学院计算机学院 软件工程系软件工程系int set : operator = ( set& right ) /判等 assert ( maxsize = right.maxsize ); for ( int i = 0; i maxsize; i+) if ( bitvectori != right.bitvectori ) return 0; return 1;thisright0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 0i16计算机学院计算机学院 软件

7、工程系软件工程系int set : subset ( set& right ) /判断 this 是否是 right 的子集 assert ( maxsize = right.maxsize ); for ( int i = 0; i maxsize; i+) if ( bitvectori & ! right.bitvectori) return 0; return 1;thisright0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 0 1 i17计算机学院计算机学院 软件工程系软件工程系若表中存在特定元素，称查找成功，应输出该元素。若表中存在特

8、定元素，称查找成功，应输出该元素。- 否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查找表查找表查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。查询查询(searching)特定元素特定元素是否在表中。是否在表中。只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。既查找，又改变（增减）集合内的数据元素。元素中某个数据项的值，可用来识别一

9、个元素元素中某个数据项的值，可用来识别一个元素 可以可以唯一唯一标识一个元素的关键字标识一个元素的关键字 例如例如“学号学号”例如例如“性别性别”识别若干元素的关键字识别若干元素的关键字 基本概念基本概念18计算机学院计算机学院 软件工程系软件工程系v 对查找表常用的操作有对查找表常用的操作有哪些？哪些？ v查询查询某个某个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v在查找表中在查找表中插入插入一元素；一元素；v从查找表中从查找表中删除删除一元素。一元素。 v查找的过程是怎样的？查找的过程是怎样的？ 19计算机学院计算机学院 软件工程系软件工程系v如何评估查找算法的优劣？如何评估

10、查找算法的优劣？ 查找的过程就是将给定的查找的过程就是将给定的k值与值与查找表查找表中各元素的关键字进中各元素的关键字进行比较的过程。所以用比较次数的平均值来评估算法的优劣，行比较的过程。所以用比较次数的平均值来评估算法的优劣，称为称为平均查找长度平均查找长度（asl：average search length）。）。显然，显然，asl值越小，时间效率越高。值越小，时间效率越高。 niiniiisuccpcpasl11) 1 ( .20计算机学院计算机学院 软件工程系软件工程系21计算机学院计算机学院 软件工程系软件工程系template int searchlist : search ( c

11、onst type& x ) const /顺序搜索关键码为 x 的对象, 第currentsize号/位置作为控制搜索自动结束的“监视哨”使用 elementcurrentsize.key = x; int i = 0; /将x送currentsize号位置设监视哨 while ( elementi.key != x ) i+; /从前向后顺序搜索 return i;22计算机学院计算机学院 软件工程系软件工程系 1010niiniiisuccpcpasl) 1 ( .)(110ipasl-niisucc23计算机学院计算机学院 软件工程系软件工程系.)()(1-nisuccnnnninas

12、l02121111顺序查找的优缺点：顺序查找的优缺点： 优点：对表中元素没有要求优点：对表中元素没有要求 缺点缺点: 平均查找长度较大平均查找长度较大24计算机学院计算机学院 软件工程系软件工程系25计算机学院计算机学院 软件工程系软件工程系- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8lowmidhigh6搜索成功的例子搜索成功的例子66low mid high5 6 8 10 125 6 7 8low midhigh626计算机学院计算机学院 软件工程系软件工程系- -1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8lowmidh

13、igh5搜索失败的例子搜索失败的例子655low mid high 6 8 10 125 6 7 8low midhigh527计算机学院计算机学院 软件工程系软件工程系binarysearch ( const type & x, const int low, const int high ) const /折半搜索的递归算法 int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( elementmid.key x ) mid = binarysearch ( x, low, mid -1 ); return mid;28计

14、算机学院计算机学院 软件工程系软件工程系template int orderedlist : binarysearch ( const type & x ) const / int high = currentsize-1, low = 0, mid; while ( low = high ) mid = ( low + high ) / 2; if ( elementmid.key x ) high = mid - 1; /左缩搜索区间 else return mid; /搜索成功 return -1; /搜索失败29计算机学院计算机学院 软件工程系软件工程系算法分析：算法分析：ordert

15、: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 2 4 6 8 10 13 15 18 20 22 24 25 27 30 156241081324202718222530折半查找的判定树：比较次数不超过完全二叉树高度。折半查找的判定树：比较次数不超过完全二叉树高度。30计算机学院计算机学院 软件工程系软件工程系最多的比较次数不超过二叉树的高度：所以最多的比较次数不超过二叉树的高度：所以最坏情况下最坏情况下的查找长度是：的查找长度是：折半折半查找成功查找成功的平均查找长度：的平均查找长度： 设查找任一元素的概率都相等，即：设查找任一元素的概率都相等，即：pi=1/n 在第在

16、第k层上最多有层上最多有2k-1 个结点，在第个结点，在第k层上的结点需层上的结点需比较比较k次。所以：次。所以： )1n(log)n(t2 niiniiisuccpcpasl11) 1 ( niisucccasl1n131计算机学院计算机学院 软件工程系软件工程系)2*h2*)1h(.2*32*21*1(n12*kn1cn1asl1h2h211kh1kin1isucc 12)1h(2h2)1h( 232211h1h2h21 nlog1) 1n(logn1n )n) 1n(log) 1n(n1) 12) 1h(n1 asl222hsucc 32计算机学院计算机学院 软件工程系软件工程系 ( 1

17、0, 20, 30, 40, 50, 60 )105030204060aslunsucc = (2*1+3*6)/7 = 20/7 aslsucc = (1+2*2+ 3*3)/6 = 14/6 33计算机学院计算机学院 软件工程系软件工程系索引顺序表的查找索引顺序表的查找(分块查找分块查找)1. 概念：是顺序查找的一种改进。概念：是顺序查找的一种改进。索引项索引项：(key,addr), key 是关键字，是关键字，addr是地址。是地址。索引表：索引表：由索引项构成的顺序表。由索引项构成的顺序表。22 15 13 8 17 20 35 24 33 40 36 29 50 48 60 68

18、54 6122 40 680 6 12最大关键字最大关键字(key)起始地址起始地址(addr)如何查找关键字为如何查找关键字为60的元素的元素?34计算机学院计算机学院 软件工程系软件工程系分块查找的算法思想：分块查找的算法思想：d=d1,d2,.,dn1) 将数据集分为将数据集分为s个块个块 b1,b2, , bs ；2) 块间有序：当块间有序：当ij时，时，bi中的任一元素小于中的任一元素小于bj中的任中的任 一元素；一元素；3) 为每个为每个bi块设一索引项块设一索引项(keyi, addri)；4) s个索引项构成索引表；个索引项构成索引表；5) 块内可有序可无序块内可有序可无序;3

19、5计算机学院计算机学院 软件工程系软件工程系查找过程查找过程:（1）首先在索引表中查找，确定在哪个块中。）首先在索引表中查找，确定在哪个块中。 可以是折半查找，也可以是顺序查找。可以是折半查找，也可以是顺序查找。（2）在块中查找。在块中查找只能是顺序查找。）在块中查找。在块中查找只能是顺序查找。36计算机学院计算机学院 软件工程系软件工程系4. 算法分析：算法分析：设在索引表中和块内都是顺序查找。设在索引表中和块内都是顺序查找。(s是索引项的数目是索引项的数目)索引表中查找：索引表中查找：alsindex=(s+1)/2块中查找：块中查找： alslock=(n/s+1)/2所以：所以： al

20、sbs= (s+1)/2 + (n/s+1)/2显然它与显然它与s 的取值有关。的取值有关。当当 时，时，asl有最小值有最小值 ns 1n例如例如 当当n=28，s=24时，时，aslbs=17, 而折半法为而折半法为8， 顺序表为顺序表为(28+1)/2=128.537计算机学院计算机学院 软件工程系软件工程系 对象关键码 key 对象存放地址 addr38计算机学院计算机学院 软件工程系软件工程系39计算机学院计算机学院 软件工程系软件工程系性别次索引次关键码次关键码 男男 女女 计计 数数 5 3 地址指针地址指针指针指针 03 08 17 24 47 51 83 9540计算机学院计

21、算机学院 软件工程系软件工程系婚否次索引次关键码次关键码 已婚已婚 未婚未婚 计计 数数 5 3 地址指针地址指针指针指针 03 08 24 47 83 17 51 95职务次索引次关键码次关键码 教师教师 教务员教务员 实验员实验员 计计 数数 5 1 2 地址指针地址指针指针指针 08 24 47 51 83 03 17 9541计算机学院计算机学院 软件工程系软件工程系42计算机学院计算机学院 软件工程系软件工程系43计算机学院计算机学院 软件工程系软件工程系44计算机学院计算机学院 软件工程系软件工程系45计算机学院计算机学院 软件工程系软件工程系46计算机学院计算机学院 软件工程系软

22、件工程系47计算机学院计算机学院 软件工程系软件工程系48计算机学院计算机学院 软件工程系软件工程系49计算机学院计算机学院 软件工程系软件工程系 rikikrn12)/( ki50计算机学院计算机学院 软件工程系软件工程系51计算机学院计算机学院 软件工程系软件工程系52计算机学院计算机学院 软件工程系软件工程系53计算机学院计算机学院 软件工程系软件工程系54计算机学院计算机学院 软件工程系软件工程系 标识符的八进制内码表示及其平方值标识符的八进制内码表示及其平方值55计算机学院计算机学院 软件工程系软件工程系56计算机学院计算机学院 软件工程系软件工程系57计算机学院计算机学院 软件工程

23、系软件工程系 58计算机学院计算机学院 软件工程系软件工程系59计算机学院计算机学院 软件工程系软件工程系 60计算机学院计算机学院 软件工程系软件工程系61计算机学院计算机学院 软件工程系软件工程系62计算机学院计算机学院 软件工程系软件工程系63计算机学院计算机学院 软件工程系软件工程系attlee burke broad blum ekersalton ederly hecht 64计算机学院计算机学院 软件工程系软件工程系65计算机学院计算机学院 软件工程系软件工程系66计算机学院计算机学院 软件工程系软件工程系67计算机学院计算机学院 软件工程系软件工程系j = (h0 - i2 )

24、 % m, if ( j 0 ) j += m68计算机学院计算机学院 软件工程系软件工程系0 1 2 3 4 5 blum burke broad ekers ederly hecht 6 7 8 9 10 11 alton attlee (3) (1) (2) (1) (2)(1)25 26 27 28 29 30 (5) (3)69计算机学院计算机学院 软件工程系软件工程系70计算机学院计算机学院 软件工程系软件工程系71计算机学院计算机学院 软件工程系软件工程系72计算机学院计算机学院 软件工程系软件工程系 (1) (3) (1) (2) (1) (1) (2) (6) 0 1 2 3

25、 4 5 6 7 8 9 10 1 8 2 5 3 4 6 773计算机学院计算机学院 软件工程系软件工程系74计算机学院计算机学院 软件工程系软件工程系75计算机学院计算机学院 软件工程系软件工程系attleealtonburkebroadblumekersederly76计算机学院计算机学院 软件工程系软件工程系 77计算机学院计算机学院 软件工程系软件工程系35154550402510203078计算机学院计算机学院 软件工程系软件工程系二叉链表二叉链表79计算机学院计算机学院 软件工程系软件工程系80计算机学院计算机学院 软件工程系软件工程系35154550402510203081计算

26、机学院计算机学院 软件工程系软件工程系35154550402510203028插入新结点插入新结点2882计算机学院计算机学院 软件工程系软件工程系 53537853786553786517537865871753786509178753786581178709537865151787098183计算机学院计算机学院 软件工程系软件工程系12311113222332384计算机学院计算机学院 软件工程系软件工程系85计算机学院计算机学院 软件工程系软件工程系5378651787092345删除45右子树空, 用左子女顶替5378651787092386计算机学院计算机学院 软件工程系软件工程系

27、53788817940923删除78左子树空, 用右子女顶替53948817092387计算机学院计算机学院 软件工程系软件工程系删除78在右子树上找中序下第一个结点填补8853788117940945236553818817940945236588计算机学院计算机学院 软件工程系软件工程系 abcabcdede89计算机学院计算机学院 软件工程系软件工程系90计算机学院计算机学院 软件工程系软件工程系91计算机学院计算机学院 软件工程系软件工程系92计算机学院计算机学院 软件工程系软件工程系93计算机学院计算机学院 软件工程系软件工程系插入插入acebdhhh-1 h-1bacedhhh-1

28、 hbhhceadh-1 h94计算机学院计算机学院 软件工程系软件工程系h插入插入bacedhhh-1hhhh-1h-1abdcehhh-1bceadh95计算机学院计算机学院 软件工程系软件工程系插入插入hhacedh-1h-1bfgegacdbfhhh-1h96计算机学院计算机学院 软件工程系软件工程系aehhcdh-1hbfgfgdhah-1cebhh97计算机学院计算机学院 软件工程系软件工程系hhh-1h-1acedbfgacebfgdhhhh-198计算机学院计算机学院 软件工程系软件工程系acedbfghhh-1hhhh-1hacebfgd99计算机学院计算机学院 软件工程系软

29、件工程系100计算机学院计算机学院 软件工程系软件工程系161633163111631691116331611931126916101计算机学院计算机学院 软件工程系软件工程系18167326119316971126183716142691173918261116102计算机学院计算机学院 软件工程系软件工程系151831816731171491615112626149103计算机学院计算机学院 软件工程系软件工程系104计算机学院计算机学院 软件工程系软件工程系105计算机学院计算机学院 软件工程系软件工程系0hhh-1不旋转1hh-1pp106计算机学院计算机学院 软件工程系软件工程系-

30、-1h+1hh不旋转0hhpp高度减1107计算机学院计算机学院 软件工程系软件工程系108计算机学院计算机学院 软件工程系软件工程系1hhh-1左单旋ph0q1hh-1phq- -1109计算机学院计算机学院 软件工程系软件工程系1hh-1左单旋ph1q0h-1phq0h-1h-1110计算机学院计算机学院 软件工程系软件工程系01hh-1p- -1qh-1或h-2h-1或h-2h-1rh-1h-1h-1h-100pqr右左双旋高度减1111计算机学院计算机学院 软件工程系软件工程系abcdefghijklmnopqrst0000000- -1- -1- -1- -1- -1- -1- -1

31、11111112计算机学院计算机学院 软件工程系软件工程系abcdefghijklmnopqrst0000000- -1- -1- -1- -1- -1- -1- -111111poopoop113计算机学院计算机学院 软件工程系软件工程系abcdefghijklmnoqrst000000- -1- -1- -1- -1- -1- -1- -111111rm114计算机学院计算机学院 软件工程系软件工程系abcdefghijklmnoqrst000000- -1- -1- -1- -1- -1- -1- -11001 mmme0115计算机学院计算机学院 软件工程系软件工程系abcdefghi

32、jnklmor00000- -100- -1- -1- -1- -1010000tq0s116计算机学院计算机学院 软件工程系软件工程系117计算机学院计算机学院 软件工程系软件工程系3520 40abcde25 3010 1545 50118计算机学院计算机学院 软件工程系软件工程系3520 40abcde25 3010 1545 50root119计算机学院计算机学院 软件工程系软件工程系120计算机学院计算机学院 软件工程系软件工程系121计算机学院计算机学院 软件工程系软件工程系303520 4025 3010 1545 50root45 50354020root10 1525122计

33、算机学院计算机学院 软件工程系软件工程系 123计算机学院计算机学院 软件工程系软件工程系124计算机学院计算机学院 软件工程系软件工程系125计算机学院计算机学院 软件工程系软件工程系126计算机学院计算机学院 软件工程系软件工程系n 127计算机学院计算机学院 软件工程系软件工程系1.空树，插入根；结束；否则：空树，插入根；结束；否则：2.找到插入位置找到插入位置 (p,i) , p在它最底层；在它最底层；3. 将将key 插入到（插入到（p,i）处；）处；4. 若若p中中key多于多于m-1，按如下方法分裂，否则结束，按如下方法分裂，否则结束.128计算机学院计算机学院 软件工程系软件工

34、程系 若若p不是根：不是根： k1 k2 . ki-1 ki ki+1 . km 2/mi p k1 k2 . ki-1ki+1 . km k1 ki k kip p一分为二一分为二p p的双亲的双亲129计算机学院计算机学院 软件工程系软件工程系 若若p是根：是根： k1 k2 . ki-1 ki ki+1 . km 2/mi p k1 k2 . ki-1ki+1 . km ki kip p一分为二一分为二创建新的根创建新的根130计算机学院计算机学院 软件工程系软件工程系n=1 加入加入5353n=2 加入加入7553 75n=3 加入加入1397513953n=5 加入加入49,1457

35、5139 14549 53131计算机学院计算机学院 软件工程系软件工程系n=7 加入加入1014953361391451017549 75n=6 加入加入36139 1455336132计算机学院计算机学院 软件工程系软件工程系133计算机学院计算机学院 软件工程系软件工程系1. 找到被删除的找到被删除的key 所在的位置所在的位置（p, i）/即即p.keyi;2. p不是最底层结点：不是最底层结点： 用用p的子树的子树ptri中的最小键中的最小键key1，代替，代替key， 问题变为删除问题变为删除key1，类似地逐次用下一层的替类似地逐次用下一层的替代当前的代当前的key，直至底层，使

36、被删除键落在最底，直至底层，使被删除键落在最底层，层，p指向该结点指向该结点 例：例：4阶阶b-树树 。15 208 1217 25 30 16 18 。p134计算机学院计算机学院 软件工程系软件工程系3. p是最底层结点：是最底层结点：36 49m = 3删除3649135计算机学院计算机学院 软件工程系软件工程系55 5875 80m = 3删除5510406560 703050acbdefgh5875 8010406560 703050acbdefgh136计算机学院计算机学院 软件工程系软件工程系不少于不少于8 126 10 14 18删除删除10108 146 12 18对称地也可

37、以将左兄弟中的最大键右旋移动对称地也可以将左兄弟中的最大键右旋移动137计算机学院计算机学院 软件工程系软件工程系138计算机学院计算机学院 软件工程系软件工程系5580m = 3删除5510406058 753050acbdefgh合并f, g58 60801040753050acbdefh139计算机学院计算机学院 软件工程系软件工程系8055m = 3删除8010406058 753050acbdefgh合并g, h60 75551040583050acbdefh140计算机学院计算机学院 软件工程系软件工程系55 5875 80完整示例完整示例：m = 3删除5010406560 70

38、3050acbdefgh用55取代555875 80删除5510406560 7030acbdefgh用58取代141计算机学院计算机学院 软件工程系软件工程系5875 8010406560 7030acbdefgh合并f, g5875 80104060 657030acbdefh142计算机学院计算机学院 软件工程系软件工程系5880104060 657530acbdefh删除70用75取代58104060 658030acbdefh删除75用80取代调整f, c, h143计算机学院计算机学院 软件工程系软件工程系58801040606530acbdefh8030 4060fh58 65d

39、b144计算机学院计算机学院 软件工程系软件工程系145l b+树是应文件系统所需而产生的一种树是应文件系统所需而产生的一种b-树的变树的变形树。形树。l 一棵一棵m阶的阶的b+树和树和m阶的阶的b-树的差异在于：树的差异在于：有有n棵子树的结点中含有棵子树的结点中含有n个关键码；个关键码；所有的叶子结点中包含了全部关键码的信息，所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。本身依关键码的大小自小而大的顺序链接。所有的非终端结点可以看成是索引部分，结点所有的非终端结点可以看成是索

40、引部分，结点中仅含有其子树根结点中最大（或最小）关键码中仅含有其子树根结点中最大（或最小）关键码。计算机学院计算机学院 软件工程系软件工程系146b树索引是一个多级索引树索引是一个多级索引(1)b树结点结构树结点结构 p1 k1 p2 pn-1 k n-1 p n 有有n-1个搜索码个搜索码k1 、k2 、kn-1 ，n个个 指针指针p1 、pn 。 结点中码值结点中码值有序存放有序存放：如果：如果ij ,则则ki kj 。计算机学院计算机学院 软件工程系软件工程系(2)叶结点结构，对于叶结点结构，对于i=1,2, ，n-1。指针。指针pi 指向指向具有具有ki 的一个文件记录（主索引文件按照

41、码值的一个文件记录（主索引文件按照码值存放）或指向一个指针桶（辅助索引），桶中存放）或指向一个指针桶（辅助索引），桶中每个指针指向具有码值每个指针指向具有码值ki 的一个文件记录。指的一个文件记录。指针针pn 指向下一个叶结点的头指针。这样可以将指向下一个叶结点的头指针。这样可以将叶结点按照码值顺序串在一起，以便对文件进叶结点按照码值顺序串在一起，以便对文件进行顺序处理。行顺序处理。 叶结点中最多有叶结点中最多有n-1个码值，至少有个码值，至少有 (n-1)/2 个个码值，各叶结点中值地范围互不相交，即若码值，各叶结点中值地范围互不相交，即若li 和和lj 是两个叶结点且是两个叶结点且ij ，

42、那么，那么li 中的所有中的所有码值都小于码值都小于lj 中的所有码值。中的所有码值。 要使要使b树索引成为稠密索引，各码值必须出树索引成为稠密索引，各码值必须出现在叶结点中。现在叶结点中。 147计算机学院计算机学院 软件工程系软件工程系(3)b树的非叶结点，形成叶结点上的一个树的非叶结点，形成叶结点上的一个多级（稀疏）索引。对于多级（稀疏）索引。对于i=2,3, ，n-1，指针指针pi 指向一棵子树，该子树中所有结点指向一棵子树，该子树中所有结点的索引码值大于等于的索引码值大于等于ki1 且小于且小于ki ，pn 指指向的子树中所有码值大于等于向的子树中所有码值大于等于kn-1 ，p1 指

43、指向子树中的所有码值均小于向子树中的所有码值均小于k1 。 非叶结点中至少有非叶结点中至少有 n/2 个指针，最多有个指针，最多有n个，指针个数称为该结点的扇出。个，指针个数称为该结点的扇出。148计算机学院计算机学院 软件工程系软件工程系(4)根结点：根结点的指针数可以小于根结点：根结点的指针数可以小于 n/2 。 除非整棵树只有一个结点，否则，根结点至少除非整棵树只有一个结点，否则，根结点至少有两个指针。完整的有两个指针。完整的b树。如图：树。如图：root sqt 59 97 15 44 5972 97 10 15 21 37 4451 5963 72 85 91 97149计算机学院计

44、算机学院 软件工程系软件工程系 通常在通常在b+树上有树上有两个头指针两个头指针，一个指向，一个指向根结点，另一个指向关键码最小的叶子根结点，另一个指向关键码最小的叶子结点结点 。 因此，可以对因此，可以对b+树进行树进行两种查找运算两种查找运算：一种是从最小关键码起顺序查找，另一一种是从最小关键码起顺序查找，另一种是根结点开始，进行随机查找。种是根结点开始，进行随机查找。150计算机学院计算机学院 软件工程系软件工程系 在在b +树上进行随机查找、插入和删除的树上进行随机查找、插入和删除的过程基本上与过程基本上与b-树类似。树类似。 在查找时，若非终端结点上的关键码等在查找时，若非终端结点上

45、的关键码等于给定值，并不终止，而是继续向下直于给定值，并不终止，而是继续向下直到叶子结点。因到叶子结点。因 此，此，在在b+树，不管查找树，不管查找成功与否，每次查找都是走了一条从根成功与否，每次查找都是走了一条从根到叶子结点的路径到叶子结点的路径。 b+树查找的分析类似于树查找的分析类似于b-树。树。151计算机学院计算机学院 软件工程系软件工程系 b树的插入树的插入 b树的插入仅在叶子结点上进行，当结树的插入仅在叶子结点上进行，当结点中的关键字个数大于点中的关键字个数大于m时要分裂成两时要分裂成两个结点，它们所含关键字的个数分别为个结点，它们所含关键字的个数分别为 和和 。并且，它们的双亲结点中。并且，它们的双亲结点中应同时包含这两个结点中的最大关键字应同时包含这两个结点中的最大关键字。其余同。其余同b-树的插入类似。树的插入类似。15221m2m计算机学院计算机学院 软件工程系软件工程系 b树的删除树的删除 b树的删除也仅在叶子