简单的方法

删除记录i：不同的选择：

移动记录i + 1，…，n到i，…，n-1

移动记录n到i

不移动记录，但链接所有自由记录到一个自由链表上

适用于需要连续处理整个文件的应用程序 文件中的记录按一个搜索键进行排序

对于N个项目的顺序搜索，比较的平均次数E (X)为≈N/2 假设每一项具有相同的为要求项的概率（即1/N），则第一项的概率为1/N为要求项，第二项的概率为1/N为要求项，以此类推，在找到要求项后，搜索将终止： E ( X ) = 1 N + 2 N + . . . + N N 1 N ∑ i = 1 N k = N + 1 2 E(X) = \frac{1}{N}+ \frac{2}{N}+...+ \frac{N}{N}\\ \frac{1}{N} \sum_{i=1}^N k = \frac{N+1}{2} E(X)=N1​+N2​+...+NN​N1​i=1∑N​k=2N+1​

二进制搜索N个排序项，最大比较次数k为 ≈ l o g 2 N ≈log_2N ≈log2​N 考虑一条长度为N的线，并一直将长度划分为两个，直到只剩下一个项 N 2 k = 1 ⇒ N = 2 k ⇒ k = l o g 2 N \frac{N}{2^k} = 1 \Rightarrow N = 2^k \Rightarrow k = log_2N 2kN​=1⇒N=2k⇒k=log2​N

删除-使用指针链

插入-定位要插入的记录的位置

需要不时地重新组织文件，以恢复顺序和顺序

使用多表群集文件组织在一个文件中存储多个关系

密集索引: 显示针对文件中的每个搜索键值的索引记录，例如讲师(instructors)关系的ID属性上的索引 在dept_name上的密集索引，教师文件按dept_name排序

稀疏索引： 仅包含某些搜索键值的索引记录。适用于在搜索键上按顺序排序的记录 要找到搜索键值为K的记录，我们先找到索引中搜索键值比K小的最大值的记录，从索引记录指向的记录依次开始

二级索引(Secondary Index)

指导教师工资领域的二级指标

索引记录指向一个桶，该桶包含指向具有该特定搜索键值的所有实际记录的指针。

聚类字段: 记录在非键字段上进行物理上的排序，每个记录都没有不同的值

Dept_number上的聚类索引，它是雇员(Employee)文件的排序非键字段

文件的非排序键字段上的密集二级索引（和块指针）。

两级ISAM（(indexed sequential access method, 索引顺序访问方法）组织.