第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树的变化 45 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