管理信息系统的数据物理组织层次

在管理信息系统中，数据的组织方式及内在的表示决定着数据处理的效率，所以数据组织是组建管理信息系统必须考虑的问题。

1．数据结构

数据结构是计算机信息处理中十分重要的概念，包括数据的存储结构及在此结构上的运算或操作。数据结构又分为数据的逻辑结构和数据的存储结构，如图3-1所示。数据的逻辑结构是指数据间的逻辑关系，逻辑结构包括两大类：线性结构和非线性结构。线性表、栈、队列及串为线性结构，而树和图则为非线性结构；存储结构又称为物理结构，指数据元素在计算机存储器中的存储方式，它一般包括四种方式：顺序存储、链接存储、索引存储及散列存储。同一种逻辑结构采用不同存储方式可以得到不同的数据结构，如线性表以顺序存储方式存储时得到顺序表数据结构，而以链接存储方式存储时则得到链表数据结构。对于给定的逻辑结构需要寻找一种恰当的与其对应的存储结构，以便在计算机中存储。下面我们将介绍几种比较常用的数据结构。

（1）数组

数组是相同类型数据元素构成的有限序列，且存储在一块地址连续的内存单元中。几乎所有的高级程序设计语言都支持数组数据类型。数组这种数据结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元中。例如要保存一位学生本学期所选学三门课程的成绩，可以定义一个一维数组A[3]，则该数组有A [0]、A [1]和A [2]三个元素，如图3-2所示。数组用A [i]表示，i称为下标值，三个数组分别保存该学生所选三门课程的成绩。在一维数组的基础上，我们可以引入多维数组。例如要保存两位学生所选课程的成绩，可以定义一个二维数组B[2][3]，则该数组有B[0][0]、B[0][1]、B[0][2]、B[1][0]、B[1][1]、B[1][2]共六个元素，用B[i][j]保存第i+1个学生所学第j+1门课程的成绩。计算机的存储结构是线性的，B数组是以行序为主序的存储方式，即先存储第0行，再存储第1行，每列中的元素是按行下标由小到大的次序存放。

图3-2 一维数组A[3]的存储示意图

对于一个以行序为主序方式存储的二维数组a[m][n]，我们假设每个数据元素在内存所占用的存储单元个数为k，第一个元素a[0][0]的存储地址由LOC（a[0][0]）确定。数组元素a[i][j]的存储地址LOC（a[i][j]）可由以下公式求出：

LOC（a[i][j]）=LOC（a[0][0]）＋i×n×k+j×k

而在以列序为主序方式存储的二维数组a[m][n]中的任一数组元素a[i][j]的存储地址LOC（a[i][j]）可由以下公式求出：

LOC（a[i][j]）=LOC（a[0][0]）＋i×n×k+j×k

从以上分析中得知，数组中任一数据元素的存储地址可通过下标值直接计算得出，它是一种随机存储结构。利用数组存放数据时，必须先定义，后使用，也就是事先给定数组元素的个数。如果事先难以确定的话，则必须把数组定得足够大，以便能定义足够多的空间存放数据，某些情况下会浪费部分内存。

（2）链表

链表是一种可以动态进行存储分配的数据结构，它是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。每个数据元素包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。图3-3表示了三位学生学号、姓名和年龄的链表存储结构。

计算机的内存储器被划分为一个个的存储单元，每个存储单元存放一个字节。存储单元按一定的规则编号，这个编号就是存储单元的地址。我们要通过“指针”来实现管理内存数据准确定位读写，也就是通过“指针”找到以它为地址的内存单元。

指针作为维系节点的纽带，可以通过它实现链式存储。假设五个学生某一门功课的成绩分别为A、B、C、D和E，这五个数据在内存中的存储单元地址分别为1000、1200、1366、1510和1620，其链表结构如图3-4所示。

图3-4 链表结构示意图

（3）栈

栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。根据栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素。这样，最后进入栈的数据元素总是最先退出栈，因此，栈具有“后进先出”（LILO：Last In Last Out）的特性。栈的应用非常广泛，表达式求值、递归过程实现都是栈应用的典型例子。下面简单讨论一下高级语言中的表达式处理是怎样通过栈实现的，例如：利用栈处理算术表达式a×（b+c/d）+e，过程如图3-5所示。

图3-5（a）表示了依次读入表达式中的“a”、“*”、“（”、“b”、“+”、“c”、“/”、“d”等单词后操作数栈ODS（图示的左边）和操作符栈OPS（图示的右边）的状态；图3-5（b）和图3-5（c）表示了读入“）”后，去括号的过程，其中t1=c/d，t2=b+t1；图3-5（d）表示了读入“+”后，ODS和OPS的状态，其中t3=a*t2；图3-5（e）表示了读入“e”后，ODS和OPS的状态；图3-5（f）表示了读入表达式结束符后，ODS和OPS的状态，其中t4=t3+e，此时操作符栈OPS为空，操作数栈ODS的栈顶元素t4就是所求的表达式的值。

图3-5 利用栈处理算术表达式的示意图

（4）队列

队列也是一种特殊的线性表，是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。当队列中没有数据元素时，称为空队列。队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。

根据队列的定义，每次进队列的数据元素都放在原当前队尾之后而成为新的队尾元素，每次出队列的数据元素都是原队头元素。这样，最先入队列的数据元素总是最先出队列，因此，队列具有“先进先出”（FIFO：First In First Out）的特性。(www.xing528.com)

队列的应用也很广泛，它可以用于各种应用系统的事件规划与事件模拟中，例如银行和商场的顾客队列；计算机操作系统中的各种资源请求排队和各种数据缓冲区的先进先出管理也用队列来实现，如操作系统用队列来处理打印作业的调度。

（5）树

树是节点之间有分支和层次关系的结构，类似于自然界的树，它是一类非常重要的非线性结构，它在大规模数据处理中应用广泛，如人类社会的族谱和各种社会组织机构的表示等等。在计算机领域中，树形结构的应用也非常广泛，磁盘文件的目录结构就是一个典型的例子。树和二叉树是常用的树形结构，由于用二叉树表示对于树的存储和运算有很大意义，可以把对于树的许多处理转换到对应的二叉树中去做。

如图3-6所示的例子，该树结构反映了不同规格的钢材的存储情况。

图3-6 树结构实例

2．数据文件

在信息系统中，数据组织一般采用文件组织和数据库组织。文件组织是一种按某种数据结构把数据记录存放在外存设备上的方式，一般适用于数据记录存储比较简单的场合。数据文件是为了某一特定目的而形成的同类记录的集合。记录是文件中可存取的最小单位，它由若干数据项构成。数据项是文件中可使用的最小单位。如果用文件描述某一事物的总体例如工资单，则文件中的若干记录描述的就是总体中的个体的情况，例如个人的工资情况，而数据项描述的则是该事物的若干属性，例如姓名、基本工资、附加工资等。数据项都有一个代表事物某一方面属性的名，同时对于每一条记录来说，对应着该属性的名，还都有一个数据项的值。例如，对于属性名为“姓名”的数据项，具体到每一个个体就有一个数据项的值，例如“张三”。

随着计算机在信息处理上的应用，出现了文件系统。文件系统是负责存取和管理文件的软件，它利用磁盘、磁带等大容量的外存设备作为存放文件的存储器，用户可以把一批数据定义成一个文件，通过文件系统命名，实现对文件的按名存取。

文件系统是数据处理的主要方式，建造容易、使用灵活、处理速度快，特别适合单项业务系统使用（如财务、库存等管理系统）。尽管现在数据库系统得到了广泛应用，但其基础仍是文件系统，学习文件系统对数据的组织和操作方式、对理解信息系统的运行过程是很有意义的。

数据文件的组织方式。数据文件的组织方式是指文件内部构造数据的方式，主要有以下几种：

（1）顺序文件

顺序文件即文件中的记录是按照某些关键字排序的文件，如表3-2所示的教师信息顺序表。顺序文件中，记录的物理次序与连接次序一致，对于文件中每一个记录，按关键字的顺序给定序号为i，则其物理顺序亦为i。顺序文件是根据记录的序号或相对位置进行存取的文件组织方式，其特点是:

表3-2 教师信息顺序表

①存取第i个记录，必须先存取前面的第i-1个记录。

②插入记录只能加在末尾。

顺序文件的优点是连续存取、速度快，主要用于进行顺序存取、批量修改的情况。对顺序文件可进行顺序查找，其平均查找长度为（n+1）/2，n为文件所含物理记录数。对于在磁盘上组织的顺序文件也可以进行分块查找或折半查找。

（2）索引文件

有时为了便于检索，除文件本身外，另外建一张指示逻辑记录和物理记录之间对应关系的索引表，这类包括文件数据区和索引表两大部分的文件称为索引文件。索引表的索引项应当按顺序排列，而数据文件本身可以按顺序排列，也可以不按顺序排列，前者称为索引顺序文件，后者称为索引非顺序文件。

为了提高文件的检索效率，可以采用索引方法组织文件。采用索引这种结构，逻辑上连续的文件可以存放在若干不连续的物理块中，但对于每个文件，在存储介质中除存储文件本身外，还要求系统另外建立一张索引表，索引表记录了文件信息所在的逻辑块号和与之对应的物理块号。索引表也以文件的形式存储在存储介质中，索引表的物理地址则由文件说明信息项给出。索引结构如图3-7所示。

图3-7 索引结构文件的示意图

不过，大多数文件不需要进行多重索引，也就是说，这些文件所占用的物理块的所有块号可以放在一个物理块内。如果对这些文件也采用多重索引，则显然会降低文件的存取速度。因此，在实际系统中，总是把索引表的头几项设计成直接寻址方式，也就是这几项所指的物理块中存放的是文件信息；而把索引表的后几项设计成多重索引，也就是间接寻址方式。在文件较短时，就可利用直接寻址方式找到物理块号而节省存取时间，如表3-3所示。

表3-3 教师信息索引

索引结构既适用于顺序存取，也适用于随机存取，并且访问速度快，文件长度可以动态变化。索引结构的缺点是由于使用了索引表而增加了存储空间的开销。另外，在存取文件时需要至少访问存储器两次以上，其中，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。由于文件在存储设备的访问速度较慢，因此，如果把索引表放在存储设备上，势必大大降低文件的存取速度。一种改进的方法是，当对某个文件进行操作之前，系统预先把索引表放入内存。这样，文件的存取就可直接在内存通过索引表确定物理地址块号，而访问存储设备的动作只需要一次。当文件被打开时，为提高访问速度将索引表读入内存，故又需要占用额外的内存空间。