数据结构第25讲：第10章查找表可扩充散列c课件.ppt

1、1 一、哈希表是什么？一、哈希表是什么？二、哈希函数的构造方法二、哈希函数的构造方法三、处理冲突的方法三、处理冲突的方法 四、哈希表的查找四、哈希表的查找9.4 哈哈 希希 表表五五.可扩充散列可扩充散列2 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为:四、哈希表的查找哈希表的查找 对于给定值 K,计算哈希地址 Hi=H(K)若若 rHi.key=NULL 则查找不成功若若 rHi.key=K 则查找成功否则否则“求下一地址 Hi”，直至 rHi.key=NULL (查找不成功)或 rHi.key=K (查找成功)为止。3int hashsize=997,.;/一个素

2、数序列typedef struct ElemType *elem;/数据元素存储基址 int count;/当前数据元素个数 int sizeindex;/hashsizesizeindex为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1/-开放定址哈希表开放定址哈希表的存储结构-4Status HashSearch(HashTable H,KeyType K,int&p,int&c)/p指示待查数据元素K在表中的位置，c为冲突计数 /SearchHashp=Hash(K);/求得哈希地址while

3、(H.elemp.key!=NULL&/该位置有记录 !EQ(K,H.elemp.key)）/且不等于K collision(p,+c);/处理冲突,求得下一探查地址 pif(EQ(K,H.elemp.key)return SUCCESS;/查找成功，返回待查数据元素位置 pelse return UNSUCCESS;/查找不成功查找算法查找算法5Status InsertHash(HashTable&H,Elemtype e)c=0;if(HashSearch(H,e.key,p,c)=SUCCESS)return DUPLICATE;/表中已有与表中已有与 e 有相同关键字的元素有相同关键

4、字的元素else if(c hashsizeH.sizeindex/2)/冲突次数冲突次数 c 未达到上限，（阀值未达到上限，（阀值 c 可调）可调）H.elemp=e;+H.count;return OK;/查找不成功时，返回查找不成功时，返回 p为插入位置为插入位置 else RecreateHashTable(H);/重建哈希表重建哈希表/InsertHash插入算法插入算法6Status DeleteHash(HashTable&H,Elemtype e)/DeleteHash else H.elemp=null;-H.count;return OK;c=0;if(HashSearch

5、(H,e.key,p,c)=UNSUCCESS)return ERROR;/表中无与 e 有相同关键字的元素删除算法删除算法H.Infop=deleted;/将待删除位置置为不可能将待删除位置置为不可能/出现的值出现的值./将待删除位置用探测序列将待删除位置用探测序列/的的下一个关键字顺序递补下一个关键字顺序递补./另外定义一个删除标志数组另外定义一个删除标志数组/并置删除标志并置删除标志pH.InfoH.elem7 1)选用的哈希函数哈希函数;2)选用的处理冲突的方法处理冲突的方法;3)哈希表饱和的程度：装载因子装载因子 =记录数记录数/表的长度表的长度 通常要求通常要求 0.5决定哈希表查

6、找的决定哈希表查找的ASL的因素的因素：哈希表查找的分析:从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。8查找关键码时所需的平均查找次数查找关键码时所需的平均查找次数在散列函数中，在散列函数中，除留余数法除留余数法优于优于其它类型其它类型的散列函数，的散列函数，最差的是最差的是折叠法折叠法。对于冲突处理方法：对于冲突处理方法：链地址法链地址法优于优于开放定址法开放定址法；链地址法需要增设链接指针链地址法需要增设链接指针,增加了存储？增加了存储？由于开放定址法须保持大量的空闲空间以确保搜索效由于开放定址法须保持大量的空闲空间以确保搜索效率，如平方探查法要求装填因子率，

7、如平方探查法要求装填因子 0.5 0.5。而记录所占。而记录所占空间又比指针大得多，故链地址法反而节省存储空间。空间又比指针大得多，故链地址法反而节省存储空间。9用不同的冲突处理方法时散列表的平均查找长度用不同的冲突处理方法时散列表的平均查找长度 如果取如果取 0.5 1.5 2.5 21.251.110从以上结果可见，哈希表的平均查找长度是 的函数，而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定在某个范围内平均查找长度限定在某个范围内。这是哈希表所特有的特点。这是哈希表所特有的特点。11例例1 1：求散列表大小并设计散列函数求散列表大小并

8、设计散列函数条件：设有一个含条件：设有一个含200个记录的散列表，要求用个记录的散列表，要求用平方探查平方探查法解决冲突，且要求按关键码查询时，找到一个法解决冲突，且要求按关键码查询时，找到一个新记录插入位置的平均探查次数不超过新记录插入位置的平均探查次数不超过1.5。问题：哈希表至少应该多大？并设计哈希函数。问题：哈希表至少应该多大？并设计哈希函数。分析：对平方探测法，查找不成功的平均搜索长度为分析：对平方探测法，查找不成功的平均搜索长度为 Un1/(1-),解答：根据要求解答：根据要求n200，且：，且：Un1/(1-)1.5 1/3 =n/m=200/m m 60012 一、哈希表是什么

9、？一、哈希表是什么？二、哈希函数的构造方法二、哈希函数的构造方法三、处理冲突的方法三、处理冲突的方法 四、哈希表的查找四、哈希表的查找9.4 哈哈 希希 表表五五.可扩充散列可扩充散列13五五.可扩充散列可扩充散列问题提出：问题提出：1 1。再散列问题：。再散列问题：对于静态散列表，无论使开发定址法还是链址对于静态散列表，无论使开发定址法还是链址法，都需要静态分配存储空间。如果表的记录太满，法，都需要静态分配存储空间。如果表的记录太满，则查找和插入的时间将很长，甚至插入操作可能失则查找和插入的时间将很长，甚至插入操作可能失败。败。由于由于静态散列表的长度不能够增加（静态散列表的长度不能够增加（

10、?），解决，解决的办法只能是另外建立一个新的散列表（原来的两的办法只能是另外建立一个新的散列表（原来的两倍），并扫描原来表中的每一个记录，并将其插入倍），并扫描原来表中的每一个记录，并将其插入到新的散列表中（到新的散列表中（复制记录复制记录）。）。数据结构数据结构用面向对象方法与用面向对象方法与C+语言描述语言描述清华大学出版社清华大学出版社 殷人昆殷人昆142 2。哈希表太长，多次访问外存。哈希表太长，多次访问外存 由于哈希表中的记录数太多，不能够一次装载到由于哈希表中的记录数太多，不能够一次装载到内存。只能根据内存缓存区的大小分段载入内存。内存。只能根据内存缓存区的大小分段载入内存。对于象

11、平方探测这样的开放定址处理冲突方法，对于象平方探测这样的开放定址处理冲突方法，进行一次哈希查找就需要进行多次访问外存的操作。进行一次哈希查找就需要进行多次访问外存的操作。p段段1 1段段2 2段段3 315 可扩充散列是一种动态散列方法，它对传统的可扩充散列是一种动态散列方法，它对传统的散列技术进行了扩充。它采用树型结构实现哈希散列技术进行了扩充。它采用树型结构实现哈希表的存储结构，使之能够表的存储结构，使之能够动态动态（再散列不需要复制再散列不需要复制）地适应对文件存储容量的需求，并能保持地适应对文件存储容量的需求，并能保持高效高效（访访问外存次数少问外存次数少）的搜索效率。）的搜索效率。1

12、.1.二叉二叉 Trie Trie 树树2.2.将二叉将二叉TrieTrie树转换为目录表树转换为目录表3.3.插入与目录扩充插入与目录扩充4.4.删除与目录收缩删除与目录收缩160 1(A)3 4 5(E)9(I)268(H)4(D)19(S)22(V)0 18(R)7(G)190 5(E)THADHAS HAVE HEHERHEREHIGHHIS表示关键字集合HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS Trie 树树1 1。多叉。多叉2 2。按字符划分。按字符划分3 3。查找需要比较。查找需要比较17 根据关键字二进制码的最低根据关键字二进制码的最低 2 2 位进行

13、划分，可以把这些位进行划分，可以把这些关键字分成关键字分成 4 4 类。假设把它们类。假设把它们 4 4 个页块的文件中个页块的文件中,每页最多每页最多可以容纳可以容纳2 2个关键码。这样就可以利用各关键码的最低个关键码。这样就可以利用各关键码的最低2 2位（位（00,00,01,10,1101,10,11）来决定它们的存储页块。）来决定它们的存储页块。001011A0,B0C2C3A1,B1标识符标识符 A0 A1 B0 B1 C2 C3 C2 C3二进位二进位 100 100 101 101 110 110 110 110 表示表示 000 001 000 001 010 011 010

14、011 1.二叉二叉 Trie 树树 设关键字序列设关键字序列 A0,A1,B0,B1,C2,C3。若每一个关键码由。若每一个关键码由 2 个字符组成个字符组成,而每一个字符用而每一个字符用 3 个二进制位表示。则有：个二进制位表示。则有：页块页块(桶桶)18二叉二叉TrieTrie树：树：根据各关键码的二进制位表示根据各关键码的二进制位表示,从从最低位最低位到最高到最高位进行划分位进行划分,各页块的索引构成一个二叉树结构。各页块的索引构成一个二叉树结构。二叉二叉TrieTrie树树构造方法：构造方法：首先首先,在根结点处按各关键码的最低位是在根结点处按各关键码的最低位是 1 1 还还是是 0

15、,0,划分为两组。对于每一组再按次低位是划分为两组。对于每一组再按次低位是 1 1 还还是是 0 0 继续分组继续分组,如此分下去如此分下去,直到每组剩下不多于直到每组剩下不多于 2 2 个关键码为止。个关键码为止。二叉二叉TrieTrie树组成树组成：在二叉在二叉TrieTrie树中有两类结点：树中有两类结点：分支结点分支结点和和叶结点叶结点。分支结点分支结点按其相关二进位是按其相关二进位是 1 1 还是还是 0,0,分为两个分分为两个分支支;叶结点叶结点包含指向关键码存放页块的指针。包含指向关键码存放页块的指针。19 根据关键字二进制码的最低根据关键字二进制码的最低 2 2 位进行划分，可

16、以把这些位进行划分，可以把这些关键字分成关键字分成 4 4 类。假设把它们类。假设把它们 4 4 个页块的文件中个页块的文件中,每页最多每页最多可以容纳可以容纳2 2个关键码。这样就可以利用各关键码的最低个关键码。这样就可以利用各关键码的最低2 2位（位（00,00,01,10,1101,10,11）来决定它们的存储页块。）来决定它们的存储页块。001011A0,B0C2C3A1,B1标识符标识符 A0 A1 B0 B1 C2 C3 C2 C3二进位二进位 100 100 101 101 110 110 110 110 表示表示 000 001 000 001 010 011 010 011

17、1.二叉二叉 Trie 树树 设关键字序列设关键字序列 A0,A1,B0,B1,C2,C3。若每一个关键码由。若每一个关键码由 2 个字符组成个字符组成,而每一个字符用而每一个字符用 3 个二进制位表示。则有：个二进制位表示。则有：页块页块(桶桶)1 1。二叉。二叉2 2。按二进制位划分。按二进制位划分3 3。查找不需要比较。查找不需要比较20二叉二叉trietrie树是一种树型结构的哈希表树是一种树型结构的哈希表 哈希函数：哈希函数：是一种从关键字到二进制码的映射。是一种从关键字到二进制码的映射。哈希地址：哈希地址：根据二进制码的最低位进行划分，关根据二进制码的最低位进行划分，关键字的二进制

18、码对应键字的二进制码对应trietrie二叉树从根到叶子二叉树从根到叶子结点的路径。叶子结点中存放记录的指针。结点的路径。叶子结点中存放记录的指针。二叉二叉trietrie树树 与与 哈希表哈希表A0,B0C2C3001011A1,B1哈希表的大小哈希表的大小：可以动态扩展。：可以动态扩展。？冲突处理方法：？冲突处理方法：？B1101 001 01散列散列取低位取低位找叶子结点找叶子结点 页块号页块号找记录指针找记录指针21A0,B0C2C3001011A1,B1C501 插入插入 新的关键码新的关键码 C5 C5（110101110101）A0,B0C2C3001011A1,B1标识符标识符

19、 A0 A1 B0 B1 C2 C3 C2 C3二进位二进位 100 100 101 101 110 110 110 110 表示表示 000 001 000 001 010 011 010 011 应把应把 C5C5 放到放到A1,B1A1,B1所在的所在的第第3 3页中。但是此时该页块已满页中。但是此时该页块已满,发生了溢出（冲突）。为此发生了溢出（冲突）。为此,将将第第3 3页页扩充一倍，分裂为两页扩充一倍，分裂为两页。22 再插入再插入 一个新关键码一个新关键码 C1(110001)C1(110001)A0,B0C2C3001011C501B101A1,C1A0,B0C2C300101

20、1A1,B1C501 应将应将C C插入到插入到A1,B1A1,B1所在的页块中。这时又发生溢出所在的页块中。这时又发生溢出,需要再需要再分裂分裂A1,B1A1,B1所在页块：根据所在页块：根据A1,B1,C1A1,B1,C1 的最低的最低4 4位将它们重新分配位将它们重新分配到这两个页块中。到这两个页块中。标识符标识符 A0 A1 B0 B1 C2 C3 C2 C3二进位二进位 100 100 101 101 110 110 110 110 表示表示 000 001 000 001 010 011 010 011 23从上面的例子得出两个结论：从上面的例子得出两个结论：如何存储二叉如何存储二

21、叉triestries树？树？将二叉将二叉TrieTrie树映射为目录表树映射为目录表，以避开在二叉以避开在二叉TrieTrie树中的长时间搜索过程，树中的长时间搜索过程，根据二进制码直接根据二进制码直接找到记录存放的页块找到记录存放的页块。如何生成分布均匀的二进制码？如何生成分布均匀的二进制码？特殊哈希函数，特殊哈希函数，把关键码转换成二进制数字表示把关键码转换成二进制数字表示的的伪随机数伪随机数集合集合,1 1。对某个页块的访问时间取决于区分。对某个页块的访问时间取决于区分(搜索搜索)关键字关键字码所需的二进制码位数；码所需的二进制码位数；2 2。如果关键字码分布不均匀，最后产生的。如果关

22、键字码分布不均匀，最后产生的trietrie树使树使倾斜的；倾斜的；进一步提出两个问题：进一步提出两个问题：24根据关键字根据关键字keykey生成分布均匀的随机二进制数生成分布均匀的随机二进制数设：设：key key AB1AB11 1。通过折叠移位累加生成一个十进制数。通过折叠移位累加生成一个十进制数A B 1A B 165 66 0165 66 012 2。采用除留余数法（模为。采用除留余数法（模为1993719937的素数）得到一的素数）得到一个界于个界于0 02 215 15 之间的一个十进制数之间的一个十进制数 18617186176566016566013 3。再将这个十进制数转

23、换成一个。再将这个十进制数转换成一个1616位的二进制数位的二进制数 0100 1000 1011 10010100 1000 1011 10014 4。取这个二进制数的若干最低位作为随机二进制数。取这个二进制数的若干最低位作为随机二进制数252.2.将二叉将二叉TrieTrie树转换为目录表树转换为目录表 首先将二叉首先将二叉TrieTrie树的树的分支结点分支结点部分部分 (索引部分索引部分)转换为一棵转换为一棵满满二叉树二叉树，即所有指向叶结点的分支结点都位于同一层次上。即所有指向叶结点的分支结点都位于同一层次上。A0,B0C2C3001011A1,B1C501A0,B0C2C30010

24、11A1,B1C501010101然后再把这棵然后再把这棵二叉树二叉树映射映射为指示各个页块的为指示各个页块的目录表。目录表。满二叉树的深度等于区分关键字所需要的最多二进制位数有些叶子结点指向同一个页块26A0,B0C2C5A1,B1C3000 001 010 011 100 101 110 111 目录表由一组目录项目录表由一组目录项（叶子结点）（叶子结点）和指向页块的和指向页块的指针指针组成。组成。每个目录项与二进制码一一对应。每个目录项与二进制码一一对应。如果区分所有的如果区分所有的页块页块需要需要 k k 位二进制数位二进制数（深度）（深度）,则目录项则目录项个数应为个数应为2 2k

25、k,其编址为其编址为 0 0 到到 2 2k k-1-1。A0,B0C2C3001011A1,B1C501010101目录项目录项项块项块27001011A0,B0C2C3A1,B1001011A0,B0C2C3A1,B1Trie 二叉树二叉树A0,B0C2A1,B1C300 01 10 11 目录项目录项由于区分由于区分4个个页块最多页块最多需要需要 2 位二进制数位二进制数,则目录项个数应为则目录项个数应为4,28Trie 二叉树二叉树A0,B0C2C3001011C501B101A1,C1由于区分由于区分 6 个个页块最多页块最多需要需要 4 位二进制数位二进制数,则目录项个数应为则目录

26、项个数应为 1629C5C30000 0001 0010 0011 0100 0101 0110 01111000 1001 1010 1011 1100 1101 1110 1111 B1C2A0,B0A1,C130A0,B0C2C5A1,B1C3000 001 010 011 100 101 110 111 在目录表上如何根据在目录表上如何根据给定值给定值查找查找页块页块和和记录记录？目录项目录项项块项块A0,B0C2C3001011A1,B1C501 目录表就是一个哈希表！目录表就是一个哈希表！给定值给定值B1B1（101001101001）31C5C3000 001 010 011 1

27、00 101 110 111 A0,B0A1,B1C2 访问一个页块的步骤为：访问一个页块的步骤为：1.1.利用散列函数将给定值散列成随机二进制码；利用散列函数将给定值散列成随机二进制码；2.2.根据区分目录项所需二进制位数，取随机二进制码根据区分目录项所需二进制位数，取随机二进制码 的若干低位，的若干低位，直接直接得到目录项的存储地址；得到目录项的存储地址；3.3.按此地址检索相关的页块按此地址检索相关的页块;4.4.在此页块中查找与给定值相等的记录在此页块中查找与给定值相等的记录（成功或失败）（成功或失败）；B1101 001 001散列散列取低位取低位取指针取指针在目录表上怎样插入和删除

28、记录？在目录表上怎样插入和删除记录？插入后页块指针怎样变化？插入后页块指针怎样变化？是否需要重新构造目录表？是否需要重新构造目录表？32 可扩充散列结构：可扩充散列结构：由一个由一个目录表目录表和一组和一组页块页块构成。构成。定义页块信息：定义页块信息：页块的局部深度页块的局部深度 PgDepthPgDepth指明该页块中存放的记录二指明该页块中存放的记录二进码地址的低位部分有多少位是进码地址的低位部分有多少位是相同相同的；的；C5C3000 001 010 011 100 101 110 111 A0,B0A1,B1 C2PgDepth=23.3.插入与目录扩充插入与目录扩充A0,B0C2C

29、3001011A1,B1C501PgDepth=3PgDepth=2PgDepth=2PgDepth=333 C5C3000 001 010 011 100 101 110 111 A0,B0A1,B1 C2PgDepth=2A0,B0C2C3001011A1,B1C501PgDepth=3PgDepth=2PgDepth=2PgDepth=3定义目录表信息：定义目录表信息：目录表深度目录表深度 DirDepthDirDepth为区分各个页块所需的二进制位数为区分各个页块所需的二进制位数。DirDepth=3DirDepthDirDepth 与与 PgDepth PgDepth 的关系的关系3

30、4关键码插入及页块分裂关键码插入及页块分裂1.1.在向一个页块插入关键码在向一个页块插入关键码 key key 时时,如果该页块如果该页块不满不满,可以直接将关键码插入可以直接将关键码插入;A0,B0C2A1,B1C300 01 10 11 DirDepth=2PgDepth=2 PgDepth=2 PgDepth=2 PgDepth=2C6C7插入插入 C6（110110）和）和 C7（110111）35 如果原来指向它的指针唯一如果原来指向它的指针唯一(PgDepth=DirDepthPgDepth=DirDepth )，则在，则在页块分裂后，必须扩充目录表。页块分裂后，必须扩充目录表。C

31、5C3000 001 010 011 100 101 110 111 A0,B0A1,B1DirDepth=3C2PgDepth=2 PgDepth=3 PgDepth=2 PgDepth=2 PgDepth=300 01 10 11 A0,B0C2A1,B1C3DirDepth=2PgDepth=2 PgDepth=2 PgDepth=2 PgDepth=2插入插入C5(110101),2.2.如果该页块已满如果该页块已满,需要分裂页块需要分裂页块364.4.若原来页块的若原来页块的 PgDepth=dPgDepth=d,分裂后两个分裂后两个兄弟兄弟页页块的二进制地址都增加一位块的二进制地址

32、都增加一位,它们的局部深度它们的局部深度PgDepth=PgDepth=d+1d+1。除了低阶共享的。除了低阶共享的d d位外位外,用用更更高高阶的一位来区分两个兄弟页块。阶的一位来区分两个兄弟页块。1.1.让目录表的深度加让目录表的深度加1 1，目录项增加一倍；目录项增加一倍；3.3.如果目录项的二进制地址有如果目录项的二进制地址有 k k 位位,则整个目录则整个目录 表的深度表的深度DirDepth=DirDepth=k k,目录项个数有目录项个数有 2 2k k 个。个。目录扩充规则目录扩充规则2.2.原来地址为的目录项改为地址为原来地址为的目录项改为地址为0 0，目录项指目录项指向的页

33、块不变，同时新增加一个目录项向的页块不变，同时新增加一个目录项1 1，目目录项的指针与原目录项录项的指针与原目录项0 0的指针相同。的指针相同。37C5C3000 001 010 011 100 101 110 111 A0,B0A1,B1DirDepth=3C2PgDepth=2 PgDepth=3 PgDepth=2 PgDepth=2 PgDepth=3插入插入C4(110 100)C5C3000 001 010 011 100 101 110 111 C4A1,B1DirDepth=3C2PgDepth=3 PgDepth=3 PgDepth=3 PgDepth=2 PgDepth=2

34、 PgDepth=3A0,B0 如果原来指向它的指针不唯一如果原来指向它的指针不唯一(PgDepthDirDepth)，则，则只需要分裂页块，不必扩充目录表。只需要分裂页块，不必扩充目录表。38C5C3000 001 010 011 100 101 110 111 A0,B0A1,B1DirDepth=3C2PgDepth=2 PgDepth=3 PgDepth=2 PgDepth=2 PgDepth=3插入插入C1（100 001）39C5C30000 0001 0010 0011 0100 0101 0110 01111000 1001 1010 1011 1100 1101 1110 1

35、111 B1C2A0,B0A1,C1DirDepth=4PgDepth=2PgDepth=4PgDepth=2PgDepth=2PgDepth=3PgDepth=4401。目录表每次扩大一倍，不需要复制记录。关于扩大目录的说明：关于扩大目录的说明：3。由于插入而引起目录扩大时，散列函数应该不变。这样就能够保证只增加目录表长度，而不影响原来的散列结果。2。虽然关键字的随机二进制散列地址空间很大，但由于从低位开始划分，区分关键字所需要的二进制位数很小，所需要的空间是动态逐步增加 的。4。目录表与链址表的区别：目录表：目录项、指针和页块（桶）组成。目录项个增加，页块大小不变 链址表：哈希表头，指针和

36、单链表组成。哈希表头不变，结点可增加。41 PgDepth=2C5C3000 001 010 011 100 101 110 111 A0,B0A1,B1 C2A0,B0C2C3001011A1,B1C501PgDepth=3PgDepth=2PgDepth=2PgDepth=3DirDepth=34.4.删除与目录收缩删除与目录收缩在执行关键字删除时在执行关键字删除时 :如果被删除关键字所在的页块如果被删除关键字所在的页块没有没有兄弟页块，兄弟页块，则只需要删除页块，不需要进行合并。则只需要删除页块，不需要进行合并。否则，若两个兄弟页块中关键码个数的总和否则，若两个兄弟页块中关键码个数的总和

37、少于或等于少于或等于其其中一个单独页块的容量时中一个单独页块的容量时,应将两个页块合并。应将两个页块合并。如何找某个页块的兄弟页块？如何找某个页块的兄弟页块？42 PgDepth=2C5C3000 001 010 011 100 101 110 111 A0,B0A1,B1 C2A0,B0C2C3001011A1,B1C501PgDepth=3PgDepth=2PgDepth=2PgDepth=3DirDepth=3求目录项求目录项p p所指页块的兄弟页块的方法：所指页块的兄弟页块的方法：如果目录项的深度小于目录表深度，如果目录项的深度小于目录表深度，即：即：PgDepth DicDepthP

38、gDepth DicDepth 则该目录项则该目录项没有没有兄弟页块兄弟页块 否则：若设目录项否则：若设目录项 p p 所指页块的所指页块的 PgDepthPgDepth=d,d,把地址把地址 p p 的第的第 dd 位位求反求反,得到一个新的二进制地址得到一个新的二进制地址 p,p,地址地址为为 pp 的目录项所指页块即为原页块的兄弟的目录项所指页块即为原页块的兄弟页块。页块。43删除删除 C4，00 01 10 11 A0,B0C2 A1,C5C3DirDepth=2PgDepth=2 PgDepth=2 PgDepth=2 PgDepth=2删除删除 C3，00 01 10 11 A0,

39、B0C2 A1,C5DirDepth=2PgDepth=2 PgDepth=2 PgDepth=2 C444 如果目录中指向每一个页块的局部深度都小于目录表的深度如果目录中指向每一个页块的局部深度都小于目录表的深度,即：即：PgDepthPgDepth DicDepth DicDepth 则需要紧缩目录。其过程与目录扩充的过程相反。则需要紧缩目录。其过程与目录扩充的过程相反。页块中关键码减少可能会导致目录表的紧缩。页块中关键码减少可能会导致目录表的紧缩。C5C3000 001 010 011 100 101 110 111 A0,B0A1,B1DirDepth=3C2PgDepth=2 PgD

40、epth=3 PgDepth=2 PgDepth=2 PgDepth=300 01 10 11 A0,B0C2A1,C5C3DirDepth=2PgDepth=2 PgDepth=2 PgDepth=2 PgDepth=2删除删除 B145性能分析性能分析n可扩充散列技术是一种非常好的问题解决方法可扩充散列技术是一种非常好的问题解决方法 :其目录表的地址空间可以扩充和收缩。其目录表的地址空间可以扩充和收缩。n在时间方面在时间方面 :用基于目录表的可扩充散列方法进用基于目录表的可扩充散列方法进行检索行检索,仅需要仅需要 2 2 次磁盘访问。一次转载目录表，次磁盘访问。一次转载目录表，一次转载页块。一次转载页块。n在空间方面在空间方面 :因增加不均匀分布的关键码可能会因增加不均匀分布的关键码可能会导致目录表扩充一倍，许多指针指到同一页块，导致目录表扩充一倍，许多指针指到同一页块，这样会消耗许多存储空间。这样会消耗许多存储空间。n在空间利用率方面评价散列技术的方式仍然用装载在空间利用率方面评价散列技术的方式仍然用装载因子因子来衡量来衡量:表中最大可容纳记录数表中最大可容纳记录数表中已存储的记录数表中已存储的记录数46本讲习题基础知识题（不提交）基础知识题（不提交）：9.21，9.22，9.24