412_文件的逻辑结构
# 4.1_2_文件的逻辑结构
各位同学大家好，在小节中我们会学习文件的逻辑结构相关的一系列知识点，那么在上个小节中，我们也简要的提到过，所谓的文件的逻辑结构就是指在用户看来文件内部的数据应该是怎么被组织起来的，而所谓的物理结构又指的是在操作系统看来，文件的数据应该是怎么被存放在外存当中的
其实在数据结构那门课当中也接触过很多逻辑结构和物理结构的问题，比如说线性表它就是一种逻辑结构，在用户看来线性表它是一组有先后顺序的元素序列，比如说 abcde，但是对于一种逻辑结构来说，也可以用不同的物理结构来实现，比如说线性表可以用顺序表的方式实现，也可以用链表的方式实现。如果用顺序表的方式实现的话，那么就意味着各个在逻辑上相邻的元素，在物理上也是相邻，也是按照这样的顺序来存放的，而如果采用的是链表这种物理结构的话，就意味着这些元素在逻辑上虽然相邻，但是在物理上可以不相邻。所以基于这样的特性，顺序表可以实现随机访问，而链表又无法实现随机访问。
所以从这个地方我们也可以看出，算法的具体实现和逻辑结构物理结构都是有关的，那文件也是一样，文件的操作的具体实现也和文件的逻辑结构物理结构都有关系。这个文件可以分为无结构文件和有结构文件两种，我们需要重点讨论的是有结构文件的这几种逻辑结构。
# 无结构文件
上个小节中我们已经知道所谓无结构文件，它其实就是由一系列的二进制流或者说字符流组成，又称为流式文件。比如说像咱们 windows 操作系统里的.txt 文件，就是一种很典型的无结构文件，由于这种结构没有很明显的这种结构特性，所以我们也不必要来讨论它的这种逻辑结构的问题
因此我们重点关注的是有结构文件，它由一组相似的记录组成，又称为记录式文件，而每条记录又由若干个数据项组成，比如说像我们的数据库表文件，像这个例子当中这就是一张数据库表，记录了各个学生的信息，包括学号、姓名、性别还有专业这样的 4 个数据项。
一般来说每条记录可以有一个数据项作为关键字，像数据库表当中就可以用学号数据项作为关键字来作为识别不同记录的一个 ID，每个学生会对应一条记录，每条记录又由若干个数据项组成，其中的学号可以作为记录的关键字，这是有结构文件，它由一系列的记录组成
根据各条记录的长度，也就是占用的存储空间是否相等，又可以把这些记录分为定长记录和可变，长记录两种，比如说像刚才咱们提到的例子当中，可以用 32 个字节来表示学号，32 个字节表示姓名，4 个字节表示性别，然后用 60 个字节表示学生的专业信息，所以既然每一个数据项的长度都相同，那么每一条记录的总长度也是相同的，也就是 128 个字节，并且在定长记录当中，每个数据项在记录当中所处的位置都是相同的。
不过可变长记录的这种有结构文件，其实才是咱们生活当中最常见的一种有结构文件。比如说有一张表，它记录了每个学生的一些基本信息，还有学生的特长，像张三的特长就是腿特长，然后李四是腿毛特长，二狗这个人他又可以熟读唐诗三百首，琴棋书画样样精通，上到了厅堂下得了厨房，精通教 c 加 Python，还有任意一种脚本语言，后面还有很多他的关于他特长的描述，而又有一些同学他是没有特长的，因此由于每个记录的特长，数据项长度是不确定的，有的特别多，有的又特别少，有的甚至没有，所以像这些记录它就是一种可变长的记录。
像之前的例子当中，专业数据项用几个字就可以描述，所以即使我们给各个学生的专业数据项分配了总共固定 60 个字节的这种长度，即使有存储空间的浪费也不至于特别明显。但是像这个例子当中，如果我们给每个学生的特长数据项都分配一个巨大的一个存储空间的话，显然有的学生对这个数据上的存储空间利用是很不充分的，这样的话就会导致存储空间利用率极低的一个问题。所以在这个例子当中，最好是让有结构文件的这些记录是可变长的记录
# 有结构文件的逻辑结构
接下来我们需要再讨论这些记录应该在逻辑上怎么被组织起来的问题，也就是有结构文件的逻辑结构的问题，分为顺序文件、索引文件和索引顺序文件这三种。
# 顺序文件
我们首先来看顺序文件这种逻辑结构，如果是顺序文件结构的话，那么文件中的这些记录会一个接一个的顺序的排列，这些记录可以是定长的，也可以是可变长的，并且各个记录在物理上可以是顺序存储，也可以是链式存储。如果说这些记录是顺序存储的话，那么在逻辑上相邻的这些记录，在物理上也是相邻的，这就类似于咱们之前提到的顺序表那种数据结构，而如果说采用的是链式存储这种物理结构的话，那么逻辑上相邻的这些记录在物理上不一定相邻，就类似于咱们之前的链表，
根据这个记录是否按照关键字的顺序来排列，又可以把顺序文件分为串结构和顺序结构这两种，串结构就是指记录之间的顺序与关键字无关，如果是串结构的话，那么记录之间的顺序一般来说是按照存入的时间先后顺序来决定的；
而如果采用的是顺序结构的话，就必须保证记录之间的先后顺序是按照关键字的顺序来排列的，显然记录到底是定长的还是可变长的，这些记录是否按照关键字有序的排列，另外这些记录在物理上到底是顺序存储还是链式存储，所有的这些区别，都会影响顺序文件到底能不能实现某一些操作的功能，接下来我们会重点讨论两个问题。
假设我们已经知道了文件的起始地址，也就是第一个记录的存放位置的话，那么我们是否能够快速的找到第 i 个记录对应的地址，也就是说是否能实现这些记录的随机存取，随机访问这件事情。第二个问题，我们能不能快速的找到某一个关键字对应的记录存放的位置，我们会根据这些各个条件的不同来进行探讨
我们直接给出结论
- 假设一个顺序文件在物理上是采用链式存储的方式来实现的话，那么无论这个顺序文件它是定长记录还是可变长记录，也无论它是串结构还是顺序结构，它肯定都无法实现随机存取。每次只能从第一个记录开始一次往后寻找，这个和我们的链表很类似，如果我们要在一个链表当中找到某一个元素的话，那么我们每次都只能从链头开始依次往后寻找，因为各个元素之间的存储位置它并没有规律，它都是离散的，所以我们并不能直接计算出某一个元素在物理上的存放地址。因此如果我们采用的是链式存储的话，那么对这个顺序文件的记录的检索查询都是不太方便的。
- 假设采用的是顺序存储的物理结构，并且这个文件是可变长记录的文件，它依然是无法实现随机存取的，每次只能从第一个记录开始一次往后查找，来看一下为什么：由于这个文件的记录是可变长的，也就是每个记录的长度不一样，所以必须在每个记录之前用一定的存储空间来表示记录的长度，假设这个记录长度可以用一个字节来表示，第 0 条记录它的逻辑地址是 0，第二条记录就应该是第 0 条记录的长度 L0，再加上它的记录长度，字段占用的字节数一个字节，所以 L0+1 这是第一个记录对应的逻辑地址，相应的应该是之前所有的这些记录的长度之和，再加上所有的这些记录的长度字段所占用的字节，每一个占用一个字节，前面总共有 i 个记录的话，总共就会占用 i 个字节。所以由于这个文件中的记录是可变长的，L0，L1，L2，这些数据并不会呈现出某种规律性，因此我们想要找到某一条记录对应的地址的话，那么只能从第一条记录开始依次往后寻找。因此如果说这个文件是可变长记录的文件，那么即使它采用了顺序存储的这种方式，依然无法实现随机存取。
- 如果说这个文件是一个定长记录的顺序文件，并且在物理上是采用顺序存储的方式的话，情况就不一样了，这就可以实现随机存取。假设每个记录的长度固定为 lL 并且这些记录在物理上是顺序存储的，那就意味着各个逻辑上相邻的记录在物理上也是相邻的存储的。所以第 0 号记录的逻辑地址为 0 的话，那么 I 号记录的逻辑地址直接可以用 L 乘以 i 就可以直接得到。因此如果是正常记录的顺序文件，并且在物理上也是顺序存储的话，那么是可以实现随机存取的功能的。
- 如果说这个顺序文件是串结构，也就是说这些记录的顺序和他们的关键字顺序是没有关系的话，这就无法快速的找到某个关键字对应的记录，因为它并不是按关键字的顺序来排列的，所以我们每次只能从头开始，依次往后便利的寻找关键字对应的记录。
- 但是如果说定长记录的顺序文件采用的是顺序结构的话，那么也就意味着这些记录是按照关键字的顺序来排列的，这样的话我们就可以用像折半查找之类的一些方法来快速的找到某一个关键字对应的记录。
到这个地方我们就回答了之前提出的两个问题，关于是否可以实现对各个记录的随机存取，这件事我们得出的结论是如果说物理上采用的是链式存储，那么肯定是无法实现记录的随机存取的。而如果说物理上采用的是顺序存储的话，那么可变长记录的顺序文件是无法实现随机存取的，而定长记录的顺序文件是可以实现随机存取的，如果说在这个基础上能保证定长记录的顺序文件，它是一种顺序结构，也就是按照关键字的顺序来排列的话，那么我们就可以实现快速的检索某一个记录的功能。
一般来说考题当中所指的顺序文件默认的是指物理上采用顺序存储的这种顺序文件，所以我们不需要考虑各个记录链式存储的这种情况。在之后我们的讲解当中，在提到顺序文件的时候也是默认如此
显然在顺序表那种数据结构当中，要增加或者删除一个元素是比较困难的。同样的，如果采用的是顺序存储的这种结构的话，那么它要删除或者增加一个记录也是比较困难的。不过如果采用的是串结构的话，那么由于不需要保证各个记录按照关键字来排序，因此对于串结构的顺序文件来说，增加和删除一个记录相对来说要简单一些，我们只需要很简单的把要增加的记录插到文件的末尾就可以了。
在实际应用当中，为了减少磁盘的 lO 次数，一般来说系统操作系统会管理一个日志文件，用日志文件来记录对这个文件当中的各个记录进行修改的一些信息，然后每隔一段时比较长的时间，再把这些信息统一的合并到外存当中的文件数据当中，比如说每隔一个小时才合并一次，或者说每隔 10 分钟才合并一次，这样的话就可以减少对于顺序存储的顺序文件进行增删改所带来的一些开销了。不过这个知识点只是简单的提一提，在考试当中并不会进行考察。
以上的这些内容是顺序文件这种逻辑结构当中需要特别注意的一些知识点，特别是定长记录可以实现随机存取，而可变长记录不可以实现随机存取这两件事。
# 索引文件
接下来我们再来看第二种逻辑结构索引文件。通过之前的讲解，我们知道如果说一个顺序文件它是可变长记录的话，那么要找到第二个记录，就必须先顺序的查找 i 前面的 i -1 记录，但是在实际生活当中又有很多应用场景又必须使用可变长记录，能不能解决可变长记录的这种查找速度慢的问题，能否让可变长记录的文件，也实现可以随机访问的功能，基于这个需求人们提出了索引文件这种逻辑结构
每一个文件会建立一张索引表，并且每一个索引表的表项会对应这个文件的一条记录，文件的这些记录在物理上不需要连续存放，但是索引表的各个表项在物理上是需要连续存放的。另外每一个索引表的表项的大小都是相等的，比如说索引号，长度，指针，这 3 个字段分别占 4 个字节，那么 1 个索引表的表项总共就需要占 12 个字节的长度，因此索引表本身也可以理解成是一种定长记录的顺序文件。
经过之前的讲解，我们也知道定长记录的顺序文件是可以支持随机访问的，所以我们可以快速的找到第 i 个记录对应的索引表项到底是存放在什么地方。另外如果我们把这个关键字作为索引号的内容，并且让索引表当中的这些表项按照关键字的顺序来排列的话，那么我们就可以让索引文件支持折半查找，这样的话就可以大幅度的提升索引文件的检索速度
不过既然每一个文件的记录会对应一个索引表项，那么我们要增加或者删除一个记录的时候，当然也需要把对应的表项进行相应的处理，要增加一个记录的时候，也需要增加一个相应的缩印表项，要删除一个记录的时候，也需要把它对应的索引表项也给删除。
通过之前的讲解，我们发现索引文件这种逻辑结构可以支持很快的检索速度，所以这种逻辑结构主要是用在对于信息处理的及时性要求很高的那种场合。另外除了用这个关键字作为索引号之外，我们还可以用别的不同的数据项作为索引号来为一个文件建立多个索引表。比如说像之前咱们提到那个例子，学生信息表当中，我们可以为关键字学号来建立一张索引表，同时也可以用姓名字段来建立一张索引表，这样的话我们就可以根据学号快速的找到对应的记录，也可以根据姓名快速的找到对应的记录了。如果说学过数据库的同学就知道，在 SQL 语言当中就可以用一条 SQL 语句就完成为某一个字段建立一张索引表的这种功能了，这是索引文件。
# 索引顺序文件
接下来我们再来看最后一种逻辑结构索引顺序文件。我们思考一下索引文件表现出来的缺点，每个记录会对应一个索引表的表项，因此如果索引表的表项比较大的话，那么索引表也会占用很大的存储空间。
比如说如果文件当中的每个记录平均只占 8 个字节，但是每 1 个索引表的表项需要占 32 个字节，那么索引表的长度都要比文件内容本身要大 4 倍，这样的话存储空间的利用率就太低了。
所以为了解决这个问题，人们提出了索引顺序文件，它是一种索引文件和顺序文件思想的结合，与索引文件类似的是索引顺序文件当中同样会为一个文件建立一张索引表，但是与索引文件不同的是索引顺序文件当中并不会为每一个记录建立一个对应的索引表项，而是会给这些记录进行分组，然后每一个分组对应一个索引表项，
比如说在这个例子当中，就是按照学生的姓氏把学生记录进行了一个分组，然后每一个分组会对应一个索引顺序，文件的索引项，每个索引项记录了分组的名字，还有分组存放的一个位置。
从这个地方可以看到索引顺序文件的索引项，并不需要按照关键字的顺序来排列，这样的话是可以更方便我们对新表项的插入操作的。也就是说索引顺序文件的索引表，它其实是一个定长记录的串结构的顺序文件。另外这样的分组就是一个顺序文件
可以看到采用了索引顺序文件这种逻辑结构之后，索引表的表项是少了很多的，所以我们完成了刚才提出的需求，也就是对索引表进行了瘦身减肥的工作。
如果采用这样的策略的话，会不会出现检索速度慢的问题？我们来分析一下。假设一个顺序文件有 1 万个记录，根据关键字检索这个文件的时候，每次只能从头开始顺序的查找，我们要找到这个关键字对应的记录的话，就平均需要查找 5000 个记录
但是如果我们把这个文件改造成这种索引顺序文件的这种逻辑结构的话，我们可以把这 1 万个记录平均分为 100 组，然后每组 100 个记录，这样的话我们要查询某一个关键字对应的记录，首先是需要顺序的查找索引表，找到这个关键字对应的分组，由于索引表只有 100 个索引项，因此平均只需要查找 50 次，就可以找到 1 个关键字对应的分组了，
相应的找到了它对应的分组之后，在分组内有 100 个记录，因此接下来我们需要顺序的查找，这 100 个记录平均只需要查找 50 次，就可以找到这个关键字对应的记录存放的位置了。所以其实采用了这种索引顺序，文件结构之后，平均的查找次数就减少为了 50+50，总共 100 次，因此这种逻辑结构也是具有比较好的检索性能的。
同样的道理，如果说一个文件有 10 的 6 次方个记录，我们可以把它分为 1000 组，每个分组是 1000 个记录，根据关键字来检索一个记录，就平均需要 500+500，总共 1000 次查询，这 1000 次其实查找的次数依然是很多的，怎么解决这个问题，我们可以建立多级索引？
对于刚才所说的这个例子来说，我们可以为这个文件先建立一张低级索引表，每一个索引表对应 100 个表项，每一个表项又对应一个分组，每一个分组当中又是 100 个记录，那不难算出我们总共会有 100 张低级索引表，因此我们又可以为这 100 张低级索引表再建立一个顶级的索引表，这样的话就形成了两级索引顺序文件。顶级索引表中总共有 100 个表项，低级索引表中每一个索引表中也是有 100 个表项，每一个表项又会对应一个分组，每个分组中又会有 100 个记录，因此如果我们按照这样分组的话，根据一个关键字来检索一个记录，平均需要查找的次数就是这个地方需要查 50 次，这个地方需要查 50 次，这个地方还需要查平均 50 次，总共平均需要 150 次的查找，就可以找到想要找的目录项了
# 小结
这个小节当中我们介绍了文件的逻辑结构，无结构文件由二进制流或者字符流组成，没有明显的逻辑结构，所以不我们不展开探讨，
我们需要重点掌握的是有结构文件的这几种逻辑结构，分为顺序文件、索引文件和索引顺序文件，
而有结构文件它是由记录组成的，分为定长记录和可变长记录。我们在考试中遇到的所谓的顺序文件，指的是默认各个记录在物理上顺序存储的这种物理结构。
需要重点注意的是，对于可变长记录的顺序文件来说，它是无法实现随机存取的，但是定长记录可以可变长记录的顺序文件，每次在查询的时候只能从头开始，依次往后查找。
第二个需要注意的点是经常记录顺序结构的顺序文件可以快速检索。所谓的顺序结构就是指这些记录按照关键字的顺序依次排列，所以由于这些记录排列的顺序是有规律可循的，因此我们可以用像折半查找之类的方法，来快速的找到一个关键字对应的记录。
在索引文件这种逻辑结构中，我们需要注意的是索引表本身就是一种定长记录的顺序文件，而如果说索引表按照关键字的顺序排列，它同样也可以向之前所说的这样支持快速检索的功能，也就是根据某一个关键字来快速找到某一个记录的功能。由于快速检索的功能和特性，因此索引文件也经常被使用在那些对于检索速度要求很高的那些场景当中。
在最后我们介绍的索引顺序文件当中，除了要理解它的这一些原理之外，我们还需要会动手计算平均查找次数。
