《【2017年整理】数据结构第10章-索引与散列》由会员分享，可在线阅读，更多相关《【2017年整理】数据结构第10章-索引与散列（20页珍藏版）》请在金锄头文库上搜索。
1、209第 10 章 索引与散列一、复 习要点索引结构和散列结构是用于外部搜索的搜索结构。数据在外存的组织即文件结构，主要分顺序、直接存取（散列）和索引文件。在这些文件组织中使用的主要是索引和散列方法。1、基本知识点要求掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。掌握动态索引结构，包括 B 树的搜索、插入、删除，通过关键码个数估算 B 树的高度的方法；B+ 树的搜索、插入与删除。掌握散列法，包括散列函数的构造、处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析。二、 难点与重点1、线性索引 密集索引、稀疏索引、索引表计算 基于属性查找建立倒排索引、单元式倒排表2、动
2、态搜索树 平衡的 m 路搜索树的定义、搜索算法 B 树的定义、B 树与平衡的 m 路搜索树的关系 B 树的插入(包括结点分裂)、删除( 包括结点调整与合并 )方法 B 树中结点个数与高度的关系 B+树的定义、搜索、插入与删除的方法3、散列表 散列函数的比较 装载因子 与平均搜索长度的关系，平均搜索长度的关系 表长 m、表中已有数据对象个数 n 和装载因子的关系 解决冲突的(闭散列)线性探查法的运用，平均探查次数的计算 线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态 线性探查法中的堆积聚集问题 解决冲突的(闭散列)双散列法的运用，平均探查次数计算 双散列法中再散列函数的设计要求与
3、表长 m 互质，为此 m 设计为质数较宜 解决冲突的(闭散列)二次散列法的运用，平均探查次数计算 注意：二次散列法中装载因子与表长 m 的设置 解决冲突的(开散列)开散列法的运用，平均探查次数计算 由平均探查次数计算装载因子，再计算表大小的方法三、教材中习题的解析10-1 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？【解答】静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统210运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型，建立方法简单，
4、存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。10-2 设有 10000 个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高搜索效率, 每一个子表的大小应设计为多大? 【解答】每个子表的大小 s = n = 10000 = 100 个记录对象。10-3 如果一个磁盘页块大小为 1024 (=1K) 字节，存储的每个记录对象需要占用 16 字节，其中关键码占 4 字节，其它数据占 12 字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第 1 个记录用于存放线性索引。另外在
5、内存中开辟了 256K 字节的空间可用于存放线性索引。试问：(1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？( 每个索引项 8 字节，其中关键码 4 字节，地址 4 字节)(2) 如果使用二级索引，第二级索引占用 1024 字节（有 128 个索引项） ，这时文件中最多可以存放多少个记录？【解答】(1) 因为一个磁盘页块大小为 1024 字节，每个记录对象需要占用 16 字节，则每个页块可存放 1024 / 16 = 64 个记录，除第一个记录存储线性索引外，每个页块可存储 63 个记录对象。又因为在磁盘文件中所有记录对象按关键码有序存储，所以线性索引可以是稀疏索引，每一个索引项存
6、放一个页块的最大关键码及该页块的地址。若线性索引常驻内存，那么它最多可存放 256 * (1024 / 8 ) = 256 * 128 = 32768 个索引项，文件中可存放 32768 * 63 = 2064384 个记录对象。(2) 由于第二级索引占用 1024 个字节，内存中还剩 255K 字节用于第一级索引。第一级索引有 255 * 128 = 32640 个索引项，作为稀疏索引，每个索引项索引一个页块，则索引文件中可存放 32640 * 63 = 2056320。 10-4 假设在数据库文件中的每一个记录是由占 2 个字节的整型数关键码和一个变长的数据字段组成。数据字段都是字符串。为
7、了存放右面的那些记录，应如何组织线性索引？【解答】将所有字符串依加入的先后次序存放于一个连续的存储空间 store 中，这个空间也叫做“堆” ，它是存放所有字符串的顺序文件。它有一个指针 free，指示在堆 store 中当前可存放数据的开始地址。初始时 free 置为 0，表示可从文件的 0 号位置开始存放。线性索引中每个索引项给出记录关键码，字符串在 store 中的起始地址和字符串的长度：397 Hello World!82 XYZ1038 This string is rather long1037 This is Shorter 42 ABC2222 Hello new World!
8、211索引表 ID 堆 store 关键码 串长度 串起始地址 0 Hello World! XYZ This string is rather long This 42 3 5682 3 12 is Shorter ABC Hello new World!397 12 01037 15 411038 26 152222 16 5910-5 设有一个职工文件： 记录地址 职工号 姓 名 性别 职 业 年龄 籍贯 月工资(元)10032 034 刘激扬 男 教 师 29 山东 720.0010068 064 蔡晓莉 女 教 师 32 辽宁 1200.0010104 073 朱 力 男 实验员 2
9、6 广东 480.0010140 081 洪 伟 男 教 师 36 北京 1400.0010176 092 卢声凯 男 教 师 28 湖北 720.0010212 123 林德康 男 行政秘书 33 江西 480.0010248 140 熊南燕 女 教 师 27 上海 780.0010284 175 吕 颖 女 实验员 28 江苏 480.0010320 209 袁秋慧 女 教 师 24 广东 720.00其中，关键码为职工号。试根据此文件，对下列查询组织主索引和倒排索引，再写出搜索结果关键码。(1) 男性职工；(2) 月工资超过 800 元的职工；(3) 月工资超过平均工资的职工；(4) 职
10、业为实验员和行政秘书的男性职工；(5) 男性教师或者年龄超过 25 岁且职业为实验员和教师的女性职工。【解答】主索引 月工资 倒排索引 职务 倒排索引 职工号 记录地址 月工资 长度 指针 职务 长度 指针0 034 10032 480. 3 073 教师 6 0341 064 10068 123 0642 073 10104 175 0813 081 10140 720. 3 034 0924 092 10176 092 1405 123 10212 209 2096 140 10248 780. 1 140 实验员 2 0737 175 10284 1200. 1 064 1758 209
11、 10320 1400. 1 081 行政秘书 1 123free212性别 倒排索引 年龄 倒排索引性别 长度 指针 年龄 长度 指针男 5 034 24 1 209073 26 1 073081 27 1 140092 28 2 092123 175女 4 064 29 1 034140 32 1 064175 33 1 123209 36 1 081搜索结果： (1) 男性职工 (搜索性别倒排索引 )：034, 073, 081, 092, 123(2) 月工资超过 800 元的职工 (搜索月工资倒排索引)：064, 081(3) 月工资超过平均工资的职工( 搜索月工资倒排索引) 月平均
12、工资 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,
13、209 & 034, 064, 073, 081,092, 123, 140, 175 = 064, 140, 17510-6 倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较这两种方式的优缺点。 【解答】在倒排索引中的记录地址用记录的实际存放地址，搜索的速度快；但以后在文件中插入或删除记录对象时需要移动文件中的记录对象，从而改变记录的实际存放地址，这将对所有的索引产生影响：修改所有倒排索引的指针，不但工作量大而且容易引入新的错误或遗漏，使得系统不易维护。记录地址采用记录的关键码，缺点是寻找实际记录对象需要再经过主索引，降低了搜索速度；但以后在文件中插入或删除记录对象
14、时，如果移动文件中的记录对象，导致许多记录对象的实际存放地址发生变化，只需改变主索引中的相应记录地址，其他倒排索引中的指针一律不变，使得系统容易维护，且不易产生新的错误和遗漏。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 下
15、图是一个 3 阶 B 树。试分别画出在插入 65、15、40、30 之后 B 树的变化。213【解答】插入 65 后：插入 15 后：插入 40 后：插入 30 后：10-9 下图是一个 3 阶 B 树。试分别画出在删除 50、40 之后 B 树的变化。80 904560 7025 35 50 85 95554525 35 50 85 9555 80 60 7065 9050 85 9555 80 60 7065 9015 3525 4550 85 9555 80 60 7065 901525 4535 404535 8055 30 4065 902550 85 9560 701560 80305520 40 70 9550214【解答】删除 50 后： 删除 40 后：10-10 对于一棵有 1999999 个关键码的 199 阶 B 树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点 )。【解答】设 B
