第5章数据库设计与ER模型

5.1 基本内容分析

5.1.1 本章重要概念

（1）DBS生存期及其7个阶段的任务和工作，DBD过程的输入和输出。

（2）概念设计的重要性、主要步骤。逻辑设计阶段的主要步骤。

（3）ER模型的基本元素，属性的分类，联系的元数、连通词、基数。采用ER方法的概念设计步骤。

（4）ER模型到关系模型的转换规则。采用ER方法的逻辑设计步骤。 （5）ER模型的扩充：弱实体，超类和子类。

5.1.2 本章的重点篇幅

（1）教材中P193-194的转换规则和实例。 （2）教材中P196-200的四个ER模型实例。

5.1.3 对ER模型的理解

ER模型是人们认识客观世界的一种方法、工具。ER模型具有客观性和主观性两重含义。ER模型是在客观事物或系统的基础上形成的，在某种程度上反映了客观现实，反映了用户的需求，因此ER模型具有客观性。但ER模型又不等同于客观事物的本身，它往往反映事物的某一方面，至于选取哪个方面或哪些属性，如何表达则决定于观察者本身的目的与状态，从这个意义上说，ER模型又具有主观性。

ER模型的设计过程，基本上是两大步：

·先设计实体类型（此时不要涉及到“联系”）；

·再设计联系类型（考虑实体间的联系）。

具体设计时，有时“实体”与“联系”两者之间的界线是模糊的。数据库设计者的任务就是要把现实世界中的数据以及数据间的联系抽象出来，用“实体”与“联系”来表示。

另外，设计者应注意，ER模型应该充分反映用户需求，ER模型要得到用户的认可才能确定下来。

5.2 教材中习题5的解答

5.1名词解释 （1）·软件工程：研究如何用科学知识、工程方面的纪律指导软件开发的过程，以提高软件质量和开发效率，降低开发成本，这样的一门学科称为“软件工程”。

·软件生存期：软件生存期是指从软件的规划、研制、实现、投入运行后的维护，直到它被新的软件所取代而停止使用的整个期间。软件生存期通常分为六个阶段：规划阶段，需求分析阶段，设计阶段，程序编制阶段，调试阶段，运行维护阶段。

·数据库工程：数据库应用系统的开发是一项软件工程，但又有自己特有的特点，所以特称为“数据库工程”。

·数据库系统生存期：我们把数据库应用系统从开始规划、设计、实现、维护到最后被新的系统取代而停止使用的整个期间，称为数据库系统生存期。这个生存期一般可划分成下面七个阶段：规划，需求分析，概念设计，逻辑设计，物理设计，实现，运行和维护 （2）·实体：可以区别的客观存在的事物，称为实体。

（2003/9/21） （高教--答案，第5、6章） 05-1

·实体集：同一类实体构成的集合，称为实体集。

·实体类型：实体集中实体的定义，称为实体类型。 ·实体标识符：能惟一标识实体的属性或属性集，称为实体标识符。有时也称为关键码（key），或简称为键。 （3）·联系：一个或多个实体之间的关联关系，称为联系。

·联系集：同一类联系构成的集合，称为联系集。 ·联系类型：联系集中联系的定义，称为联系类型。

（4）·属性：实体的某一特性，称为属性。 ·基本属性：不可再分割的属性，称为基本属性。

·复合属性：可再分解成其他属性的属性，称为复合属性。 ·单值属性：同一实体的属性只能取一个值，称为单值属性。 ·多值属性：同一实体的属性可能取多个值，称为多值属性。

·导出属性：通过具有相互依赖的属性推导而产生的属性，称为导出属性。 （5）·联系：

·联系的元数：一个联系涉及到的实体集个数，称为该联系的元数。

· 联系的连通词：联系涉及到的实体集之间实体对应的方式（指对应一个还是多个实

体），称为联系的连通词。

·实体的基数：是对连通词更为精确的描述。譬如有两个实体集E1和E2，E1中每个实体与E2中有联系实体数目的最小值Min和最大值Max，称为E1的基数。

（6）·弱实体：一个实体对于另一些实体（父实体）具有很强的依赖联系，而且该实体主键的部分或全部从其父实体中获得，则称该实体为弱实体。

·子类实体和超类实体：某个实体类型中所有实体同时也是另一个实体类型中的实体，此时称前一实体类型是后一实体类型的子类，后一实体类型称为超类。其实体分别称为子类实体和超类实体。 ·继承性：指子类继承其超类上定义的所有属性，但其本身还可以包含其他的属性。 5.2 数据库系统的生存期分成哪几个阶段？数据库结构的设计在生存期中的地位如何？ 答：对DBS生存期的划分，一般分为七个阶段，即规划、需求分析、概念设计、逻辑设计、物理设计、实现和运行维护。 DB结构设计的任务就是把概念设计阶段设计好的基本ER图转换成与选用的具体机器上的DBMS所支持的数据模型相符合的逻辑结构。 5.3 基于数据库系统生存期的数据库设计分成哪几个阶段？ 答：基于DBS生存期的DBD分成以下五个阶段：

规划；需求描述和分析；概念设计；逻辑设计；物理设计。 5.4 数据库设计的规划阶段应做哪些事情？

答：DBD中规划阶段的主要任务是进行建立DB的必要性及可行性分析，确定DBS在组织中和信息系统中的地位，以及各个DB之间的联系。

5.5 数据库设计的需求分析阶段是如何实现的？目标是什么？ 答：需求分析阶段的工作由下面四步组成： ·分析用户活动，产生用户活动图；

·确定系统范围，产生系统范围图；

·分析用户活动所涉及的数据，产生数据流图；

·分析系统数据，产生数据字典。 需求分析阶段的目标是对系统的整个应用情况作全面的、详细的调查，确定企业组织的目标，收集支持系统总的设计目标的基础数据和对这些数据的要求，确定用户的需求；并把

（2003/9/21） （高教--答案，第5、6章） 05-2

这些要求写成用户和数据库设计者都能接受的文档。 5.6 概念设计的具体步骤是什么？

答：概念设计的主要步走可分为三步：

（1） 进行数据抽象，设计局部概念模式； （2） 将局部概念模式综合成全局概念模式；

（3） 评审。

5.7 逻辑设计的目的是什么？试述逻辑设计阶段的主要步骤及内容。

答：逻辑设计的目的是把概念设计阶段设计好的基本ER图转换成与选用的具体机器上的DBMS所支持的数据模型相符合的逻辑结构（包括数据库模式和外模式）。这些模式在功能、性能、完整性和一致性约束及数据库的可扩充性等方面均应满足用户的各种要求。

逻辑设计阶段主要有五步：形成初始模式，设计子模式，设计应用程序梗概，评价模式和修改模式。（解释略）

5.8 什么是数据库结构的物理设计？试述其具体步骤。

答：对于给定的基本数据模型选取一个最适合应用环境的物理结构的过程，称为DB的物理设计。 物理设计有五步：

确定DB的存储记录结构；确定数据存储按排；存取方法的设计；完整性和安全性的设计；应用程序设计。

5.9 数据库实现阶段主要做哪几件事情？

答：数据库实现阶段主要有以下三项工作： 建立实际DB结构；装入试验数据调试应用程序；装入实际数据进入试运行状态。 5.10 数据库系统投入运行后，有哪些维护工作？

答：DBS投入运行以后，就进入运行维护阶段。其主要工作有四项： 维护DB的安全性与完整性及系统的转储和恢复； DB性能的监督、分析与改进；

增加DB新功能；

改正运行中发现的系统错误。

5.11 设某商业集团数据库中有三个实体集。一是“商店”实体集，属性有商店编号、商店名、地址等；二是“商品”实体集，属性有商品号、商品名、规格、单价等；三是“职工”实体集，属性有职工编号、姓名、性别、业绩等。

商店与商品间存在“销售”联系，每个商店可销售多种商品，每种商品也可放在多个商店销售，每个商店销售一种商品，有月销售量；商店与职工间存在着“聘用”联系，每个商店有许多职工，每个职工只能在一个商店工作，商店聘用职工有聘期和月薪。

（1）试画出ER图，并在图上注明属性、联系的类型。 （2）将ER图转换成关系模型，并注明主键和外键。 解：(1) ER图如图5.1所示。

月销售量 M 1 月薪 （2003/9/21） （高教--答案，第5、6章） 05-3

商店 商店编号 商店名 地址 销售 聘用 聘期 N 商品 N 职工 商品号 商品名 规格 单价 姓名 性别 业绩

图5.1 职工编号

（2）这个ER图可转换4个关系模式： 商店（商店编号，商店名，地址）

职工（职工编号，姓名，性别，业绩，商店编号，聘期，月薪） 商品（商品号，商品名，规格，单价） 销售（商店编号，商品号，月销售量）

5.12 设某商业集团数据库中有三个实体集。一是“公司”实体集，属性有公司编号、公司名、地址等；二是“仓库”实体集，属性有仓库编号、仓库名、地址等；三是“职工”实体集，属性有职工编号、姓名、性别等。 公司与仓库间存在“隶属”联系，每个公司管辖若干仓库，每个仓库只能属于一个公司管辖；仓库与职工间存在“聘用”联系，每个仓库可聘用多个职工，每个职工只能在一个仓库工作，仓库聘用职工有聘期和工资。

(1) 试画出ER图，并在图上注明属性、联系的类型。

(2) 将ER图转换成关系模型，并注明主键和外键。

解：(1) ER图如图5.2所示。

公司 1 隶属 仓库编号

N 仓库 公司编号 公司名 地址

仓库名 （2003/9/21） （高教--答案，第5、6章） 05-4

地址 1 聘用 聘期 工资

N 职工

图5.2

职工编号 姓名 性别

（2）这个ER图可转换3个关系模式：

公司（公司编号，公司名，地址）

仓库（仓库编号，仓库名，地址，公司编号）

职工（职工编号，姓名，性别，仓库编号，聘期，工资）

5.13 设某商业集团数据库有三个实体集。一是“商品”实体集，属性有商品号、商品名、规格、单价等；二是“商店”实体集，属性有商店号、商店名、地址等；三是“供应商”实体集，属性有供应商编号、供应商名、地址等。

供应商与商品之间存在“供应”联系，每个供应商可供应多种商品，每种商品可向多个供应商订购，每个供应商供应每种商品有个月供应量；商店与商品间存在“销售”联系，每个商店可销售多种商品，每种商品可在多个商店销售，每个商店销售每种商品有个月计划数。 试画出反映上述问题的ER图，并将其转换成关系模型。

解：ER图如图5.3所示。

供应商编号

供应商 M M 月计划数 月供应量 供应 销售 商店 供应商名 地址 商店号 商店名 地址 N N （2003/9/21） （高教--答案，第5、6章） 05-5

商品

商品号 商品名 规格 单价 图5.3

（2）这个ER图可转换5个关系模式：

供应商（供应商编号，供应商名，地址） 商店（商店号，商店名，地址）

商品（商品号，商品名，规格，单价）

5.14 假设要为银行的储蓄业务设计一个数据库，其中涉及到储户、存款、取款等信息。试设计ER模型。

解：储蓄业务主要是存款、取款业务，可设计如图5.4所示的ER图。

1 1 存款日期 储户 账号 身份证号 姓名 地址 存款余额

供应（供应商编号，商品号，月供应量） 销售（商店号，商品号，月计划数）

取款日期 取款 存款

N N

存款单 取款单 （2003/9/21） （高教--答案，第5、6章） 05-6

存款单号 金额 存款方式 取款单号 图5.4

金额 取款方式

5.15 某体育运动锦标赛有来自世界各国运动员组成的体育代表团参赛各类比赛项目。试为该锦标赛各个代表团、运动员、比赛项目、比赛情况设计一个ER模型。 解：图5.5是ER图的一种设计方案。 团编号 地区 住所 类别编号 类别名 主管 代表团 比赛类别 1 成员 1 属于 N 运动员 N M 参加 编号N 比赛项目 姓名 年龄 性别 项目编号 项目名 级别 比赛时间 得分 图5.5

5.16 假设某超市公司要设计一个数据库系统来管理该公司的业务信息。该超市公司的业务管理规则如下:

⑴该超市公司有若干仓库，若干连锁商店，供应若干商品。

⑵每个商店有一个经理和若干收银员，每个收银员只在一个商店工作。

⑶每个商店销售多种商品，每种商品可在不同的商店销售。 ⑷每个商品编号只有一个商品名称，但不同的商品编号可以有相同的商品名称。每种商品可以有多种销售价格。

⑸超市公司的业务员负责商品的进货业务。 试按上述规则设计ER模型 解：图5.6是ER图的一种设计方案。

M 业务员 进货 库存 P 商店 发货 N （2003/9/21） （高教--答案，第5、6章） 1 1 05-7 N 销售 M 拥有 主管 仓库 N M M P N 商品

N

图5.6

5.17 假设要根据某大学的系、学生、班级、学会等信息建立一个数据库，一个系有若干专业，每个专业每年只招一个班，每个班有若干学生。一个系的学生住在同一宿舍区。每个学生可以参加多个学会，每个学会有若干学生，学生参加某学会有个入会年份。试为该大学的系、学生、班级、学会等信息设计一个ER模型。 解：图5.7是ER图的一种设计方案。

宿舍区 1 住宿 N 系 1 设置 N 专业 1 （2003/9/21） （高教--答案，第5、6章） 05-8

招收 N

图5.7

5.18 试把教材中5.5.2、5.5.3、5.5.4等三小节中的ER模型转换成关系模型, 并指出每个关系模式的主键和外键。

（1）（教材中P197的5.5.2节）公司车队信息系统的ER模型

本例为某货运公司设计了车队信息管理系统，对车辆、司机、维修、保险、报销等信息和业务活动进行管理。其ER图如图5.8所示。

部门 M 开销 N 1 N 车辆 N N 1 1 保险公司 N 车队 1 N 司机 N 调用 聘用 拥有 保险1 报销 保险2 维修 1 （2003/9/21） （高教--答案，第5、6章） 05-9 维修公司

该ER图有7个实体类型，其结构如下： 部门（部门号，名称，负责人） 车队（车队号，名称，地址）

司机（司机号，姓名，执照号，电话，工资） 车辆（车牌号，车型，颜色，载重） 保险公司（保险公司号，名称，地址） 维修公司（维修公司号，名称，地址）

开销（顺序号，费用类型，费用，日期，经手人）

实体之间有7个联系，其中6个是1:N联系，1个是M:N联系。其中联系的属性如下： 调用（出车编号，出车日期，车程，费用，车辆数目） 保险1（投保日期，保险种类，费用） 保险2（投保日期，保险种类，费用）

进而，读者可以很容易地转换成关系模式集。 解：根据ER图和转换规则，7个实体类型转换成7个关系模式，1个M:N联系转换成1个关

系模式，共8个关系模式，如下：

部门（部门号，名称，负责人） 车队（车队号，名称，地址）

司机（司机号，姓名，执照号，电话，工资，车队号，保险公司号，投保日期，

保险种类，费用）

车辆（车牌号，车型，颜色，载重，车队号，保险公司号，投保日期，保险种类，费用，维修公司号）

保险公司（保险公司号，名称，地址） 维修公司（维修公司号，名称，地址）

开销（顺序号，车牌号，费用类型，费用，日期，经手人）

调用（出车编号，车队号，部门号，出车日期，车程，费用，车辆数目）

（2）（教材中P198的5.5.3节）人事管理信息系统的ER模型

上海交通电器有限公司设计了人事管理信息系统，其中涉及到职工、部门、岗位、技能、培训课程、奖惩记录等信息。其ER图如图5.9所示。

M

工资 1 享有 1 职工 选课 N 属于 1 培训课程 部门 M 设置 N （2003/9/21） （高教--答案，第5、6章） 05-10

N 技能 接受 M M 考核 N 聘任 1 N 奖惩 N 岗位 图5.9

这个ER图有7个实体类型，其属性如下：

职工（工号，姓名，性别，年龄，学历） 部门（部门号，部门名称，职能）

岗位（岗位编号，岗位名称，岗位等级） 技能（技能编号，技能名称，技能等级） 奖惩（序号，奖惩标志，项目，奖惩金额）

培训课程（课程号，课程名，教材，学时）

工资（工号，基本工资，级别工资，养老金，失业金，公积金，纳税）

这个ER图有7个联系类型，其中1个1:1联系，2个1:N联系，4个M:N联系。联系类型的属性如下：

选课（时间，成绩）

设置（人数）

考核（时间，地点，级别） 接受（奖惩时间）

解：根据ER图和转换规则，7个实体类型转换成7个关系模式，4个M:N联系转换成4个

关系模式，共11个模式，如下：

职工（工号，姓名，性别，年龄，学历，部门号，岗位编号）

部门（部门号，部门名称，职能）

岗位（岗位编号，岗位名称，岗位等级） 技能（技能编号，技能名称，技能等级） 奖惩（序号，奖惩标志，项目，奖惩金额） 培训课程（课程号，课程名，教材，学时）

工资（工号，基本工资，级别工资，养老金，失业金，公积金，纳税） 选课（工号，课程号，时间，成绩） 设置（部门号，岗位编号，人数）

考核（工号，技能编号，时间，地点） 接受（工号，序号，奖惩日期）

（3）（教材中P199的5.5.4节）旅游管理信息系统的ER模型

上海普教旅行社设计了一个小型的国内旅游管理信息系统，其中涉及到与业务有关的信息有旅游线路、班次、团体、旅客、保险员、导游、宾馆、交通工具等。其ER图如图5.10所示。

旅游线路 （2003/9/21） （高教--答案，第5、6章） 05-11

1

游客

N 参加 1 保险 导游 M 陪同 N 开设 N 1 交通 1 交通工具 旅游班次 1 有 M 食宿 N 宾馆 旅游团 1 1 组成 N 图5.10

这个ER图有8个实体类型，其属性如下：

旅游线路（路线号，起点，终点，天数，主要景点）

旅游班次（班次号，出发日期，回程日期，旅游标准，报价） 旅游团（团号，团名，人数，联系人，地址，电话）

游客（游客编号，姓名，性别，年龄，身份证号码，住址，电话）

导游（导游编号，姓名，性别，年龄，身份证号码，住址，电话，语种，等级，业

绩） 交通工具（旅游班次号，出发工具，出发日期，出发班次，出发时间，回程工具，

回程日期，回程班次，回程时间） 宾馆（宾馆编号，宾馆名，城市，星级，标准房价，联系人，职务，地址，电话，

传真） 保险单（保险单编号，保险费，投保日期）

这个ER图有7个联系类型，其中2个1:1联系，3个1:N联系，2个M:N联系。 解：根据ER图和转换规则，8个实体类型转换成8个关系模式，2个M:N联系转换成2个关

系模式，共10个关系模式，如下：

旅游线路（路线号，起点，终点，天数，主要景点）

旅游班次（班次号，路线号，出发日期，回程日期，旅游标准，报价） 旅游团（团号，旅游班次号，团名，人数，联系人，地址，电话）

游客（游客编号，团号，姓名，性别，年龄，身份证号码，住址，电话）

导游（导游编号，姓名，性别，年龄，身份证号码，住址，电话，语种，等级，

业绩）

（2003/9/21） （高教--答案，第5、6章） 05-12

交通工具（旅游班次号，出发工具，出发日期，出发班次，出发时间，回程工具，回程日期，回程班次，回程时间）

宾馆（宾馆编号，宾馆名，城市，星级，标准房价，联系人，职务，地址，电话，

传真）

保险（保险单编号，团号，人数，保险费，投保日期） 陪同（旅游班次号，导游编号） 食宿（旅游班次号，宾馆编号）

5.3 自测题

5.3.1 填空题

1．数据库设计过程的输入包括四部分内容：__________，__________，__________和

__________。 2．数据库设计过程的输出主要有两部分：__________和__________。

3．规划阶段具体可以分成三个步骤：___________、___________和___________。 4．需求分析的工作主要有下面四步组成：分析用户活动，产生__________；确定系统范围，

产生__________；分析用户活动涉及的数据，产生__________；分析系统数据，产生__________。 5． 需求分析中的数据字典通常包含以下五个部分：__________，__________，__________，

__________和__________。 6．概念设计的目标是产生反映____________的数据库概念结构，即概念模式。 7．概念设计阶段可分为三步来完成：__________，__________和__________。

8．就方法的特点而言，需求分析阶段通常采用__________的分析方法；概念设计阶段通常

采用__________的设计方法。 9．逻辑设计的主要工作是：__________________________。

10．逻辑设计的步骤有五步：__________，__________，__________，__________和__________。

11．物理设计可分成五步进行：__________，__________，__________，__________和

__________。 12．DBS的维护工作由__________承担的。 13．DBS的维护工作主要包括以下四个部分：_________，_________，_________，_________。

5.3.2 单项选择题（在备选的答案中选出一个正确答案）

1．需求分析阶段设计数据流程图（DFD）通常采用 A．面向对象的方法 B．回溯的方法

C．自底向上的方法

2．概念设计阶段设计概念模型通常采用 A．面向对象的方法 C．自底向上的方法 3．设计子模式属于数据库设计的

B．回溯的方法

[

]

D．自顶向下的方法

[

]

D．自顶向下的方法

[ [

] ]

A．需求分析 B．概念设计 C．逻辑设计 D．物理设计

4．概念结构设计的主要目标是产生数据库的概念结构，该结构主要反映 A．应用程序员的编程需求 B．DBA的管理信息需求

（2003/9/21） （高教--答案，第5、6章） 05-13

C．数据库系统的维护需求 D．企业组织的信息需求

5．数据库设计人员和用户之间沟通信息的桥梁是 [ ] A．程序流程图 B．实体联系图 C．模块结构图 D．数据结构图

6．有两个不同的实体集，它们之间存在着一个1:1联系和一个M:N联系，那么根据ER模

型转换成关系模型的规则，这个ER结构转换成的关系模式个数为 [ ] A．2个 B．3个 C．4个 D．5个

7．如果有10个不同的实体集，它们之间存在着12个不同的二元联系（二元联系是指两个

实体集之间的联系），其中3个1:1联系，4个1:N联系，5个M:N联系，那么根据ER模型转换成关系模型的规则，这个ER结构转换成的关系模式个数为 [ ]

A．14个 B．15个 C．19个 D．22个

[

]

A．每个实体类型转换成一个关系模式 B．每个联系类型转换成一个关系模式 C．每个M:N联系类型转换一个关系模式

D．在处理1:1和1:N联系类型时，不生成新的关系模式

9．当同一个实体集内部的实体之间存在着一个1:N联系时，那么根据ER模型转换成关系模型的规则，这个ER结构转换成的关系模式个数为 [ ] A．1个 B．2个 C．3个 D．4个

10．当同一个实体集内部的实体之间存在着一个M:N联系时，那么根据ER模型转换成关

系模型的规则，这个ER结构转换成的关系模式个数为 A．1个 B．2个 C．3个 D．4个

[ [

] ]

8．在ER模型转换成关系模型的过程中，下列叙述不正确的是

11．在数据库设计中，子类与超类存在着 A．相容性联系

C．继承性的联系

B．调用的联系 D．一致性联系

5.3.3 设计题

假设要为某商业集团设计一个数据库，该集团中有若干仓库、若干商店、经销若干商品。 试画一个有关仓库、商店、商品、采购员、职工、顾客、供应商、采购、入库、出库、销售聘用等信息的ER图。

5.3.4 ER图实例

在数据库设计中，ER模型的设计是一个很重要的环节。为了帮助学习者提高数据库设计水平，有利于毕业设计和今后的工作，我们从毕业生的论文中挑选了5个ER模型，供参考。这些设计并不是惟一的，可能还不完善，但大家从中可得到有益的启发，拓宽思路。 1．某学员为医院“住院管理信息系统”设计了数据库的ER模型，对医生、护士、病人、病房、诊断、手术、结账等有关信息进行管理，其ER图如图5.11所示。

这个ER图有8个实体类型，其属性如下： 病人（住院号，姓名，性别，地址） 医生（医生工号，姓名，职称） 护士（护士工号，姓名，职称）

病床（病床编号，床位号，类型，空床标志） 手术室（手术室编号，类型）

手术（手术标识号，类型，日期，时间，费用）

（2003/9/21） （高教--答案，第5、6章） 05-14

诊断书（诊断书编号，科别，诊断）

收据（收据编号，项目，金额，收款员，日期）

这个ER图有11个联系类型，其中1个是1：1联系，8个1：N联系，2个是M：N联系。联系的属性如下：

协助（角色）

处方（处方单号，序号，药品名称，规格，数量，费用） 入住（入院日期，出院日期）

试把这个ER图转换成关系模型。并指出各个关系模式的主键和外键。 N 诊断书 医生 1 书写 M 1 M N 主刀 N 护士 协助 处方 拥有 N N 手术 N N 接受 1 N 1 1 病人 1 位于 入住 结账 1 手术室 1 病床 N 收据 1 N 安排 分配 1 图5.11住院管理信息系统的ER图

2．某学员为电脑专卖店设计开发了“电脑销售信息管理系统”，数据库的ER模型对商品、供应商、仓库、营业员、门店的有关信息进行了管理，其ER图如图5.12所示。 这个ER图有7个实体类型，其属性如下：

商品（商品编号，名称，类别，单位，单价） 供应商（供应商编号，名称，账号，地址）

仓库（仓库编号，地址，负责人） 门店（门店编号，名称，地址）

采购员（采购员编号，姓名，业绩）

管理员（管理员编号，姓名，业绩） 营业员（营业员编号，姓名，业绩）

这个ER图有7个联系类型，其中2个是1：N联系，1个M：N联系，4个是M：N：

（2003/9/21） （高教--答案，第5、6章） 05-15

P联系。联系的属性如下：

采购（采购单号，数量，日期） 进货（进货单号，数量，日期） 配送（配送单号，数量，日期） 销售（销售单号，数量，日期）

存储（库存量，日期，安全库存量）

试把这个ER图转换成关系模型。并指出各个关系模式的主键和外键。 M 采购员 N 营业员 采购 进货 管理 N 供应商 M 管理员 N P 商品 N M M 存储 P N 1 仓库 M N 销售 配送 N 属于 P 1 P 门店

图5.12 电脑销售信息管理系统的ER图

3．某学员为证券营业网点设计的业务信息管理系统，对客户、资金、证券和业务活动进行了管理，其ER图如图5.13所示。

该ER图有5个实体类型，其结构如下：

客户（股东账号，身份证号，姓名，地址，客户类别，开户日期）

资金（资金账号，金额，可取余额，冻结金额，解冻金额，利息，日期） 证券（证券代码，名称，每手股数）

委托（委托序号，数量，买卖类别，价格，时间，操作员） 成交（成交序号，数量，买卖类别，成交价格，时间）

该ER图有8个联系类型，其中6个1:N联系，2个M:N联系。其中，联系的属性如下：

持有（金额，可用数量，冻结数量，解冻数量，日期）

存取（存取单序号，存取标志，金额，日期）

试把这个ER图转换成关系模式集，并指出每个模式的主键和外键。

1 证券 委托 N 冻结2

N N N 1 申请 持有 1 冻结1 M M （2003/9/21） （高教--答案，第5、6章） 05-16

1 过户 客户

4．某学员为某出版社设计了图书发行信息管理系统，数据涉及到图书、作者、开印、入库、客户和发行员等信息。得到的全局ER图如图5.14所示。

作者 开印单 入库单

出库 M M N N 编著 开印 入库 N 1 图书 M 收款 1 M P 发行员 订购 N N 客户 N

该ER图有6个实体类型，其结构如下：

图5.14 图书发行系统的ER图

图书（图书编号，书名，定价，包本数，开本，统一书号，库存量） 作者（作者编号，姓名，性别，地址，电话）

开印单（印单号，开单日期，定价，印数，制单人）

入库单（入库单号，日期，送书单位，数量，包本数，版印次） 发行员（发行员代号，姓名，电话）

客户（客户编号，名称，地址，开户行，账号，税号，收款方式）

实体类型之间有6个联系，其中2个1:N联系，3个M:N联系，1个M:N:P联系，在图上均已标出。其中联系的属性如下所示。

（2003/9/21） （高教--答案，第5、6章） 05-17

订购（订购单号，日期，数量）

出库（出库单号，日期，数量，包本数） 收款（收款单号，金额，收款日期） 编著（日期，备注）

试将ER图转换成关系模型，并注明主键和外键。

5．某学员为上海闵行区物资供应公司设计了库存管理信息系统，对货物的库存、销售等业务活动进行管理。其ER图如图5.15所示。

P 供应商 M 入库 N 采购员 M 报损单 N 销售员 N 采购 报损 定单 N 1 货物 M 存储 M P 客户 M P 出库 P N 仓位 N 图5.15 库存管理系统的ER图

该ER图有7个实体类型，其结构如下：

货物（货物代码，型号，名称，形态，最低库存量，最高库存量） 采购员（采购员号，姓名，性别，业绩） 供应商（供应商号，名称，地址）

销售员（销售员号，姓名，性别，业绩）

客户（客户号，名称，地址，账号，税号，联系人） 仓位（仓位号，名称，地址，负责人）

报损单（报损号，数量，日期，经手人）

实体间联系类型有6个，其中1个1:N联系，1个M:N联系，4个M:N:P联系。其中联系的属性如下。

入库（入库单号，日期，数量，经手人）

出库（出库单号，日期，数量，经手人） 存储（存储量，日期）

定单（定单号，数量，价格，日期）

（2003/9/21） （高教--答案，第5、6章） 05-18

采购（采购单号，数量，价格，日期）

试将ER图转换成关系模型，并注明主键和外键。

5.4 自测题答案

5.4.1 填空题答案

1．总体信息需求 处理需求 DBMS特征 硬件和OS特性 2．完整的数据库结构 应用程序设计原则 3．系统调查 可行性分析 确定总目标和制定项目开发计划 4．业务流程图

系统范围图

数据流程图

数据字典

5．数据项 数据结构 数据流 数据存储 加工过程 6．企业组织信息需求

7．设计局部概念模式 综合成全局概念模式 评审 8．自顶向下逐步细化 自底向上逐步综合

9．把概念模式转换成DBMS能处理的模式

10．形成初始模式 设计子模式 应用程序设计梗概 模式评价 模式修正 11． 存储记录结构设计 确定数据存储安排 访问方法的设计

完整性安全性设计 程序设计

12．DBA

13．DB的转储与恢复 DB的安全性与完整性控制 DB的重组织和重构造

DB性能的监督、分析和改进

5.4.2 单项选择题答案

1．D

7．B

2．C 8．B

3．C 9．A

4．D 10．B

5．B 11．C

6．B

5.4.3 设计题答案

客户 N 销售 P N 聘用 （高教--答案，第（2003/9/21）5、 6章） 05-19 1 商店P 商品 M 出库 N M 采购员 M 采购 N 供应商 M 这个数据库一种可能的ER图如图5.16所示，图中只画出实体、联系，未画出其属性。

入库 P 仓库 N P 图5.16 库存管理系统的ER模型

职工 5.4.4 ER图实例答案

1．解：根据ER图和转换规则，8个实体类型转换成8个关系模式，2个M：N联系转换成2个关系模式。因此，图5.11的ER图可转换成10个关系模式，如下所示：

病人（住院号，姓名，性别，地址，病房编号，床位号，入院日期，出院日期）

医生（医生工号，姓名，职称）

护士（护士工号，姓名，职称，手术室编号）

病床（病床编号，床位号，类型，空床标志，护士工号）

手术室（手术室编号，类型）

手术（手术标识号，类型，日期，时间，费用，手术室编号，医生工号，住院号） 诊断书（诊断书编号，科别，诊断，医生工号，住院号） 收据（收据编号，项目，金额，收款员，日期，住院号）

协助（手术标识号，医生工号，角色）

处方（处方单号，序号，药品名称，规格，数量，费用，住院号，医生工号）

2．解：根据ER图和转换规则，7个实体类型转换成7个关系模式，1个M：N联系和4个M：N：P联系转换成5个关系模式。因此，图5.12的ER图可转换成12个关系模式，如下所示：

商品（商品编号，名称，类别，单位，单价） 供应商（供应商编号，名称，账号，地址） 仓库（仓库编号，地址，负责人）

门店（门店编号，名称，地址）

采购员（采购员编号，姓名，业绩）

管理员（管理员编号，姓名，业绩，仓库编号） 营业员（营业员编号，姓名，业绩，门店编号）

采购（采购单号，数量，日期，采购员编号，供应商编号，商品编号） 进货（进货单号，数量，日期，供应商编号，商品编号，仓库编号） 配送（配送单号，数量，日期，商品编号，仓库编号，门店编号） 销售（销售单号，数量，日期，商品编号，门店编号，营业员编号） 存储（商品编号，仓库编号，日期，库存量，安全库存量）

3．解：根据ER图和转换规则，5个实体类型转换成5个关系模式，2个M:N联系转换成2

个关系模式。因此，图5.13的ER图可转换成7个关系模式，如下：

客户（股东账号，身份证号，姓名，地址，客户类别，开户日期）

资金（资金账号，金额，可取余额，冻结金额，解冻金额，利息，日期） 证券（证券代码，名称，每手股数）

委托（委托序号，股东账号，证券代码，资金账号，数量，买卖类别，价格，时间，操作员）

成交（成交序号，股东账号，证券代码，资金账号，数量，买卖类别，成交价

格，时间）

（2003/9/21） （高教--答案，第5、6章） 05-20

持有（股东账号，证券代码，日期，金额，可用数量，冻结数量，解冻数量）

存取（存取单序号，股东账号，资金账号，存取标志，金额，日期）

4．据转换规则，ER图中有6个实体类型，可转换成6个关系模式，另外ER图中有3个M:N联系和1个M:N:P联系，也将转换成4个关系模式。因此，图5.14的ER图可转换成10个关系模式，具体如下：

图书（图书编号，书名，定价，包本数，开本，统一书号，库存量） 作者（作者编号，姓名，性别，地址，电话）

开印单（印单号，开单日期，图书编号，定价，印数，制单人）

入库单（入库单号，日期，送书单位，数量，包本数，版印次，图书编号） 发行员（发行员代号，姓名，电话）

客户（客户编号，名称，地址，开户行，账号，税号，收款方式） 订购（订购单号，日期，数量，客户编号，图书编号，发行员代号） 出库（出库单号，日期，数量，包本数，客户编号，图书编号） 收款（收款单号，金额，收款日期，客户编号，图书编号）

编著（作者编号，图书编号，日期，备注）

5．据转换规则，ER图中有7个实体类型，可转换成7个关系模式，另外ER图中有1个M:N联系和4个M:N:P联系，也将转换成5个关系模式。因此，图5.15的ER图可转换成12个关系模式，具体如下：

货物（货物代码，型号，名称，形态，最低库存量，最高库存量）

采购员（采购员号，姓名，性别，业绩） 供应商（供应商号，名称，地址）

销售员（销售员号，姓名，性别，业绩）

客户（客户号，名称，地址，账号，税号，联系人） 仓位（仓位号，名称，地址，负责人）

报损单（报损号，数量，日期，经手人，货物代码）

入库（入库单号，日期，数量，经手人，供应商号，货物代码，仓位号） 出库（出库单号，日期，数量，经手人，客户号，货物代码，仓位号） 存储（货物代码，仓位号，日期，存储量）

定单（定单号，数量，价格，日期，客户号，货物代码，销售员号）

采购（采购单号，数量，价格，日期，供应商号，货物代码，采购员号）

第6章 数据库的存储结构

6.1 基本内容分析

6.1.1 本章重要概念

本章有以下一些重要概念：

（1）计算机系统的存储介质层次。

（2）两种文件组织：定长记录和变长记录。被拴记录，悬挂指针，分槽式页结构。 （3）四种文件结构：堆文件、顺序文件、散列文件和聚集文件。 （4）索引技术：主索引及三种实现方法（稠密、稀疏、多级索引）；辅助索引；B+树索引文件；B树索引文件。

（5）散列技术：散列函数；散列索引；静态散列；动态散列（可扩充散列结构）。 （6）两种多键访问技术：网格文件和分区散列。

（2003/9/21） （高教--答案，第5、6章） 05-21

6.1.2 本章的重点篇幅

（1）教材中P214的图6.8（分槽式页结构）。

（2）教材中P224～232的B+树索引文件和B树索引文件。 （3）教材中P236～241的可扩充散列结构。 （2）教材中P242～244的网格文件。

6.2 教材中习题6的解答

6.1 名词解释

（1）·定长记录文件：记录为定长格式的文件。

·变长记录文件：记录为变长格式的文件。

·被拴记录（pinned record）：被指针指向的记录，称为被拴记录。

·悬挂指针（dangling pointer）：如果指针指向的记录已被删除，那么该指针称为悬挂指针。悬挂指针指向的空间称为“垃圾”，别人无法使用。 （2）·堆文件：以输入顺序为序的文件，称为堆文件。

·顺序文件：记录按查找键值升序或降序的顺序存储的文件，称为顺序文件。 ·散列文件：将记录的某个属性值通过散列函数求得的值作为记录的存储地址的文件，称为散列文件。

·聚集文件：可以存储多个关系（表）的记录的文件，称为聚集文件。 （3）·有序索引：根据记录中某种排序顺序建立的索引，称为有序索引。

·主索引：如果索引的查找键值的顺序与主文件的顺序一致，那么这种索引称为主索引，也称为聚集索引。 ·稠密索引：对于主文件中每一个查找键值建立一个索引记录，索引记录包括查找键值和指向具有该值的记录链表的第一个记录的指针。这种索引称为“稠密索引”。 ·稀疏索引：在主文件中，对若干个查找键值才建立一个索引记录，这种索引称为“稀疏索引”。 ·多级索引：在索引很大时，还可对索引建立索引，这样就形成树结构的多级索引。 ·辅助索引：不是根据主索引的查找键值，而是根据其他查找键值来寻找主文件的记录，这种索引称为辅助索引。

·平衡树：一棵m阶平衡树或者为空，或者满足以下四个条件： 每个结点至多有m棵子树；根结点或为叶结点，或至少有两棵子树；

每个非叶结点至少有m/2棵子树；叶结点在同一层次上。

·B+树：一棵m阶B+树是平衡树，多个结点至多有m-1个查找键值和m个指向子树的

指针，但叶结点中的指针指向主文件中的记录，而非叶结点形成了叶结点上的一个多级稀疏索引。

·B树：B树类似于B+树，B树中所有查找键值只能出现一次，但可出现任何结点上。 （4）·散列方法：根据记录的查找键值，使用一个函数计算得到的函数值，作为磁盘块的地址，对记录进行存储和访问，这种方法称为散列方法。

·桶溢出（散列碰撞）：在散列组织中，每个桶的空间是固定的，如果某个桶内已装满记录，还有新的记录要插入到该桶，这种现象称桶溢出。

·封闭散列法：即溢出桶拉链法。某桶号的空间分成基本桶和溢出桶两种。 ·开放式散列法：把桶的集合固定下来，也就是只考虑基本桶，不考虑溢出桶。如果有一个桶装满了记录，还需装入新记录时，就在桶集中挑选一个有空闲空间的桶去装新记录。

（2003/9/21） （高教--答案，第5、6章） 05-22

（5）·散列索引：把查找键值与指针一起组合成散列文件结构的一种索引。

·静态索引：在散列函数确定以后，所有的桶地址及桶空间都确定了。这种技术称为“静态散列”技术。 ·动态散列：桶空间可以随时申请或释放的散列技术，称为“动态散烈”技术。 ·可扩充散列：对静态散列中成倍扩充法的改进，能随时根据需要申请和释放桶。 （6）·单键索引：只使用一个查找键的查询，称为单键查询。 ·多键查询：使用多个查找键的查询，称为多键查询。

·网格文件：网格文件是由网格矩阵和线性标尺组成的结构，网格矩阵中每个格子中有一个指针，指向一个桶。

·分区散列：是对散列技术的扩充，能允许在多个属性上进行索引。

6.2 试叙述计算机系统的物理存储介质层次,并说明每一种介质的数据访问速度。 答：根据访问数据的速度、成本和可靠性，计算机系统的存储介质可分成以下六类： ① 高速缓冲存储器（cache）：这是一种静态的随机访问存储器（Static Random Access Memory，简记为SRAM）。CPU用cache存储器来加快程序的执行。 ② 主存或内存：这是一种动态的随机访问存储器（Dynamic RAM，简记为DRAM）。现在微机的内存已达200MB。

上述两种存储器是一种易失性存储器，即掉电时会丢失存储的内容。 ③ 快闪存储器（Flash Memory）：这种存储器采用EEPROM（电可擦写可编程只读存储器）技术，其优点是存取速度快，缺点是必须一次擦写或写入。其容量已达32兆位，存取速度7×10/s，写传输速度是430KB/s。

④ 磁盘：是一种直接访问存储器，现在微机上磁盘的容量已达180GB，I/O传输速度达80MB/s。

上述两种存储器属于非易失性存储器，也称为联机存储器。

⑤ 光盘：这种存储器是利用光学原理来存储数据，并通过激光元件来读取数据。自动光盘机的容量已达数千吉字节，旋传速度达400转/分钟，传输速度为200KB/s。数据视频盘（DVD）的容量在4～15吉字节之间。

⑥ 磁带：主要用于数据存档和备份。磁带的容量为1600～6250字节/英寸，一般可达50吉字节。自动磁带机可以存储数量级达太字节的数据。

上述两种存储器是一种脱机存储器，又称为第三级存储器。

6.3 试对“被拴记录”下个确切的定义。被拴记录在物理存储中起什么作用？有什么利弊？ 答：在数据库中，被指针指向的记录，称为“被拴记录”。被拴记录表示记录已被其他用户引用。如果不小心把被拴记录删掉，那么指向该记录的指针成了“悬挂指针”。悬挂指针指向的空间是“垃圾”，别人无法使用。

6.4 在教材（P212）的图6.5中，删除记录5。试比较使用下面各种操作时的利弊：

①把记录5以下的记录依次移上一个记录位置。 ②把最后一个记录（记录7）移到记录5的位置。 ③在记录5中置删除标志位，不移动记录。

答：①把被删记录后的记录依次移上来，平均要移动文件中的一半记录。

②把文件中最后一个记录填补到被删记录位置，这时只要移动一个记录。 ③在被删结点处置删除标志位，这时使指向该记录的指针成为悬挂指针。 6.5 在教材（P213）的图6.6的文件中，画出执行下列三个操作后的文件结构：

①插入（AN，B-678，800）记录； ②删除记录2；

③插入（AN，A-384，600）记录。

（2003/9/21） （高教--答案，第5、6章） 05-23

-8

答：解：①插入记录在“记录1”处。

②删掉记录2，并且记录2链接到被删结点链表的链首处。 ③插入记录在“记录2”处。 此时图见图6.1。

文件首部 0 1 2 3 4 5 6 7 8

LIU AN AN A-102 B-678 A-384 600 800 600 600 800 600 400

ZHANG A-214 LIU B-215 ZHANG B-467 LIU C-333 图6.1

6.6 试举一个数据库应用例子，说明在表达变长记录时，有时预留空间方法要比指针形式好。并作解释。 答：譬如在文件中表达学生和选修课程情况，如果每个学生选修课程门数都在12~15门之间，那么此时使用预留空间形式较好，空间浪费较小。

6.7 试举一个数据库应用例子，说明在表达变长记录时，有时指针形式比预留空间方法好。并作解释。

答：譬如在文件中表达学生和其奖惩情况，每个学生的奖惩项目的差别是比较大的，那么此时用指针表示方式较好。

6.8 在教材（P215）的图6.9变长记录预留空间的文件中，画出执行下列三步操作后的文件结构：

①插入（HE，E-254，800）记录；

②插入（LOU，C-293，600）记录； ③删除（LIU，C-333，400）记录。

解：执行题中三步操作后的文件结构如图6.2所示。

0 1 2 3 4 5

LIU WEN HE ZHANG ZHOU LOU A-102 B-306 F-257 A-214 C-343 B-428 600 700 800 600 750 850 B-215 ⊥ E-254 B-467 ⊥ C-293 800 ⊥ 800 600 ⊥ 600 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ 图6.2

6.9 在教材（P215）的图6.9的文件中，如果还要插入（LIU，F-834，750）记录，会发生什么现象？如何处理？有何利弊？

解：此时，LIU的记录长度超过最大长度，此时有两种实现方式： 一种是改组文件，增加记录长度，以适应应用的需要。但这样有可能造成空间浪费。

（2003/9/21） （高教--答案，第5、6章） 05-24

另一种是再取一个记录，放（LIU, F-834, 750）值，但是应该使这一条记录与原来的记

录联系起来，可通过指针等方法来实现。

6.10 在教材（P216）的图6.10变长记录指针表示方式的文件中，画出执行下列三步操作后的文件结构：

①插入（HE，E-254，800）记录；

②插入（LOU，C-293，600）记录； ③删除（LIU，C-333，400）记录。

解：执行题中三步操作后的文件结构如图6.3所示。

0 1 2 3 4 5 6 7 8 9 10

LIU WEN HE ZHANG ZHOU LOU A-102 B-306 F-257 A-214 C-343 B-215 B-428 B-467 E-254 C-293 600 700 800 600 750 800 850 600 800 600 图6.3

6.11 在顺序文件组织中，为什么只有一个溢出记录时，仍然要申请一个溢出块存放这个溢出记录？

答：由于文件被组织成物理块的形式，当数据块放满时，只能再申请一个溢出块，把溢出记录放到溢出块中。

6.12 在关系数据库存储时，试说出下面每种存储技术的两个优点和两个缺点：

①每个文件中只存储一个关系；

②每个文件中存储多个关系（或整个数据库）。

答：①每个文件存储一个关系。其优点是：管理简单，一般的OS就能实现；系统实现方便，一般适用于规模小的数据库。其缺点是文件之间分离，没有联系；数据联系通过软件实现，效率较低。

②每个文件中存储多个关系。其优点是：使有联系的数据混放在一起，提高查询速度；加强数据之间的联系。其缺点是：增加了系统的复杂性；对两个文件中的查询处理，速度将变慢。

6.13 设关系数据库中有两个关系：

COURSE（COURSE_NAME，TEACHER） ENROLLMENT（COURSE_NAME，STUDENT_NAME，GRADE）

设有三门课程，五个学生，学生与课程间有选修联系。试用聚集文件表示这两个关系的文件结构。

解：设有三门课程：PL、OS、DB，五个学生：BAO、CHEN、GU、HAI和YU。如果用户查询多数是从课程找选修的学生。那么可用图6.4表示这个文件：

（2003/9/21） （高教--答案，第5、6章） 05-25

PL PL PL OS OS DB DB DB

WU BAO GU LIU GU MA BAO YU 85 95 90 80 70 OS CHEN 90 图6.4

6.14 什么情况下使用稠密索引比稀疏索引要好？并请作必要的解释。

答：在存取时间和空间开销方面，如果强调存取时间，那么应采用稠密索引。这是因为稠密索引是对每个查找键值建立一个索引记录，所以查找速度较快。

6.15 索引机制加快了查询处理，但为什么文件只在单属性的查找键上建索引？尽可能所出你的理由。

答：文件只在单属性的查找键上建索引，这样可以简化系统的管理。如果一个索引有多个属性构成，那么在查询时，若查询条件不是等值操作，而是比较操作，就会带来复杂性，会有较多的I/O操作。

6.16 主索引和辅助索引之间有什么区别？

答：两种索引的区别在于： 主索引是指索引的查找键值的顺序与主文件的顺序一致的索引。而辅助索引，是指索引的查找键值的顺序与主文件的顺序不一致的索引。

6.17 在同一关系上能否对两个不同查找键值建立两个主索引？为什么？

答：在同一关系上不允许对两个不同查找键值建立两个主索引，这是因为大多数情况下，主文件的顺序不可能同时与两个索引的查找键值顺序一致。

6.18 设查找键值集为{2，3，5，7，11，17，19，23，29，31}。假设初始时B+树为空，按升序次序插入键值。就下面三种情况建立三棵B+树： ① 4阶； ② 6阶； ③ 8阶。 解：①4阶B+树如图6.5所示。 19 符合B+树要求：

每个叶结点至少应有2个查找键，

5，11 29 至多有3个查找键；每个非叶结点至少应有2个指针，至多有4个指针；根结点或者没有指针，或者至少2个指针至多有4个指针。

2，3

5，7

11，17

19，23 29，31 图6.5

+

②6阶B树如图6.6所示。

（2003/9/21） （高教--答案，第5、6章） 05-26

7，19

2，3，5

7，11，17 图6.6

19，23，29，31

+

③8阶B树如图6.7所示。

2，3，5，7 11，17，19，23，29，31 图6.7

6.19 对6.18题中建立的B+树，试叙述下列查找操作的过程：

① 找查找键值为11的记录；

② 找查找键值在7~17之间的记录； 解：B+树的查询方法如下： 要检索查找键值为k的所有记录，首先在根结点中找大于k的最小查找键值（设为Ki），然后沿着Ki左边的指针Pi到达第二层的结点。在第二层的结点，用类似的方法找到一个指针，进入第三层的结点„„，一直到进入B+树的叶结点，找到一个指针直接指向主文件的记录，或指向一个桶（存放指向主文件记录的指针），最后把所需记录找到。 （对6.18题中建立的B+树的查找过程略）

6.20 对6.18题中建立的B+树，画出执行下列每一步操作后B+树：

① 插入9； ② 插入10； ③ 插入8； ④ 删除23； ⑤ 删除19 解：（1）对6.18题中的4阶B+树，在插入查找键值9，10，8后，如图6.8所示。 2，3

再删除23后，如图6.9所示。

11

19 11 5，9，11 29 5，7，8

9，10

11，17 图6.8

19，23 29，31 5，9 19 （2003/9/21） （高教--答案，第5、6章） 05-27

2，3 5，7，8 9，10 图6.9 11，17 19，29，31

再删除19后，如图6.10所示。

5，9 29 11 2，3

5，7，8

9，10 图6.10

11，17 29，31

（2）对6.18题中的6阶B+树，在插入键值9、10、8后，如图6.11所示。

7，10，19 2，3，5

7，8，9

10，11，17 19，23，29，31 图6.11

再删除23、19后，如图6.12所示。

+

（3）对6.18题中的8阶B树，在插入键值9、10、8和删除23、19后，如图6.13所示。

2，3，5，7，8，9，10 11 2，3，5

7，8，9

图6.12

10，11，17，29，31 7，10 11，17，29，31 （2003/9/21） （高教--答案，第5、6章） 05-28

图6.13

6.21 对于6.18题的查找键值集，建立B树。

解：据教材中的描述，m阶B树，非叶结点中最多可包含m个指针和m-1个查找键值，而叶结点最多可包含n个指针和n-1个查找键值，而n和m间关系有n>m。 （1）对6.18题中的查找键值集，建立4阶B树。

此时非叶结点中最多3个查找键值，而假设叶结点中最多可以4个查找键值。

再插入2、3、5、7、11后的B树如图6.14所示。

2，3

图6.14

5 7，11

再插入17、19、23、29、31后的B树如图6.15所示。

2，3

7，11 图6.15

19，23，29，31 5，17

（2）对6.18题中的查找键值集，建立6阶B树。

（3）对6.18题中的查找键值集，建立8阶B树。 此时非叶结点中最多7个查找键值，而假设叶结点中最多可以8个查找键值。

在插入10个键值后的B树如图6.17所示。

11 （2003/9/21） （高教--答案，第5、6章） 05-29

此时非叶结点中最多5个查找键值，而假设叶结点中最多可以6个查找键值。 在插入10个键值后的B树如图6.16所示。

7 2，3，5

图6.16

11，17，19，23，29，31

2，3，5，7

图6.17

17，19，23，29，31

6.22 封闭式散列法和开放式散列法之间有什么区别？在数据库应用中，这两种方法各有什么利弊？

答：封闭式散列法和开放式散列法是指在桶溢出时所采用的方法。

（1） 封闭式散列法是指每个桶号的存储空间分成基本桶和溢出桶两种。溢出桶链接成一条溢出链，查找某桶号的数据就在这条溢出链中进行，不会到其他溢出链中查找。 （2） 开放式散列法是把桶集固定下来，也就是只考虑基本桶，不考虑溢出桶。如果有一个桶装满了记录，那么就在桶集中挑选一个有空闲空间的桶，装入新记录。

封闭散列法的优点是查找速度快，但结构比较复杂。开放散列法的空间较省，但插入、删除操作比较复杂。所以现在大多数DBS中都是使用封闭散列法。

6.23 在散列文件组织中，是什么原因引起桶溢出的？有什么办法能减少桶溢出的次数？ 答：产生桶溢出的原因有两个： 初始设计时桶数偏少；散列函数的“均匀分布性”不好。 对于前一个原因，在设计散列函数时，桶数应放宽些，一般存储空间应有20%的余量，让它空闲着，以利减少桶溢出的机会。对于后一个原因，不管散列函数如何好，再留有空间余量，桶溢出现象难免还会发生，因此用封闭散列法和开放式散列法来解决桶溢出问题。 6.24 设查找键值集为{2，3，5，7，11，17，19，23，29，31}，散列函数为h（x）=（x mod 8），每个桶可存储3个记录。试建立一个可扩充散列结构，并画出示意图。 解：查找键值的散列值为：

键值X 2 3 5 7 11 17 19 23 29 31

插入键值2、3、5后的可扩充散列结构，如图6.18所示。

0 0 0 2 3 5 （2003/9/21） （高教--答案，第5、6章） 05-30 桶0 散列值h（X） 2（010） 3（011） 5（101） 7（111） 3（011） 1（001） 3（011） 7（111） 1（001） 7（111）

桶地址表

图6.18

在插入键值7、11后的结构图，如图6.19所示。 桶0

1 1 0 2 1 3 11 1 桶1 5 7

图6.19

再插入键值17后的结构图，如图6.20所示。 2 桶0

17

2 2 桶1 2

3 11 1 桶2，桶3 5 7

图6.20

再插入键值19、23、29、31后的结构图，如图6.21所示。 2 桶0，桶1 17 3 29 （2003/9/21） --答案，第5、6章） 05-31

0 1 2 3 0 1 2 3 4 （高教

6.25 对6.24题中的可扩充散列结构，试叙述执行下列各操作后可扩充散列结构如何变化：

① 删除11； ② 删除31； ③ 插入1； ④ 插入15。 解：在6.24题的可扩充散列结构中，执行本题的各个操作后，得到的结构图如图6.22所示。

2 桶0 12 29 1 （2003/9/21） （高教--答案，第5、6章） 05-32

2 7 23 31 2 5 桶6，桶7

3 3 11 19 桶4，桶5

3 桶3 桶2 2 图6.21

0 1 2 3

图6.22

2 7 23 15 2 2 桶1 2 3 19 2 5 桶2

桶3

6.26 为什么散列结构不适宜对查找键进行范围查询？ 答：由于范围查询的查找键是分散在各个桶中，因此散列结构不适宜对查找键进行范围查询。

（2003/9/21） （高教--答案，第5、6章） 05-33