精华内容
下载资源
问答
  • 常见的文件物理结构包括
    千次阅读
    2020-07-09 18:04:38

    1、顺序结构

    优点:
    结构简单,实现容易,顺序存取速度快。
    缺点:
    1、用户创建文件时要给出文件的大小;
    2、不利于文件的动态增加和修改;
    3、对每个文件要求存放在存储介质上的

    2、链接文件

    优点:
    1、提高了磁盘空间利用率,不存在外部碎片问题
    2、不必事先知道文件长度
    3、文件动态扩充和修改容易
    4、顺序存取效率高
    缺点:
    1、不适于随机存取,随机存取效率太低,
    2、链接指针占用一定的空间
    3、可靠性问题,如指针出错

    3、索引结构

    优点:
    1、保持了链接结构的优点,又解决了其缺点
    2、即能顺序存取,又能随机存取
    3、满足了文件动态增长、插入删除的要求
    4、能充分利用外存空间
    缺点:
    索引表本身带来了系统开销,如:内外存空间,存取时间

    4、直接文件

    优点:
    把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。
    缺点:
    不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,要处理“冲突”问题。

    更多相关内容
  • 文件物理结构

    千次阅读 2021-04-08 23:35:23
    将文件数据按照某种规则或以某种数据结构存储在磁盘中,即文件在磁盘中实际存在的物理状态,就是通常所说的文件物理结构。不难想到,若文件物理结构能让我们在存、取数据时更加方便快捷,就是一个好的物理结构。当然...

    文件的物理结构

    一、概述

    1. 什么是文件的物理结构

    这要从操作系统的功能引入,我们都知道,操作系统是最接近硬件的系统软件,操作系统的功能之一就是对外设—磁盘的管理,而磁盘中通常存储了一系列文件数据,因此,磁盘管理之一就是怎样将文件数据在磁盘中分配、组织起来的问题

    2. 讨论文件物理结构的目的

    将文件数据按照某种规则或以某种数据结构存储在磁盘中,即文件在磁盘中实际存在的物理状态,就是通常所说的文件物理结构。不难想到,若文件物理结构能让我们在存、取数据时更加方便快捷,就是一个好的物理结构。当然了,万物皆有适用定律,这点我们将在下面讨论。

    二、文件物理结构的分类概述

    下图为文件物理结构的分类

    在这里插入图片描述
    在具体讨论这几种组织方式之前,我们先列出一些文件组织方式的中基本问题,以便能够更加清楚的说明文件物理结构的本质。

    1. 文件块

    文件块也称为“磁盘块”,类似于内存分页的概念,磁盘中的存储单元被划分为了一个个“块/磁盘块/文件块”。内存与磁盘之间的数据交换,即读/写操作、磁盘I/O,都是以“块”为单位进行的,即每次读入一块,或每次写出一块。该过程如下图所示:
    在这里插入图片描述

    2. 文件的逻辑块

    在计算机中,物理–逻辑是一对相对的词,逻辑是从用户的视角,将文件中数据按照怎样的方式组织起来,我们熟悉的数据结构就是逻辑上的概念。相对地,物理是从操作系统或硬件的角度,文件数据在磁盘中的实际存储位置。

    在这里插入图片描述上图左侧为文件的逻辑块划分,逻辑块0被存储在物理块4中,逻辑块1被存储在物理块N中。这种从逻辑地址到物理地址的映射实值上对用户是不透明的,即由操作系统负责实现从文件逻辑地址到物理地址的映射

    三、文件物理结构的详细解释

    本部分对上述三种:连续分配、链式分配、索引分配的原理进行详细的说明。

    1. 连续分配方式

    (1)核心思想—文件在磁盘占有一组连续的块。

    逻辑上相邻的块在物理上也一定是相邻的,如下图所示,文件aaa的三个相邻的逻辑块,映射的3个物理块也一定是相邻的。
    在这里插入图片描述
    (2)逻辑块到物理块的转变

    物理块号=起始块号+逻辑块号:

    (3)连续分配的优缺点
    优点

    • 连续分配可以实现顺序分配和随机访问
    • 顺序读写时速度最快
    • 缺点

    2. 链式分配方式

    链式分配采取离散分配的方式,为文件分配离散的磁盘块。又分为隐式链接显式链接两种。

    2.1 隐式链接

    (1)核心思想:隐式链接就像我们熟知的链表数据结构,除最后一个盘块,每个磁盘块中都有指向下一磁盘块的指针,文件目录包含文件第一块的指针个最后一块的指针。

    在这里插入图片描述(2)逻辑块到物理块的转变
    用户给出要访问的逻辑块号i,操作系统找到该文件对应的目录项(FCB),从目录项中找到起始块号(即0号块),将0号逻辑块读入内存,由此知道1号逻辑块存放的物理块号,于是读入1号逻辑块,再找到2号逻辑块的存放位置…以此类推。因此,访问i号逻辑块,总共需要i+1此磁盘I/O
    (3)隐式链接分配的优缺点

    优点

    • 方便文件拓展,不会有碎片,外存利用率高。
      缺点
    • 隐式链接分配只支持顺序访问,不支持随机访问,查找效率低。
    • 指向下一个盘块的指针也需要耗费少量的存储空间。

    2.2 显示链接

    (1)核心思想
    把用于链接文件个物理块的指针显示地存放在一张表中。即,文件分配表(File Allocation Table)。
    在这里插入图片描述假设某个文件“aaa”依次存放在磁盘块2-5-0-1,在文件分配表中,以数组模拟链表,显示地存储了各物理块号之间的顺序,且用-1表示文件的结尾。
    注意:一个磁盘仅设置一张FAT。开机时,将FAT读入内存,并常驻内存。FAT的各个表项在物理上连续存储,且每一个表项的长度都相同,因此,“物理块号”字段可以是隐藏的。可以说,显示链接用数组模拟实现了隐式链接中各个物理块之间的链接关系。

    (2) 文件逻辑块号到物理块号的转变

    用户给出想要访问的逻辑块号i,操作系统找到该文件对应的目录项(FCB)…
    从目录项中找到起始块号,若i>0,则查询内存中的文件分配表FAT,往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。
    (3) 显示链接的优缺点

    优点

    • 不会有外部碎片,很方便文件拓展。
    • 外存利用率高,并且支持随机访问。
    • 相较于隐式链接,地址转换不需要访问磁盘,因此文件的访问效率更高。
      缺点
    • 文件分配表需要占用一定的存储空间。

    3.索引分配

    (1)核心思想

    索引分配允许文件离散地分配在各个磁盘中,系统会为每个文件建立一张索引表,索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能记类似于内存管理中的页表–建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块成为索引快,文件数据存放的磁盘块成为数据块。
    在这里插入图片描述

    假设某个文件“aaa”的数据依次存放在磁盘块2-5-13-9。7号磁盘块作为文件“aaa”的索引快,索引块中保存了索引表的内容。由于索引块是存放在磁盘中,文件目录需要指明文件的索引块是几号磁盘
    在前面的显式链接分配中,文件分配表左侧以各个磁盘中,物理块号的地址由小到大的顺序列出,因此,显示链接是一个磁盘对应一个FAT,而在索引分配中,如上图,一个索引针对一个文件,即一个文件对应一个索引表

    (2)索引分配中逻辑块号到物理块号的转变

    用户给出要访问的逻辑块号i,操作系统找到该文件对应的目录项(FCB),从中找到索引块的块号,即索引表的存放位置,将索引表从外存读入内存,并查找索引表,即可知道该逻辑块在外存中的存放位置。

    (3)索引分配的优缺点

    优点

    • 支持随机访问,文件拓展容易;
      缺点
    • 索引表需要占用一定的存储空间

    (4)索引分配的进一步探讨

    索引表是存放在磁盘中的,考虑这样一种情况:若每个磁盘块1KB,一个索引表项4B,则一个磁盘块只能存放256个索引项。如果一个文件的大小超过了256块,那么一个磁盘块是装不下文件的整张索引表的,如何解决这个问题?

    方案一:链接方案

    索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。
    在这里插入图片描述假设磁盘块大小为1KB,一个索引表项占4B,则一个磁盘块只能存放256个索引项。
    这样的处理方式不可避免的引入了链接的缺点-即无法随机访问,假设想要访问最后一个逻辑块,就必须找到最后一个索引块,而各个索引快之间是用指针链接起来的,因此必须先顺序地读入前255个索引块。这显然是很低效的。

    方案二:多层索引

    多层索引解决了链接方案的低效问题,其原理类似于多级页表。使第一层索引块指向第二层索引块。还可以根据文件大小的要求再建立第三层、第四层索引块。
    在这里插入图片描述假设磁盘块大小为1KB,一个索引表项占4B,则一个磁盘块只能存放256个索引项。

    • 若某文件采用两层索引,则该文件的最大长度可以达到2562561KB=65,546KB=64MB
      可根据逻辑块号算出应该查找索引表中的哪个表项。如:
      要访问1026号逻辑块,则1026/256=4, 1026%256=2
      因此可以先将一级索引表掉入内存,查询4号表项,将其对应的二级索引表调入内存,再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。访问目标数据块,需要3次磁盘I/O
    • 若采用三层索引,则文件的最大长度为256256256*1KB=16GB。此时访问数据块,需要4次磁盘I/O。
      结论:采用K层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要K+1次磁盘操作。
    方案三:混合索引

    混合索引是多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。

    我在学习的过程中感到这部分是方案一和方案二的套娃操作,就不再用文字记录了。

    四、结论

    将顺序分配、链接分配、索引分配方法的优缺点,总结于下表:

    在这里插入图片描述

    以上内容为本人学习文件物理结构的总结,欢迎指正!!

    展开全文
  • 一、文件物理结构文件实现) (一)文件块、磁盘块(二)文件分配方式1. 连续分配 连续分配 方式要求 每个文件在磁盘上占有一组连续的块 优点 :支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序...

    一、文件的物理结构(文件实现)

    在这里插入图片描述
    在这里插入图片描述

    (一)文件块、磁盘块

    在这里插入图片描述
    在这里插入图片描述

    (二)文件分配方式

    1. 连续分配

    • 连续分配 方式要求 每个文件在磁盘上占有一组连续的块
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 优点 :支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序访问时速度最快
    • 缺点 :不方便文件拓展;存储空间利用率低,会产生磁盘碎片

    2. 链接分配

    • 链接分配 采取离散分配的方式,可以为文件分配离散的磁盘块。分为 隐式链接显式链接 两种。

    (1)隐式链接

    • 隐式链接 ——除文件的最后一个盘块之外,每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针
      在这里插入图片描述
      在这里插入图片描述
    • 是否方便拓展文件?
    • 若此时要拓展文件,则可以随便找一个空闲磁盘块,挂到文件的磁盘块链尾,并修改文件的FCB
    • 优点:很方便文件拓展,不会有碎片问题,外存利用率高
    • 缺点:只支持顺序访问,不支持随机访问,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。
    • 考试题目中遇到未指明隐式/显式的“链接分配”,默认指的是隐式链接的链接分配

    (2)显示链接

    • 把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表(FAT,File Allocation Table)
      在这里插入图片描述
    • 假设某个新创建的文件“aaa”依次存放在磁盘块 2 →5 →0 →1
    • 假设某个新创建的文件“bbb”依次存放在磁盘块 4 →23 →3
    • 注意:一个磁盘仅设置一张FAT。开机时,将FAT读入内存,并常驻内存。 FAT 的各个表项在物理上连续存储,且每一个表项长度相同,因此“物理块号”字段可以是隐含的。
      在这里插入图片描述
    • 优点:很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高。
    • 缺点 :文件分配表的需要占用一定的存储空间。

    (二)索引方式

    • 索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表,索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块
      在这里插入图片描述
    • 如何实现文件的逻辑块号到物理块号的转换?
      ①、用户给出要访问的逻辑块号 i,操作系统找到该文件对应的目录项(FCB)…
      ②、从目录项中可知索引表存放位置,将索引表从外存读入内存,并查找索引表即可只 i 号逻辑块在外存中的存放位置。
      ③、可见,索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配一个空闲块,并增加一个索引表项即可)但是索引表需要占用一定的存储空间
    • 若每个磁盘块1KB,一个索引表项4B,则一个磁盘块只能存放 256 个索引项。
    • 如果一个文件的大小超过了256块,那么一个磁盘块是装不下文件的整张索引表的,如何解决这个问题?
      ①链接方案;②多层索引;③混合索引;

    1. 链接方案

    • 链接方案:如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。
      在这里插入图片描述

    2. 多层索引

    • 多层索引:建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
    • 采用 K 层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要 K + 1 次读磁盘操作.
      在这里插入图片描述

    3. 混合索引

    • 混合索引 :多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表) 。
      在这里插入图片描述
    • 这种结构的索引支持的最大文件长度为65800KB
    • 若顶级索引表还没读入内存
      ①、访问0~7号逻辑块:两次读磁盘;
      ②、访问8~263:三次读磁盘;
      ③、访问264~65799:四次读磁盘;
    • 对于小文件来说,只需较少的读取磁盘次数就可以访问目标数据块。(一般计算机中小文件更多)

    • 超级超级超级重要考点
      ①要会根据多层索引、混合索引的结构计算出文件的最大长度(Key:各级索引表最大不能超过一个块);
      ②要能自己分析访问某个数据块所需要的读磁盘次数(Key:FCB中会存有指向顶级索引块的指针,因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。
    • 另外,要注意题目条件——顶级索引块是否已调入内存
      在这里插入图片描述

    展开全文
  • 文件物理结构(附脑图)

    千次阅读 多人点赞 2020-05-23 11:48:46
    大多数在字符设备上传输的信息可作为连续文件看待。这种文件的信息是按线性为序存取的,这种方法在大多数磁带系统中常使用...磁盘的结构允许文件管理系统按三种不同的方法组织文件:连续文件、串联文件、随机文件结构

    文件的物理结构涉及文件在文件存储器上的安排。文件结构表示了一个文件在辅存上的安置、链接和编目的方法。它和文件的存取方法以及辅存设备的特性等都有密切的关系。因此,在确定一个文件的结构时,必须考虑到文件的大小、记录是否定长、访问的频繁程度和存取方法等。

    大多数在字符设备上传输的信息可作为连续文件看待。这种文件的信息是按线性为序存取的,这种方法在大多数磁带系统中常使用,是比较简单的文件结构。磁盘存储设备上具有较为复杂的文件组织。在磁盘表面按径向缩减的一组同心圆称为磁道(track) ,每一个磁道又可进一步分为扇区(sector) 。在磁盘系统中被转换的最小信息单位通常是一个扇区(或称为块)。磁盘的结构允许文件管理系统按三种不同的方法组织文件:连续文件、串联文件、随机文件结构

    在这里插入图片描述

    1. 连续文件(数组结构)

    连续文件结构是由一组分配在磁盘连续区域的物理块组成的。连续文件存放到磁盘的连续的物理块上,若连续文件的逻辑记录大小正好与磁盘的物理块大小一样大(都为512B),那么一个磁盘块存放一个逻辑记录,而且存放连续文件的磁盘块号是连续的。连续文件的第一个逻辑记录所在的磁盘块号记录在该文件的文件目录项中,该目录项还需记录共有多少磁盘块。连续文件结构如图1所示。

    图1 连续文件结构

    图1中表示一个连续文件A,它由三个记录组成,这些记录被分配到物理块号为100、101、 102的相邻物理块中,这里假定文件的逻辑记录和物理块的大小是相等的(当然也可以是一个物理块包括几个逻辑记录或一个逻辑记录占有几个物理块)。对于这种文件结构,存取块中的一个记录是非常简单的。若给定记录号为 r r r,记录长度为 I I I,物理块大小为 s i z e size size,则相对块号计算为 b = I ∗ r / s i z e b=I*r/size b=Ir/size.

    连续文件结构的基本优点是在连续存取时速度较快,如果文件中第n个记录刚被存取过,而下一个要存取的是n+1个记录,则这个存取操作将会很快完成。当连续文件在顺序存取设备(或称为单一存储设备,如磁带)上时, 这一优点是很明显的。所以,存于磁带上的记录一般均采用连续结构。如果是直接存取设备(或称为多路存储设备,如磁盘),在多道程序情况下,由于其他用户可能驱使磁头移向其他柱面,因而就会降低这一优越性。所以,对于磁盘、磁鼓可以采用连续结构,也可采用非连续结构(后者更为好些)。

    对于顺序处理的情况,顺序文件结构是一种最经济的结构方式。连续文件结构对于变化少、可以作为一个整体处理的大量数据段较为方便,而对那些变化频繁的少量记录不宜采用。而且,对于连续文件结构来说,其文件长度一经固定便不易改变,因而不利于文件的增生和扩充。

    2.串联文件

    2.1 串联文件结构(链表结构)

    串联文件结构是按顺序由串联的块组成的,即文件的信息按存储介质的物理特性存于若干块中,一块中可包含一个逻辑记录或多个逻辑记录,也可以是若干物理块包含一个逻辑记录。每个物理块的最末一个字(或第一个字)作为链接字,它指出后继块的物理地址。文件的最后一块的链接字为结束标记“ ∧ \land ”,它表示文件至本块结束。串联文件结构如图2所示,一个文件A有三个记录,分别分配到100、150、 57号物理块中,它的第一个物理块号由该文件的文件目录项指出。

    图2 串联文件结构

    串联文件采用的是一种非连续的存储结构,文件的逻辑记录可以存放到不连续的物理块中,能较好地利用辅存空间。另外,还易于对文件进行扩充,即只要修改链接字就可将记录插入到文件中间或从文件中删除若干记录。

    串联文件结构虽比较易于修改,但由于要存放链指针而需要一定的存储空间。对这类文件的存取都必须通过缓冲区,待得到链接字后才能找到下一个物理块的地址。所以,串联文件只适用于顺序存取方式,而不适用于直接存取方式。因为在直接存取时为了找到一个记录,文件必须从文件头开始一块一块查找,直到所需的记录被找到。

    2.2 文件映照结构(静态链表结构)

    在文件映照结构中,系统有一个文件映照图(以磁盘块号为序),图中每一个表项用来记录磁盘块号。每个文件的文件目录项中,用于描述文件物理结构的表项指向文件映照图中的某个位置,其内容为该文件的第一块, 其后的各块,在文件映照图中依次勾链,文件的最后一块用尾标记表示。文件映照结构如图3所示。其中,文件A占据了磁盘的第3、6、4和8块。

    图3 文件映照结构

    文件映照结构如同串联文件(块链接法) 一样,顺序存取时较快。文件映照图一般较大,不宜保存在主存中,因此,通常将其本身作为一个文件保存在磁盘中,需要时再每次送一块到主存在最坏的情况下,也可能要把文件映照图全部读入主存,才能找到一个文件在磁盘中的所有物理块。仅当表示文件的物理块的一些单元恰好在文件映照图的同一块中时,才能降低开销。由此可见,把每个文件所占的空间尽量靠近显然是有利的,而不应该将文件散布在整个磁盘上。

    Windows系统的文件分配表( 即FAT表)是通过一一个链接列表(即文件映照结构)来
    实现的。FAT是一个包含N个整数的列表,N是存储设备上最大的簇数(磁盘上最小可寻址存储单元称为扇区,通常每个扇区为512个字节(或字符)。由于多数文件比扇区大得多,因此如果对一个文件分配最小的存储空间,将使存储器能存储更多数据,这个最小存储空间即称为簇)。表中每个记录的位数称为FAT大小,是12、16或32三个数之一。感兴趣的读者可查阅有关的资料。

    3. 随机文件

    随机文件组织是实现非连续分配的另一种方案。在随机文件结构中,数据记录存放于直接存取型存储设备(如磁盘、光盘)上, 数据记录的关键字与其地址之间建立某种关系。随机文件的记录就是按这种关系排列、分布的,并利用这种关系进行存取。.有三种形式的随机文件结构:直接地址结构计算寻址结构索引结构。索引结构在第4节讨论。

    3.1 直接地址结构

    当知道某个记录的地址时,可直接使用这个地址进行存取。这意味着,用户必须知道每个记录的具体地址,这是很不方便的。因此,直接地址结构并不常用。当然在使用这种结构时,存取效率是最高的,因为不需要进行任何“查找”。在某些数据库系统中的“数据库码”,就是采用这种结构。

    3.2 计算寻址结构—— 散列文件

    在计算寻址结构方法中,记录的关键字经过某种计算处理,转换成相应的地址。这种计算方式就是通常所说的散列(hash, 也称为“杂凑”)。如果用以标识记录的关键字与记录地址之间存在一种直接关系,那么,利用这种关系实现记录存取的文件称为散列文件。

    这种直接关系是通过关键字的变换来建立的。由于一般情况下,地址的总数比可能的关键字的值的总数要小得多,即不会是一对一的关系,因此不同的关键字在计算之后,可能会得出相同的地址,称为“冲突”。一种散列算法是否成功的一个重要标志,是看其将不同的关键字映射到同一地址的几率有多大,这个几率越小,则此散列算法的性能越好,即“冲突”产生的几率越小越好。

    散列算法的基本思想是根据关键字来计算相应记录的地址,所以必须解决如下两个问题:其一,寻找一个hash函数h(k)实现关键字到地址的转换;其二,确定解决冲突的办法。

    常用的散列算法如下。

    • 截段法,截取关键字的某一指定部分作为地址。这里之所以截段是为了缩小关键字的数值范围,且截取时应选择随机性较好的段。
    • 特征位抽取法,抽取关键字数码串的某些位并将其连接起来作为地址。这种方法既可起到缩小关键字数值范围的作用,又能更灵活有效地选择那些随机性较好的数位。
    • 除余法,把标识符除以某一数而取其余数作为地址。使用这种方法时,除数的选择很重要。例如,除数的大小可保证变换所得的地址范围落在给定的存储区内,而除数的性质与关键字的变换结果在存储区的分布及冲突情况多少密切相关。在许多情况下,选用质数作为除数
    • 折叠法,把关键字数码串分段,然后叠加起来作为地址。有时,还可把折叠后的结果再折叠。
    • 平方取中法,把关键字平方后取其结果的中间部分作为地址。

    以上列举了五种变换方法,变换的方法形形色色,在此不再一一列举。但值得注意的是,不同的变换方法应针对不同情况加以选择。因为每一种变换方法都有自己的特点,一个独立变换对于关键字集合来说,在任何情况下总是好的这种情况并不存在。相对而言,在大部分情况下,除余法比别的办法好。

    4. 索引文件

    4.1 索引文件结构

    为了能随机地访问文件的任何一部分,构造了索引文件。这种文件将逻辑文件顺序地划分成长度与物理存储块长度相同的逻辑块,然后为每个文件分别建立逻辑块号与物理块号的对照表。这张表称为该文件的索引表。用这种方法构造的文件称为索引文件。索引文件的索引项按文件逻辑块号顺序排列,而分配到的物理块号可以是不连续的。例如,某文件A有四个逻辑块,分别存放在物理块23、19、26、29中,该索引文件结构如图4所示。

    图4 索引文件结构

    索引文件在存储区中占两个区:索引区数据区。索引区存放索引表,数据区存放数据文件本身。访问索引文件需要两步操作。第一步是查文件索引,由逻辑块号查得物理块号:第二步是由此物理块号而获得所要求的信息。这样做需两次访问文件存储器。如果文件索引表已经预先调入主存,则只要一次访问就行了。

    索引文件的优点是可以直接读写任意记录,而且便于文件的增删。当增加或删除记录时,应对索引表及时加以修改。由于每次存取都涉及索引表的查找,因此,所采用的查找策略对文件系统的效率有很大的影响。通常使用的查找策略有二分查找和顺序扫描两种。

    4.2 索引表的组织

    如果索引文件比较大,索引表项也就比较多,若按顺序表组织,索引表就会较长,查找不便。索引表的组织对文件系统的效率有很大的影响。下 面讨论三种索引表的组织结构。

    1. 直接索引

    • 直接索引结构。在文件目录项中有一组表项用于索引,每一个表项登记的是逻辑记录所在的磁盘块号。直接索引文件的结构如图5 (图中的逻辑记录号实际上可以省略)所示。

    图5 直接索引结构

    • 直接索引结构文件大小的计算。在直接索引结构中,文件目录项中用于索引的表项数目决定了文件最大的逻辑记录数,设表项数目为 n n n,逻辑记录大小为 512 B 512B 512B,则所允许的文件最大的字节数是 n ∗ 512 B n*512B n512B。在图5所示的直接索引结构中, n = 4 n=4 n=4, 逻辑记录大小为 512 B 512B 512B,则所允许的文件最大的字节数是 4 ∗ 512 B 4*512B 4512B为了突破这一限制,提出了一级间接索引结构。

    2. 一级间接索引

    在一级间接索引结构中,利用磁盘块作为一级间接索引表块。若磁盘块的大小为
    512B,用于登记磁盘块号的表项占用2B,这样,一个磁盘块可以登记256个表项。

    • 一级间接索引。文件目录项中有一组表项,其内容登记的是第一级索引表块的块号。第一级索引表块中的索引表项登记的是文件逻辑记录所在的磁盘块号。

    图6 一级间接索引结构

    • 一级间接索引结构文件大小的计算。在一级间接索引结构中,若文件目录项中用于索引的表项数目为,逻辑记录大小为 512 B 512B 512B,则所允许的文件最大的字节数是 n ∗ 256 ∗ 512 B ( n ∗ 512 B 2 B ∗ 512 B ) n*256*512B(n*\frac{512B}{2B}*512B) n256512B(n2B512B512B)。如图6所示的一级间接索引结构中, n = 4 n=4 n=4, 逻辑记录大小为 512 B 512B 512B,则所允许的文件最大的字节数是 4 ∗ 256 ∗ 512 B 4*256*512B 4256512B.为了进一步扩大文件的大小,增强文件系统的能力又提出了二级间接索引结构。

    3. 二级间接索引

    • 二级间接索引。文件目录项中有一组表项,其内容登记的是第二级索引表块的块号。第二级索引表块中的索引表项登记的第一级索引表块的块号,第一级索引表项中登记的是文件逻辑记录所在的磁盘块号。二级间接索引文件的结构如图7所示(注:图中,省略了索引表以及存放记录的磁盘块的块号,省略了逻辑记录号)。

    图7 二级间接索引结构

    • 二级间接索引结构文件大小的计算。在二级间接索引结构中,利用磁盘块作为一级间接和二级间接索引表块。每个磁盘块可以登记 256 256 256个表项。.在二级间接索引结构中,若文件目录项中用于索引的表项数目为 n n n,逻辑记录大小为 512 B 512B 512B,则所允许的文件最大的字节数是 n ∗ 25 6 2 ∗ 512 B ( n ∗ ( 512 B 2 B ) 2 ∗ 512 B ) n*256^2*512B(n*(\frac{512B}{2B})^2*512B) n2562512B(n(2B512B)2512B)。在图7所示的二级索引结构中,所允许的文件最大的字节数是 4 ∗ 25 6 2 ∗ 512 B 4*256^2*512B 42562512B.

    为了进一步增强文件系统的能力,还可以提出了三级间接索引结构。但必须注意到,随着索引级数的增加,虽然能表示的文件逻辑记录数目增加了,但要检索到一个记录所需时间也增加了。在UNIX系统中,采用的是一种改进的索引表,使UNIX文 件系统使用方便且十分有效。

    5. 文件物理结构比较

    文件的物理结构和存取方法与系统的用途和物理设备特性密切相关。比如,慢速字符设备和磁带上的文件应组织为连续文件,故应采用顺序存取方法。很显然,在磁带上组织索引文件或串联文件不太合适,因为来回倒带定位花费的时间开销太大。对于磁盘(鼓)那样的设备,可以有多种结构和存取方法。

    • 连续文件的特点。连续文件的优点是不需要额外的空间开销,只要在目录中指出起始块号和文件长度,就可以对文件进行访问,且一次可以读出整个文件。对于固定不变且要长期使用的文件(比如系统文件),这是一种较为节省的方法。连续文件存在如下缺点。

      • 不能动态增长。因为在它后面如果已记录了别的文件,则这一文件增长就可能破坏后一文件。如果后移下一个文件,则系统开销太大,甚至不可能。
      • 一开始就提出文件长度要求,而要用户预先提出文件较准确的长度不是太容易的。
      • 一次要求比较大的存储空间,不一定好找。因为,如果辅存上只有许多小的自由空间,虽然其总容量大于文件要求,但由于不连续,因而这些空间可能被浪费。
    • 串联文件的特点。串联文件的优点是:可以较好地利用辅存空间;易于文件扩
      充。顺序存取较为方便。但存在如下缺点。

      • 在处理文件时若要进行随机访问,需要花费较大的开销,在时间上比较浪费。
      • 对块链接而言,每个块中都要有链接字,所以要占用一定的存储空间。
    • 随机文件的特点。随机文件是一种比较好的结构,综合了,上述两种方法的优点,既能有效地利用存储空间,又能方便地直接存取。其中索引文件结构应用比较广泛。在实现索引结构时应考虑如何有效地存储和访问索引表,使文件系统既能支持足够大的文件、又能够保证系统的响应时间。

    展开全文
  • Oracle数据库的物理结构介绍

    千次阅读 2021-05-02 02:50:44
    1、物理结构(由控制文件、数据文件、重做日志文件、参数文件、归档文件、口令文件组成)一个数据库中的数据存储在磁盘上物理文件,被使用时,调入内存。其中控制文件、数据文件、重做日志文件、跟踪文件及...
  • 一、文件物理结构 文件物理结构又称为文件的存储结构,它是指文件在外存上的存储组织形式,是与存储介质的存储性能有关。常用的物理结构有连续文件结构、串联文件结构、索引文件结构三种。 二、文件的三种...
  • Oracle的物理存储结构

    千次阅读 2021-05-05 01:13:01
    Oracle的物理存储结构:Oracle物理存储结构主要包括三种类型的物理文件,分别是数据文件(*.dbf),控制文件(*.ctl)和重做日志文件(*.log)。1. 数据文件数据文件主要是存储数据的文件。例如,数据文存储的表的记录和...
  • 文件分配对应于文件物理结构,是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种:连续分配、链接分配和索引分配。 连续分配 连续分配方式要求每个文件在磁盘上占有一道连续的块。 优点:支持顺序访问和...
  • 文件管理 文件系统基础 ...有结构文件由若干相关记录组成;无结构文件被看成是一个字符流。 文件属性 文件名:同一个目录下不允许有重名文件 标识符:一系统内各文件的标识符唯一,对用户而言没有可
  • PDF学习二:PDF文件物理结构

    千次阅读 2018-06-08 18:40:47
      说明: 在PDF学习一 Hello World中简单提到了PDF文件结构。本文将重点讲PDF文件结构,指的是其文件物理组织方式,决定对象是如何存放在一个PDF文件中, 它们是如何被访问的,如何被更新的。...PDF文件物理结构...
  • 从逻辑结构方面讲Oracle 数据库以逻辑结构进行内部的管理和维护的这些结构包括表空间段区和块 从物理结构方面讲Oracle 数据库有外部的存储方法Oracle 数据库由一系列的物理文件组成主要有数据文件控制文件和重做日志...
  • 同样的,在外存管理中,为了方便对文件数据的管理,文件的逻辑地址空间被分为了一个个文件“块”。 于是文件的逻辑地址页可以表示为(逻辑块号,块内地址)的形式。 二、文件分配方式 1、连续分配 2、链接...
  • 逻辑结构与物理结构

    千次阅读 2020-03-20 20:20:29
    逻辑结构常见有四种类型:集合结构,线性结构,树形结构,图形结构。 所谓集合结构:表面意思,没有什么深刻意义,就是数据元素同属一个集合,单个数据元素之间没有任何关系。如下图所示。 ...
  • 文件物理结构有哪3种,分别具备什么优缺点 2012-01-03 18:55妖孽YH | 分类:数据结构及算法 | 浏览3597次
  • 文件系统笔记一、磁盘物理结构

    千次阅读 2018-01-11 16:31:24
    文件系统笔记一、磁盘物理结构 引言:文件系统从根本上说,就是操作系统对磁盘进行的抽象和装扮。故了解磁盘的物理结构,是我们学习文件系统的基础。 文件系统笔记一、磁盘物理结构 一、磁盘概念引入 二、...
  • 数据库设计之物理结构设计

    万次阅读 多人点赞 2018-07-03 10:58:59
    数据库在物理设备上的存储结构与存取方法称为数据库的物理结构,它依赖于选定的数据库管理系统。为一个给定的逻辑数据模型选取一个最适合应用要求的物理结构的过程,就是数据库的物理设计。 一、数据库的物理...
  • 文件物理结构是从实现观点出发,又称为文件的存储结构,是指文件在外存上的存储组织形式。文件的逻辑结构与存储介质特性无关,但文件物理结构与存储介质的特性有很大关系。 按逻辑结构,文...
  • 文件物理结构文件分配方式) 连续分配 链接分配 索引分配 文件目录 文件控制块 FCB 索引结点(FCB的改进) 文件存储空间管理 空闲表法 空闲链表法 位示图法 成组链接法 文件共享 硬链接:基于索引结点的共享方式...
  • 简述Linux文件系统通过i节点把文件的逻辑结构和物理结构转换的工作过程。 参考答案: Linux通过i节点表将文件的逻辑结构和物理结构进行转换。 i 节点是一个64字节长的表,表中包含文件的相关信息,其中有文件的...
  • Oracle 物理结构

    千次阅读 2019-05-20 17:31:36
    逻辑结构—————物理结构 物理结构 不同类型的数据文件,数据文件是真实存在的 逻辑结构 数据库为数据库中的所有数据,分配逻辑数据库空间。数据库空间分配的单位是数据块、区段和段。 顺序:表空间-段-区-块 很...
  • 数据结构文件

    千次阅读 2022-04-19 16:46:15
    和表类似,文件是大量记录的集合。习惯上称存储在主存储器(内存储器)中的记录集合为表,称存储在二级存储器(外...操作系统中的文件仅是一维的连续的字符序列,无结构、无解释。它也是记录的集合,这个记录仅是一个字...
  • 常见文件物理结构有以下几种: 1、顺序结构又称连续结构。这是一种最简单的物理结构,它把逻辑上连续的文件信息依次存放在连续编号的物理块中。只要知道文件在存储设备上的起始地址(首块号)和文件长度(总块数)...
  • 比较详细的FAT32说明文档,研究磁盘结构的能用上
  • 数据结构之逻辑结构与物理结构(存储结构)

    万次阅读 多人点赞 2017-10-15 21:22:11
    逻辑结构分为四种类型:集合结构,线性结构,树形结构,图形结构。 所谓集合结构:表面意思,没有什么深刻意义,就是数据元素同属一个集合,单个数据元素之间没有任何关系。如下图所示。   线性结构类似...
  • oracle六种物理文件.pdf

    2020-08-10 03:44:52
    精品文档 2010-05-14 14:06340 人阅读 评论 (0) 收藏举报 一控制文件 Control File 保存有关数据库的结构信息 控制文件是一个小型的二进制文件可以记录数据库的物理结构包括 * 数据库名称 * 数据文件和日志文件的...
  • 类似于数据结构的“逻辑结构”和“物理结构”。 如“线性表”就是一种逻辑结构,在用户角度看来,线性表就是一组有先后关系的元素序列,如:a,b,c,d,e … “线性表”这种逻辑结构可以用不同
  • Oracle数据库存储结构物理存储结构数据文件(data files)控制文件(control files)在线重做日志(online redo log)逻辑存储结构数据块(data blocks)区(extents)段(segments)表空间(tablespaces) ...
  • oracle 存储结构分为物理结构和逻辑结构,这两周存储结构既相互独立又相互联系。 1. oracle 物理结构 主要文件: ·数据文件包含数据库的用户或应用程序数据,以及元数据和数据字典。 ·重做日志文件: 用于...
  • 文件结构

    千次阅读 2016-04-05 22:59:13
    文件结构 文件的逻辑结构  文件的逻辑结构一般分为两类,一类为流式结构,一类为记录式结构。流式结构文件的基本构成单位是字符,文件是有逻辑意义的、无结构的一串字符的集合,是一个无结构的字节序列,如下...
  • 生成用于Elmer多物理场有限元代码的精炼非结构化网格的示例。 作者Fabien Gillet-Chaulet 2013,Rupert Gladstone的进一步修改() 这些目录可以从公共github存储库获取: 请注意,将需要安装gmsh和yams(以及elmer...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 375,527
精华内容 150,210
热门标签
关键字:

常见的文件物理结构包括