ch10 数据库系统概念(第6版)第十章存储结构和文件结构

数据库复习题汇总

单元练习 一单项选择题 1.文件系统与数据库系统相比较，其缺陷主要表现在数据联系弱、数据冗余和（）。 A.数据存储低 B.处理速度慢 C.数据不一致 D.操作烦琐 2.数据的存储结构与数据逻辑结构之间的独立性称为数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 数据存储结构：即内模式。 数据逻辑结构：即模式 用户视图：即外模式 3.在数据库系统中，对数据操作的最小单位是（）。 A.字节 B.数拯项 C.记录 D.字符 4.数据的逻辑结构与用户视图之间的独立性称为数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 5.下述各项中，属于数据库系统的特点的是（）。 A.存储量大 B.存取速度快 C.数据共享 D.操作方便 6.在数据库系统中，模式/内模式映像用于解决数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 7.在数据库系统中，模式/外模式映像用于解决数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 8.数据库结构的描述，称为（）。 A.数据库模型 B.数据库 C.数据库管理系统 D.数据字典 数据库模型有层次模型网状和关系模型 9.数据库中全体数据的逻辑结构描述称为（ A. 存储模式 B.内模式 C.外模式 D.模式 10.保证数摇库中数摇及语义的正确性和有效性，是数据库的（）。 A.完全性 B.准确性 C.完整性 D.共享性 11.在数据库系统中，数据独立性是指（）。 A.用户与计算机系统的独立性 B.数据库与il?算机的独立性 C.数据勺应用程序的独立性 D.用户与数摇库的独立性 12.结构数据模型的三个组成部分是数据结构、数据操作和（）。 A.数据安全性控制 B.数摇一致性规则 C.数^]^完整性约束 D.数摇处理逻辑 13.在数据操纵语言（DML）的基本功能中，不包括的是（）。 A.插入新数据 B.描述数据库结构 C.对数据库中数据排序 D.删除数据库中数据 14.控制数摇库整体结构、负责数据库物理结构和逻辑结构的注义打修改的人员是（）。 A.系统分析员 B.应用程序员 C.专业用户 D.数据库管理员 15.K列关于数据库系统正确的叙述是（）。 A.数据库系统比文件系统存储数据量大 B.数据库系统中数据存储没有冗余 C.数据库系统中数据存储冗余较小 D.数据库系统比文件系统存取速度快 16.在数据库中，发生数据不一致现象的根本原因是（）。 A.数据存储量太大 B.数摇安全性差 C.数据相互关系复杂 D.数据冗余 17.层次型、网状型和关系型数据模型的划分根据是（）。 A.数据之间联系方式 B.数据之间联系的复杂程度

数据库的体系结构

数据库基础 （ 视频讲解：25分钟） 本章主要介绍数据库的相关概念，包括数据库系统的简介、数据库的体系结构、数据模型、常见关系数据库。通过本章的学习，读者应该掌握数据库系统、数据模型、数据库三级模式结构以及数据库规范化等概念，掌握常见的关系数据库。 通过阅读本章，您可以： 了解数据库技术的发展 掌握数据库系统的组成 掌握数据库的体系结构 熟悉数据模型 掌握常见的关系数据库 1 第 章

1.1 数据库系统简介 视频讲解：光盘\TM\lx\1\数据库系统简介.exe 数据库系统（DataBase System，DBS）是由数据库及其管理软件组成的系统，人们常把与数据库有关的硬件和软件系统称为数据库系统。 1.1.1 数据库技术的发展 数据库技术是应数据管理任务的需求而产生的，随着计算机技术的发展，对数据管理技术也不断地提出更高的要求，其先后经历了人工管理、文件系统、数据库系统等3个阶段，这3个阶段的特点分别如下所述。 （1）人工管理阶段 20世纪50年代中期以前，计算机主要用于科学计算。当时硬件和软件设备都很落后，数据基本依赖于人工管理，人工管理数据具有如下特点： ?数据不保存。 ?使用应用程序管理数据。 ?数据不共享。 ?数据不具有独立性。 （2）文件系统阶段 20世纪50年代后期到60年代中期，硬件和软件技术都有了进一步发展，出现了磁盘等存储设备和专门的数据管理软件即文件系统，文件系统具有如下特点： ?数据可以长期保存。 ?由文件系统管理数据。 ?共享性差，数据冗余大。 ?数据独立性差。 （3）数据库系统阶段 20世纪60年代后期以来，计算机应用于管理系统，而且规模越来越大，应用越来越广泛，数据量急剧增长，对共享功能的要求越来越强烈。这样使用文件系统管理数据已经不能满足要求，于是为了解决一系列问题，出现了数据库系统来统一管理数据。数据库系统满足了多用户、多应用共享数据的需求，它比文件系统具有明显的优点，标志着管理技术的飞跃。 1.1.2 数据库系统的组成 数据库系统是采用数据库技术的计算机系统，是由数据库（数据）、数据库管理系统（软件）、数

数据库的存储结构(文件、记录的组织和索引技术)

数据库的存储结构（文件、记录的组织和索引技术） by 沈燕然0124141 利用课余时间自学了第6章《数据库存储结构》，对于数据 库不同层次的存储结构，文件记录组织和索引技术有了一定的 了解，在这篇札记中将会结合一些具体应用中涉及到的数据存 储和索引知识，以及通过与过去学习过的一些数据结构比较来 记录自己学习的心得体会。这些实例涉及不同的数据库系统， 如Oracle, DB2和Mysql等等，它们之间会有一些差异。不过 本文旨在探讨数据存储方面的问题，因而兼容并包地将其一并收入，凡是可能需要说明之处都会加上相应的注解。：） 1、数据库（DBS）由什么组成？——逻辑、物理和性能特征 1、什么是数据库系统（DBS）——DBS用文件系统实现 在关系模型中，我们把DBS看成关系的汇集。DBS存在的目的就是为了使用户能够简单、方便、容易地存取数据库中的数据。因此在用户的眼中，数据库也就是以某种方式相关的表的集合。用户并不需要去关心表之间关系，更不需要了解这些表是怎样存储的。但是我们现在从DBA(数据库管理员)的角度来看，情况就比那稍稍复杂一点。 实际的数据库包含许多下面列出的物理和逻辑对象： ?表、视图、索引和模式(确定数据如何组织) ?锁、触发器、存储过程和包(引用数据库的物理实现) ?缓冲池、日志文件和表空间(仅处理如何管理数据库性能) 2、什么是表空间？——表空间相当于文件系统中的文件夹。 表空间被用作数据库和包含实际表数据的容器对象之间的一层，表空间可以包含多个不同的表。用户处理的实际数据位于表中，他们并不知道数据的物理表示，这种情况有时被称为数据的物理无关性。

上图描述了一个ORACLE数据库大致的表空间组织，USER中存放主要的数据表,TEMP存放临时数据表,INDX存放索引,TOOLS存放回退段(RBS). 表空间在DB2数据库系统中是比较典型的说法，在Mysql等系统中也直接使用文件系统中文件夹的概念。新建一个表的时候可以指定它所在的表空间，至于用文件具体存储数据时如何存储这可能就是各个数据库系统的商业机密了，至少DB2是这样。另外值得关注的一点是不同于oracles对表空间的严格要求，Mysql的数据库形式相对比较简单，以文件夹的形式存放在安装目录的/data/下面，该数据库的每一个表对应两个文件，一个存放表中数据，另一个存放元数据信息，也就是建表时指明的列属性等等信息。 3、文件中的记录在物理上如何实现？——文件组织形式 在外存中，DB以文件形式组织，而文件由记录组成。文件结构由OS的文件系统提供和管理。文件组织有两种方式——定长记录格式和变长记录格式。 那种格式更好？ 定长记录格式——优点是插入操作较简单。 缺点是对记录长度有硬性要求，而且有的记录可能横跨多个快，降低读写效率。 变长记录格式——优点是记录长度自由方便 缺点是记录长度差异导致删除后产生大量“碎片”，记录很难伸长，尤其“被拴记录”移动代价相当大。 中庸之道——预留空间和指针方式 记录长度大多相近——采用预留空间方法，取最大记录长为统一标准，在短记录多于空间处填特定空值或记录尾标志符。 记录长度相差很大——采用指针形式（每纪录后的指针字段把相同属性值记录链接起来）。文件中使用两种块——固定块（存放每条链中第一条记录）和溢出块（存放其 余纪录）。 3、记录在文件中怎样组织？

数据库的存储结构

第五章数据库的存储结构 5.1数据库存储介质的特点 ●内存 容量低（一般只有几百M，最多一两个G），价格高，速度快，数据易丢失（掉电、当机等）。 一般做DBMS（或CPU）和DB之间的数据缓冲区。 实时/内存数据库系统中使用内存存放实时数据。 ●硬盘 容量高（一般有几十G，多到一两百G），价格中，速度较快，数据不易丢失（除非物理性损坏）。 一般做用来存放DB。 实时/内存数据库系统中使用硬盘存放历史数据库。 ●移动硬盘（USB接口） 容量高（一般有几十G），价格中，速度较快，数据不易丢失（除非物理性损坏）。 一般做用来做备份。 ●光盘 容量低（一般650M/片，但光盘可在线更换，海量），价格低，速度中，数据不易丢失（除非物理性损坏）。 一般做用来做备份。 ●磁盘（软盘） 容量低（一般有几M，优盘多到一两百M），价格中，速度较慢，数据不易丢失（除非物理性损坏）。 一般数据库不使用磁盘。 ●磁带 容量低（但可在线更换，海量），价格低，速度最慢，且要按顺序存取，数据不易丢失（除非物理性损坏）。 一般做用来做备份。 按速度从高到低： 内存、硬盘、USB盘（移动硬盘和优盘）、光盘、软盘、磁带。 按在线容量从大到小： 硬盘、移动硬盘、内存、光盘、磁带、优盘、软盘。 物理块：512byte/1K/2K/4K/8K 原因： (1)减少I/O的次数； (2)减少间隙的数目，提高硬盘空间的利用率。 ORACLE逻辑块与物理块（init.ora中db_block_size定义逻辑块大小） 缓冲块和缓冲区（即SGA中的Data Buffer Cache） 延迟写(delayed write)技术/预取(Prefetching)技术（ORACLE中由DBWR进程完成数据的读写）

数据库的内存结构

系统全局区域（SGA） 大型池（Large Pool） 在SGA中大型池是可选的缓冲区。它可以根据需要有管理权进行配置。它可以提供一个大的区以供象数据库的备份与恢复等操作。 Oracle实例的内存结构组织包含在称为系统全局区域（System Global Area,SGA）的内存区域中。SGA在虚拟内存中进行分配，用于存放Oracle服务器进程。SGA内存结构组织包括共享池、数据库缓冲区高速缓存以及重做日志缓冲区，许多进程共享SGA。 1.共享池 共享池包括两个组件----库高速缓存和数据字典高速缓存。库高速缓存和数据字典高速缓存。库高速缓存储存当前最新使用的SQL语句及其执行计划。数据字典高速缓存则储存最新使用的数据字典信息，如表的定义、用户名和权限等。共享池的大小可以影响数据库的性能，在OLTP环境中更是如此。 2.数据库缓冲区高速缓存 当用户提交一个SQL查询时，为完成请求，服务器进程先查找数据库缓冲区高速缓存中的数据块。如果数据库缓冲区高速缓存中没有用户要求的数据块，那么服务器进程必须从物理设备中读取数据块，并在该缓冲区高速缓存中存放此数据的备份，这样，对相同数据块的后续请求就可以在内存中找到，而无需物理读取。 3.重做日志缓冲区 数据进行的所有更改都存储在重做日志缓冲区中，这些记录在以后会被拷贝到重做日志文件中。 程序全局区域（PGA） 程序全局区域（Program Global Area,PGA）是包含一个单个服务器进程数据的内存区域。在用于专门的服务器配置时，PGA由排序区域、会话信息、游标状态和堆栈空间组成。PGA在一个进程开始时进行分配，并在进程终止时释放。 数据库实例 为了访问数据库中的数据，Oracle使用一组为所有用户共享的后台进程。此外，还有一些存储结构（统称为系统全局区域）用来存储最近从数据库查询的数据。通过减少对数据库文件的I/O次数，这些存储区域可以改善数据库性能。 Oracle数据库实例通常称为数据库服务器，用来访问数据库文件集的存储结构及后台服务进程的集合。一个数据库可以被多个实例访问（对应于Oracle的并行服务器选项）。1．服务器启动和关闭 在用户能够操作Oracle数据库之前，必须先对数据库服务器执行一个启动操作。这个过程包括启动一个数据库实例、数据库实例挂上数据库和打开数据库。在服务器启动之后，数据库就可以被使用了。 相反，通过执行数据库服务器关闭操作，可以使一个数据库不可用。服务器关闭是服务器的反过程：首先要关闭数据库，然后从实例卸载数据库，最后关闭实例。在服务器关闭后，用户不能访问数据库，知道重新启动服务器才可以再次访问。 2．服务器连接 在一个Oracle实例启动并运行后，可以建立于服务器的连接来执行数据库工作。在后台，数据库实例工作机制负责完成用户请求。在同一时间，在保持数据库完整的同时，数据库实例自动地保护全部事务的工作。

数据库原理习题与答案第3章数据库系统结构

第三章．数据库系统结构 习题： 一．选择题 1．数据库技术中采用分级方法将数据库的结构划分成多个层次，是为了提高数据库的（1）和（2）。 （1）A.数据独立性 B.逻辑独立性 C.管理规范性 D.数据的共享 （2）A.数据独立性 B.物理独立性 C.逻辑独立性 D.管理规范性 2．数据库中，数据的物理独立性是指。 A.数据库与数据库管理系统的独立 B.用户程序与DBMS的相互独立 C.用户的应用程序与存储在磁盘上数据库中的数据是相互独立的 D.应用程序与数据库中数据的逻辑结构相互独立 3．数据库系统的最大特点是。 A.数据的三级抽象和二级独立性 B.数据共享性 C.数据的结构化 D.数据独立性 4．在数据库的三级模式结构中，描述数据库中全体数据的全局逻辑结构和特征的是 。 A.外模式 B.内模式 C.存储模式 D.模式 5．数据库系统的数据独立性是指。 A.不会因为数据的变化而影响应用程序 B.不会因为系统数据存储结构与数据逻辑结构的变化而影响应用程序 C.不会因为存储策略的变化而影响存储结构 D.不会因为某些存储结构的变化而影响其它的存储结构 6．数据库三级模式体系结构的划分，有利于保持数据库的。 A.数据独立性 B.数据安全性 C.结构规范性 D.操作可行性

1．试述数据库系统三级模式结构，这种结构的优点是什么。 2．定义并解释以下术语：模式、外模式、内模式、DDL、DML。 3．什么叫数据与程序的物理独立性？什么叫数据与程序的逻辑独立性？为什么数据库系统具有数据与程序的独立性？

一．选择题 4．（1）B （2）B 5．C 6．A 7．D 8．B 9．A 二．简答题 1．数据库系统的三级模式结构由外模式、模式和内模式组成。外模式，亦称子模式或用户模式，是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。模式，亦称逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。模式描述的是数据的全局逻辑结构，外模式涉及的是数据的局部逻辑结构，通常是模式的子集。内模式，亦称存储模式，是数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述。 数据库系统的三级模式是对数据的三个抽象级别，它把数据的具体组织留给DBMS 管理，使用户能逻辑抽象地处理数据，而不必关心数据在计算机中的表示和存储。 为了能够在内部实现这三个抽象层次的联系和转换，数据库系统在这三级模式之间提供了两层映像：外模式/模式映像和模式/内模式映像，正是这两层映像保证了数据库系统中的数据能够具有较高的逻辑独立性和物理独立性。 2．模式，亦称逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。外模式，亦称子模式或用户模式，是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。内模式，亦称存储模式，是数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述。 DDL：数据定义语言，用来定义数据库模式、外模式、内模式的语言。 DML：数据操纵语言，用来对数据库中的数据进行查询、插入、删除和修改的语句。 3．数据与程序的逻辑独立性：当模式改变时，由数据库管理员对各个外模式//模式的映像做相应改变，可以使外模式保持不变。应用程序是依据数据的外模式编写的，从而

第二章数据库的存储结构

第2章数据库的存储结构 本章学习目标 本章主要介绍了基本的文件组织方式及各自的特点，并在此基础上介绍了Ｄ ＢＭＳ系统所采用的倒排表、索引链接文件与多重链表文件索引、Ｂ+树等快速文 件查找处理方法。通过本章学习，读者应该掌握以下内容： ●●顺序文件、链表文件、随机存取文件、索引组织文件等文件组织方 式的特点 ●●倒排表的操作 ●●Ｂ+树的组织结构与基本操作 在数据库系统设计时必须考虑如何在机器上实现的问题，要求能将各种数据存储在机器内，而且要能反映各种数据之间的联系；要求存储、维护尽可能方便高效；要求检索、使用数据操作简单，运行效率高。为此要讨论各种存储组织结构和各类索引结构。 数据库是利用文件系统来完成数据的存取的，数据及相关联系可在一个文件中存放，也可分别存放；文件有顺序文件，随机文件等不同类型；顺序文件又有按某个码排序的文件及按记录录入先后次序存放的文件等不同。 2.1基本文件组织 2.1.1顺序文件组织 在顺序文件中，记录被物理地按地址次序排列，排列顺序为按某一码值的升或降序，也可为记录录入的先后次序。 按码值排序时，其顺序还与存储方式有关。有按二进制数和ASCII码存储两种形式，如按前者，根据码值数值大小排序。如按后者，可视为字符串，对二个字符串比较时，从左边第一个字符起进行比较，直到对应字符不相同为止，此时该二字符的ASCII码值较大者对应的字符串较大。。例如“ABCDEF”和“ABZ”二个串，第三个字符对应不相同，其左边各字符对应都相同，则因“ABZ”的第三个字符的ASCII码值较大，这个串的值也就较大。采用这类排序文件，优点是在查找时可利用二分法，插值算法和分区算法等方法加快查找速度，缺点是在进行数据录入，修改、删除时要花费大量时间用于排序，非常耗时。而且，对于数据库数据的检索要求将是多方面的，例如按姓名查找某个人，或者按专业来查找一批人，或者按姓名与专业来查找一批人等，不可能按每一种检索要求生成一个排序文件，因为

数据库的体系结构

数据库的体系结构 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

数据库的体系结构 1.三级模式结构 数据库的体系结构分为三级：外部级、概念级和内部级（图），这个结构称为数据库的体系结构，有时亦称为三级模式结构或数据抽象的三个级别。虽然现在DBMS的产品多种多样，在不同的操作系统下工作，但大多数系统在总的体系结构上都具有三级结构的特征。 从某个角度看到的数据特性，称为数据视图(Data View)。 外部级最接近用户，是单个用户所能看到的数据特性，单个用户使用的数据视图的描述称为外模式。概念级涉及到所有用户的数据定义，也就是全局性的数据视图，全局数据视图的描述称概念模式。内部级最接近于物理存储设备，涉及到物理数据存储的结构，物理存储数据视图的描述称为内模式。 图三级模式结构 数据库的三级模式结构是对数据的三个抽象级别。它把数据的具体组织留给DBMS去做，用户只要抽象地处理数据，而不必关心数据在计算机中的表示和存储，这样就减轻了用户使用系统的负担。 三级结构之间往往差别很大，为了实现这三个抽象级别的联系和转换，DBMS在三级结构之间提供两个层次的映象(Mapping)：外模式／模式映象，模式／内模式映象。这里的模式是概念模式的简称。 数据库的三级模式结构，即数据库系统的体系结构如图所示。

图数据库系统的体系结构 2.三级结构和两级映象 （1）概念模式 概念模式是数据库中全部数据的整体逻辑结构的描述。它由若干个概念记录类型组成，还包含记录间联系、数据的完整性安全性等要求。 数据按外模式的描述提供给用户，按内模式的描述存储在磁盘中，而概念模式提供了连接这两级的相对稳定的中间点，并使得两级中任何一级的改变都不受另一级的牵制。概念模式必须不涉及到存储结构、访问技术等细节，只有这样，概念模式才能达到物理数据独立性。概念模式简称为模式。 （2）外模式 外模式是用户与数据库系统的接口，是用户用到的那部分数据的描述。外模式由若干个外部记录类型组成。 用户使用数据操纵语言(DML)语句对数据库进行操作，实际上是对外模式的外部记录进行操作。有了外模式后，程序员不必关心概念模式，只与外模式发生联系，按照外模式的结构存储和操纵数据。 （3）内模式 内模式是数据库在物理存储方面的描述，定义所有内部记录类型、索引和文件的组织方式，以及数据控制方面的细节。

试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------

数据库的物理结构设计

2.6 数据库物理结构设计 ?数据库在物理设备上的存储结构与存取方法称为数 据库的物理结构，它依赖于给定的计算机系统。 ?为一个给定的逻辑数据模型选取一个最适合应用环 境的物理结构的过程，就是数据库的物理设计。 ?充分了解应用环境，详细分析要运行的事务，以获得选择物理数据库设计所需参数 ?充分了解所用RDBMS的内部特征，特别是系统提供的存取方法和存储结构

?关系数据库物理设计的内容 –为关系模式选择存取方法(建立存取路径) –设计关系、索引等数据库文件的物理存储结构 ?物理数据库设计所需参数 －数据库查询事务（查询的关系，查询条件所涉及的属性，连接条件所涉及的属性，查询的投影属性）－数据更新事务（被更新的关系，每个关系上的更新操作条件所涉及的属性，修改操作要改变的属性值）－每个事务在各关系上运行的频率和性能要求

其他需考虑的问题： 目标DBMS支持的特性、功能和选项； 主机计算机系统的特性和能力； 磁盘存储配置； 数据量。

数据库物理设计步骤： 1.数据库逻辑模式调整 2.文件组织与存取设计 3.数据分布设计 4.安全模式设计 5.确定系统配置 6.物理模式评估

1数据库逻辑模式调整 将与平台无关的描述数据库逻辑结构的关系模式及其视图转换为所选定的具体DBMS平台可支持的基本表和视图，并利用DBMS提供的完整性机制设计定义在基本表上的面向应用的业务规则。 （1) 实现目标数据库基本表和视图 遵循目标数据库的语法规则或变通 （2)设计基本表业务规则 利用目标DBMS提供的Check、断言、触发器等完成完整性约束

2文件组织与存取设计 （1)分析事务的数据访问特性 ?使用事务/表交叉引用矩阵，分析系统內重要事务对各基表的访问情况，确定事务访问哪些基本表，对哪些基本表执行了何种操作，并进一步分析各操作涉及到的基本属性表。 将所有事务路径映射到表中； 确定哪些表最常被事务访问； 分析选出的包含了这些表的事务。

数据的存储结构是指

(1)数据的存储结构是指 (A)存储在外存中的数据(B)数据所占的存储空间量 (C)数据在计算机中的顺序存储方式(D)数据的逻辑结构在计算机中的表示 (2)下列关于栈的描述中错误的是 (A)栈是先进后出的先性表 (B)栈只能顺序存储 (C)栈具有记忆作用 (D)对栈的插入和删除操作中，不需要改变栈底指针 (3)对于长度为N的线性表,在最坏的情况下,下列各排序法所对应的比较次数中正确的是 (A)冒泡排序为N/2 (B)冒泡排序为N (C)快速排序为N (D)快速排序为N(N-1)/2 (4)对长度为N的线性表进行顺序查找,在最坏的情况下所需要的比较次数为 (A)log2n (B)n/2 (C)n (D)n+1 (5)数字字符0的ASCII值为48,若有以下程序main() { char a='1',b='2'; printf("%c,",b++); printf("%d\n",b-a); } 程序运行后的输出结果是 (A)3,2 (B)50,2 (C)2,2 (D)2,50 1.D 2.B 3.D 4.C 5.C （1）用二维表数据来表示实体及实体之间联系的数据模型称为＿＿。 （2）在Visual FoxPro中说明数组后，数组的每个元素在未赋值之前的默认值是＿＿。（3）可以在项目管理器的＿＿选项卡下建立命令文件。 （4）在Visual FoxPro中数据库文件的扩展名是＿＿，数据库表文件的扩展名是＿＿。（5）打开数据库设计器的命令是＿＿DA TABASE。 （6）SQL插入记录的命令是INSERT，删除记录的命令是＿＿，修改记录的命令是＿＿。 （7）在SQL的嵌套查询中，量词ANY和＿＿是同义词。在SQL查询时，使用子句指＿＿出的是查询条件。 （8）从职工数据库中计算工资合计的SQL语句是