【从零开始学习计算机科学】数据库系统（四）数据库的物理设计

数据库的物理设计

物理设计任务是考虑用文件表示逻辑数据模型(数据库模式)的不同方式。
一个数据库被映射到多个不同的文件(file)，文件由操作系统来管理，这些文件被永久存储在磁盘上。
一个文件在逻辑上被组织成记录的一个序列，记录被映射到磁盘块(block)上。每个文件(file)被分成定长的存储单元-块(block)，块是数据存储和传输的基本单位(默认一般是4-8KB)。
一个块可以包括很多记录(假设一个记录总比块小；对大数据如图片需单独处理和存储)，且一个记录的数据不能跨块存储。

记录的类型

定长记录

其为每条记录分配固定大小存储空间，可以简单地在连续空间中依次存储记录（类似线性表）。其记录不能跨块存储，因此每一块中只分配能完整容纳的最大记录数，会造成少量空间浪费。删除记录时会移动其他记录。为了节约实际，可建立空闲列表组织被删除记录空间，进行再利用。

定长记录

上图中为每条记录分配可容纳的最大字节数（53字节）

变长记录

数据库中变长记录出现的方式有以下三种：一个文件中存储多种类型的记录；记录中有变长字段；记录中有可重复字段，如数组。

实现变长记录，要解决的问题有：如何表示记录，使得能访问每个字段；如何在物理块中存储变长记录，使得能访问每条记录。

文件中记录的组织方式

文件中记录的组织方式主要有以下几种：

• 堆文件：记录在文件空间中任意放置；
• 顺序文件：按一定的顺序在文件中组织记录；
• 散列文件：按照散列函数计算值存放相应记录；
• 多表簇集文件：不同关系表里的记录存放在同一个文件中。

如果一条记录被删除，首先，它所占用的空间被释放，它所对应的条目被置成删除状态（例如将ES置为-1，该条目可以留作后面插入的记录使用）；其次，块中位于被删除记录左边的所有记录右移，使删除而被释放的空间集中到块的中部，所有被移动的记录所对应条目的EP值也需要跟着修改，使其指向记录的起始位置；最后，修改EFS的值，使它指向空闲空间的尾部，只要块中有空闲的空间，使用类似的技术可以使记录增长或缩短。由于块的大小有限，典型为4KB，因此在块内移动记录的代价并不会太高。

变长记录组织

顺序文件组织

顺序文件的逻辑组织方式将关系中记录按“某属性/组-搜索码”排列，并用指针将记录依序连接。其特点是按搜索码搜索的效率高。

顺序文件的物理组织方式：
将关系中记录按搜索码次序进行物理存储；采用定长记录或变长记录方式；一个记录的信息不能分存在两个物理块中。

顺序文件的物理组织方式

顺序文件组织的缺点是删除和插入记录时的开销大(大量移动记录)，改善方法是采用指针管理，即引入空闲列表，空闲列表组织被删除后的空间。

执行删除后的文件组织

执行插入后的文件组织

当待插入位置没有空间时，用溢出块存放插入的记录。但需定期执行重组。

多表聚集文件组织

多表聚集文件组织是指将多个关系的数据组织在一个文件中（它们的记录相互交织在一起）。

多表聚集文件组织

实现多表聚集文件组织，需底层操作系统配合，实现对文件的管理(只有大型数据库系统才支持)。这种方式的优点是对同一个文件内的表进行连接查询的效率高，
不足之处是单表查询效率低，且记录大小可变。改进思路是将指针链添加到链接特定关系的记录，即使用指针将属于一个表的全部记录连接起来。

改进后多表聚集文件组织

物理设计的任务

前面，介绍了大型数据库管理系统(DBMS)支持的文件中记录的物理存储方式，实际上都是由DBMS自动实现对用户定义好的逻辑数据(关系)的自动存储，似乎物理存储对用户是透明的，就像大家上机所感受的一样。
那么，数据库应用设计人员还需要做物理设计工作吗，如何做？

数据库物理设计（应用开发中）的主要工作是：

1. 在定义关系模式时，需要确定采用定长还是变长记录。解决此问题可以通过确定采用的属性类型，因有变长属性。
2. 对每个关系模式，需要确定影响记录存放次序的搜索码。解决此问题可以根据常用/重要的查询要求，确定主码或建聚集索引Cluster Index。
3. 对每个关系模式，需要确定是否还需要建立辅助索引文件。解决此问题可以根据常用/重要的查询要求，确定建哪些索引Index。
4. 对具有连接条件的一组关系模式，需要确定是否采用多表聚集文件存储。解决此问题可以根据多表连接上重要应用查询快速访问需要。
5. 对应用的所有关系模式，需要确定应当划分为多少个数据库来存储。解决此问题可以根据关系模式间相关性、应用相关性、数据保密需要、数据库备份需要等。
6. 对每个数据库，需要确定数据库文件存放的物理路径（不同服务器，不同介质）。解决此问题可以根据访问效率需要、应用相关性、数据重要性等方法。

元数据管理

到目前为止，我们只考虑了关系本身的表示。一个关系数据库系统需要维护关于关系的数据，如关系的模式等。一般来说，这样的“关于数据的数据”称为元数据(metadata)。

关于关系的关系模式和其他元数据存储在称为数据字典(datadictioary)或系统目录(systemcatalog)的结构中。
系统必须存储的信息类型有：关系的名字。每个关系中属性的名字。属性的域和长度。在数据库上定义的视图的名字和这些视图的定义。完整性约束(例如，码约束)。
此外，很多系统为系统的用户保存了下列数据：授权用户的名字。关于用户的授权和账户信息。用于认证用户的密码或其他信息。

数据库可能还会存储关于关系的统计数据和描述数据。例如：每个关系中元组的总数。每个关系所使用的存储方法(例如，聚簇或非聚簇)。
数据字典也会记录关系的存储组织(顺序、散列或堆)，和每个关系的存储位置:如果关系存储在操作系统文件中，数据字典将会记录包含每个关系的文件名。如果数据库把所有关系存储在一个文件中，数据字典可能将包含每个关系中记录的块记在如链表这样的数据结构中。
目前，绝大多数关系数据库管理系统——RDBMS，采用自描述方式，即数据存储采用关系模式，元数据存储也采用关系模式。

一个简单的ER图示
其中，一个数据库对应n个块，一个数据库包含多个表。

数据库缓冲区

建立缓冲区的原因在于：CPU处理信息快捷，但从磁盘读取记录缓慢；缓冲区一次I/O读多硬盘上多个记录(按块)，可明显减少磁盘I/O开销(连续读-节省时间)，例如查询所有学生的记录；缓冲区中的记录，可能为多个应用所需要，其可明显减少磁盘I/O开销(重复读-浪费时间)，例如大家同时查询奥运会最新100米跑成绩。

数据库系统的一个主要目标就是尽量减少磁盘和存储器之间传输的块数目。臧少礅盘访问次数的一种方法是在主存储器中保留尽可能多的块。这样做的目标是最大化要访问的块已经在主存储器中的几率，这样就不再需要访问磁盘。因为在主存储器中保留所有的块是不可能的，所以需要管理主存储器中用于存储块的可用空间的分配。缓冲区( buffer)是主存储器中用于存储磁盘块的拷贝的那-部分。每个