根据查询要求从一个
计算机文件或数据库中提取所需要的数据的技术,这是
数据处理的基本技术之一。如果要查找的数据全部放在计算机
内存储器中,这种查找即称为内查找;若要查找的数据不在内存而在
外存储器中,这种查找便称为外查找。数据一般按照
数据项、记录、文件三级组织在一定的结构之中。用于组织文件的基本
数据项称为关键字。所谓从文件中查找数据是指根据给定的关键字值在文件中找出包含该关键字值的记录。对于不同的文件结构和查询要求,需要用不同的查找技术。
此法要求被查找的文件中记录是按
关键字值大小顺序排列的。将文件一分为二,把给定关键字值与中点的记录比较,若匹配,则查找成功;否则判断所要查找的记录可能在上半部分,还是在下半部分。然后,对确定的部分继续上述过程,直至找到要求的记录,查找成功;或最后只剩下一个记录仍不能匹配,查找失败。若文件中记录数为N,则查到一个记录的最多比较次数为log2N。
对于随机文件,如果是计算寻址结构的文件可以采用直接查找的方法,即利用关键字值和记录位置之间的对应关系直接找到该记录。如果是索引结构的文件,先用上述方法查找索引,在索引中找到相应关键字值后,再由索引表上对应的地址找到相应的记录。不同查找方法的效率很不相同,这主要取决于文件结构和查询问题的特点,查询算法本身也是重要影响因素。