9.4 实现关系运算的算法代价

��在关系代数中，不同的关系运算有：σ、Π、-、∪、∩、x和�≡怂愕鹊取Ｊ迪终庑┰怂愕牟煌�算法是在《数据结构》这门课里要讲的内容，其中还包括算法的复杂性分析。数据库课不讲具体的算法实现！本节的主要内容是以前面介绍的代价模型为基础，根据数据字典中的统计信息来分析实现关系运算的具体算法的磁盘存取代价，即在磁盘和主存储器之间传送的数据块数！
��
9.4.1　选择运算

��在查询处理中，实现选择运算的算法通常是文件扫描。文件扫描是用于定位、检索满足选择条件的记录的搜索算法。在将要介绍的算法中，假定关系保存在单个文件中。用于选择运算的搜索算法有：
��⑴�不用索引的搜索算法--文件扫描
����①�线性搜索算法A1
����②�二分法搜索算法A2
��⑵�使用索引的搜索算法--索引扫描
����①�在建立主索引的码属性上的等值比较算法A3
����②�在建立主索引的非码属性上的等值比较算法A4
����③�其他……