[系统运维]《数据库系统概念》学习笔记——存储和文件结构

存储和文件结构

物理存储介质概述

几种有代表性的存储介质：

• 高速缓冲存储器（cache）。
  是最快最昂贵的的存储介质。
  高速缓冲存储器一般很小，由计算机系统硬件来管理它的使用。

• 主存储器（main memory）。
  是用于存放可处理的数据的存储介质。
  通用机器指令在主存储器上执行。
  对于存储整个数据库来说还是太小（或太昂贵）。
  如果发生电源故障或者系统崩溃，主存储器的内容通常会丢失。

• 快闪存储器（flash memory）。
  快闪存储器不同于主存储器的地方是在电源关闭（或故障）时数据可保存下来。
  有两种类型的快闪存储器：NAND、NOR快闪。
  快闪存储器还广泛地用于在 “USB盘”中存储数据，它可以插入电脑设备的通用串行总线（Universal Serial Bus, USB）槽。
  在存储等量数据时，快闪存储器也在作为磁盘存储器的替代品使用。这种磁盘驱动器替代品就是所谓的固态驱动器。

• 磁盘存储器（magnetic-disk storage）。
  用于长期联机数据存储的主要介质是磁盘。
  通常整个数据库都存储在磁盘上。
  为了能够访问数据，系统必须将数据从磁盘移动到主存储器。在完成指定的操作后，修改过的数据必须写回磁盘。

• 光学存储器（optical storage）。
  最流行的形式是光盘（Compact Disk, CD），它可以容纳大约700MB的数据，播放约80分钟。
  数字视频光盘（Digital Video Disk, DVD）的每一盘面可容纳4.7GB或者8.5GB的数据（一张双面盘最多可以容纳17GB的数据）。
  可以用数字万能光盘（digital versatile disk） 代替 数字视频光盘（digital videodisk） 作为DVD的全称。
  自动光盘机（jukebox） 系统包含少量驱动器和大量可按要求（通过机械手）自动装入某一驱动器的光盘。

• 磁带存储器（tape storage）。
  主要用于备份数据和归档数据。
  磁带比磁盘便宜，但访问数据也比磁盘慢得多，这是因为磁带必须从头顺序访问。
  磁带存储器称为顺序访问（sequential-access） 的存储器。
  磁盘存储器称为直接访问（direct-access） 的存储器，它可以从磁盘的任何位置读取数据。
  磁带具有很大的容量（现在的磁带可以容纳40~300GB的数据），并且可以从磁带设备中移除，因此它们非常适合进行便宜的归档存储。

根据不同存储介质的速度和成本，可以把它们按层次结构组织起来。

层次越高，这种存储介质的成本就越贵，但是速度就越快。
沿着层次结构向下，存储介质每比特的成本下降，但是访问时间会增加。

最快的存储介质（如高速缓冲存储器和主存储器）称为基本存储（primary storage）。
层次结构中基本介质的下一层介质（如磁盘）称为辅助存储（secondary storage）或联机存储（online storage）。
层次结构中最底层的介质（如磁带机和自动光盘机）称为三级存储（tertiary storage）或脱机存储（offline storage）

易失性存储（volatile storage）在设备断电后将丢失所有内容。
图中所示的层次结构中，从主存储器向上的存储系统都是易失性存储，而主存储器之下的存储系统都是非易失性存储。

磁盘和快闪存储器

磁盘的物理特性

磁盘在物理上是相对简单的。
磁盘的每一个盘片（platter）是扁平的圆盘。
它的两个表明都覆盖着磁性五中，信息就记录在表面上。
盘片由硬金属或玻璃制成。

通过反转磁性物质磁化的方向，读写头（read-write head）将信息磁化存储到扇区中。

磁盘控制器（disk contraller）作为计算机系统和实际的磁盘驱动器硬件之间的接口。

磁盘控制器为它所写的每个扇区附加校验和（checksum），校验和是从写到扇区中的数据计算得到。
当读取一个扇区时，磁盘控制器用读到的数据再一次计算校验和，并且把它与存储的校验和比较。
两者不一致时，认为读取出错，重读，连续几次后，磁盘控制器发出一个读操作失败的信号。

磁盘控制器执行的另一个有趣的任务是坏扇区的重映射（remapping of bad sector）。
当磁盘初始化时，或视图写一个扇区时，如果磁盘控制器检测到一个损坏的扇区，它会把此扇区在逻辑上映射到另一个物理位置（从为此目的而留出的额外扇区中分配）。
重映射记录在磁盘或非易失性存储器中，而在写操作在新的位置上执行。

磁盘通过一个高速互联通道连接到计算机系统。

磁盘通常可以通过电缆之间与计算机系统的磁盘接口相连，也可以放置到远端并通过高速网络与磁盘控制器相连。

在存储区域网（Storage Area Network, SAN）体系结构中，大量的磁盘通过高速网络与选多计算机服务器相连。
通常磁盘采用独立磁盘冗余阵列（Redundant Array of Independent Disk, RAID）技术进行本地化组织，从而给服务器一个很大且非常可靠的磁盘的逻辑视图。

网络附加存储（Network Attached Storage, NAS ）由SAN发展而来。它通过使用网络文件系统协议（如NFS或CIFS）提供文件系统接口，而不是看似一张大磁盘的网络存储器。

磁盘性能的度量

磁盘质量的主要度量指标是容量，访问时间，数据传输率，可靠性。

访问时间（access time）是从发出读写请求到数据开始传输间的时间。

为了访问（读写）磁盘上指定扇区的数据，磁盘壁首必须移动，以定位到正确的磁道，然后等待磁盘旋转，直到指定的扇区出现在它下方。

磁盘臂重定位的时间称为寻道时间（seek time），它随磁盘臂移动距离的增大而增大。

平均寻道时间（average seek time）是寻道时间的平均值，是在一个（均匀分布的）随机请求的序列上计算得到的。

旋转等待时间（rotational latency time）：一旦读写头到达了所需的磁道，等待访问的扇区出现在读写头下所花费的时间。

一旦待访问数据的第一个扇区来到读写头下方，数据传输就开始了。
数据传输率（data-transfer rate）是从磁盘获得数据或向磁盘存储数据的速率。

平均故障时间（Mean Time To Failure, MTTF），这是磁盘可靠性的度量标准。
磁盘（或其他任何系统）的平均故障时间是，平均说来可以期望系统无故障连续运行的时间量。

磁盘块访问的优化

磁盘地址，是以块号的形式提供。
一个块（block）是一个逻辑单元，它包含固定数目的连续扇区。
数据在磁盘和主存储器间以块为单位传输。
页（page）常用来指块。

来自磁盘的连续请求可归类为顺序访问模式或随机访问模式。

在一个顺序访问（sequential access）模式中，连续的请求会请求处于相同的磁道或相邻磁道上连续的块。

随机访问（random access）模式下，相继的请求会请求那些随机位于磁盘上的块。

为提高访问块的速度，产生了许多技术。

• 缓冲
  从磁盘读取的块存储在内存缓冲区中，以满足将来的要求。
  缓存通过操作系统和数据库系统共同运作。

• 预读
  一个磁盘块被访问时，相同磁道的连续块也被读入内存缓冲区，即便没有针对这些块的即将来临的请求。

• 调度
  如果需把一个柱面上的几个块从磁盘传输到主存储器，我们可以按块经过读写头的顺序发出访问块请求，从而节省访问时间。
  如果所需块在不同柱面上，按照使磁盘臂移动最短距离顺序发出访问块的请求是非常有利的。
  磁盘臂调度算法试图把对磁道的访问按照能增加可以处理的访问数量的方式排序。
  电梯算法：
  假设一开始，磁盘臂从最内端磁道向磁盘最外端移动。
  对每条有访问请求磁道，磁盘臂在那磁道停下，为这条磁道请求提供服务，然后继续向外移动，直到没有对更外层磁道的等待请求。
  到达最外，反向向内侧移动，如此往复。
  磁盘控制器可对请求排序以提高性能。

• 文件组织
  为了减少块访问时间，可以按照与预期的数据访问方式最接近的方式来组织磁盘上的块。

• 非易失性写缓冲区
  更新操作密集的数据库应用的性能，如事务处理系统的性能，高度依赖于磁盘写操作的速度。
  写指令前，先把指令内容记录到非易失性存储器，便于中断后恢复。

• 日志磁盘
  一种专门用于写顺序日志的磁盘。
  对日志磁盘的所有访问都是顺序的，这从根本上消除了寻道时间，并且一次可以写几个连续的块，使得写日志磁盘比随机的写要快许多倍。
  支持上述日志磁盘的文件系统称作日志文件系统（joumaling file system）。

由应用程序执行的写操作一般不写入日志磁盘中。数据库系统实现它们自己形式的日志。

快闪存储

两种快速存储器：NOR快闪和NAND快闪。

NOR快闪：允许随机访问闪存中的单个字，并且拥有和主存可媲美的读取速度。

NAND快闪：它的读取需要将整个数据页从NAND快闪取到主存储器中，该数据页通常包括 512~4096 字节。

NAND快闪明显比NOR快闪便宜，并且拥有更高的存储容量，且目前更广泛使用。

RAID

为提高性能和可靠性，提出独立磁盘冗余阵列的多种磁盘组织技术。

使用RAID是因为它有更高的可靠性和更高的执行效率，而不再是因为经济原因。
使用RAID的另一个关键理由是它易于管理和操作。

通过冗余提高可靠性

冗余：存储正常下不需要的额外信息。

冗余信息可在磁盘故障时用于重建丢失的信息。

实现冗余最简单（但最昂贵）的方法是复制每一张磁盘。这种技术称为镜像。

通过并行提高性能

通过在多张磁盘上进行数据拆分来提高传输速率。

数据拆分最简单的形式是将每个字节按比特分开，存储到多个磁盘上。这种拆分称为比特级拆分。

块级拆分是将块拆分到多张磁盘。

磁盘系统中的并行有两个主要的目的：

• 负载平衡多个小的访问操作（块访问），以提高这种访问操作的吞吐量。
• 并行执行大的访问操作，以减少大访问操作的响应时间。

RAID 级别

通过结合奇偶校验位和磁盘拆分拆分思想。
提供冗余和并行以取得可靠性，速度的提升。

• RAID０级
  指块级拆分但没有任何冗余的磁盘阵列。

• RAID１级
  指使用块级拆分的磁盘镜像。
  一些厂商用RAID１＋０或 RAID 10 指代拆分的镜像，RAID１指不用拆分的镜像。

• RAID２级
  称为内存风格的纠错码组织结构，使用奇偶校验位。

• RAID３级
  位交叉的奇偶校验组织机构。
  磁盘控制器能检测一个扇区是否正确地读出，可使用一个单一的奇偶校验位来检错和纠错。
  RAID３对多张常规磁盘只需要一个奇偶校验磁盘。
  比特位拆分。

• RAID４级
  块交叉的奇偶校验组织结构
  使用块级拆分，此外在一张独立的磁盘上为其他N张磁盘上对应的块保留一个奇偶校验块。

• RAID５级
  块交叉的分布奇偶校验位组织结构。
  将数据和奇偶校验位都分布到所有的N+1张磁盘中。
  奇偶校验快和数据块存储在不同磁盘。

• RAID６级
  P+Q冗余方案。
  采用纠错码。
  

RAID 级别的选择

选择RAID级别应考虑以下的因素：

• 所需的额外磁盘存储代理的花费。
• 在I/O操作数量方面的性能需求。
• 磁盘故障时的性能。
• 数据重建过程（即，故障磁盘上的数据在新磁盘上重建的过程）中的性能。

硬件问题

选择RAID实现还要考虑的另一个因素在硬件层上。

RAID可以在不改变硬件层，只修改软件的基础上实现，这样的RAID称为软件RAID。
具有专用硬件支持的系统称为硬件RAID系统。

硬件RAID实现能够使用非易失性RAM在需要执行的写操作执行之前记录它们。

为了尽量减少数据丢失的可能，良好的RAID控制器会进行擦洗，也就是说，在磁盘空闲时期，对每张此批的每一个扇区进行读取，如果发现某个扇区无法读取，则数据从RAID组织的其余磁盘中进行恢复，并写回到扇区中。

一些硬件RAID实现允许热交换，就是在不切断电源的情况下将出错磁盘用新的磁盘替换。

好的RAID实现提供多个备用电源。
这样的RAID系统还拥有多个磁盘接口，和RAID系统与计算机系统的多个互连（或者与计算机系统网络的连接）。
因此，任何单个部件的故障不会使RAID系统停止工作。

其他的RAID应用

RAID的概念已经推广到其他的存储设备上，包括磁带阵列和无线系统上的数据广播。

在运用于磁盘带阵列时，RAID可以在磁带阵列中的一盘磁带毁坏后恢复磁带上的数据。
当运用于数据广播时，数据块分成小单元，连同奇偶校验单元一起传播。
如果其中一个单元由于某种原因没有接收到，它可以从其他的单元中重新构造出来。

第三级存储

两种最常用的第三级存储介质是光盘和磁带。

光盘

光盘具有640~700MB的存储容量。
在一些需要大量数据的应用中，数字视频光盘（DVD）正在代替光盘。

自动光盘机是存储大量的光盘（可以达到几百张）的设备，它可以按照需求自动将光盘装载到少量驱动器（通常是1~10个驱动器）中的一个上。

光盘的装载和卸载时间通常是几秒的数量级，这比光盘的访问时间要长得多。

磁带

磁带主要用于备份，存储不经常使用的数据，以及作为将数据从一个系统转到另一个系统的脱机介质。
磁带还应用于存储大量数据，例如视频和图像数据，它们不需要迅速地访问，或者因为数据量太大以至于磁盘存储太昂贵。

磁带设备是相当可靠的，好的磁带驱动系统对刚写的数据执行一次读操作以确保数据正确记录。
但是磁带能可靠地读写的次数是有限的。

自动磁带机，像自动光盘机一样，存放大量的磁带，并有少量可用于安装磁带的驱动器。
它用于存储大量数据，存储范围最大可达若干 PB（$10^{1}5$字节），而存取时间在几秒到几分钟的数量级。

文件组织

一个数据库被映射到多个不同的文件，这些文件由底层的操作系统来维护。
这些文件永久地存在于磁盘上。
一个文件在逻辑上组织成为记录的一个序列。这些记录映射到磁盘块上。
文件由操作系统作为一种基本结构提供，所以我们将假定作为基础的文件系统是存在的。

每个文件分成定长的存储单元，称为块。
块是存储分配和数据传输的基本单元。

一个块可能包括很多条记录。
一个块所包含的确切的记录集合是由使用的物理数据组织形式所决定的。

在关系数据库中，不同关系的元组通常具有不同的大小。
把数据库映射到文件的一种方法是使用多个文件，在任意一个文件只存储一个固定长度的记录。
另一种选择是构造自己的文件，使之能够容纳多种长度的记录。

定长记录

在文件的开始处，分配一定数量的字节作为文件头。
文件头将包含有关文件的各种信息。

被删除的记录形成了一条链表，经常称为空闲列表。

在插入一条新纪录时，我们使用文件头所指向的记录，并改变文件头的指针以指向下一个可用记录。
如果没有可用的空间，我们就把这条新纪录添加到文件末尾。

对定长记录文件的插入和删除是冗余实现的，因为被删除记录留出的可用空间恰好是插入记录所需要的空间。
如果我们允许文件中包含不同长度的记录，这样的匹配将不再成立。

插入的记录可能无法放入一条被删除记录所释放的空间中，或者只能占用这个空间的一部分。

变长记录

变长记录以下面几种方式出现在数据库系统中：

• 多种记录类型在一个文件中存储。
• 允许一个或多个字段是变长的记录类型。
• 允许可重复字段的记录类型，例如数组或多重集合。

实现变长记录存在不同的技术，都必须解决两个不同的问题：

• 如何描述一条记录，使得单个属性可以轻松地抽取。
• 在块中如何存储变长记录，使得块中的记录可以轻松地抽取。

一条有变长度属性的记录表示通常具有两个部分：初始部分是定长属性，接下来是变长属性。

对定长属性，分配存储它们的值所需的字节数。
对变长属性，在记录的初始部分中表示为一个对（偏移量，长度）值，其中偏移量表示在记录中该属性的数据开始的位置，长度表示变长属性的字节长度。

在记录的初始定长部分之后，这些属性的值是连续存储的。
因此，无论定长还是变长，记录初始部分存储有关每个属性的固定长度的信息。

下图，显示了一个instructor记录，它的前三个属性ID, name, dept_name是变长字符串，第四个属性salary是一个大小固定的数值。
假设偏移量和长度值存储在两个字节中，即每个属性占４个字节。
salary属性假设用８个字节存储，并且每个字符占用和其拥有字符数一样多的字节数。

上图也说明了空位图 的使用，用来表示记录的那个属性是空值。
在这个特定的记录中，如果salary是空值，该位图的第４位将置１，存储在12~19字节的salary值将被忽略。

下面处理在块中存储变长记录的问题，分槽的页结构一般用于在块中组织记录。
如上图所示，每个块的开始处有一个块头，其中包含以下信息：

• 块头中记录条目的个数。
• 块中空闲空间的末尾处。
• 一个由包含记录位置和大小的记录条目组成的数组。

实际记录从块的尾部开始连续排列。
块中空闲空间是连续的，在块头数组的最后一个条件和第一条记录之间。
如插入一条记录，在空闲空间的尾部给这条记录分配空间，并且将包含这条记录大小和位置的条目添加到块头。

如果一条记录被删除，它所占用的空间被释放，并且它的条目被设置成被删除状态（如记录的大小被设置为－１）。
此外，块中在被删除记录前的记录将被移动，使得由删除而产生的空间空间被重用，并且所有空闲空间仍然存在于块头数组最后一个条目和第一条记录之间。
块头中的空闲空间末尾指针也要适当修改。

分槽的页结构要求没有指针直接指向记录。取而代之，指针必须指向块头中记有记录实际位置的条目。
在支持指向记录的间接指针的同时，这种间接层次允许移动记录以防止在块的内部出现碎片空间。

文件中记录的组织

• 堆文件组织
  一条记录可放在文件中任何地方，只要那地方有空间存放这记录。
  记录没顺序。通常，每个关系使用一个单独的文件。
• 顺序文件组织
  记录根据其“搜索码”的值顺序存储。
• 散列文件组织
  在每条记录的某些属性上计算一个散列函数。
  散列函数的结果确定了记录应放到文件的哪个块。

通常，每个关系的记录用一个单独的文件存储。

在多表聚簇文件组织中，几个不同关系的记录存储在同一个文件中。而且，不同关系的相关记录存储在相同的块中，于是一个I/O操作可以从所有关系中取到相关的记录。

顺序文件组织

顺序文件是为了高效处理按某个搜索码的顺序排序的记录而设计的。
搜索码是任何一个属性或者属性的集合。

通过指针把记录有序链接起来。

对插入操作，应用如下规则：

1. 在文件中定位按搜索码顺序处于待插入记录之前的那条记录。
2. 如果这条记录所在的块中有一条空闲记录（即删除后留下来的空间），就在这里插入新的记录。否则，将新纪录插入到一个溢出块中。不管哪种情况，都要调整指针，使其能按搜索码顺序把记录链接在一起。

多表聚簇文件组织

多表聚簇文件组织是一种在每一块中存储两个或更多个关系的相关记录的文件结构。
这样的文件组织允许我们使用一次块的读操作来读取满足连接条件的记录。

数据字典存储

一个关系数据库系统需要维护关于关系的数据，如关系的模式等。
一般来说，这样的“关于数据的数据”称为元数据。

关于关系的关系模式和其他元数据存储在称为数据字典或系统目录的结构中。

系统必须存储的信息类型有：

• 关系的名字。
• 每个关系中属性的名字。
• 属性的域和长度。
• 在数据库上定义的视图的名字和这些视图的定义。
• 完整性约束（例如，码约束）。

此外，很多系统为系统的用户保存了下列数据：

• 授权用户的名字。
• 关于用户的授权和账户信息。
• 用于认证用户的密码或其他信息。

数据库可能还会存储关于关系的统计数据和描述数据。例如：

• 每个关系中元组的总数。
• 每个关系所使用的存储方法（例如，聚簇或非聚簇）。

数据字典也会记录关系的存储组织（顺序、散列或堆），和每个关系的存储位置：

• 如果关系存储在操作系统文件中，数据字典将会记录包含每个关系的文件名。
• 如果数据库把所有关系存储在一个文件中，数据字典可能将包含每个关系中记录的块记在如链表这样的数据结构中。

有必要存储关于每个关系的每个索引的信息：

• 索引的名字。
• 被索引的关系的名字。
• 在其上定义索引的属性。
• 构造的索引的类型。

数据库缓冲区

缓冲区是主存储器中用于存储磁盘块的拷贝的那一部分。
负责缓冲区空间分配的子系统称为缓冲区管理器。

缓冲区管理器

类似操作系统对虚拟内存的管理。

• 缓冲区替换策略
  当缓冲区中没有剩余空间时，在新块读入缓冲区之前，必须把一个块从缓冲区中移出。
  最近最少使用策略，即最近访问最少的块被写回磁盘，并从缓冲区中移走。
• 被钉住的块
  不允许写回磁盘的块称为被钉住的块。
• 块的强制写出
  在某些情况下，尽管不需要一个块所占用的缓冲区空间，但必须把这个块写回磁盘。这样的写操作称为块的强制写出。

缓冲区替换策略

在操作系统中，最近最少使用块替换策略是一个可以接收的替换策略。
具体替换策略，依赖于使用场景，目标都是希望完成任务目标要求下，尽可能少的与磁盘交互。

学习参考资料：

《数据库系统概念》第6版