12.5 直接存取与多关键字文件

01直接存取文件（散列文件）

1、直接存取文件指的是利用杂凑（Hash）法进行组织的文件。

2、直接存取文件类似于哈希表，即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。

3、与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的。

4、若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶（Bucket）。

5、直接存取文件的优点是：文件随机存放，记录不需进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。

6、直接存取文件的缺点是：不能进行顺序存取、只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次的插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时需重组文件。

02多重表文件

1、多重表文件（Multilist File）的特点是：记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（称为主索引）；对于每一个次关键字项建立次关键字索引（称为次索引）。

2、所有具有同一次关键字的记录构成一个链表。

3、主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头指针和链表长度。

4、多重链表文件易于构造，也易于修改。如果不要求保持链表的某种次序，则插入一个新记录时容易的，此时可将记录插在链表的头指针之后。但是，要删去一个记录却很繁琐，需在每个次关键字的链表中删去该记录。

03倒排文件

1、倒排文件和多重表文件的区别在于次关键字的结构不同。

2、通常，称倒排文件中的次关键字索引为倒排表，具有相同次关键字的记录之间不设指针相链，而在倒排表中该次关键字的一项中存放这些记录的物理记录号。

3、倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。

C语言 | 用指针对10个数排序

更多案例可以go公众号：C语言入门到精通