【概述】

查找最理想情况是：不经过任何比较，直接得出待查记录的存储位置

这就需要在记录的存储位置与其关键码之间建立一个确定的对应关系 $H$，使得每个关键码 $key$ 与唯一的存储位置 $H(key)$ 相对应

【概述】

倒排表是对次关键码的一种索引表，其索引项包括以下两个结构：

• 次关键码：要记录的表项
• 记录号表：存储具有相同次关键字的所有记录的记录号，并且有序排列

【概述】

黄金分割又称黄金比例，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 $1:0.618$ 或 $1.618:1$，黄金比例不仅在绘画、艺术上有着重要的审美价值，在工程上也具有极大的作用

在二分查找中，每次查找都是将查找表一分为二，无论数据是偏大还是偏小，很多时候都未必是最合适的做法

【概述】

以查字典为例，在英文字典中查 “apple” 时，下意识的会翻开前面的书页，当查 “zoo” 时，下意识的翻开一定是后面的书页，显然，此时还绝对不是从中间开始查起，而且有一定目的地从前或从后查找

同样的，以取值范围在 $1$ 到 $10000$ 间的从小到大均匀分布在数组中的 $100$ 个元素为例，若要查找元素 $5$，那么自然而然的会考虑从数组下标较小的开始查找

【概述】

分块索引，又称索引顺序查找，其吸取了顺序查找和二分查找的优点，属于线性索引结构，既适用于静态索引，又适用于动态索引

其基本思想是将查找表分为若干子块，这些子块之间满足分块有序这个要求，即这些块满足以下两个条件：

【概述】

稠密索引常见于静态索引中，在线性索引里，若文件中的每个记录对应一个索引项，则这种索引称为稠密索引

在稠密索引中，无论文件是否按关键码有序，索引项总是按关键码有序进行排列

【概述】

在进行数据查找操作，当数据量不是很大时，一般的查找技术足以满足需求

但对于服务器来说，其是以大型数据库为中心的，并且其将大型数据库作为文件存放于外存中的，而当需要进行数据查找操作时，查找技术处理过于缓慢，为加快查找速度，设计出了索引这种结构

【基本思想】

计数排序是非比较类排序一种，其基本思想是：对于给定的输入序列中的每一个元素 $x$，确定该序列中值小于 $x$ 的元素的个数，一旦有了这个信息，就可以将 $x$ 直接存放到最终的输出序列的正确位置上

例如，如果输入序列中只有 $17$ 个元素的值小于 $x$ 的值，则 $x$ 可以直接存放在输出序列的第 $18$ 个位置上

【基本思想】

基数排序借助多关键字排序的思想，对单逻辑关键字进行排序，简单来说，其是基于关键字各位的大小进行排序

假设长度为 $n$ 的线性表中每个结点 $a_j$ 的关键字由 $d$ 元组 $(k_j^{d_-1},k_j^{d_-2},…,d_j^1,d_j^0)$ 组成，满足 $0\leq k_j^i\leq r-1$，其中 $k_j^{d-1}$ 为最主关键字，$k_j^0$ 为最次关键字，且 $0\leq j <n,0\leq i\leq d-1$