索引与散列1
需积分: 0 193 浏览量
2022-08-03
13:23:12
上传
评论
收藏 416KB PDF 举报
第 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!
剩余13页未读，继续阅读
评论0