数据结构第10章-索引与散列

209第10章索引与散列一、复习要点索引结构和散列结构是用于外部搜索的搜索结构。数据在外存的组织即文件结构，主要分顺序、直接存取（散列）和索引文件。在这些文件组织中使用的主要是索引和散列方法。1、基本知识点要求掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。掌握动态索引结构，包括B树的搜索、插入、删除，通过关键码个数估算B树的高度的方法；B+树的搜索、插入与删除。掌握散列法，包括散列函数的构造、处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析。二、难点与重点1、线性索引密集索引、稀疏索引、索引表计算基于属性查找建立倒排索引、单元式倒排表2、动态搜索树平衡的m路搜索树的定义、搜索算法B树的定义、B树与平衡的m路搜索树的关系B树的插入(包括结点分裂)、删除(包括结点调整与合并)方法B树中结点个数与高度的关系B+树的定义、搜索、插入与删除的方法3、散列表散列函数的比较装载因子与平均搜索长度的关系，平均搜索长度的关系表长m、表中已有数据对象个数n和装载因子的关系解决冲突的(闭散列)线性探查法的运用，平均探查次数的计算线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态线性探查法中的堆积聚集问题解决冲突的(闭散列)双散列法的运用，平均探查次数计算双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜解决冲突的(闭散列)二次散列法的运用，平均探查次数计算注意：二次散列法中装载因子与表长m的设置解决冲突的(开散列)开散列法的运用，平均探查次数计算由平均探查次数计算装载因子，再计算表大小的方法三、教材中习题的解析10-1什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？【解答】静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，210树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型，建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。10-2设有10000个记录对象,通过分块划分为若干子表并建立索引,那么为了提高搜索效率,每一个子表的大小应设计为多大?【解答】每个子表的大小s=n=10000=100个记录对象。10-3如果一个磁盘页块大小为1024(=1K)字节，存储的每个记录对象需要占用16字节，其中关键码占4字节，其它数据占12字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用于存放线性索引。试问：(1)若将线性索引常驻内存，文件中最多可以存放多少个记录？(每个索引项8字节，其中关键码4字节，地址4字节)(2)如果使用二级索引，第二级索引占用1024字节（有128个索引项），这时文件中最多可以存放多少个记录？【解答】(1)因为一个磁盘页块大小为1024字节，每个记录对象需要占用16字节，则每个页块可存放1024/16=64个记录，除第一个记录存储线性索引外，每个页块可存储63个记录对象。又因为在磁盘文件中所有记录对象按关键码有序存储，所以线性索引可以是稀疏索引，每一个索引项存放一个页块的最大关键码及该页块的地址。若线性索引常驻内存，那么它最多可存放256*(1024/8)=256*128=32768个索引项，文件中可存放32768*63=2064384个记录对象。(2)由于第二级索引占用1024个字节，内存中还剩255K字节用于第一级索引。第一级索引有255*128=32640个索引项，作为稀疏索引，每个索引项索引一个页块，则索引文件中可存放32640*63=2056320。10-4假设在数据库文件中的每一个记录是由占2个字节的整型数关键码和一个变长的数据字段组成。数据字段都是字符串。为了存放右面的那些记录，应如何组织线性索引？【解答】将所有字符串依加入的先后次序存放于一个连续的存储空间store中，这个空间也叫做“堆”，它是存放所有字符串的顺序文件。它有一个指针free，指示在堆store中当前可存放数据的开始地址。初始时free置为0，表示可从文件的0号位置开始存放。线性索引中每个索引项给出记录关键码，字符串在store中的起始地址和字符串的长度：397HelloWorld!82XYZ1038Thisstringisratherlong1037ThisisShorter42ABC2222HellonewWorld!211索引表ID堆store关键码串长度串起始地址0HelloWorld!XYZThisstringisratherlongThis4235682312isShorterABCHellonewWorld!39712010371541103826152222165910-5设有一个职工文件：记录地址职工号姓名性别职业年龄籍贯月工资(元)10032034刘激扬男教师29山东720.0010068064蔡晓莉女教师32辽宁1200.0010104073朱力男实验员26广东480.0010140081洪伟男教师36北京1400.0010176092卢声凯男教师28湖北720.0010212123林德康男行政秘书33江西480.0010248140熊南燕女教师27上海780.0010284175吕颖女实验员28江苏480.0010320209袁秋慧女教师24广东720.00其中，关键码为职工号。试根据此文件，对下列查询组织主索引和倒排索引，再写出搜索结果关键码。(1)男性职工；(2)月工资超过800元的职工；(3)月工资超过平均工资的职工；(4)职业为实验员和行政秘书的男性职工；(5)男性教师或者年龄超过25岁且职业为实验员和教师的女性职工。【解答】主索引月工资倒排索引职务倒排索引职工号记录地址月工资长度指针职务长度指针003410032480.3073教师6034106410068123064207310104175081308110140720.3034092409210176092140512310212209209614010248780.1140实验员20737175102841200.10641758209103201400.1081行政秘书1123free212性别倒排索引年龄倒排索引性别长度指针年龄长度指针男5034241209073261073081271140092282092123175女4064291034140321064175331123209361081搜索结果：(1)男性职工(搜索性别倒排索引)：{034,073,081,092,123}(2)月工资超过800元的职工(搜索月工资倒排索引)：{064,081}(3)月工资超过平均工资的职工(搜索月工资倒排索引){月平均工资776元}：{064,081,140}(4)职业为实验员和行政秘书的男性职工(搜索职务和性别倒排索引)：{073,123,175}&&{034,073,081,092,123}={073,123}(5)男性教师(搜索性别与职务倒排索引)：{034,073,081,092,123}&&{034,064,081,092,140,209}={034,081,092}年龄超过25岁且职业为实验员和教师的女性职工(搜索性别、职务和年龄倒排索引)：{064,140,175,209}&&{034,064,073,081,092,140,175,209}&&{034,064,073,081,092,123,140,175}={064,140,175}10-6倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较这两种方式的优缺点。【解答】在倒排索引中的记录地址用记录的实际存放地址，搜索的速度快；但以后在文件中插入或删除记录对象时需要移动文件中的记录对象，从而改变记录的实际存放地址，这将对所有的索引产生影响：修改所有倒排索引的指针，不但工作量大而且容易引入新的错误或遗漏，使得系统不易维护。记录地址采用记录的关键码，缺点是寻找实际记录对象需要再经过主索引，降低了搜索速度；但以后在文件中插入或删除记录对象时，如果移动文件中的记录对象，导致许多记录对象的实际存放地址发生变化，只需改变主索引中的相应记录地址，其他倒排索引中的指针一律不变，使得系统容易维护，且不易产生新的错误和遗漏。10-7m=2的平衡m路搜索树是AVL树，m=3的平衡m路搜索树是2-3树。它们的叶结点必须在同一层吗？m阶B树是平衡m路搜索树，反过来，平衡m路搜索树一定是B树吗？为什么？【解答】m=3的平衡m路搜索树的叶结点不一定在同一层，而m阶B_树的叶结点必须在同一层，所以m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树不一定是B_树。10-8下图是一个3阶B树。试分别画出在插入65、15、40、30之后B树的变化。213【解答】插入65后：插入15后：插入40后：插入30后：10-9下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。8090456070253550859555452535508595558060706590508595558060706590153525455085955580607065901525453540453580553040659025508595607015608030552040709550214【解答】删除50后：删除40后：10-10对于一棵有1999999个关键码的199阶B树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。【解答】设B树的阶数m=199，则m/2=100。若不包括失败结点层，则其最大层数为logm/2((N+1)/2)=log1001000000=3若使得每一层关键码数达到最大，可使其层数达到最小。第0层最多有(m-1)个关键码，第1层最多有m(m-1)个关键码，第2层最多有m2(m-1)个关键码，，第h-1层最多有mh-1(m-1)个关键码。层数为h的B树最多有(m-1)+m(m-1)+m2(m-1)+…+mh-1(m-1)=(m-1)(mh–1)/(m-1)=mh–1个关键码。反之，若有n个关键码，n≤mh–1，则h≥logm(n+1)，所以，有1999999个关键码的199阶B树的最小层数为logm(n+1)=log199(1999999+1)=log1992000000=310-11给定一组记录，其关键码为字符。记录的插入顺序为{C,S,D,T,A,M,P,I,B,W,N,G,U,R,K,E,H,O,L,J}，给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录。【解答】插入C,S,D插入T插入A插入M插入P插入I插入B,W,N,G插入U803020406070955555802030607095CDSCDSTSACDSTSACDSSTDMACDSSTDMPACDMSDISTMPABCDMSDGISTWMNPABCDMSUDGISTMNPUW215插入R插入K插入E插入H插入O,L插入J10-12设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存储15个记录。对于1,2,3,4,5层的B+树，最多能存储多少记录，最少能存储多少记录。【解答】ABCDMDGIPRMNSTUWSUPABCDIMDGMNSUPUWPRSTIKABCDIMDEGMNSUPUWPRSTIKABCDGIMDEMNSUPGHPRSTIKUWDEMNOSUPGHPRSTIKLUWABCDGIMDEMNOSUIPGHPRSTIJKLABCDGUWKM216一层B+树：根据B+树定义，一层B+树的结点只有一个，它既是根结点又是叶结点，最多可存储m1=15个记录，最少可存储m1/2=8个记录。二层B+树：第0层是根结点