没有合适的资源?快使用搜索试试~ 我知道了~
索引与散列
资源推荐
资源详情
资源评论
第 10 章 索引与散列
第 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 中的起始地址和字符串的长度:
397 Hello World!
82 XYZ
1038 This string is rather long
1037 This is Shorter
42 ABC
2222 Hello new World!
1
第 10 章 索引与散列
索引表 ID 堆 store
关键码 串长度 串起始地址
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
2
free
第 10 章 索引与散列
123 175
女
4 064 29 1 034
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 后:
3
80 90
45
60 7025 35 50 85 95
55
剩余14页未读,继续阅读
资源评论
lhh5356
- 粉丝: 0
- 资源: 40
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功