209 第1 0 章 索引与散列 一、复习要点 索引结构和散列结构是用于外部搜索的搜索结构。数据在外存的组织即文件结构，主要分顺序、直接存取（散列）和索引文件。在这些文件组织中使用的主要是索引和散列方法。 1、基本知识点 要求掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。掌握动态索引结构，包括 B 树的搜索、插入、删除，通过关键码个数估算 B 树的高度的方法；B+树的搜索、插入与删除。掌握散列法，包括散列函数的构造、处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析。 二、难点与重点 1、线性索引 密集索引、稀疏索引、索引表计算 基于属性查找建立倒排索引、单元式倒排表 2、动态搜索树 平衡的m 路搜索树的定义、搜索算法 B 树的定义、B 树与平衡的m 路搜索树的关系 B 树的插入(包括结点分裂)、删除(包括结点调整与合并)方法 B 树中结点个数与高度的关系 B+树的定义、搜索、插入与删除的方法 3、散列表 散列函数的比较 装载因子 与平均搜索长度的关系，平均搜索长度的关系 表长 m、表中已有数据对象个数n和装载因子的关系 解决冲突的(闭散列)线性探查法的运用，平均探查次数的计算 线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态 线性探查法中的堆积聚集问题 解决冲突的(闭散列)双散列法的运用，平均探查次数计算 双散列法中再散列函数的设计要求与表长 m 互质，为此 m 设计为质数较宜 解决冲突的(闭散列)二次散列法的运用，平均探查次数计算 注意：二次散列法中装载因子与表长 m 的设置 解决冲突的(开散列)开散列法的运用，平均探查次数计算 由平均探查次数计算装载因子，再计算表大小的方法 三、教材中习题的解析 10-1 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？ 【解答】 静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间， 210 树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型，建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂...
