第10章索引与散列 第10章索引与散列 10-1什么是静态索引结构?什么是动态索引结构?它们各有哪些优缺点? 【解答】 静态索引结构指这种索引结构在初始创建,数据装入时就已经定型,而且在整个系统运 行期间,树的结构不发生变化,只是数据在更新。动态索引结构是指在整个系统运行期间 树的结构随数据的增删及时调整,以保持最佳的搜索效率。静态索引结构的优点是结构定型, 建立方法简单,存取方便:缺点是不利于更新,插入或删除时效率低。动态索引结构的优点 是在插入或删除时能够自动调整索引树结构,以保持最佳的搜索效率:缺点是实现算法复杂 10-2设有10000个记录对象,通过分块划分为若干子表并建立索引,那么为了提高搜索效 率,每一个子表的大小应设计为多大? 【解答】 每个子表的大小s=「n1=「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个字节 Hello world 的整型数关键码和一个变长的数据字段组成。数据字段都 是字符串。为了存放右面的那些记录,应如何组织线性索 1038 This string is rather lon 【解答】 37 This is Shorter 将所有字符串依加入的先后次序存放于一个连续的 存储空间 store中,这个空间也叫做“堆”,它是存放所有 字符串的顺序文件。它有一个指针free,指示在堆 store中当前可存放数据的开始地址。初 始时free置为0,表示可从文件的0号位置开始存放。线性索引中每个索引项给出记录关键 码,字符串在 store中的起始地址和字符串的长度: 索引表ID
第 10 章 索引与散列 1 第 10 章 索引与散列 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 堆 store 397 Hello World! 82 XYZ 1038 This string is rather long 1037 This is Shorter 42 ABC 2222 Hello new World!
第10章索引与散列 关键码串长度|串起始地 Hello World! XYZ This string is rather long This is Shorter a BC Hello new World 397 1037 59 10-5设有一个职工文件 记录地址职工 刘激扬 10068 蔡晓莉 1200.00 10104 实验员 480.00 10140 1400.00 行政秘书 南燕 实验员 1032020 袁秋慧 0.00 其中,关键码为职工号。试根据此文件,对下列查询组织主索引和倒排索引,再写出搜 索结果关键码。(1)男性职工:(2)月工资超过800元的职工;(3)月工资超过平均工资的职 工;(4)职业为实验员和行政秘书的男性职工;(5)男性教师或者年龄超过25岁且职业为实 验员和教师的女性职工 【解答】 主索引 月工资倒排索引 职务倒排索引 123 10104 10140 10176 12310212 10248 780 实验员 175 200 0320[14001 os-[政秘书 性别倒排索引 年龄倒排索引 年龄长 指针 123 175 女 064 034
第 10 章 索引与散列 2 关键码 串长度 串起始地址 0 Hello World! XYZ This string is rather long This 42 3 56 82 3 12 is Shorter ABC Hello new World! 397 12 0 1037 15 41 1038 26 15 2222 16 59 10-5 设有一个职工文件： 记录地址 职工号 姓 名 性别 职 业 年龄 籍贯 月工资(元) 10032 034 刘激扬 男 教 师 29 山东 720.00 10068 064 蔡晓莉 女 教 师 32 辽宁 1200.00 10104 073 朱 力 男 实验员 26 广东 480.00 10140 081 洪 伟 男 教 师 36 北京 1400.00 10176 092 卢声凯 男 教 师 28 湖北 720.00 10212 123 林德康 男 行政秘书 33 江西 480.00 10248 140 熊南燕 女 教 师 27 上海 780.00 10284 175 吕 颖 女 实验员 28 江苏 480.00 10320 209 袁秋慧 女 教 师 24 广东 720.00 其中，关键码为职工号。试根据此文件，对下列查询组织主索引和倒排索引，再写出搜 索结果关键码。(1) 男性职工；(2) 月工资超过 800 元的职工；(3) 月工资超过平均工资的职 工；(4) 职业为实验员和行政秘书的男性职工；(5) 男性教师或者年龄超过 25 岁且职业为实 验员和教师的女性职工。 【解答】 主索引 月工资 倒排索引 职务 倒排索引 职工号 记录地址 月工资 长度 指针 职务 长度 指针 0 034 10032 480. 3 073 教师 6 034 1 064 10068 123 064 2 073 10104 175 081 3 081 10140 720. 3 034 092 4 092 10176 092 140 5 123 10212 209 209 6 140 10248 780. 1 140 实验员 2 073 7 175 10284 1200. 1 064 175 8 209 10320 1400. 1 081 行政秘书 1 123 性别 倒排索引 年龄 倒排索引 性别 长度 指针 年龄 长度 指针 男 5 034 24 1 209 073 26 1 073 081 27 1 140 092 28 2 092 123 175 女 4 064 29 1 034 free
第10章索引与散列 搜索结果 (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, 081092,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树的变化 8019 6070 【解答】 插入65后 5580
第 10 章 索引与散列 3 140 32 1 064 175 33 1 123 209 36 1 081 搜索结果： (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-7 m = 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 后： 45 80 90 25 35 50 60 70 85 95 55 55 80
第10章索引与散列 253 插入15后 插入40后 5、80 25145 651 插入30后 55 65 90 10-9下图是一个3阶B树。试分别画出在删除50、40之后B树的变化 50 70 【解答】 删除50后 80 删除
第 10 章 索引与散列 4 插入 15 后： 插入 40 后： 插入 30 后： 10-9 下图是一个 3 阶 B 树。试分别画出在删除 50、40 之后 B 树的变化。 【解答】 删除 50 后： 删除 40 后： 45 25 35 50 60 70 85 95 65 90 50 85 95 55 80 60 70 65 90 15 35 25 45 50 85 95 55 80 60 70 65 90 15 25 45 35 40 45 35 80 55 30 40 25 65 90 15 50 60 70 85 95 30 60 80 20 40 55 70 95 50 30 80 20 40 60 70 95 55
第10章索引与散列 10-10对于一棵有199999个关键码的199阶B树,试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点) 【解答】 设B树的阶数m=199,则m/21=100。若不包括失败结点层,则其最大层数为 Llogrm/(N+1)2)+1=lg0010000001=4 若使得每一层关键码数达到最大,可使其层数达到最小。第0层最多有(m-1)个关键码,第 1层最多有(m-1)2个关键码,…,第h1层最多有(m-1)个关键码。层数为h的B树最多有 (m-1)+(m-1)2+…+(m-1)1=(m-1)(m-1)-1)/(m-2)个关键码。反之,若有n个关键 码,n≤(m-1)((m-1)-1)/(m-2),则h≥logm-)(n(m-2)/(m-1)+1),所以,有199999 个关键码的199阶B树的最小层数为 「 log (m-1)(n(m-2)(m-1)+1)1=「log198(199197/198+1)=Iog19819898991 10-11给定一组记录,其关键码为字符。记录的插入顺序为{C,S,D,T,AMP,L,B,W,N,G, U,R,K,E,HO,LJ},给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录 【解答】 插入C,S,D插入T 插入A 插入M CDS ST A C 插入P 插入I DMS DMP ST A C I AP ST 插入B,W,N,G 插入U IDMS ABCIDGIMNPI IST ABCIDGI ANPIST UW 插入R PR 插入K
第 10 章 索引与散列 5 10-10 对于一棵有 1999999 个关键码的 199 阶 B 树，试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点)。 【解答】 设 B 树的阶数 m = 199，则m/2 = 100。若不包括失败结点层，则其最大层数为 logm/2 ((N+1)/2) + 1 = log100 1000000 +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) = log 198 1989899 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 插入 K 55 80 20 30 60 70 95 C D S C D S T S A C D S T S A C D S D M S T A C D S D M P S T A C D M S D I M P S T A B C D M S D G I M N P S T W A B C D M S U D G I M N P S T U W A B C D M D G I M N P R S T U W S U P P