第二节　数据库的数据结构及存储结构

 

一、数据结构

　　传统的数据库有三类：层次数据库、网状数据库和关系数据库。它们分别采用树、图和线性表三种不同数据结构。各有其适应性。
　　例1．3：一个学校有许多系：电系、机系、化工系……每个系通过系代码，系名，系地址，系电话，系专业设置，……等数据来描述。每个系下辖多个教研室。如电系下辖计算机，电子信息，自动控制等教研室；机系下辖机械制造，质检，制图等教研室； 化工系下辖化工材料， 有机化工等教研室。每个教研室有室代码，室名，室电话等数据表现其属性。每个教研室负责管理老师，学生。
　　假设计算机教研室有张、王、林等老师，有A1、B1、C1等学生。电子信息教研室有肖、吴、陈等老师，有A2、B2、C2、D2等学生。自动控制教研室有廖、章等老师，有A3、B3等学生，机械制造教研室有任、钟、王等老师，有A4、B4、C4等学生。质检教研室有明、任等老师，有A5、B5等学生，制图教研室有王老师，有A6、B6、C6等学生，化工材料教研室有李、吴等老师，有机化工教研室有陈、张等老师，有A7等学生。
　　教师用职工号、姓名、性别等描述，学生用学号、姓名、性别等描述。
　　如果系统常要讨论的是某个系有哪些教研室，了解有关教研室的情况、老师的情况、学生的情况， 以及某个教研室有哪些老师， 有哪些学生等问题。可以使用链表将所有数据如图1．4连接进行存储，其中每个框表示一个实体型，包括各有关数据项。

　　这类结构可以实现从头开始循链表查询上述问题，层次数据库就是如此组织数据的。下面简单介绍一下层次数据库数据逻辑结构。

二、IMS层次数据库结构概述

　　在早期层次数据库结构的典型代表IMS（Information Management System）中使用的是链表结构方式。在IMS中以实体集组成树型结构， 称为记录型，图1．4的记录型结构如图1．5所示。代表一个实体集的数据结构称为片段型，例如图1．5中“系”、“教研室”、“老师”、“学生”均为片段型。一个实体的数据称为片段值，例如“系”的片段值有：电系、机系、化工系等，“教研室”的片段值有：计算机、电子信息、电气控制、机械制造、质检等。根片段每一个片段值及其子孙片段值构成一棵树，称为记录，以链表相互关联。

图1.5 学校组织的层次数据结构模型

　　例如“电系”记录的数据由如下片段值构成：电系，计算机教研室，张老师，王老师，林老师，学生A1，学生B1，学生C1，电子信息教研室，肖老师，吴老师， 陈老师， 学生A2，学生B2，学生C2，学生D2，自动控制教研室，廖老师，章老师，学生A3，学生B3。
　　“机系”记录的数据由如下片段值构成：机系，机械制造，任老师，钟老师，王老师，学生A4，学生B4，学生C4，质检教研室，明老师，任老师，学生A5，学生B5，制图教研室，王老师，学生A6，学生B6，学生C6。
　　这种层次结构形式，能用来解决前述所求问题。但查询只能从头顺着链向后走，因此要回答某老师是属哪个系及哪个教研室这类问题比较困难，数据维护操作也比较麻烦。 在图1.5中一个系连同其所有教研室、教师和学生等子孙成员数据称一条记录， 这些记录是不等长的， 因而存储处理也较困难。常用的另一种数据结构是线性表，是关系数据库采用的数据结构，下面简单介绍一下关系数据库数据逻辑结构。

三、关系数据库结构概述

　　关系数据库采用线性表形式组织数据，如上述同样问题，它采用系、教研室、教师、学生等四个线性表来组织有关数据，如表1.2、表1.3、表1.4、表.5所示。

表1.2 系部数据表

系代码 系名 系地址 系电话 系专业设置 D1 电系 机二楼 247 计算机、电信、自控 D2 机系 机二楼 354 机械、质检、制图 D3 化工系 机二楼 564 化工材料、有机

 

表1.3 教研室数据表

室代码 室名 室电话 系代码 01 计算机 260 D1 02 电子信息 261 D1 03 自动控制 262 D1 04 机械制造 370 D2 05 质检 371 D2 06 制图 372 D2

 

表1.4 老师数据表

职工号 姓名 性别 室代码 X01 张 男 01 X02 王 女 01 X03 林 女 01 X04 肖 男 02 X05 吴 女 02 X06 陈 男 02 X07 章 男 03 X08 廖 男 03 X09 钟 男 04 X10 王 男 04 X11 任 女 04

 

表1.5 学生数据表

学号 姓名 性别 室代码 S1 A1 男 01 S2 B1 男 01 S3 C1 女 01 S4 A2 女 02 S5 A3 男 03 S6 B3 男 03

 

　　采用的每一表称为一个关系； 表的每一行称为一条记录， 代表一个实体；每一列称为字段或数据项，代表实体的一个属性。
　　在学生的学籍与成绩管理系统中，我们要考虑学生的基本情况、所学课程、学生成绩等多个方面的内容，一个学生在学校中将学习许多课程，同时一门课一般说总是有许多学生学习。若要存放这些数据并问及有关学生和课程二者之间的问题，例如问某个学生学习了哪些课程，各自成绩等。学生到课程之间关联关系如图1．6所示。

学生　　　　　　　　　　　　　　　课程

　　如果进一步要问某门课程有哪些学生学及其成绩，就需建立反向的课程到学生之间关联关系，如图1．7所示。

课程　　　　　　　　　　　　　　　 学生

　　同时涉及两个方向关系，显然不便采用层次数据结构，但可采用线性表结构。例如作如下设计：在前面所举各表基础上增加课程表包括课程号，课程名，开课单位等。结构如表1．6所示。

表1.6 课程数据表

课程号 课程名 开课单位 C1 C语言 01 C2 操作系统 01 C3 数据库 01 C4 电工学 02 C5 电机学 03 C6 机械原理 04 C7 制图学 06 C8 C语言 02

　　再设计一个将表1.5和表1.6联系起来的表，如表1.7所示成绩表。

表1.7 成绩表

学号 课程号 分数 S1 C1 80 S1 C2 85 S1 C3 80 S2 C5 80 S2 C6 90 S3 C1 90 S3 C2 85 S3 C4 90 S3 C7 95

　　根据这样的结构，可以回答许多关于学生与课程关系的问题，例如问学生A1学习了哪些课程及其成绩,我们可在表1.5的学生表中查出A1学号为S1，再在表1.7中查得S1所学课程号有C1、C2、C3，各自分数为80、85、80。 再在表1.6中查得C1、C2、C3课程名为C语言、操作系统和数据库，有了这些数据，很容易打印成绩单，形成如下的表1.8。

表1.8 A1选修课程成绩查询结果

学号 姓名 C语言 操作系统 数据库 S1 A1 80 85 80

　　同样方法可很容易查某门课程有哪些学生学及其成绩的问题。
　　对于线性表我们前面已见到类似于VFP的存储方式， 利用三个表存储学生、课程和成绩数据，所有数据以等长记录形式顺序存放。由于在查询时需要操作三个表，表的关联操作耗费时间，因而效率较低。
　　当遇到课程和学生这类问题时，也可借助链表形式建立数据与数据间的联系。例如仿照线性表将学生与课程的数据分别在不同的存储区域内存放，同时用不同链表分别描述从学生到课程的联系和课程到学生的联系。针对不同应用需求,使用不同的链表联系。例如求各个学生学习了哪些课程的问题,使用如图1.6所示的链表联系。求各门课程有哪些学生学的问题， 使用如图1.7所示的链表联系。
　　这两个链表结构可同时存在，只是如何建立指针的问题。网状数据库就采用这样的数据结构，其典型代表是DBTG（Data Base Task Group数据库任务组）数据库。下面简单介绍一下网状数据库数据逻辑结构。

四、网状数据库结构概述

　　在DBTG中，将不同实体集的数据分别在不同的存储区域内存放，对应一个实体的数据称为记录，其数据结构称为记录型。针对不同应用需求建立不同链表描述实体集与实体集的联系，然后根据不同应用需求，使用不同的链表联系。面向应用的每一个实体集与实体集的联系整体称为“系”，其数据结构称为系型。在一个“系”中可以有许多链，一条链链接的所有数据元素的集合称为“系值”。链的起始元素称为系主记录，其他称为成员记录。系主记录是根，成员记录是叶子，构成一棵二级树。图1.8描述了两个“系”：“学生一课程”及“课程一学生”。前者用于查一个学生学习了哪些课程的问题，后者用于查一门课程有哪些学生学的问题。

图1．8 “学生一课程”系与“课程一学生”系

　　这样一种结构方式中每一个记录型都可能是根，也可能是叶子。针对不同应用，一个记录型可参与多个系， 是一些系的根， 同时是另一些系的叶子。从全局看它实际是网状结构。其优点：由于根据应用需要在录入数据或应用之前已建立了所需的关联，因而查询速度快，效率较高。但对每一类应用均要预先建立联接，指针结构过于复杂，给数据维护带来不便，且灵活性也不够。
　　从上面讨论可见，对不同应用问题可能需要采用不同的数据结构和存储结构来组织数据。采用链表结构优点是效率高，缺点是结构较复杂，维护不方便，操作缺少灵活性。采用线性表结构并以顺序文件形式存放，结构较简单，数据维护容易，容易实施，有很强的适应性和灵活性，因此是目前采用的主要形式，缺点是效率较低。