[科普中国]-索引无序文件

简介

索引是为了加速对表中数据行的检索而创建的一种分散的存储结构。索引是针对表而建立的，它是由数据页面以外的索引页面组成的，每个索引页面中的行都会含有逻辑指针，以便加速检索物理数据。1索引文件一般分为索引顺序文件和索引无序文件。

主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。

索引无序文件是指主文件按主关键字无序的文件。通常将索引非顺序文件简称为索引文件。索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。

索引文件索引文件由主文件和索引表构成。

①主文件：文件本身。

②索引表：在文件本身外建立的一张表，它指明逻辑记录和物理记录之间的一一对应关系。

索引表组成索引表由若干索引项组成。一般索引项由主关键字和该关键字所在记录的物理地址组成。

索引文件的存储索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。

索引文件的建立建立索引文件的过程：

（1） 按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的

（2） 待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。

存取存取文件中的记录需按以下步骤：

（1）整个索引文件都载入到内存中（文件很小，只占用很小的内存空间）。

（2）搜索项目，用高效的算法（如折半查询法）查找目标键。

（3）检索记录的地址。

（4）按照地址，检索数据记录并返回给用户。2

更新操作插入：将插入记录置于数据区的末尾，并在索引表中插入索引项；

删除：删去相应的索引项。

随机存取在计算机科学中，随机存取（直接访问）代表同一时间访问一组序列中的一个随意组件。反之则称顺序访问，即是需要更多时间去访问一个远程组件。介分两者的传统图解就似比较一轴古代画卷（循序︰所有在组件之前的物料必须事先卷开）及一本图书（随机︰可以随时翻至任何一页）。而更近现代的例子就如比较卡式磁带（循序︰我们必须快速跳过早前的歌曲才可聆听后期的歌曲）及一张CD（随机︰我们可以随意跳至我们想要之处）。不过，RAM一词却被用以作为电脑中的半导体芯片内存电路。

于数据结构中，随机存取暗指可由一堆数字之中，能够持续访问N值的能力，而且除了数组（及相关结构，例如动态数组）以外，绝少数据结构能够作出类似程序。另外，随机存取对不少算法，如快速排序及二元搜索而言不可或缺。其他数据结构，如合并排序，则凭随机存取作出有效率的输入、删除抑或搜索功能。