第四节 计算机信息存贮

当前，无论是信息的印刷存贮、缩微存贮、磁存贮、光存贮还是其它新型存贮技术，都已与计算机技术紧密地联系在一起。而计算机科学本身就是一门研究信息的结构、存取、处理和应用的科学。下面对计算机信息存贮的结构及计算机存贮系统加以概述。

一、计算机信息存贮的结构

（一）信息的逻辑结构

信息的逻辑结构关系到计算机存取和利用信息的方式。信息在某种意义上代表着现实世界的客观现象，作为计算机处理的对象，则应抽象成能为计算机处理的数据集合。通常，数据集合中的数据元素不是孤立的，而是彼此相关的，这种彼此相互之间存在的相互关系就叫结构。人们将数据元素之间内在的、固有的联系称为逻辑结构。逻辑结构可分为两类：

  1. 线性结构。这类结构的特点是：数据元素按一定顺序构成一个有限序列，除了第一个和最后一个数据元素外，每个数据元素有且仅有一个直接前趋和一个直接后继。

线性结构是一种最常用、最简单的数据结构。如单向线性表、双向循环表、环形表、数组、串、限定性的线性表、栈和队伍等，都是线性结构。

  1. 非线性结构。现实世界中许多问题以非线性结构（又称离散结构）来表示要比线性结构表示明确、方便得多。非线性结构中最常用和最重要的是树型结构和网型结构。
  1. 树型结构：这类结构的特点是至少存在一个结点（元素）；除了根结点和子结点外，其他结点最多只有一个直接前趋，并有一个或不只一个直接后继。

通常，人们在研究树型结构时，又把树分为二叉树、线索树、二叉排序树、判定树、森林等来讨论。

树型结构能很好地描述信息结构的层次特性，是信息的重要组织形式之一，在计算机科学等领域应用十分广泛。

  1. 网型结构：网型结构的特点是结点间的联系是任意的，即任何一个数据元素都可以与其他元素相联结。

人们又通常分有向图和无向图来讨论网型结构。

网型结构已广泛应用于系统工程、遗传学、控制论、电子线路、统计力学及计算机网络等科技领域。

在研究线性结构、树型结构和网型结构时，一般采用下列四种方式加以记录：

  1. 序列方式：即先按段间关系规定顺序，然后按顺序排列各段的方式。这种方式实际上是以隐含的形式记录着信息的内在关系。

采用这种方式的优点是，对段进行顺序处理时效率较高。其缺点是：不易表现网型结构；对段的增加、删除或修改很不方便；寻找单个元很费时间

（它适于大批处理）。

  1. 指针方式：即在段中放一指引元（又称之为“指针”）用以指引与其相关的方式。

  2. 列表方式：把数据间的关系独立出来，用行列列表表示出来。它可以用来表示各种数据结构。

  3. 混合方式：即前三种方式的混合使用，有时会达到更好的效果。例如，索引顺序就是常见的一种混合记录方式。

（二）信息的存贮结构

当信息由计算机进行处理时，就必须考虑其他计算机存贮器中的映象问题，这就是信息的存贮结构或物理结构。一种逻辑结构可以通过映象得到与它相应的存贮结构。信息的两大类逻辑结构——线性结构和非线性结构，分别由顺序映象和非顺序映象得到两种不同的存贮结构：顺序存贮结构和非顺序存贮结构。

  1. 顺序存贮结构。在计算机中，主存贮器由字的有序序列构成，每个字包含 8 到 64 个二进制数位，可以用一个地址引用它的内容。最常用最简单的方式是以一片地址连续的存贮空间顺序存贮线性结构的数据元素，即以数据元素在存贮器中物理位置上的紧邻来表示数据元素之间的逻辑关系。在程序设计语言中，常用向量这种数据类型来描述顺序存贮结构，它利用计算地址定出数据元素的位置。

顺序存贮结构的优点是结构简单，容易实现，顺序存取速度较快，可随机存取表中任一元素。

以顺序存贮结构构造的文件，称为连续文件或顺序文件。存贮介质可以是磁带、磁盘和光盘。文件中记录的长度允许是定长的或可变长的。

  1. 非顺序存贮结构。非顺序存贮结构的最大特点是不要求逻辑上相邻的元素在物理位置上也相邻，即可以用一组任意的存贮空间存贮数据元素。典型的非顺序存贮结构就是链式存贮结构。采用链式结构，在逻辑上是有序的， 而在物理上则可能是无序的。

采用链式结构构造的文件，称为串联文件，存贮介质可能是磁盘、磁鼓和光盘。这种链式结构的文件建立时，无需事先确定好文件的长度，且允许文件动态增长，插入和删除记录都比较方便。

显然，对于非线性结构的信息，很难以顺序存贮结构映象；而非顺序存贮结构既能映象线性结构，又能较好地映象非线性结构。

二、计算机信息存贮

（一）计算机存贮系统的结构

计算机是存贮与处理信息的机器。计算机存贮系统主要由存贮器及存贮管理软件构成。

  1. 存贮器。存贮器是组成计算机系统的重要部件，输入的信息必须存贮在某一规定的位置上，一旦需要时才能很方便地使用。因此，需设存贮器。存贮器可以分为内存贮器（主存贮器）和外存贮器（辅助存贮器）两部

分。

内存贮器存贮容量较小，但存取速度快；外存贮器的存贮容量大，但存取速度较慢。人们通常是把常用的数据放在快速存取的主存贮器里，供随时调用；而把不常用的数据存入容量大、速度慢的外存贮器里。

目前所用的内存贮器是磁芯存贮器。这种存贮器往往由数千万字节的存贮单位组成，为了识别这些存贮单位，每一字节应编好地址，数据则按地址存贮在规定的位置上，或从规定的位置取出。存入和取出所需时间，称为存取时间。

由于磁芯存贮器容量有限，无法容纳帐目信息之类的大量数据，因此这类数据应存贮在费用低廉而容量很大的外存贮器内。外存不和计算机的操作直接发生关系，只有在必要时才移到磁存贮器进行处理。

外存贮器主要有两种：磁带存贮器和随机存取存贮器。

磁带存贮器是一种顺序存贮器，它是按照磁带录音的原理进行存贮的。当存取数据时，必须从头按顺序检索到所需位置，故其存取时间因存贮位置不同而相差很大。为了克服这一缺点，就研制出了随机存取存贮器。这种存贮器是根据地址进行查找的，所以无论存贮位置如何，其存取时间大致相等。

随机存取存贮器的载体是磁鼓和磁盘。磁盘是一种快速的大容量外存， 是大型软件系统必不可少的硬件基础。磁盘部分可更换的磁盘存贮器称为磁盘组件，现已研制出在一台驱动器上可安装九个磁盘组件的存贮器，大大提高了存贮容量。

为提高存取速度，人们又在中央处理器和内存贮器之间增加了一个小容量高速的缓冲存贮器，用以存放中央存贮器当前最常用的指令和数据，与主存交换信息。

  1. 存贮管理。存贮器是计算机系统中的关键性资源，能否合理有效地使用它，取决于计算机操作系统中的存贮管理模块和文件管理模块。

不同的操作系统可能采取不同的存贮管理方式，但其目的都是一致的， 即为了解决存贮空间的分配，扩充主存贮器容量，实现信息的存贮、修改、检索、共享和保护，提高存贮空间的利用率。

在操作系统中，通常讨论的存贮管理内容是对内存贮器的管理，而文件管理的内容是对外存贮器的管理。

  1. 内存的管理：对内存的分配通常有两种分配策略：静态分配策略和动态分配策略，分别采取静态重定位和动态重定位技术。我们把作业在装入过程中进行地址变换（即把逻辑地址变换成内存中的物理地址）的方式称为静态重定位；而把作业在执行进程中，当访问到某一指令或数据时，才进行地址变换的方式称为动态重定位。具体的存贮管理方案有：单一连续区分配、分区、分页、分段、段页式分配等。不同的存贮管理方案有不同的分配方式、保护信息的措施和共享信息的可能性。

  2. 外存的管理：对外存的管理，是由操作系统中的文件管理系统—— 存取和管理信息的模块，通过提供为用户建立文件，对文件存贮空间进行组织、分配、保护，负责文件的读取、转贮、控制等功能来实现的。用户只需知道他们的文件名和操作命令，便可按名存取和操作，而不必关心文件究竟存放在什么物理位置上。

对外存空间的分配，可根据信息的逻辑结构采用两种分配策略，一是分配连续的存贮区域，二是分配不连续的物理块。

  1. 虚拟存贮器：对于内存贮器容量的扩充，通常借助于自动覆盖和交换技术来达到。一个大作业提交给系统，其中一部分信息在内存，另一部分信息暂时留在外存，需要时若内存空间已满，系统将自动依据某种算法选择暂时不用的信息从内存移出，再将需要处理的信息调入内存。此时呈现给用户的是一级存贮器的映象，这就是所谓的虚拟存贮器的概念。有了虚拟存贮器后，正在运行的多道作业的全部地址空间总和可以大于主存的容量。

要实现虚拟存贮器，要有动态重定位地址变换机构，一定容量的内、外存贮器和相应的管理软件。

二、文件信息的存贮方式

文件是在逻辑上具有完整意义的信息集合。不同的信息集合提交给计算机系统进行处理，通常是以文件为单位并以文件名来识别的一个作业或一个任务。文件的逻辑结构可分为两种：一是记录式文件，这类文件由若干逻辑记录组成，逻辑记录是在逻辑上具有独立含义的一个信息单位；二是流式文件，这类文件是一个顺序的信息流集合。文件的存贮结构密切地依赖于存贮设备的物理特性，但对用户而言，文件概念的引入，使得用户可以用统一的方式去存取不同存贮介质上的信息。

一个计算机系统必须提供一定的外存空间，供用户存放以文件形式组织的信息。一般说来，一个以程序设计语言编写的文件作为一个作业，从文件输入到信息输出，须经过编辑、编译、链接和运行四个不同的作业步，在外存以三种形式的用户库来存贮。

（一）源程序库

以源语言形式出现的计算机程序库称源程序库。任何经编辑作业步处理的信息都可以存放在源程序库中，而无须每次上机重新建立文件。由源程序库提交系统执行，必须经过编译、链接和运行三个作业步。

（二）相对形式库

在具有一定规模的、支持多道程序设计的计算机系统中，用户可以将经过编译作业步处理而产生的相对模块存入在磁盘或磁带上建立的相对形式库。

用户可以将所有已调试好的子模块存入相对形式库，需要经常改动的主模块存入源程序库；或者将已调试好的主模块和其它子模块存入相对形式库，而新添加的未调试好的子模块存入源程序库。这样存贮的优点是，提交系统执行时，节省了时间较长的编译作业步，从而节省了整个作业的执行时间。

（三）执行形式库

用户可以将经编辑、编译和链接三个作业步的目标模块存入在磁盘或磁带上建立的执行形式库。当用户的程序比较成熟，则无须改动，而每次运行需要更换不同的数据集合时，最好采用这种方式，可有效地缩短机时，加快执行速度。

总之，计算机存贮是计算机技术发展的基础，也是其它存贮技术赖以发展的条件。无论是信息的缩微存贮、磁存贮、光盘存贮，还是更新型的存贮及检索，都是建立在计算机技术的基础之上，与计算机技术紧密结合，才能寻求更大的发展空间。可见，计算机存贮及技术乃是计算机科学、信息科学长久研究的课题。