第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!