存储器层次

     存储器一般分为几个层次，如下图所示，数据库一般存储在磁盘上。其中，高速缓存的空间一般在1M左右，处理器访问高速缓存的数据只需几纳秒。主存储器的空间可以是1G或者更大，将数据从内存转移到处理器或高速缓存的速度在10～100ns的范围内。辅助存储器的容量可以达到1TB甚至更大，在磁盘和主存间传送一个字节的时间在10ms左右。第三级存储器容量可以非常大，按花费时间可能达到几秒甚至几分钟。

       正常情况下，数据在相邻层之间进行传输。由于磁盘到内存传输数据需要花费较多时间，所以磁盘被划分为磁盘块，每块的大小为4K～64K，操作系统已块为单位在内存和磁盘间传递数据。在更低层次上，主存储器和高速缓存间的传输以高速缓存线为基本单元，一般是32个连续字节。

磁盘

     下图给出了一个磁盘驱动器两个主要的移动部件，一个是磁盘组合，一个是磁头组合。磁盘被组织成磁道(track)，所有盘面上半径相同的磁道构成了柱面(cylinder)，磁道又被组织成扇区(sector)，扇区是被间隙（gap）分割的圆弧片段，间隙未被磁化为0或1，用于区分不同的扇区。就读写磁盘而论，扇区是不可分割的单位；就磁盘错误而论，它也是一个不可分割的单位。第二个可移动部件是磁头组合，它承载着磁头。每一个盘面有一个磁头，它及其贴近的悬浮在盘面上，但是绝对不与盘面接触（否则就要发生“头损害”，盘片被破坏）。磁头读出经过它下面的盘面的磁方向，也能改变其磁方向，以便在磁盘上写入信息。

一个或多个磁盘驱动器被一个磁盘控制器所控制，能完成以下功能：

1 移动磁头使其定位到一个特定半径位置，使某一柱面任何磁道都可以被读写

2 从磁头所在柱面的扇区中选择一个扇区。控制器也负责识别何时旋转主轴已经到达了所要求的扇区正移动到磁头下面的那个点。

3 将从所要求的扇区读取的二进制位传送到主存储器

4 可能的话，将一整条或更多磁道缓存于磁盘控制器的内存中。

存取一个磁盘块需要三步，每一步都有相关延迟：

1 寻道时间：磁盘控制器将磁头组合定位到磁盘块所在磁道的柱面上所需时间。如磁头已经位于所需柱面，则寻道时间为0，但需要大约1ms启动磁头，约10ms移过所有磁头

2 旋转延迟：磁盘控制器等待访问块的第一个扇区旋转到磁头下。典型磁盘旋转一次大约10ms，因此旋转延迟是0～10ms，平均5ms

3 传输时间：当磁盘控制器读取或写数据时，数据所在扇区和扇区间隙经过磁头。传输时间相对较小，因为一个磁道上通常有很多块，所以传送时间在毫秒级以下。

将这三种延迟相加，典型的平均延迟为10ms，最大延迟为20ms

计算的IO模型

      执行磁盘读写所花费的时间或许要比操作主存中的数据所花费的时间唱得多，这样，磁盘I/0次数就是算法所需的时间近似值。当进行数据库查询某个键值K时，如果该键值有索引，能标示K值所在的磁盘块，则只需一次磁盘IO，记录在块内的位置通常不重要。以Megatron747磁盘举例，它能够以11ms的时间读取16KB的磁盘块，在11ms中，一个现代微处理器可以执行几百万条指令，在一个块中寻找特定记录K需要执行成千条指令，即时是最慢的线性查找，搜索时间也比块访问时间的1%还少。

      提高磁盘读写的方法 ：1 按柱面组织数据，将关系存储在不同磁盘的单一柱面，这样能节省寻道时间 2 磁盘镜像，多个磁盘存储相同数据 3 用电梯算法来进行磁盘调度 4预取和大规模缓冲

磁盘故障

有四种磁盘故障类型，分别是

1 间断性故障，读或写一个扇区的某次尝试失败，但经过反复尝试，又能成功读写

2 介质损坏，一个或多个二进制位永久损坏，不管尝试多少次，正确地读一个扇区成为不可能

3 写故障，扇区既不能正确地写，也无法读出，一般是正在写入时断电导致但

4 磁盘崩溃，整个磁盘突然永久变为不可读

间断性故障发生时，如果控制器能以某种方式判断磁盘块的好坏，就能通过多次尝试解决，知道数据被正确读写或者到达最大重试次数。常用的判断方法是校验和，为每一个磁盘块分配n个独立位作为校验码，校验算法很简单，保持二进制位的集合和校验位中1的总数为偶数。每一位奇偶位校验出错误的可能性为50%，加入我们用4个字节作为校验码，纳秒大约40亿此中仅有一次错误不能检查出来。

介质损坏和写存储可以通过稳定存储的策略来解决，即保持扇区是成对的，每一对代表一个扇区内容，两个扇区中内容一样。读的时候读取任意一个扇区，只要校验正确即可。写的时候，两个都需要写入，便于写入过程中出问题后下次恢复。

磁盘崩溃的解决策略成为RAID（Redundant Array of Independent Disk）

RAID1:一个数据盘一个冗余盘，比较简单

RAID4:使用一个冗余盘和多个数据盘，冗余盘根据所有数据盘计算出来，在冗余盘中，第i块由所有数据盘第i块的奇偶校验位组成。读的时候，没什么分别，写的时候，除了写入数据盘，还需要写入冗余盘。当任一盘发生磁盘崩溃后，都可以通过其他盘计算出来。

RAID5:RAID4冗余盘的平均写次数是其他数据盘的n被，针对这个问题，RAID5提出一种优化策略，使得数据盘直接互为备份，没有专门的冗余盘，分散风险。比如有4个磁盘，磁盘0是柱面0，4 ，8...的备份，磁盘1是柱面1，5，8...的备份.

RAID6:针对多个盘崩溃的处理，原理很简单，通过特殊的分组，使得任意两个盘变化时都能通过别的盘恢复，例如下面的冗余模型。

组织磁盘上的数据

用一个记录来表示一个数据元素，在磁盘块中的连续字节存放，一般来说，一个磁盘块中仅存放一个关系的元素是一种常见的组织方式。

定长记录，记录的长度固定，一般每个字段都会遵循四字节对其，提高以后在内存中的效率。如下面的例子，创建数据表的SQL语句如下：

CREATE TABLE MovieStar （name Char(30) PRIMARY KEY,

                                                  address VARCHAR(2255),

                                                  gender CHAR(1),

                                                   birthdate DATE)

记录的格式如下图所示：

块和记录的地址表示

       通常，数据库系统包括一个服务器进程，它为一个或多个客户端提供二级存储器数据。服务器的数据位于数据库地址空间，空间中的地址涉及块或块内偏移，这个地址空间表示地址的方法有物理地址和逻辑地址。物理地址包括磁盘标识符，柱面号，磁道号，块号，记录在快内的偏移量等，逻辑地址与物理地址一一对应，通过映射表进行查询，映射表的简介层次给我们提供了很大的灵活性。一种较另外的记录地址表示方法是偏移量表，即块的首部有一个指针表，分别指向不同记录的起始地址。指针从前往后依次增加，记录从后往前依次增加，如下图所示，这带来了很多优点：

1 我们可以在块内移动记录，我们只需改变该记录在偏移量表中的表项，指向这条记录的指针仍能找到它

2 如果偏移量表项足够大，能存储这条记录的“转向地址”，我们可以允许记录移到另一块

3 如果记录被删除，我们在偏移量表项中留下一删除标记，防止之前得指针指到新的记录上产生意外错误。

指针混写

现代关系型数据库系统允许属性是指针类型，索引结构也是由内部有指针的块组成，在磁盘上，这些指针是数据库地址，当磁盘块加载进虚拟内存后，数据项需要转为内存地址才可使用。目前使用一种指针混写（pointer swizzling）的技术，总的思想是块内指针可以混写，在内存中用内存地址，在数据库里用数据库地址。所以，一个块内指针包括两部分，1 一个二进制位表示目前是数据库地址还是内存地址，2 数据库或内存指针。系统会维护一个数据库地址和内存地址的转换表，这个转换表和上面的映射表有很大区别，这个只会记录加载到内存的数据项地址。

 在磁盘块加载到内存的时候会更新该表，将磁盘块中的指针加到转换表中。这些指针既包括记录指向其他地方的指针也包括自身和其记录的地址。

将磁盘块写会磁盘的时候，需要将内存地址转成数据库地址再写入。但需要注意，磁盘块在某些情况下会被钉住，即别的块中有指针指向该块中的数据项，此时不能直接写入，需要解混写这些引用块中的指针后才能写入。那如何找到这些引用块呢，可以采用下图方法，在转换表中增加一项，通过链表指向所有混写指针。

变长数据和记录

变长字段可以节省存储空间，一般可采用如下格式存储，在记录头部增加记录长度和指向变长字段的指针。

重复字段，即记录中的字段F出现次数可变，我们可以采用如下存储方式，将F的所有出现放在一起，首部信息执行第一次出现F的地址。

可变格式，如XML元素等，可以采用如下带标记的字段序列格式：

不能装入一个块中的记录，需要在块首部增加一些额外信息：1 一个二进制位表示该块是否为一个片段 2 如果是一个片段，需要几个二进制位表示它是否属于第一个或最后一个片段 3 如果同一个记录有前一个或后一个片段，需要有指针连起来，如下图所示