数据库系统-学习记录9
《数据库系统实现》
ch2.辅助存储管理
存储器层次
层次
存储器的层次图如图1所示：
在图中，越往下的存储器效率越高，成本也越大
高速缓存：当处理器需要数据和指令时，数据和指令就会从内存移到髙速缓存中，处理器访问髙速缓存的数据只需几纳秒
主存储器：发生在计算机中的每一件事情，不论是指令的执行还是数据的操纵，都是作用于驻留在内存的信息上。将数据从内存转移到处理器或高速缓存的速度在10~100ns的范围内
辅助存储器：典型的辅助存储器是磁盘，因为一次可以传送大量字节，磁盘的数据传送速度问题比较复杂
第三级存储器：用以保存数以兆兆字节计的数据，与辅助存储器相比，其读/写时间要长得多，但是其容量比磁盘大得多，每个字节花费比磁盘小。许多第三级设备需要机械臂或者传送器将磁带或光盘（例如DVD）放到读取设备上。读取数据需要花费几秒甚至几分钟，但可以达到PT级别的读写容量
在存储器层次间传送数据
磁盘被划分成磁盘块（或称块），每块的大小是4~64kB。整个块被从一个称为缓冲区的连续内存区域中移进移出
易失和非易失存储器
一个易失的设备，当切断电源时，它会“忘记”所存储的信息。另一个方面，一个非易失的设备，当设备被关闭或电源发生故障时，能保持它的内容完整无缺，甚至长期地保存下去
虚拟存储器
典型的软件运行在虚拟存储器中，它是一个地址空间，大小一般为32位，即在虚拟存储器中有2 32 ^{32} 32B或4GB。虚拟存储器是操作系统和操作系统运用机器硬件的产物，它不是存储器层次之一
磁盘
磁盘结构
磁盘的结构如图2所示（右图为俯视图）：
磁盘控制器
磁盘控制器是一个小型处理器，能够完成以下功能：
1、将磁头定位到一个特定的半径位置，使得某一柱面任何磁道都可以被读写
2、从磁头所在柱面的扇区中选择一个扇区
3、将从所要求的扇区读取的二进制位传送到计算机的主存储器
4、将一整条或更多磁道缓存于磁盘控制器的内存中，期待该磁道的许多扇区能够被很快读取，从而避免对磁盘的额外访问
磁盘存取特性
存取一个磁盘需要3步，每一步都有相应的时间延迟：
1、寻道：磁盘控制器将磁头组合定位在磁盘块所在磁道的柱面上
2、旋转：磁盘控制器等待访问块的第一个扇区旋转到磁头下
3、传输：当磁盘控制器读取或写数据时，数据所在的扇区和扇区间的空隙经过磁头
寻道时间、旋转延迟和传输时间的总和称为磁盘的延迟
加速对辅助存储器的访问
当磁盘访问请求的到达频率变得非常高时，请求可能会被无限阻塞。因此，减少磁盘的访问时间就显得极其重要
计算的I/O模型
I/O开销的主导地位：执行磁盘读写所花费的时间或许要比用于操纵主存中的数据所花费的时间长得多。这样，块访问（磁盘I/O)次数就是算法所需要的时间的近似值，而且应该被最小化
按柱面组织数据
由于寻道时间占平均块访问时间的一半，将一些可能被一起访问的数据，例如关系，存储在单个柱面上或几个临近的柱面上是有意义的
如果选择在一个单个磁道上或者在一个柱面上连续地读所有块，那么就可以只考虑第一次寻道时间（移动到柱面上的时间）和第一次旋转等待时间（等待第一个块移动到磁头下的时间），而忽略其他时间
使用多个磁盘
使用多个磁盘（每个磁盘都有独立的磁头组）代替一个磁盘时，常常能够提高系统的性能
磁盘镜像
使用两个或更多的磁盘保留同样的数据副本，能够：
1、使数据不会因一个磁头损坏而损坏，因为已损磁盘的镜像上的数据仍是可读的
2、提高读磁盘块的速率（但无法提高写入的速率）
磁盘调度和电梯算法
提高磁盘系统吞吐率的另一个有效方法是让磁盘控制器在若干个请求中选择一个来首先执行
电梯算法：是调度大量块请求的一个简单而有效的方法。将磁头看做是在做从柱面最内圈到最外圈，然后再返回来、横跨磁盘的扫描，则这个过程可以与电梯相类比。
当磁头通过柱面时，如果有一个或多个对该柱面上的块的请求，磁头就停下来。根据请求，所有这些块被读或写。然后磁头沿着其正在行进的同一方向继续移动，直至遇到下一个包含要访问块的柱面。当磁头到达其行进方向上的某一个位置时，在该位置的前方不再有访问请求，磁头就朝相反方向移动。
预取和大规模缓冲
在一些应用中，我们能够预测从磁盘请求块的顺序。如果这样，我们就能在需要这些块之前将它们装入主存。这样做的好处是我们能较好地调度磁盘，通过采用诸如电梯算法等，减少访问块所需要的平均时间
磁盘故障
间断性故障
尝试读一个磁盘块，但该磁盘块的正确内容没有被传送到磁盘控制器中，就是一个间断性故障发生了。如果控制器能以某种方式判断出磁盘块的好坏，那么在读到坏数据后，控制器可以重新发送读请求，直到该扇区被正确读取
控制器也可以尝试写一个扇区，但最终被写入的内容也许不是原来想要写人的。唯一的检测写正确的方法是让磁盘再转一遍从而再读一次磁盘块。执行校验的一个直截了当的方法是读这个扇区，并且与我们打算写的扇区进行比较
校验和
现在的手段，仅用一个读操作，就能决定一个扇区的好/坏状态，这是利用每个扇区的若干个附加位完成的。这些附加位，称为校验和（checksum）。在读取数据时，如果发现校验和不正确，则一定有读错误；反之，在使用许多校验位的情况下，校验和正确时，有极大的把握认为没有发生读错误
校验和的一种简单形式，是根据扇区内的所有位的奇偶性来计算：如果在一个二进制集合中有奇数个1，则说数据具有奇数奇偶性，反之，为偶数奇偶性。在奇数奇偶性下，校验和取1，作为奇偶位加在二进制位的序列中；而在偶数奇偶性下，校验和取0
例如：二进制位序列01101000，具有奇数个1，则校验和取1，作为奇偶位加在后面，即得到：011010001
根据上述的规则，加上校验和后，二进制位序列总会呈现出偶数奇偶性。如果发生了一个位错误，则会使得二进制位序列呈现出奇数奇偶性，从而检查出错误
如果发生的位错误不止一个，则一个奇偶校验位有50%的概率检测到错误。通过增加奇偶校验位到n位，可以将假正率降低到 1 / 2 n 1/2^n 1/2n
稳定存储
在应用了上述校验的基础上，仍然可能发生的一种意外：覆盖了一个扇区，却没有读出这个扇区的内容
解决方案：使用两个成对的扇区，可以通过交替尝试读取这两个扇区来实现稳定存储
奇偶块
减少磁盘崩溃造成数据丢失的一种有效方法为奇偶块方法。此方法不管有多少数据盘，都只使用一个冗余盘
利用这种方法，如果出现了某个块的丢失，通过冗余盘也能够很快地对这个块进行恢复
组织磁盘上的数据
定长记录
记录被存放在辅助存储器中，但记录的操作仍需要在内存中进行
通常，记录的存放以记录的首部（header）开始。首部是关于记录自身信息的一个定长区域
记录的字段的起始地址通常是4或8的倍数，这样会使得读写更有效率
图3展示了某关系的定长存储的地址分配情况：
注意到所有的字段的起始地址(name、address、gender、birthdate)都是4或8的整数倍，即便它们的长度没有占满这个分配的空间
定长记录在块中的放置
块和记录地址的表示
客户机-服务器系统中的地址
客户端应用使用常规的虚拟地址空间，服务器的数据处于数据库地址空间
数据库地址空间中的地址涉及块或块内偏移，在此空间内可以用物理地址和逻辑地址这两种方式表示地址
逻辑地址和结构地址、指针混写
变长数据和记录
变长数据通常会存储在定长数据之后
对于变长数据，一般除了第一个变长字段外，剩下的均对应首部的一个指向它的起始地址的指针
例如，图5中的name和address就是变长字段，注意到有指向address起始地址的指针：
对于具有重复定长字段（每一个字段是定长的，但重复次数不定）的记录，一般放在变长数据之后。在首部也有指向这段重复记录的第一条起始地址的指针，如图6所示，这里的影片指针是重复定长字段：
记录的修改
插入
当关系的记录没有特定的存储顺序时，随意寻找一个有空闲空间的块即可
当关系的记录有特定的存储顺序时，如果使用了有偏移量表的块存储方式，则可以利用滑动来完成插入，否则会更加复杂
删除
如果使用了有偏移量表的块存储方式，则可以通过滑动的方式，使得块中空间紧凑（将删去的那一块空档填上）
修改
修改定长记录时，对存储系统没有影响
但在修改变长记录时，可能需要在其所在的块中创建更多的空间，甚至创建一个溢出块