第八章 2索引与散列

《第八章 2索引与散列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8章索引与散列第8章索引与散列10-1什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？【解答】静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型，建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。10-2设有10000个记录对象,通过分块划分为若干子表并建立

2、索引,那么为了提高搜索效率,每一个子表的大小应设计为多大?【解答】每个子表的大小s=énù=é10000ù=100个记录对象。10-3如果一个磁盘页块大小为1024(=1K)字节，存储的每个记录对象需要占用16字节，其中关键码占4字节，其它数据占12字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用于存放线性索引。试问：(1)若将线性索引常驻内存，文件中最多可以存放多少个记录？(每个索引项8字节，其中关键码4字节，地址4字节)(2)如果使用二级索引，第二级索引占用1024字节（有128个

3、索引项），这时文件中最多可以存放多少个记录？【解答】(1)因为一个磁盘页块大小为1024字节，每个记录对象需要占用16字节，则每个页块可存放1024/16=64个记录，除第一个记录存储线性索引外，每个页块可存储63个记录对象。又因为在磁盘文件中所有记录对象按关键码有序存储，所以线性索引可以是稀疏索引，每一个索引项存放一个页块的最大关键码及该页块的地址。若线性索引常驻内存，那么它最多可存放256*(1024/8)=256*128=32768个索引项，文件中可存放32768*63=2064384个记录对象。(2)由于第二级索引占用1024个字节，内存中还剩255K字节

4、用于第一级索引。第一级索引有255*128=32640个索引项，作为稀疏索引，每个索引项索引一个页块，则索引文件中可存放32640*63=2056320。397HelloWorld!82XYZ1038Thisstringisratherlong1037ThisisShorter42ABC2222HellonewWorld!10-4假设在数据库文件中的每一个记录是由占2个字节的整型数关键码和一个变长的数据字段组成。数据字段都是字符串。为了存放右面的那些记录，应如何组织线性索引？【解答】将所有字符串依加入的先后次序存放于一个连续的存储空间store中，这个空间也叫做“

5、堆”，它是存放所有字符串的顺序文件。它有一个指针free，指示在堆store中当前可存放数据的开始地址。初始时free置为0，表示可从文件的0号位置开始存放。线性索引中每个索引项给出记录关键码，字符串在store中的起始地址和字符串的长度：索引表ID堆store14第8章索引与散列关键码串长度串起始地址0HelloWorld!XYZThisstringisratherlongThis4235682312isShorterABCHellonewWorld!free39712010371541103826152222165910-5设有一个职工文件：记录地址职工号姓名

6、性别职业年龄籍贯月工资(元)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)男性职工

7、；(2)月工资超过800元的职工；(3)月工资超过平均工资的职工；(4)职业为实验员和行政秘书的男性职工；(5)男性教师或者年龄超过25岁且职业为实验员和教师的女性职工。【解答】主索引月工资倒排索引职务倒排索引职工号记录地址月工资长度指针职务长度指针003410032480.3073教师6034106410068123064207310104175081308110140720.3034092409210176092140512310212209209614010248780.1140实验员20737175102841200.1064175820910320140

8、0.108