第八章2索引与散列

第8章索引与散列1第8章索引与散列10-1什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？【解答】静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型，建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。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中的起始地址和字符串的长度：索引表ID堆store397HelloWorld!82XYZ1038Thisstringisratherlong1037ThisisShorter42ABC2222HellonewWorld!第8章索引与散列2关键码串长度串起始地址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行政秘书1123性别倒排索引年龄倒排索引性别长度指针年龄长度指针男5034241209073261073081271140092282092123175女4064291034free第8章索引与散列3140321064175331123209361081搜索结果：(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树的变化。【解答】插入65后：80904560702535508595555580第8章索引与散列4插入15后：插入40后：插入30后：10-9下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。【解答】删除50后：删除40后：452535508595607065905085955580607065901535254550859555806070659015254535404535805530406590255085956070156080305520407095508030204060709555第8章索引与散列510-10对于一棵有1999999个关键码的199阶B树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。【解答】设B树的阶数m=199，则m/2=100。若不包括失败结点层，则其最大层数为logm/2((N+1)/2)+1=log1001000000+1=4若使得每一层关键码数达到最大，可使其层数达到最小。第0层最多有(m-1)个关键码，第1层最多有(m-1)2个关键码，，第h-1层最多有(m-1)h个关键码。层数为h的B树最多有(m-1)+(m-1)2+…+(m-1)h-1=(m-1)((m-1)h–1)/(m-2)个关键码。反之，若有n个关键码，n≤(m-1)((m-1)h–1)/(m-2)，则h≥log(m-1)(n(m-2)/(m-1)+1)，所以，有1999999个关键码的199阶B树的最小层数为log(m-1)(n*(m-2)/(m-1)+1)=log198(1999999*197/198+1)=log198198989910-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插入U插入R插入K55802030607095CDSCDSTSACDSTSACDSSTDMACDSSTDMPACDMSDISTMPABCDMSDGISTWMNPABCDMSUDGISTMNPUWABCDMDGIPRMNSTUWSUPP第8章索引与散列6插入E插入H插入O,L插入J10-12设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存储15个记录。对于1,2,3,4,5层的B+树，最多能存储多少记录，最少能存储多少记录。【解答】一层B+树：根据B+树定义，一层B+树的结点只有一个，它既是根结点又是叶结点，最多可存储m1=15个记录，最少可存储m1/2=8个记录。二层B+树：第0层是根结点，它最多有m=100棵子树，最少有2个结点；第1层是叶结点，它最多有m个结点，最多可存储m*m1=100*15=1500个记录，最少有2个结点，最少可存储2*m1/2=16个记录。三层B+树：第2层是叶结点。它最多有m2个结点，最多可存储m2*m1=150000个记录。最少有2*m/2=100个结点，最少可存储2*m/2*m1/2=800个记录。四层B+树：第3层是叶结点。它最多有m3个结点，可存储m3*m1=15000000个记录。最少有2*m/22=2*502=5000个结点，存储2*m/22*m1/2=40000个记录。五层B+树：第4层是叶结点。它最多有m4个结点，可存储m4*m1=1500000000个记ABCDIMDGMNSUUWPRSTIKABCDIMDEGMNSUPUWPRSTIKABCDGIMDEMNSUPGHPRSTIKUWDEMNOSUPGHPRSTIKLUWABCDGIMDEMNOSUIPGHPRSTIJKLABCDGUWKM第8章索引与散列7录。最少有2*m/23=2*503=250000个结点，存储2*m/23*m1/2=2000000个记录。10-13设散列表为HT[13],散列函数为H(key)=key%13。用闭散列法解决冲突,对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。(1)采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。(2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7*key)%10+1,寻找下一个空位的公式为Hi=(Hi-1+RH(key))%13,H1=H(key)。画出相应的散列表,并计算等