精华内容
下载资源
问答
  • 常见的记录式结构文件不包括
    千次阅读
    2020-03-31 20:57:16

    转载地址:

    https://blog.csdn.net/haiross/article/details/46829875?utm_source=blogxgwz7

    文件的逻辑结构是从用户观点出发看到的文件的组织形式。文件的物理结构是从实现观点出发,又称为文件的存储结构,是指文件在外存上的存储组织形式。文件的逻辑结构与存储介质特性无关,但文件的物理结构与存储介质的特性有很大关系。

    按逻辑结构,文件有无结构文件和有结构文件两种类型:无结构文件和有结构文件。

    无结构文件(流式文件)

    无结构文件是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累保存,它是有序相关信息项的集合,以字节(Byte)为单位。由于无结构文件没有结构,因而对记录的访问只能通过穷举搜索的方式,故这种文件形式对大多数应用不适用。但字符流的无结构文件管理简单,用户可以方便地对其进行操作。所以,那些对基本信息单位操作不多的文件较适于釆用字符流的无结构方式,如源程序文件、目标代码文件等。

    有结构文件(记录式文件)

    有结构文件按记录的组织形式可以分为:

    1) 顺序文件。

    文件中的记录一个接一个地顺序排列,记录可以是定长的或变长的,可以顺序存储或以链表形式存储,在访问时需要顺序搜索文件。顺序文件有以下两种结构:

    第一种是串结构,记录之间的顺序与关键字无关。通常的办法是由时间决定,即按存入时间的先后排列,最先存入的记录作为第1个记录,其次存入的为第2个记录,依此类推。

    第二种是顺序结构,指文件中的所有记录按关键字顺序排列。

    在对记录进行批量操作时,即每次要读或写一大批记录,对顺序文件的效率是所有逻辑文件中最高的;此外,也只有顺序文件才能存储在磁带上,并能有效地工作,但顺序文件对查找、修改、增加或删除单个记录的操作比较困难。

    2) 索引文件。

    如图4-1所示。对于定长记录文件,如果要查找第i个记录,可直接根据下式计算来获得第i个记录相对于第一个记录的地址:


    然而,对于可变长记录的文件,要查找第i个记录时,必须顺序地查找前i-1个记录,从而获得相应记录的长度L,然后才能按下式计算出第i个记录的首址:


    注意:假定每个记录前用一个字节指明该记录的长度。
     


    图4-1  索引文件示意图


    变长记录文件只能顺序查找,系统开销较大。为此可以建立一张索引表以加快检索速度,索引表本身是定长记录的顺序文件。在记录很多或是访问要求高的文件中,需要引入索引以提供有效的访问。实际中,通过索引可以成百上千倍地提高访问速度。

    3) 索引顺序文件。

    索引顺序文件是顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中的所有记录分为若干个组,为顺序文件建立一张索引表,在索引表中为每组中的第一个记录建立一个索引项,其中含有该记录的关键字值和指向该记录的指针。

    如图4-2所示,主文件名包含姓名和其他数据项。姓名为关键字,索引表中为每组的第一个记录(不是每个记录)的关键字值,用指计指向主文件中该记录的起始位置。索引表只包含关键字和指计两个数据项,所有姓名关键字递增排列。主文件中记录分组排列,同一个组中关键字可以无序,但组与组之间关键字必须有序。查找一个记录时,通过索引表找到其所在的组,然后在该组中使用顺序查找就能很快地找到记录。
     


    图4-2  索引顺序文件示意图


    对于含有N个记录的顺序文件,查找某关键字值的记录时平均需要查找N/2次。在索引顺序文件中,假设N个记录分为N1/2组,索引表中有N1/2个表项,每组有N1/2个记录,在查找某关键字值的记录时,先顺序查找索引表,需要查找N1/2/2次,然后再在主文件中对应的组中顺序查找,也需要查找N1/2/2次,这样总共查找N1/2/2+N1/2/2=N1/2次。显然,索引顺序文件提高了查找效率,如果记录数很多,可以釆用两级或多级索引。

    索引文件和索引顺序文件都提高了存取的速度,但因为配置索引表而增加了存储空间。

    4) 直接文件或散列文件(Hash File)

    给定记录的键值或通过Hash函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件,没有顺序的特性。

    散列文件有很高的存取速度,但是会引起冲突,即不同关键字的散列函数值相同。

    更多相关内容
  • 一、文件的逻辑结构 类似于数据结构的“逻辑结构”和“物理结构”。 ①、如“线性表”就是一种逻辑结构,在用户角度看来,线性表就是一组有先后关系的元素序列,如:a,b, c, d, e …… ②、“线性表”这种逻辑结构...

    一、文件的逻辑结构

    在这里插入图片描述

    • 类似于数据结构的“逻辑结构”和“物理结构”。
      ①、如“线性表”就是一种逻辑结构,在用户角度看来,线性表就是一组有先后关系的元素序列,如:a,b, c, d, e ……
      ②、“线性表”这种逻辑结构可以用不同的物理结构实现,如:顺序表/链表。顺序表的各个元素在逻辑上相邻,在物理上也相邻;而链表的各个元素在物理上可以是不相邻的。因此,顺序表可以实现“随机访问”,而“链表”无法实现随机访问。
      ③、可见,算法的具体实现与逻辑结构、物理结构都有关(文件也一样,文件操作的具体实现与文件的逻辑结构、物理结构都有关)

    (二)无结构文件

    • 按文件是否有结构分类,可以分为无结构文件、有结构文件两种。
    • 无结构文件 :文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如:Windows 操作系统中的 .txt 文件。
    • 文件内部的数据其实就是一系列字符流,没有明显的结构特性。

    (三)有结构文件

    • 有结构文件 :由一组相似的记录组成,又称“记录式文件”。每条记录又若干个数据项组成。如:数据库表文件。一般来说,每条记录有一个数据项可作为关键字(作为识别不同记录的ID)
      在这里插入图片描述
    • 根据各条记录的长度(占用的存储空间)是否相等,又可分为定长记录可变长记录两种。
      在这里插入图片描述
      在这里插入图片描述

    1. 顺序文件

    • 顺序文件 :文件中的记录一个接一个地顺序排列(逻辑上),记录可以是定长的或可变长的。各个记录在物理上可以顺序存储链式存储
      在这里插入图片描述
      在这里插入图片描述

    2. 索引文件

    在这里插入图片描述

    3. 索引顺序文件

    在这里插入图片描述

    (1)索引顺序文件(检索效率分析)

    在这里插入图片描述

    • 若一个顺序文件有10000个记录,则根据关键字检索文件,只能从头开始顺序查找(这里指的并不是定长记录、顺序结构 的顺序文件),平均须查找 5000 个记录
    • 若采用索引顺序文件结构,可把 10000 个记录分为 √10000 = 100 组,每组 100 个记录。则需要先顺序查找索引表找到分组(共100个分组,因此索引表长度为 100,平均需要查 50 次),找到分组后,再在分组中顺序查找记录(每个分组100 个记录,因此平均需要查 50 次)。可见,采用索引顺序文件结构后,平均查找次数减少为 50+50 = 100 次
    • 同理,若文件共有 106个记录,则可分为 1000 个分组,每个分组 1000 个记录。根据关键字检索一个记录平均需要查找 500+500 = 1000 次。这个查找次数依然很多,如何解决呢?

    (2)多级索引顺序文件

    • 为了进一步提高检索效率,可以为顺序文件建立多级索引表。例如,对于一个含 106个记录的文件,可先为该文件建立一张低级索引表,每 100 个记录为一组,故低级索引表中共有 10000 个表项(即10000个定记录),再把这 10000 个定长记录分组,每组100个,为其建立顶级索引表,故顶级索引表中共有 100 个表项。
      在这里插入图片描述

    二、文件目录

    在这里插入图片描述

    (一)文件控制块

    在这里插入图片描述

    • 当我们双击“照片”后,操作系统会在这个目录表中找到关键字“照片”对应的目录项(也就是记录),然后从外存中将“照片”目录的信息读入内存,于是,“照片”目录中的内容就可以显示出来了。
      在这里插入图片描述
    • FCB 的有序集合称为“文件目录”,一个FCB就是一个文件目录项
    • FCB 中包含了文件的基本信息文件名物理地址、逻辑结构、物理结构等),存取控制信息(是否可读/可写、禁止访问的用户名单等),使用信息(如文件的建立时间、修改时间等)。
    • 最重要,最基本的还是 文件名、文件存放的物理地址FCB 实现了文件名和文件之间的映射。使用户(用户程序)可以实现“按名存取”
    • 需要对目录进行哪些操作?
      ①、搜索:当用户要使用一个文件时,系统要根据文件名搜索目录,找到该文件对应的目录项
      ②、创建文件:创建一个新文件时,需要在其所属的目录中增加一个目录项
      ③、删除文件:当删除一个文件时,需要在目录中删除相应的目录项
      ④、显示目录:用户可以请求显示目录的内容,如显示该目录中的所有文件及相应属性
      ⑤、修改目录:某些文件属性保存在目录中,因此这些属性变化时需要修改相应的目录项(如:文件重命名)

    (二)目录结构

    1. 单级目录结构

    • 早期操作系统并不支持多级目录,整个系统中只建立一张目录表,每个文件占一个目录项。
      在这里插入图片描述

    2. 两级目录结构

    • 早期的多用户操作系统,采用两级目录结构。分为主文件目录(MFD,Master File Directory)和用户文件目录(UFD,User Flie Directory)。
      在这里插入图片描述

    3. 多级目录结构(又称树形目录结构)

    在这里插入图片描述

    • 用户(或用户进程)要访问某个文件时要用文件路径名标识文件,文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径
    • 例如:自拍.jpg 的绝对路径是 “/照片/2015-08/自拍.jpg
    • 系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表;找到“照片”目录的存放位置后,从外存读入对应的目录表;再找到“2015-08”目录的存放位置,再从外存读入对应目录表;最后才找到文件“自拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作
    • 很多时候,用户会连续访问同一目录内的多个文件(比如:接连查看“2015-08”目录内的多个照片文件),显然,每次都从根目录开始查找,是很低效的。因此可以设置一个“当前目录”。
    • 例如,此时已经打开了“照片”的目录文件,也就是说,这张目录表已调入内存,那么可以把它设置为“当前目录”。当用户想要访问某个文件时,可以使用从当前目录出发的“相对路径” 。
    • 在 Linux 中,“.”表示当前目录,因此如果“照片”是当前目录,则”自拍.jpg”的相对路径为:“./2015-08/自拍.jpg”。从当前路径出发,只需要查询内存中的“照片”目录表,即可知道”2015-08”目录表的存放位置,从外存调入该目录,即可知道“自拍.jpg”存放的位置了。
    • 可见,引入“当前目录”和“相对路径”后,磁盘I/O的次数减少了。这就提升了访问文件的效率。
    • 树形目录结构可以很方便地对文件进行分类,层次结构清晰,也能够更有效地进行文件的管理和保护。但是,树形结构不便于实现文件的共享。为此,提出了“无环图目录结构

    4. 无环图目录结构

    在这里插入图片描述

    • 可以用不同的文件名指向同一个文件,甚至可以指向同一个目录(共享同一目录下的所有内容)。
    • 需要为每个共享结点设置一个共享计数器,用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时,只是删除该用户的FCB、并使共享计数器减1,并不会直接删除共享结点。
    • 只有共享计数器减为0时,才删除结点。
    • 注意:共享文件不同于复制文件。在 共享文件中,由于各用户指向的是同一个文件,因此只要其中一个用户修改了文件数据,那么所有用户都可以看到文件数据的变化。

    (三)索引结点(FCB的改进)

    在这里插入图片描述

    • 当找到文件名对应的目录项时,才需要将索引结点调入内存,索引结点中记录了文件的各种信息,包括文件在外存中的存放位置,根据“存放位置”即可找到文件。
    • 存放在外存中的索引结点称为“磁盘索引结点”,当索引结点放入内存后称为“内存索引结点”。
    • 相比之下内存索引结点中需要增加一些信息,比如:文件是否被修改、此时有几个进程正在访问该文件等
    展开全文
  • 数据结构——文件

    千次阅读 多人点赞 2020-02-13 15:51:51
    数据库文件记录的类型不同】 (1)操作系统的文件 (2)数据库文件 2.定长记录文件&不定长记录文件【含有信息长度】 (1)定长记录文件 (2)不定长记录文件 3.单关键字文件&多关键字文件记录中...

    目录:

    一:什么是文件?

    1.表

    2.文件

     

    二:文件及类别

    1.操作系统的文件&数据库文件【记录的类型不同】

    (1)操作系统的文件

    (2)数据库文件

    2.定长记录文件&不定长记录文件【含有信息长度】

    (1)定长记录文件

    (2)不定长记录文件

    3.单关键字文件&多关键字文件【记录中关键字的多少】

    (1)单关键字文件

    (2)多关键字文件

     

    三:逻辑结构&物理结构

    1.逻辑结构

    2.物理结构

    3.文件的组织方式 

    4.物理记录&逻辑记录之间的3种关系:

     

    四:文件的操作【运算】

    1.文件的检索 

    (1)顺序存取

    (2)直接存取

    (3)按关键字存取

    ①简单询问:

    ②区域询问:

    ③函数询问:

    ④布尔询问:

    2.文件的修改

     

    五:顺序文件

    1.定义 

    2.连续文件&串联文件

    3.特点

    4.举例

     

    六:索引文件

    1.定义

    2.图解

    3.索引顺序文件&索引非顺序文件

    4.特点

    5.检索

    (1)检索方式

    (2)索引文件的修改更新

    (3) 稠密索引&非稠密索引

     

    七:ISAM文件和VSAM文件

    1.ISAM文件

    (1)定义

    (2)文件结构示列

    (3)磁道索引项结构

    (4)柱面索引

    (5)溢出区3种设置方法

    (6)文件的插入和溢出处理

    (7)柱面索的位置

    2.VSAM文件

    (1)定义

    (2)文件的结构示意图

    (3)控制区间的结构示意图

    (4)解决文件的溢出和插入

     

    八:直接存取文件【散列文件】

    1.定义 

    2.桶

    3.处理溢出 【溢出桶-基桶】

    4.直接存取文件示例

    5.桶的容量和查找次数的关系 

    6.优缺点

     

    九:多关键字文件

    1.多重表文件

    2:倒排序文件


    一:什么是文件?

    1.表

    集合为表,文件在外存集合为表

     

    2.文件

    存储在二级存储器(外存储器)中记录集合为文件

     

    二:文件及类别

    1.操作系统的文件&数据库文件【记录的类型不同

    (1)操作系统的文件

    操作系统中的文件仅是一维的连续的字符序列,无结构、无解释

    它也是记录的集合,这个记录仅是一个字符组

     

    用户为了存取、加工方便,把文件中的信息划分成若干组

    每一组信息称为一个逻辑记录,且可按顺序编号

    (2)数据库文件

    数据库中的文件是带有结构的记录的集合

    这类记录是由一个或多个数据项组成的集合,它也是文件中可存取的数据的基本单位

     

    数据项是最基本的不可分的数据单位,也是文件中可使用的数据的最小单位

     

    例如,图12. 1所示为一一个数据库文件,每个学生的情况是一一个记录,它由10个数据项组成。

    2.定长记录文件&不定长记录文件【含有信息长度

    (1)定长记录文件

    若文件中每个记录含有的信息长度相同,则称这类记录为定长记录,由这类记录组成的文件称做定长记录

    (2)不定长记录文件

    若文件中含有信息长度不等的不定长记录,则称不定长记录文件

    3.单关键字文件&多关键字文件【记录中关键字的多少

    (1)单关键字文件

    若文件中的记录只有一个惟一标识记录的主关键字,则称单关键字文件

    (2)多关键字文件

    若文件中的记录除了含有一个主关键外,还含有若干个次关键字,则称为多关键字文件

    记录中所有非关键字的数据项称为记录的属性

     

    三:逻辑结构&物理结构

    1.逻辑结构

    记录的逻辑结构是指记录在用户或应用程序员面前呈现的方式

    是用户对数据的表示和存取方式

     

    通常,记录的逻辑结构着眼在用户使用方便

    2.物理结构

    记录的物理结构是数据在物理存储器上存储的方式

    数据的物理表示和组织

     

    而记录的物理结构则应考虑提高存储空间的利用率减少存取记录的时间

    它根据不同的需要及设备本身的特性可以有多种方式

     

    从11.1节的讨论中已得知:

    一个物理记录指的是计算机用一条I/O命令进行读写的基本数据单位

    对于固定的设备和操作系统,它的大小基本上是固定不变的

    逻辑记录大小是由使用要求定的

    3.文件的组织方式 

    文件在存储介质(磁盘或磁带)上的组织方式称为文件的物理结构

     

    文件可以有各种各样的组织方式,其基本方式有3种:

    顺序组织、随机组织和链组织

     

    一个特定的文件应采用何种物理结构应综合考虑各种因素

    如:存储介质的类型、记录的类型、大小和关键字的数目以及对文件作何种操作

    4.物理记录&逻辑记录之间的3种关系:

    (1) 一个物理记录存放一个逻辑记录

    (2)一个物理记录包含多个逻辑记录

    (3)多个物理记录表示一个逻辑记录

    用户读/写一个记录是指逻辑记录

    查找对应的物理记录则是操作系统的职责

     

    图12.2简单表示了这种关系

    图中的逻辑记录和物理记录满足上述第- -种关系,物理记录之间用指针相链接

     

    四:文件的操作【运算

    文件的操作有两类:检索和修改

    1.文件的检索 

    文件的检索有下列3种方式:

    (1)顺序存取

    存取下一个逻辑记录

     

    (2)直接存取

    存取第i个逻辑记录

    以上两种存取方式都是根据记录序号(即记录存人文件时的顺序编号)或记录的相对位置进行存取的

     

    (3)按关键字存取

    给定一个值,查询一个或-批关键字与给定值相关的记录

     

    对数据库文件可以有如下4种查询方式:

    ①简单询问:

    查询关键字等于给定值的记录

    例如,在图12.1的文件中,给定--个准考证号码或学生姓名,查询相关记录

    ②区域询问:

    查询关键字属某个区域内的记录

    例如,在图12.1的文件中查询某某中学的学生成绩,则给定准考证号的某个数值范围。

    ③函数询问:

    给定关键字的某个函数

    例如查询总分在全体学生的平均分以上的记录或处于中值的记录。.

    ④布尔询问:

    以上3种询问用布尔运算组合起来的询问

    例如,查询总分在600分以上且数学在100分以上,或者总分在平均分以下的外语在98分以,上的全部记录。

    2.文件的修改

    文件的修改包括插入一个记录删除-一个记录更新-个记录 3种操作

    文件的操作可以有实时和批两种不同方式

     

    通常实时处理对应答时间要求严格,应在接收询问之后几秒钟内完成检索和修改,而批量处理则不然

    不同的文件系统其使用有不同的要求

    例如,一个民航自动服务系统,其检索和修改都应实时处理;而银行的用有不同的要求

    例如,一个民航自动服务系统,其检索和修改都应实时处理;而银行的件上,在一天的营业之后再进行批量处理

     

    五:顺序文件

    1.定义 

    顺序文件(SequentialFile)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的

    即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的

    2.连续文件&串联文件

    若次序相继的两个物理记录在存储介质上的存储位置是相邻的,则又称连续文件

    若物理记录之间的次序由指针相链表示,则称串联文件

    3.特点

    顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式

    它的特点是:

    (1)存取第i个记录,必须先搜索在它之前的i-1个记录

    (2)插人新的记录时只能加在文件的末尾

    (3)若要更新文件中的某个记录,则必须将整个文件进行复制

    由于顺序文件的优点是连续存取的速度快

    因此主要用于只进行顺序存取、批量修改的情况

    若对应答时间要求不严时亦可进行直接存取

    4.举例

    磁带是一种典型的顺序存取设备

    因此存储在磁带上的文件只能是顺序文件

    磁带文件适合于文件的数据量甚大、平时记录变化少、只作批量修改的情况

    在对磁带文件作修改时,--般需用另一条复制带将原带上不变的记录复制-遍

    同时在复制的过程中插人新的记录和用更改后的新记录代替原记录写人

    为了修改方便起见,要求待复制的顺序文件按关键字有序(若非数据库文件,则可将逻辑记录号作为关键字)

     

    磁带文件的批处理过程可如下进行:

    待修改的原始文件称做主文件存放在一条磁带上

    所有的修改请求集中构成一个文件,称做事务文件,存放在另一台磁带上

    尚需第三台磁带作为新的主文件的存储介质

    =====================================================================================

    主文件按关键字自小至大(或自大至小)顺序有序

    事务文件必须和主文件有相同的有序关系

    因此,首先对事务文件进行排序,然后将主文件和事务文件归并成-一个新的主文件

    图12.3为这个过程的示意图

    在归并的过程中,顺序读出主文件与事务文件中的记录比较它们的关键字并分别进行处理

    对于关键字不匹配的主文件中的记录,则直接将其写人新主文件中

    “更改”和“删去”记录时,要求其关键字相匹配

    “删去”不用写人

    “更改”则要将更改后的新记录写入新主文件

    “插人”时不要求关键字相匹配,可直接将事务文件.上要插入的记录写到新主文件的适当位置

    =====================================================================================

    例如有一个银行的账目文件:

    主文件保存着各储户的存款余额;

    每个储户作为一个记录,储户账号为关键字;记录按关键字从小到大顺序排列

    一天的存人和支出集中在一个事务文件中,事务文件也按账号排序

    成批地更改主文件并得到一个新的主文件

    其过程如图12.4所示

     

    六:索引文件

    1.定义

    除了文件本身(称做数据区)之外

    另建立--张指示逻辑记录和物理记录之间一一对应关系的表一索引表

    这类包括文件数据区索引表两大部分的文件称做索引文件

    2.图解

    图12. 5所示为两个索引表的例子

    索引表中的每一项称做索引项

    论主文件是否按关键字有序,索引表中的索引项总是按关键字(或逻辑记录号)顺序排列

    3.索引顺序文件&索引非顺序文件

    若数据区中的记录也按关键字顺序排列,则称索引顺序文件

    反之,若数据区中记录不按关键字顺序排列,则称索引非顺序文件

    4.特点

    索引表是由系统程序自动生成的

    在记录输人建立数据区同时建立一个索引表

    表中的索引项按记录输人的先后次序排列

    待全部记录输入完毕后再对索引表进行排序

     

    例如,对应于图12.6(a)的数据文件

    索引表如图12.6(b)所示

    而图12.6(c)为文件记录输人过程中建立的索引表

    5.检索

    (1)检索方式

    索引文件的检索方式直接存取或按关键字(进行简单询问)存取

    检索过程和第9章讨论的分块查找相类似

     

    分两步进行:

    首先,查找索引表,若索引表上存在该记录,则根据索引项的指示读取外存上该记录

    否则说明外存上不存在该记录,也就不需要访问外存

    由于索引项的长度比记录小得多,通常可将索引表-次读入 内存

    由此在索引文件中进行检索只访问外存两次

    一次读索引,一-次读记录

    并且由于索引表是有序的;则查找索引表时可用折半查找法

    (2)索引文件的修改更新

    索引文件的修改也容易进行

    删除-个记录时,需删去相应的索引项

    插人-一个记录时,应将记录置于数据区的末尾

    同时在索引表中插人索引项

     

    更新记录时,应将更新后的记录置于数据区的末尾,同时修改索引表中相应的索引项

     

    当记录数目很大时,索引表也很大,以致-一个物理块容纳不下

    在这种情况下查阅索索引表需占用3个物理块的外存,每一个物理块容纳3个索引

    则建立的查找表如图12.7所索引表需占用3个物理块的外存

    检索记录时,查找查找表,查索引表,然后读取记录

    3次访向外存即可。若查找表中项目还多,则可建立更高一级的索引

    通常最高可有四级索引:数据文件→索引表→查找表- +第二查找表- +第三查找表

    而检索过程从最高一级索引即第三查找表开始,需要5次访问

    上述的多级索引是一种静态索引,各级索引均为顺序表结构

    其结构简单,但修改很不方便,每次修改都要重组索引。因此,当数据文件在使用过程中记录变动较多时,应采用动态索引

    如二叉排序树(或二叉平衡树)、B树以及键树,这些都是树表结构,插人、删除都很方便

    又由于它本身是层次结构,则无需建立多级索引,而且建立索引表的过程即二叉排序树(或平衡树)作索引,其查找性能已在第9章中进行了详细讨论

    反之,当文件二叉排序树(或平衡树)作索引,其查找性能已在第9章中进行了详细讨论

    反之,当文件很大时,索引表(树表)本身也在外存,则查找索引时尚需多次访问外存,并且,访问外存的次数恰为查找路径.上的结点数。显然,为减少访问外存的次数,就应尽量縮减索引表的深度

    因此,此时宜采用m叉的B-树作索引表。m的选择取决于索引项的多少和缓冲区的大小。又,从“9. 2. 3/键树”的讨论可见,键树适用于作某些特殊类型的关键字的索引表

    和上述对排序树的讨论类似,当索引表不大时,可采用双链表作存储结构(此时索引表在内存);反之,则采用Trie树。总之,由于访问外存的时间比内存查找的时间大得多,所以.对外存中索引表的查找效能主要取决于访问外存的次数,即索引表的深度

    (3) 稠密索引&非稠密索引

    显然,索引文件只能是磁盘文件

    综上所述,由于数据文件中记录不按关键字顺序排列

    则必须对每个记录建立一个索引项

    如此建立的索引表称之为稠密索引,它的特点是可以在索引表中进行“预查找”,即从索引表便可确定待查记录是否存在或作某些逻辑运算

    如果数据文件中的记录按关键字顺序有序,则可对一组记录建立-一个索引项,这种索引表称之为非稠密索引

    它不能进行“预查找”,但索引表占用的存储空间少,管理要求低

     

    七:ISAM文件和VSAM文件

    1.ISAM文件

    (1)定义

    索引顺序存取方法ISAM为Indexed Sequential Access Methed的缩写,它是一种专为磁盘存取设计的文件组织方式

    由于磁盘是以盘组、柱面和磁道三级地址存取的设备

    则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引

    (2)文件结构示列

    文件的记录在同一盘组上存放时,应先集中放在一个柱面上

    然后再顺序存放在相邻的柱面上,对同一柱面,则应按盘面的次序顺序存放

    shi

    例如图12.8为存放在一个磁盘组上的ISAM文件

    (3)磁道索引项结构

    每个柱面建立一个磁道索引

    每个磁道索引项由两部分组成:基本索引项溢出索引项

    如图12.9所示,每一部分都包括关键字指针两项

    前者表示该磁道中最末一个记录的关键字(在此为最大关键字)

    后者指示该磁道中第-一个记录的位置

    (4)柱面索引

    柱面索引存放在某个柱面上,若柱面索引较大,占多个磁道,则可建立柱面索引的索引一主索引

    在ISAM文件上检索记录时,先从主索引出发找到相应的柱面索引

    再从柱面索引找到记录所在柱面的磁道索引

    最后从磁道索引找到记录所在磁道的第-一个记录的位置

    由此出发在该磁道上进行顺序查找直至找到为止

    反之,若找遍该磁道而不存在此记录,则表明该文件中无此记录

    例如,查找关键字为21的记录时的查找路径如图12. 8中的粗实线所示

     

    从图12.8中读者可看到,每个柱面上还开辟有-个滥出区

    并且,磁道索引项中有溢出索引项,这是为插人记录所设置的

    由于ISAM文件中记录是按关键字顺序存放的,则在插人记录时需移动记录

    并将同一磁道上最末一个记录移至溢出区,同时修改磁道索引项

    (5)溢出区3种设置方法

    通常溢出区可有3种设置方法:

    (1)集中存放一整个文件 设-一个大的单- - 的溢出区;

    (2)分散存放一每个柱 面设一个溢出区;

    (3)集中与分散相结合一溢 出时记录先移至每个柱面各自的溢出区,待满之后再使用共溢出区

    图12.8是第二种设置法

    (6)文件的插入和溢出处理

    每个柱面的基本区是顺序存储结构

    溢出区链表结构

    同一磁道溢出的记录由指针相链

    该磁道索引的溢出索引项中的关键字指示该磁道溢出的记录的最大关键字

    指针则指示在溢出区中的第一个记录

     

    图12.10所示为插人记录和溢出处理的具体例子

    其中(a)为插人前的某一柱面上的状态

    (b)为插入R.s时,将第二道中关键字大于65的记录顺次后移,且使Roo溢出至溢出区的情况

    (c)为插人Res之后的状态,此时2道的基本索引项的关键字改为80,且溢出索引项的关键字改为90

    其指针指向第4道第一个记录即Rgo;

    (d)是相继插人Ras和Ra后的状态,Ro。

    s插人在第3道的第一个记录的位置而使Rrs溢出。

    而由于80<83<90,则R被直接插人到溢出区,作为第2道在溢出区的第一个记录,

    并将它的指针指向Reo的位置,同时修改第2道索引的溢出索引项的指针指向Res。

    (7)柱面索的位置

    通常,磁道索引放在每个柱面的第一道上,那么,柱面索引是否也放在文件的第一个柱面上呢?由于每一次检索都需先查找柱面索引,则磁头需在各柱面间来回移动,我们希望磁头移动距离的平均值最小。假设文件占有n个柱面,柱面索引在第x柱面上。则磁头移动距离的平均值为:

    柱面索引应放在数据文件的中间位置的柱面上

     

    2.VSAM文件

    (1)定义

    虚拟存储存取方法VSAM是Virtual Storage Access Method的缩写

    这种存取方法利用了操作系统的虚拟存储器的功能,给用户提供方便

    对用户来说,文件只有控制区间控制区城等逻辑存储单位

    与外存储器中柱面、磁道等具体存储单位没有必然的联系

    用户在存取文件中的记录时,不需要考虑这个记录的当前位置是否在内存

    不需要考虑何时执行对外存进行“读/写”的指令

    (2)文件的结构示意图

    VSAM文件的结构如图12. 11所示。

    它由3部分组成:索引集、顺序集和数据集

    文件的记录均存放在数据集中

    数据集中的一个结点称为控制区间(Control Interval)它是一个I/O操作的基本单位,它由一组连续的存储单元组成

     

    控制区间的大小可随文件不同而不同

    但同一文件.上控制区间的大小相同

     

    每个控制区间含有一个或多个按关键字递增有序排列的记录

    顺序集和索引集一起构成- -棵B+树,为文件的索引部分

    顺序集中存放每个控制区间的索引项

    (3)控制区间的结构示意图

    每个控制区间的索引项由两部分信息组成:

    即该控制的一个结点,结点之间用指针相链结,而每个结点又在其上- -层的结点中建有索引,且逐的一个结点,结点之间用指针相链结,而每个结点又在其上- -层的结点中建有索引,且逐层向上建立索引

    所有的索引项都由最大关键字和指针两部分信息组成,这些高层的索引项形成B+树的非终端结点。因此,VSAM文件既可在顺序集中进行顺序存取,又可从最高层的索引(B+树的根结点)出发进行按关键字存取。顺序集中一个结点连同其对应的所有控制区间形成-个整体,称做控制区域(ControlRange)。每个控制区间可视为--个逻辑磁道,而每个控制区域可视为-一个逻辑柱面

    在VSAM文件中,记录可以是不定长的,则在控制区间中除了存放记录本身以外

    还有每个记录的控制信息(如记录的长度等)

    整个区间的控制信息(如区间中存有的记录数等)

    控制区间的结构如图12. 12所示。

    在控制区间上存取-一个记录时需从控制区间的.两端出发同时向中间扫描 

    (4)解决文件的溢出和插入

    VSAM文件中没有溢出区,解决插人的办法是在初建文件时留有空间

    -.是每个控制区间内不填满记录,在最末-个记录和控制信息之间留有空隙;

    二是在每个控制区域中有一些完全空的控制区间,并在顺序集的索引中指明这些空区间

    当插人新记录时,大多数的新记录能插人到相应的控制区间内

    但要注意为了保持区间内记录的关键字自小至大有序

    则需将区间内关键字大于插入记录关键字的记录向控制信息的方向移动

     

    若在若干记录插人之后控制区间已满,则在下一个记录插人时要进行控制区间的分裂

    即将近乎一半的记录移到同一控制区域中全空的控制区间中,并修改顺序集中相应索引

    倘若控制区域中已经没有全空的控制区间,则要进行控制区域的分裂

    此时顺序集中的结点亦在VSAM文件中删除记录时,需将同一控制区间中较删除记录关键字大的记录向前情况

     

    在VSAM文件中删除记录时,需将同一控制区间中较删除记录关键字大的记录向前移动

    空间留给以后插人的新记录。若整个控制区间变空,则需修改顺序集中相应的索引项

     

    由此可见,VSAM文件占有较多的存储空间,一般只能保持约75%的存储空间利用率

    但它的优点是:动态地分配和释放存储空间,不需要对文件进行重组,并能较快地对插人的记录进行查找

    查找一一个后插人记录的时间与查找一一个原有记录的时间是相同的

    为了作性能上的优化,VSAM用了一些其他的技术,如指针和关键字的压缩、索引的存放处理等

     

    八:直接存取文件【散列文件

    1.定义 

    直接存取文件指的是利用杂凑(Hash)法进行组织的文件

    类似于哈希表,即根据:

    文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上,故又称散列文件

    2.桶

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

    若干个记录组成一个存储单位,在散列文件中,这个存储单位叫做桶(Bucket)

     

    假若-一个桶能存放m个记录

    这就是说,m个同义词的记录可以存放在同一地址的桶中

    而当第m+1个同义词出现时才发生溢出”

    处理溢出也可采用哈希表中处理冲突的各种方法,但对散列文件,主要采用链地址法。

    3.处理溢出 【溢出桶-基桶

    当发生“溢出”时,需要将第m+1个同义词存放到另一个桶中

    通常称此桶为“溢出桶”;相对地,称前m个同义词存放的桶为“基桶”

    溢出桶和基桶大小相同,相互之间用指针相链接

    当在基桶中没有找到待查记录时,就顺指针所指到溢出桶中进行查找

    因此,希望同--散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远最好在同一柱面上

    4.直接存取文件示例

    例如,某一文件有18 个记录

    其关键字分别为278, 109 , 063, 930,589 ,184, 505 ,269 , 008 ,083,164, 215,330,810,620,110,384,355

    桶的容量m=3,桶数b=7。用除留余数法作哈希函数H(key)=key MOD 7

    由此得到的直接存取文件如图12. 13所示

    5.桶的容量和查找次数的关系 

    在直接文件中进行查找时,首先根据给定值求得哈希地址(即基桶号)

    将基桶的记录出桶的记录读人内存继续进行顺序查找,直至检索成功或不成功

    因此,总的查找时出桶的记录读人内存继续进行顺序查找,直至检索成功或不成功

    因此,总的查找时出桶的记录读人内存继续进行顺序查找,直至检索成功或不成功。

    因此,总的查找时间为:

    a为存取桶数的期望值(相当于哈希表中的平均查找长度),

    对链地址处理溢出来说,a=1+g;

    te为存取-个桶所需的时间;ti为在内存中顺序查找一个记录所需时间。

    a为装载因子,在散列文件中.

    n为文件的记录数,

    b为桶数,m为桶的容量。

    显然,增加m可减少a,也就使a减小,此时虽则使ti增大,但由于te>>ti,则总的时间T仍可减少

    图12.14 展示了a和a的关系。

    在直接存取文件中删除记录时,和哈希表一样,仅需对被删记录作--标记即可

    6.优缺点

    总之,直接存取文件的优点是:

    文件随机存放,记录不需进行排序

    插人、删除方便

    存取速度快

    不需要索引区,节省存储空间

     

    缺点是:

    不能进行顺序存取,只能按关键字随构不合理

    即溢出桶满而基桶内多数为被删除的记录此时亦需重组文件

    结构不合理,即溢出桶满而基桶内多数为被删除的记录

    此时亦需重组文件

     

    九:多关键字文件

    多关键字文件的特点是

    在对文件进行检索操作时,不仅主关键字进行简单询问

    经常需要对次关键字进行其他类型的询问检索

    1.多重表文件

    多重表文件(MultilistFile)的特点是:

    记录按主关键字的顺序构成-一个串联文件

    并建立主关键字索引(称为主索引)

     

    对每一个次关键字项建立次关键字索引(称为次索引)

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

    主索引为非稠密索引,次索引为稠密索引


     多重链表文件易于构造,也易于修改

    如果不要求保持链表的某种次序,则插人一个新记录是容易的

    此时可将记录插在链表的头指针之后

    但是,要删去一个记录却很繁琐,需在每个次关键字的链表中删去该记录

    2:倒排序文件

    倒排文件和多重表文件区别在于关键字索引的结构不同

    通常,倒排文件中的次关键字索引倒排表

    具有相同次关键字的记录之间不设指针相链

    而在倒排表中该次关键字的一项中存放这些记录的物理记录号

    解答,如询问“软件”专业的学生中有否选课程“乙”的

    则只要将“软件”索引中的记录号和“乙”索引中的记录号作求“交”的集合运算即可

    插人和删除记录时,倒排表也要作相应的修改

    值得注意的是倒排表中具有同--次关键字的记录号是有序排列的,则修改时要作相应移动

     

    若数据文件非串链文件,而是索引顺序文件(如ISAM文件),

    倒排表中应存放记录的主关键字不是物理记录号

     

    倒排文件的缺点维护困难

    在同一索引表中,不同的关键字其记录数不同

    各倒排表的长度不等,同--倒排表中各项长度也不等

    展开全文
  • 文件结构

    千次阅读 2016-04-05 22:59:13
    文件的结构 文件的逻辑结构  文件的逻辑结构一般分为两类,一类为流式... 记录式结构文件是由若干个记录组成,每个记录有一个键,可按键进行查找。记录式文件是有结构的文件。文件是一个固定长度记录的序列,每条
    文件的结构

    文件的逻辑结构

          文件的逻辑结构一般分为两类,一类为流式结构(流文件),一类为记录式结构。流式结构文件的基本构成单位是字符,文件是有逻辑意义的、无结构的一串字符的集合,是一个无结构的字节序列,如下图所示:




          记录式结构文件是由若干个记录组成,每个记录有一个键,可按键进行查找。记录式文件是有结构的文件。文件是一个固定长度记录的序列,每条记录有其内部结构,记录式文件图示如下:



    文件的物理结构

          文件的物理结构分为三种:顺序结构,链接结构和索引结构。
          顺序结构指一个文件的信息存放在若干连续的物理块中。其优点是简单,支持顺序存取和随机存取,顺序存取速度相对较快。缺点是文件不能动态增长,不利于文件插入和删除。其图示如下:




          链接结构指一个文件的信息存放在若干不连续的物理块中,各块之间通过指针连接,前一个物理块指向下一个物理块其优点是提高了磁盘空间利用率,不存在外部碎片问题,有利于文件插入和删除,有利于文件动态扩充。缺点是存取速度慢,不适于随机存取。其图示如下:




          索引结构指一个文件的信息存放在若干不连续物理块中,系统为每个文件建立一个专用数据结构--索引表,并将这些块的块号存放在一个索引表中。其优点是保持了链接结构的优点,又解决了其缺点,即能顺序存取,又能随机存取,满足了文件动态增长、插入删除的要求,也能充分利用外存空间。缺点是索引表本身带来了系统开销。其图示如下:



    展开全文
  • 1.6 文件系统总览2 文件逻辑结构3 文件目录结构 1 初识文件管理 文件——就是一组有意义的信息/数据集合 文件系统核心问题: 计算机中存放了各种各样的文件,一个文件有哪些属性? 文件内部的数据应该怎样组织起来...
  • 2、Linux系统保持UNIX文件系统的风格,提供流式文件界面,这种结构具有简洁灵活的特点,但并直接支持记录式文件和关键字检索。本实验是在Linux文件系统基础上,设计一组库函数,以提供对随机检索的支持。 实验内容...
  • 操作系统-文件结构以及文件管理

    千次阅读 2020-07-29 22:21:48
    文件的管理,文件结构有哪几种,文件类型,文件属性,文件常用的几种操作你都了解多少?
  • 1 文件文件系统 1.1 基本概念 文件实际上是对磁盘的抽象,是指一组带标识(即文件名)的、在逻辑上有完整意义的信息项的序列。
  • 文件的逻辑结构

    千次阅读 2020-07-25 08:59:06
    用户所看到的文件称为逻辑文件,它是由一系列的逻辑记录组成的。 文件的逻辑结构:这是从用户观点出发...在记录式文件中,每个记录都用于描述实体集中的一个实体。分为定长记录和变长记录。 定长记录:文件中所有记录的
  • 文件系统-文件的逻辑结构与存取方法 逻辑结构 字符流式的无结构文件 字符流的无结构文件中...记录式的有结构文件把文件中的基本信息(记录)按不同方式排列构成不同的逻辑结构,方便用户对文件中的记录进行修改...
  • TEXTFILE 文本格式文件(行存储)适用场景SequenceFile(二进制序列化文件)适用场景sequenceFile如何解决小文件问题RCFile(行列式文件)存储方式ORC(优化的行列式文件)存储方式适用场景Parquet适用场景 ...
  • 日志结构文件系统的设计与实现

    千次阅读 2017-12-06 22:34:34
    from The Design and Implementation of a Log-Structured File System——–Mendel Rosenblum...日志式文件系统将所有的更改以日志结构连续的写入磁盘,以这种方式来同时加速了文件写入和崩溃恢复。日志是磁盘的上
  • 文件结构及存取方法

    千次阅读 2016-10-11 12:42:22
    文件的组织形式是文件结构,从不同的角度分析文件有不同的结构形式:逻辑结构和物理结构。从用户角度出发,研究文件的抽象组织方式而定义的文件组织形式为文件的逻辑结构;从系统的角度出发,研究文件的物理组织...
  • Linux文件系统目录结构详解

    万次阅读 2017-10-08 13:09:34
    对于每一个Linux学习者来说,了解Linux文件系统的目录结构,是学好Linux的至关重要的一步.,深入了解linux文件目录结构的标准和每个目录的详细功能,对于我们用好linux系统只管重要,下面我们就开始了解一下linux...
  • Excel 文件结构化解析示例

    千次阅读 2020-11-26 11:48:22
    在数据分析业务中,经常要把Excel文件数据结构化解析以后再进行计算或导入关系数据库,但许多Excel文件的格式并规整,而且文件结构也多种多样,导致编程进行结构化的工作量会比较大,而且很难通用,每次都要针对...
  • 参考文章:行存储和列存储优缺点和paruqet文件结构 一、列存储和行存储的比较 列存储和行存储是针对数据在存储介质中的排序形式而言的,假设存在一张table,那么: 行存储:依次连续存储第1、2、3...
  • 文件的逻辑结构总结

    千次阅读 2016-10-16 21:57:12
    文件的逻辑结构总结@(OS)逻辑结构:从用户观点出发看到的文件的组织形式,是用户可以直接处理的数据及其结构。独立于文件的物理特性。也称为文件组织。 物理结构:从实现的角度出发,OS看到的文件的存储结构。是...
  • 文件管理 文件也属于系统资源,其就是一组有意义的信息、数据集合。 计算机中存放了各种各样的文件: 一个文件具有哪些属性? 文件内部的数据应该被怎样组织起来? 文件之间又应该怎么组织起来? 从下往上看...
  • MySQL目录结构以及配置文件详解

    万次阅读 多人点赞 2018-01-03 12:42:46
    昨天给大家进行了数据库介绍,今天将正式带领大家进入我们的课题MySQL讲解部分,首先给大家介绍一下MySQL安装后的目录结构和配置文件详解。 一、MySQL的目录结构  1、bin目录  用于放置一些可执行文件,...
  • 关键词:文件系统、文件的逻辑/物理结构与存取方法、连续文件、串联文件、索引文件 —— 样例 ⭐️⭐️⭐️、文件顺序存储/直接存储设备、空闲区表法、空闲链表法、位示图法、文件目录、文件控制块和索引结点、文件...
  • 常见文件系统解析

    千次阅读 2017-08-05 15:41:17
    文件系统是操作系统用于明确存储设备(常见的是磁盘,也有基于NAND Flash的固态硬盘)或分区上的文件的方法和数据结构;即在存储设备上组织文件的方法。操作系统中负责管理和存储文件信息的软件机构称为文件管理...
  • VTD的文件结构和Project建立的思路

    千次阅读 2019-04-19 17:40:36
    智能驾驶仿真软件VTD的学习资料较少,新建了一个QQ群:993708460,加群前请私聊群主(QQ:2059799865)加入。...该软件目前国内极少有人或者企业使用,现将使用过程中的心得记录下来。 学习任...
  • (一)文件层次结构 现代操作系统有多种文件系统类型(如FAT32、NTFS、 ext2、ext3、ext4等),因此文件系统的层次结构也不尽相同。图4-11是一种合理的层次结构。   图4-11文件系统层次结构 1) 用户调用接口 ...
  • Hive学习(四):Hive文件存储结构

    千次阅读 2022-01-06 16:29:30
    Hive支持多种文件的存储结构,以对应不同的场景,Hive通过在创建表时的sorted as来指定文件结构。 基础知识 对于一张表数据的存储 id name sex 1 张三 男 2 李四 女 行存储 以一行...
  • mp4文件结构

    千次阅读 2016-12-03 16:17:19
    一、基本概念 ...MP4文件中的所有数据都装在box(QuickTime中为atom)中,也就是说MP4文件由若干个box组成,每个box有类型和长度,可以将...box中可以包含另一个box,这种box称为container box。一个MP4文件首先
  • 文件系统(一)---文件系统基础知识

    千次阅读 2022-03-28 22:52:56
    前面主要是学习linux进程管理的调度,其细节越来越多,结合目前移动设备,其调度算法越来越复杂,涉及到芯片涉及,电源管理,多核负载等,这块内容暂时告一段落,本章正式进入到文件系统的学习。 现在的磁盘是具有大...
  • 【操作系统】文件的逻辑结构

    千次阅读 2017-12-04 19:38:16
    文件的逻辑结构总结@(OS)逻辑结构:从用户观点出发看到的文件的组织形式,是用户可以直接处理的数据及其结构。独立于文件的物理特性。也称为文件组织。 物理结构:从实现的角度出发,OS看到的文件的存储结构。是...
  • 操作系统之文件管理

    千次阅读 多人点赞 2020-09-22 03:05:15
    一、文件文件系统 1.1 文件是什么 文件是对磁盘的抽象 所谓文件是指一组带标识(标识即为文件名)的、在逻辑上有完整意义的信息项的序列。 信息项:构成文件内容的基本单位(单个字节,或多个字节),各信息项...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 246,080
精华内容 98,432
关键字:

常见的记录式结构文件不包括