1. 查找章节引言(Chapter Introduction: Search)¶
组织与检索信息是大多数计算机 应用的核心,而查找无疑是所有 计算任务中最频繁执行的。 查找可以抽象地看作一个过程,用于确定 具有特定值的元素是否是特定集合的成员。 更常见的查找视角是尝试在 记录集合中找到具有 特定键值的记录,或者找出集合中键 值满足某一标准(例如落在某个 数值范围内)的那些记录。
我们可以如下正式定义查找。 假设我们有一个集合 L,包含 \(n\) 条记录,形式为
其中 \(I_j\) 是与键 \(k_j\) 相关联的信息, 来自第 \(j\) 条记录,\(1 \leq j \leq n\)。 给定特定的键值 \(K\), 查找问题 是定位 L 中满足 \(k_j = K\) 的一条记录 \((k_j, I_j)\) (如果存在的话)。 查找 是一种系统的方法,用于 定位键值为 \(k_j = K\) 的记录。
成功查找 是找到键为 \(k_j = K\) 的记录的查找。 不成功查找 是 根本没有找到键为 \(k_j = K\) 的记录(且不存在这样的记录)。
精确匹配查询 是查找键值 与指定键值匹配的记录。 范围查询 是搜索所有键值 落在指定键值范围内的记录。
我们可以把查找算法归为三种通用的 方法:
顺序与链表方法。
按键值直接访问(散列)。
树索引方法。
这些方法中的任何一种都可能适合实现 字典 ADT。 然而,每种方法都有不同的性能特征,这使得它 在特定情况下成为首选方法。
本章考虑查找存储在 链表中的数据的各种方法。 这里的链表指任何链表实现,包括 链表或数组。 这些方法大多适用于序列 (即允许重复键值),尽管也有一些特殊 技术适用于 集合。 本章前三节的技术最 适合查找存储在 RAM 中的记录集合。 第 Hashing 章介绍散列,这是一种在 数组中组织数据的技术,使得数组中每条记录的位置 是其键值的函数。 散列适用于记录存储在 RAM 或 磁盘上的情况。
第 Indexing 章讨论在磁盘上组织 信息的基于树的方法,包括一种常用的文件结构, 称为 B 树。 几乎所有必须组织存储在磁盘上的大型记录集合的 程序,都使用散列或 B 树的某种变体。 散列只对某些访问应用( 精确匹配查询)实用,并且通常只适用于不允许重复 键值的情况。 对于任何散列不合适的动态磁盘存储应用, B 树是首选方法。
