第六章 存储技术与数据库物理设计
返回到 『四级数据库』6．1 文件组织
6．1．1 数据库的物理结构
- 数据库中的应用数据是以文件形式存储在外存上的，文件在逻辑上被组织成记录的序列，即每个DB文件可看作是逻辑记录的集合；
- 一个文件在磁盘上占有一定的物理存储空间，文件中的每个逻辑记录被映射存储到某个特定的磁盘块上，一个文件在物理上可以看作是由存放文件记录的一系列磁盘块组成，称为物理文件；
- 文件的逻辑记录与磁盘间的映射关系是由操作系统或DBMS来管理的，当需要对一个文件的逻辑记录进行操作时，先要根据这种映射关系找到该逻辑记录所在的磁盘块，然后再进行操作。
- 从数据库物理结构角度需要解决如下4个问题：
- 文件的组织；
- 文件的结构；
- 文件的存取；
- 索引技术；
6．1．2 文件组织
- 数据库与文件的对应关系
- 在外存中，数据库以文件形式组织，文件由逻辑记录组成，记录由多个域组成；
- 一个关系数据库包括一张或多张关系表，关系表与文件的对应关系有如下方式：
- 每张关系表 单独用 一个文件来存储，由DBMS通过OS的文件管理功能来管理；
- 现代中大型DBMS是由OS直接分配一块大的磁盘空间，DBMS将该磁盘空间作为数据库磁盘文件直接管理，DB的所有关系表都存储在该文件中；
- 关系表在逻辑上由一系列元组组成，元组由多个属性组成，每个元组可以用磁盘文件中的一个逻辑记录来存储，记录包括多个域，对应元组的多个属性；
2、文件记录格式：
- 数据库文件通常采用两种逻辑记录格式：定长记录格式和变长记录格式；
6．2 文件结构与存取
6．2．1 堆文件
- 堆文件 也称 无序文件，记录 随机 存储在文件物理空间，新插入的记录存储在文件的末尾；
- 堆文件常常用作存储那些将来使用，但目前不清楚如何使用的记录，为了实现文件记录的有效存取，堆文件经常与附加的存取路径一起使用；
- 查找操行平均需要搜索（B+1）/2个磁盘块，效率比较低；
- 插入操作十分简单，先读文件头，找到最末磁盘地址，将最末磁盘块读入内存，将需插入的新记录写入磁盘块的末端，最后将修改过的磁盘块写回磁盘；
- 删除比较复杂，可以先找到被删除记录所在的磁盘块，读入内存后在内存缓冲区删除记录，最后再写回磁盘；
- 也可以在每个记录的磁盘空间增加一个删除标志位，当需要删除记录时，将标示位置1；
6．2．2 顺序文件
- 顺序文件 按照 文件记录在查询码上的取值的大小顺序排列各个记录；
- 顺序文件的每个记录中有一个指针字段，根据查询码大小用指针将各个记录按序连接起来；
- 文件建立时，应尽量使记录的物理顺序与查找码的顺序一致，以减少访问磁盘块的次数；
- 根据查询条件对顺序文件进行查询时，如查询条件定义在查找码上，则使用二分法查找技术快速找到记录，如条件不在查找码上，则必须从头到尾依次扫描磁盘块，与堆文件一致，所以顺序文件的访问效率也不高；
-
顺序文件插入工作, 包括定位和插入：
- 定位：在指针链中找到插入的位置，即插入记录在哪个记录的前面；
- 插入：如有自由空间，则在该位置插入新记录，
- 如没有自由空间，则只能插入溢出块中，重新调整记录指针链关系，保证记录顺序；
6．2．3 聚集文件
- 聚集文件是一种具有多种记录类型文件，存储了来自多个关系表的数据，每个关系表对应文件中的一种记录类型；
- 当数据库中数据量效大时，对数据库查询需要多次访问磁盘文件，严重影响性能指标，为了降低多表操作时的磁盘访问次数，提高多表查询速度，可采用聚集文件；
- 聚集文件将不同关系表中有关联关系的记录存储在同一磁盘块内，从而减少多表查询时磁盘块的访问次数，提高处理速度；
6．2．4 索引文件
是一种利用索引技术 快速文件访问的文件组织和存取方法；
6．2．4 散列文件
是一种利用散列函数支持快速文件访问的文件组织和存取方法；
6．3 索引技术
6．3．1 基本概念
- 索引技术：是一种快速文件访问技术，它将一个文件的每个记录在某个或某些域（属性）上的取值与该记录的物理地址直接联系起来，提供了一种根据记录域的取值快速访问文件记录的机制；
- 它的关键是建立取值域到记录的物理地址的映射关系，这种映射关系叫索引；
-
索引技术分类：
- 有序索引技术：利用索引文件（相当于书的目录）实现记录域（查找码）取值到记录物理地址间的映射关系，
- 索引文件由索引记录组成，每个记录中记载一个索引项，索引项记录了某个特定的查找码值和具有该值的数据文件记录的物理地址；
- 散列技术：利用一个散列函数实现记录域取值到记录物理地址间的直接映射关系；
3、有序索引：有序索引作为基于索引文件的索引技术，需要考虑两个问题：
（1）如何组织索引文件中的索引记录；（2）如何从索引文件出发，访问数据文件中的数据记录；
- 当需要采用有序索引机制快速访问数据文件时，首先要为该数据文件建立一个索引文件，它是索引记录和索引项的集合；
- 索引文件建立的方法：
- 首先选定某些记录域作为查找码，
- 然后建立数据记录在查找码上的取值与物理地址间的映射关系，组成索引项。
- 所有索引项作为索引记录存储在索引文件中，索引文件根据某个特定的查找码值的顺序组织为顺序文件；
- 一个数据文件可以有多个（提供的查询方式可多样）查找码和索引文件；
6．3．2 有序索引的分类及特点
- 聚集索引与非聚集索引
- 对数据文件和它的一个特定的索引文件，如果数据文件中数据记录的排列顺序与索引文件中索引项的排列顺序相一致，则该索引文件称为聚集索引，否则称为非聚集索引；
- 在一个数据文件上除了建立一个聚集索引外，还可建立多个非聚集索引；
-
稠密索引和稀疏索引
如果数据文件中的每个查找码都在索引文件中都对应一个索引记录，称为稠密索引，如果只一部分对应，则称为稀疏索引；
-
主索引和辅索引
在数据文件包含主码的属性集上建立索引称为主索引，在非主码属性上建立的索引称为辅索引；
4、单层索引和多层索引
- 单层索引（线性索引）：索引项根据键值在索引文件中顺序排列，组织成一维线性结构，每个索引项直接指向数据文件中的数据记录；
- 当数据文件很大时，即使采用稀疏索引，建成的索引文件也很大，导致效率低下，
- 为解决该问题，可对索引文件中的索引项本身再建立一级稀疏索引，组成2层索引结构；
- 进一步地，可建立多层树型索引结构来快速定位；
6．4 散列技术
6．4．1 散列文件
- 散列是一种快速查找技术，它利用定义在文件记录上的查找码，通过计算一个散列函数，以散列函数值作为记录的物理地址，实现对文件记录直接快速访问。
-
首先指定文件记录的一个域作为查找码（散列域），然后定义一个查找码上的函数（散列函数），函数的输入为查找码值，输出为物理地址；
- 一般使用桶作为基本的存储单位，一个桶可存放多个文件记录，物理地址可以是记录所在的桶号，散列函数的输出可以是桶号；
6．4．2 散列函数
- 散列方法依赖于好的散列函数，它应该尽可能均匀地将查找码分布到各个桶中，具体要满足如下两个条件：
- 地址的分布是均匀的；
- 地址的分布是随机的；
6．4．3 桶溢出
- 产生桶溢出的两个原因：
- 文件初始设计时，为文件记录预留的存储空间不足；
- 散列函数的均匀分布性不好；
- 设计散列函数时，应根据文件大小决定物理空间，一般应有20%余量，再设计合适的桶数目和桶大小，尽可能留有一些空闲桶，降低桶溢出的可能性；
- 桶溢出的现象是难免的，需要DBS采用相应的桶溢出处理机制；
- 散列方法的缺点：为了避免桶溢出。必须选一合适的散列函数，但这比较复杂，而且不象索引文件那样可以据数据记录变化动态调整。
6．5 数据字典
- 数据字典（系统目录）中存储了数据库对象的各类描述信息和DBMS所需的控制信息，全称数据库元数据；
- 数据库对象的各类描述信息：包括外模式、模式、内模式以及它们之间的映射的描述；
- DBMS所需的控制信息：包括查询优化、安全性检查、用户权限验证等；
- 数据字典主要包括：
- 关系模式信息；
- 与视图描述有关的信息；
- 关系的存储结构和存取方法信息；
- 完整性约束信息；
- 安全性有关信息；
- 数据库运行统计信息；
6．6 数据库物理设计
6．6．1 设计步骤和内容
- 数据库物理结构设计：在具体的硬件环境、OS、DBMS约束下，根据数据库逻辑设计结果，设计合适的数据库物理结构。目标是存储空间占用少、访问效率高和维护代价低；
- 一旦选定了硬件平台、OS和DBMS，数据库的数据存储和存取方式等可用的物理模式也就随之确定了；
- 数据库物理设计主要包括以下步骤：
- 数据库逻辑模式调整：将数据库逻辑模式及其视图转换为DBMS支持的基本表和视图，并利用DBMS提供的完整性机制设计业务规则；
- 文件组织与存取设计：配置基本表的文件组织形式，据实际情况为基本表设计合适的存取方法和路径；
- 数据分布设计：
- 安全模式设计：
- 确定系统配置：
- 物理模式评估：
6．6．2 数据库逻辑模式（是独立于具体的DBMS的）调整
- 物理数据库设计首先需要根据数据库逻辑结构信息，设计目标DBMS平台支持的基本表的模式信息，这些模式信息代表了所要开发的具体目标数据库的结构，这个过程称为数据库逻辑模式调整，主要包括如下设计内容：
- 实现目标数据库基本表和视图：采用目标DBMS所支持的建表方法，设计基本表及其面向模型的完整性约束；
- 设计基本表业务规则；
6．6．3 DB文件组织与存取设计
1、分析事务的数据访问特性
- 使用事务-基本表交叉引用矩阵，分析系统内数据库事务对各个基本表的访问情况，确定事务访问了哪些基本表，对这些基本表执行了何种操作，并进一步分析各操作涉及到的基本表属性；
- 估计各事务的执行频率；
- 对每张基本表，汇总所有作用于该表上的各事务的操作频率信息；
-
了解并选择数据库文件结构
- 如果数据库中的一个基本表中的数据量很少，但是操作非常频繁，该基本表可采用堆文件组织方式；
- 顺序文件支持基于查找码的顺序访问，也支持快速二分查找；
-
如果用户查询是基于散列域值的等值匹配，特别是如果访问顺序是随机的，散列文件比较合适。
- 但散列文件组织不适合以下情况：
- 基于散列值域的非精确查询；
- 基于非散列域进行查询时；
-
B-树和B+树文件是实际数据库系统中使用非常广泛的索引文件结构，适合于定义在大数据量基本表上、基于查找码的等值查询等；
-
如果某些重要而频繁的用户查询经常需要进行多表连接操作，可考虑将这些基本表组织为聚集文件；
-
设计存取路径：
- 为数据库文件设计合理的物理存储位置；
- 为基本表设计索引机制（虽然加快了数据查询速度，但同时也减慢了数据更新速度）：索引可以提高文件存取速度，改善访问性能，但索引由DBMS管理，它的建立、维护需要一定的系统开销，数据的操作会引起索引的重新调整，还占用一定的存储空间，可根据如下三大原则决定是否为一个基本表建立索引：
- 1. 对于经常需要查询、连接、统计操作，且数据量大的基本表可考虑建立索引，而对于经常执行插入、删除、更新操作或小数据量的基本表应尽量不建立索引；
- 2. 一个基本表上除了可以建立一个聚集索引外，还可以建立多个非聚集索引，
- 但索引越多，对表内数据更新所需的开销越大，对于一个更新频繁的表应少建或不建索引；
- 3. 索引可以由用户根据需要随时创建或删除，以提高数据查询性能；
6．6．4 数据分布设计
1、不同类型数据的物理分布
- 各种数据在系统中的作用不同，使用的频率也不一样，应根据实际使用情况放在合适的物理介质上；
- 使用频率低但数据量大的，可以放在磁带中，而使用频繁，要求响应时间短的，必须放在支持直接存取的磁盘存储介质上；
-
应用数据的划分和分布
- 根据数据的使用特征划分：可将基本表划分为频繁使用分区和非频繁使用分区，分别存放在不同的磁盘上，对前者可考虑建立B+树等多层索引，而后者不建立或只建立单层索引；
- 根据时间、地点划分；
- 分布式数据库系统中的数据划分：
3、派生属性数据分布
- 派生属性指该属性的取值可根据表中其他属性的取值惟一确定；
- 对带有派生属性的基本表可采用两种实现方式：
- 将派生属性作为基本表内单独一列，称为派生列；
- 派生属性不出现在基本表中；
-
关系模式的去规范化
- 在数据库物理设计阶段，可以对考虑数据库中某些3NF、BCNF模式是否可以降低其规范化程度，以提高查询效率，这称为关系模式的去规范化处理，但不满足3NF的关系模式又可能导致数据库访问异常，因此，设计基本表时，需在规范化和查询效率间权衡；
-
BCNF，全称为Boycee Codd Normal Form，中文叫巴斯范式，是由Boyce和Codd提出的,比3NF又进了一步,通常认为是修正的第三范式。
- 设关系模式R<U，F>∈1NF，如果对于R的每个函数依赖X→Y，若Y不属于X，则X必含有超码，那么R∈BCNF。
满足BCNF条件有：
- 所有非主属性对每一个候选键都是完全函数依赖；
- 所有的主属性对每一个不包含它的候选键，也是完全函数依赖；
- 没有任何属性完全函数依赖于非候选键的任何一组属性。
6．6．5 安全模式设计
1、系统安全设计
- 是指为数据库服务器合法用户分配用户名和口令，使其能够正常登录服务器访问所需的数据，
- 还可采用基于CA认证的系统安全控制机制；
-
数据安全设计
- 是指通过数据库系统视图机制和授权机制为用户对数据库对象访问的权限；
- 引用数据视图机制，只给用户需求的那部分数据访问权限，防止由合法用户造成信息泄密，
- 另外数据视图还可以防止基本表发生改变时，影响用户的访问；
-
权限是允许用户对一给定的数据库对象可执行的操作；
- 数据库安全设计需要根据用户需求，采用授权机制，为用户分配合法访问的权限；
6．6．6 确定系统配置
- 要根据实际应用系统的运行情况配置系统参数；
6．6．7 物理模式评估
- 在设计过程中，通过对时间效率、空间效率、维护代价和用户要求权衡考虑，择优采用；
- 评估物理数据库的方法完全依赖所选用的DBMS，主要从定量估算各方案的存储空间、存取时间和维护代价入手；
