数据库的讲义存储与文件结构 课件

1、存储与文件结构存储与文件结构物理存储介质概述磁盘RAID第三级存储存储访问文件组织文件中的记录组织物理存储介质的分类数据存取的速度每单位数据的成本可靠性系统故障或者电源故障造成的数据丢失存储设备的物理故障可以将存储介质分为：易失存储：当电源关闭时，所存储的内容就会丢失非易失存储：即便在电源关闭时，存储内容也不会丢失包括辅助存储和第三级存储，以及具有后备电源的主存储器物理存储介质高速缓存 最快和最昂贵的存储介质；是易失的；由计算机操作系统管理。主存储器快速存取 （10到100纳秒；1纳秒= 109 秒）通常太小（或者太贵）而不能存储整个数据库容量可达数G字节，当前得到了广泛的应用其容量不断上升，

2、而每一字节的购买成本却在稳定而快速的下降（大约每2至3年下降一倍）易失的 如果发生电源故障或者系统故障，主存储器中的内容通常会丢失。物理存储介质（续）闪存在电源故障时能够将数据保存下来数据可以被擦除和写入只能支持有限次的写入和擦除操作。擦除数据时，必须擦除整个闪存中的数据读速度与主存储器一样快但写速度很慢（需要几个微秒）,擦除速度则更慢单位存储成本与主存储器大致相当广泛应用于嵌入设备如数字相机中也称为EEPROM （Electrically Erasable Programmable Read-Only Memory）物理存储介质（续）磁盘数据存储在旋转的盘片上，通过电磁方式读写是用于长期保存

3、数据的主要介质；通常能够存储整个数据库在存取数据时需要把数据从磁盘移动到主存储器，修改完毕后还需要将数据写回磁盘与主存储器相比，磁盘的存取速度要慢的多直接存取 与磁带不同，磁盘可以以任意顺序读取盘片上的数据硬盘与软盘现在，磁盘的容量可达100 GB与主存储器和闪存相比，磁盘在容量上要大得多，而每字节代价却小得多随着技术的进步，磁盘的性能仍然在稳定和快速的提高 （大约每2至3年增长一倍）在电源故障和系统故障时不会丢失数据磁盘故障会毁坏数据，但这种情况很少发生物理存储介质（续）光存储器非易失的，使用激光器从旋转的盘片上读取数据最常见的形式是：CD-ROM（ 640 MB）和DVD （4.7到17

4、GB）使用只能写一次，但能多次读的光盘来归档数据 (CD-R和DVD-R)也存在可以多次写的光盘 (CD-RW，DVD-RW和DVD-RAM)与磁盘相比，光盘的读写速度都更慢光盘柜系统，使用大量可移动的盘片，少数驱动器和自动装载和卸载盘片的机构来存储大量的数据物理存储介质（续）磁带存储器非易失的，主要用来备份（以便对磁盘故障进行恢复）和归档数据顺序存取 比磁盘的速度要慢得多非常高的容量（40到300 GB)可以从磁带驱动器中移出磁带 磁带存储的代价远低于磁盘磁带库可以用来存储海量的数据从数百TB (1TB = 109 字节)到PB (1PB = 1012 字节)存储设备层次结构存储设备层次结构

5、（续）基本存储：最快的存储介质但却是易失的（包括高速缓存、主存储器）辅助存储器：下一层存储介质，非易失的，存取速度较快，也称为联机存储设备例如：闪存，磁盘第三级存储：层次的最低一级，非易失的，存取速度较慢，也称为脱机存储设备例如：磁带，光盘硬盘工作原理图磁盘读写头位置与盘片表面非常接近（几乎挨到）以电磁方式读或者写信息盘片的表面划分为圆形的磁道在通常的硬盘上每个盘片上有超过16,000条磁道每个磁道又划分为多个扇区扇区是读写的最小数据单位扇区的大小通常为512个字节每条磁道通常包含：200（在内侧磁道） 到 400（在外侧磁道）个扇区要读写扇区磁盘臂要通过摆动将磁头定位到正确的磁道上随着盘片的

6、不断旋转，当扇区从磁头下经过时，就可以对数据进行读写磁头和磁盘的组合方式多个磁盘盘片安装在一个轴上（通常是2到4个磁盘）每个盘片一个磁头，安装在同一个磁盘臂上柱面 i由所有盘片的第 i 条磁道构成磁盘（续）早期的磁盘容易产生磁头故障早期磁盘的表面覆盖着一层金属氧化涂层，这层涂层会在磁头故障中碎裂，并毁坏磁盘上的所有数据现在的磁盘很少会发生这样灾难性的故障，尽管某些扇区还是可能损毁的磁盘控制器 计算机系统和磁盘驱动器硬件之间的接口能够接受对扇区进行读写的高级命令能够进行一些操作，例如将磁盘臂移动到右侧磁道，并读写数据能够为每个扇区计算和附加校验和来验证读取的数据是否是正确的如果数据损坏了，在大多

7、数情况下，重新计算的校验和与存储的校验和都是不匹配的在写完数据后，重新读回数据以确保写操作是正确的对坏扇区进行映射磁盘子系统多个磁盘通过一个控制器连接到计算机系统控制器的功能（求校验和，进行坏扇区映射）通常是由各个磁盘来完成的，以便减少磁盘控制器的负担。磁盘接口标准簇ATA (AT adaptor) 系列标准SCSI (Small Computer System Interconnect) 系列标准上述各个标准的一些变化形式 (在速度和容量上有所不同)磁盘的性能度量存取时间 从发出读写请求到数据开始传输之间的时间，由：寻道时间 将磁盘臂重定位到正确的磁道上所花费的时间平均寻道时间是最坏情况下寻

8、道时间的1/2在通常的磁盘上为4到10 毫秒旋转等待时间 等待被存取的扇区出现在磁头下的时间平均旋转等待时间是最坏情况下旋转等待时间的1/2在通常的磁盘上为4到11 毫秒 (每分钟5400到15000转)数据传输率 是从磁盘获取数据或者向磁盘存储数据的速率通常为 4到8 MB每秒由于多个磁盘可能会共用同一个控制器，所以控制器的速率也是很重要的例如：ATA-5: 66 MB/秒，SCSI-3: 40 MB/秒，光纤通道: 256 MB/秒磁盘的性能度量（续）平均故障时间 (MTTF) 磁盘在不出现故障的情况下可以持续运行的平均期望时间通常为3到5年新磁盘出现故障的可能性非常低，其理论MTTF为3

9、0,000到1,200,000小时磁盘块存取的优化磁盘块 一条磁道上连续的几个扇区构成的序列数据在磁盘和主存储器之间以块为单位进行传输块的大小从512字节到几KB不等磁盘块越小，需要传输的次数越多磁盘块越大，被浪费的空间越多，因为存在许多没有被填满的块现在，磁盘块的大小一般为4到16KB磁盘臂调度算法对等待中的磁道访问请求进行调度安排，使磁盘臂移动的距离最小化电梯算法：向一个方向移动磁盘臂（从外侧磁道到内侧磁道或者相反），处理下一个与磁盘臂移动方向相同的请求，直到没有该方向的请求为止，然后向反方向移动，并重复上述步骤磁盘块存取的优化（续）文件组织 根据对文件的存取方式来组织磁盘块，从而优化磁盘

10、块的存取时间例如，将相关的信息存储在同一个或者邻近的柱面上随着时间的流逝，文件会变得碎片化例如，对文件进行插入、删除数据的操作或者磁盘上空闲的磁盘块是分散的，那么新创建的文件所包含的磁盘块就会分散在整个磁盘上对碎片化的文件进行顺序存取会增加磁盘臂的移动一些系统具有能够减少文件系统碎片的应用程序，以便加快文件的存取速度磁盘块存取的优化（续）非易失写缓冲区 通过将块立即写入非易失的RAM缓冲区来加速磁盘写操作非易失RAM：具有后备电源的RAM或者闪存即使电源故障，当电源恢复时仍然可以安全地将数据写回到磁盘当磁盘没有其他请求时或者请求已经等待了一段时间，控制器就会将数据写入到磁盘那些需要首先将数据安

11、全地保存才可以继续执行的数据库操作，现在就可以不必等待将数据写入磁盘了可以对写操作进行重新排序，以最小化磁盘臂的移动磁盘日志 将对于块的修改按照顺序记录在一个专门的磁盘上可以像非易失RAM那样使用因为不需要寻道，写日志磁盘的速度是非常快的不需要特殊的硬件 (NV-RAM)文件系统通常通过对写操作进行重新排序来提高性能基于日志的文件系统：将数据以安全的顺序写入 NV-RAM或者日志磁盘如果不采用日志的方式记录数据，就会冒文件系统数据损坏的风险RAIDRAID: Redundant Arrays of Independent Disks（廉价磁盘冗余阵列）一种对大量磁盘进行管理，并提供单个磁盘视图

12、的磁盘组织技术通过并行使用多个磁盘从而达到高速度和高容量通过数据的冗余存储，即使在磁盘故障的情况下也可以恢复数据N个磁盘组成的集合中的一些磁盘出现故障的几率远高于特定的单个磁盘发生故障的几率例如，对于一个拥有100个磁盘，每个磁盘的MTTF为100,000小时 (约11年）的系统，其系统MTTF为1000小时（约41天）对于拥有大量磁盘的系统来说，使用冗余的技术避免数据丢失是非常重要的RAID最初是作为大而昂贵的磁盘的替代方法而提出的RAID 的I最初代表 “inexpensive现在RAID被采用的原因是因为其更高的可靠性和带宽RAID 的I 现在的含义是“independent”通过冗余提

13、高可靠性冗余 存储额外的信息以便在磁盘故障时重建信息例如，镜像技术(或影像技术)复制每一个磁盘，逻辑磁盘由两个物理磁盘组成写数据时需要同时对两块磁盘进行写操作读数据时只需要对其中一块磁盘进行读操作如果两个磁盘中的一个出现故障，另外一个磁盘上的数据仍然可用只有当一个磁盘出现故障，而且在系统修复前其镜像磁盘也出现故障的情况下，才会出现数据丢失除了火灾、建筑倒塌或者电源故障等情况以外，发生上述情况的可能性非常小平均的数据丢失时间取决于平均的故障时间和平均的修复时间例如，如果一对镜像的磁盘（假定磁盘故障之间是相互独立的）的MTTF为100,000小时，平均修复时间为10小时，则平均数据丢失时间为500

14、*106小时（或者57,000年）通过并行性提高性能磁盘系统中的并行有两个目的：对多个小的存取操作进行负载平衡以提高吞吐量并行执行大的存取操作，以减少大的存取操作的响应时间可以通过拆分数据并将其分布到多个磁盘上以提高数据传输率比特级拆分 将每个字节按比特拆开并分布到多个磁盘上在八个磁盘构成的阵列中，将每个字节的第i个比特位写到第i个磁盘上每次存取所读取的数据量是单个磁盘的八倍块级拆分 对于 n个磁盘的阵列，文件的第i 块将存放到第(i mod n) + 1块磁盘上如果所请求的数据块保存在不同的磁盘上，就可以并行地存取这些块当对很长的、顺序排列的块进行存取时可以并行的存取所有的磁盘RAID的级别

15、通过使用磁盘拆分与奇偶校验位相结合的方法，以低成本提供数据冗余的模式不同的RAID级别，具有不同的成本、性能和可靠性特征RAID 0级：使用块级拆分；没有冗余为一些不关心数据丢失风险的高性能应用程序所使用RAID 1级：使用块级拆分的镜像磁盘提供最佳的写性能通常为类似于存储数据库系统中日志文件的应用程序所使用RAID的级别（续）RAID 2级：内存风格的纠错码与比特拆分技术RAID 3级：位交叉的奇偶校验单个奇偶校验位足以进行纠错，而不仅仅是检测错误，因为我们知道哪个比特发生故障了在写数据时，必须计算相应的奇偶校验位，并将奇偶校验位写入磁盘要恢复毁坏磁盘上的数据，需要对其他磁盘（包括存储奇偶校

16、验位的磁盘）上的比特进行XOR运算RAID的级别（续）RAID 3级（续）比单个磁盘更快的数据传输率，但由于每个磁盘都必须参加每一次I/O，所以每秒的I/O次数相对较少包容了RAID 2级（具有2级所有的优点，但成本更低）RAID 4级：块交叉奇偶校验；使用块级拆分，并将一个独立的磁盘上为其他N块磁盘上对应的块保留一个奇偶校验块在写数据块的时候，必须计算相应块的奇偶校验位，并写入奇偶校验磁盘要找出毁坏的块的值，可以对其他盘（包括奇偶校验磁盘）上相应的块的位进行XOR运算RAID的级别（续）RAID 4级（续）相对于3级，读取独立的块时具有较高的I/O速率读块时只需读取单个磁盘，所以存储在不同块

17、上的块可以被并行读取在读取多个块时，比不使用拆分技术的情况具有更高的传输率在写一个块之前，必须计算奇偶校验数据需要读取旧的奇偶校验块，当前块的旧值，当前块的新值来进行计算（两次块读取+两次块写入）奇偶校验块成为独立块写操作的瓶颈，因为每次写磁盘块时，都要写入奇偶校验磁盘RAID的级别（续）RAID 5级：块交叉的分布奇偶校验；将数据和奇偶校验位都分布在所有N + 1个磁盘上，而不是将数据存储在N个磁盘上，奇偶校验位存储在另外一个磁盘上。例如，具有5个磁盘的阵列，第n组磁盘块的奇偶校验块存储在第 (n mod 5) + 1个磁盘上，而数据块存储在其他四个磁盘上。RAID的级别（续）RAID 5级

18、（续）比4级的I/O速率高如果块和他们的奇偶校验块存放在不同的磁盘上，就可以进行并行写操作。包容了4级：与之具有相同的优点，但却避免了奇偶校验磁盘造成的瓶颈RAID 6级：P+Q冗余模式；与5级类似，但存储了额外的冗余信息以防止多个磁盘出现故障。以更高的成本换取了比5级更好的可靠性；使用并不广泛。RAID级别的选择选择RAID既别的因素费用 性能：每秒钟的I/O操作数，以及在正常操作情况下的带宽故障期间的性能在重建故障磁盘期间的性能包括重建故障磁盘需要花费的时间只有当数据安全性并不重要的情况下，才使用用RAID 0例如，可以从其它数据源快速恢复数据的情况下2级和4级从没有被使用过，因为它们已经

19、为3级和5级所包容3级也不再使用了，因为比特级拆分在读单个块时也需要存取所有磁盘，浪费了磁盘臂移动的时间，而块级拆分（5级）可以避免这种情况。6级很少被使用，因为对几乎所有应用程序来说， 1级和5级已经能够提供充分的安全性了。所以，只需要在1级和5级之间进行选择即可RAID级别的选择（续）1级比5级具有更好的写性能5级在写单个块的时候，至少需要读取两个块和写入两个块。而1级只需要写入两个块。1级更适合用在更新频率高的环境中，如日志磁盘1级比5级具有更高的存储成本在磁盘驱动器容量正在快速增大（50%/year）的同时，磁盘存取时间却减少的很慢（每10年增快3倍），I/O的需求已经有了巨大的增长，

20、例如，对于 Web服务器当购买了足够多的磁盘满足所需的I/O 率的时候，它们通常都拥有空余的磁盘空间，因而通常并不需要额外花费金钱来实现1级5级适合用于具有很大的数据量，但只具有较低更新率的场合1级则适用于所有其他情况硬件问题软件RAID：RAID的实现完全通过软件来实现，不需要特殊的硬件支持硬件RAID：需要使用特殊的硬件来实现RAID使用非易失的来记录正在被执行的写操作注意：在写操作期间的电源故障可能会导致磁盘上的数据损坏例如，在一个镜像系统中，如果在写完第一个块之后，和第二个块之前发生电源故障当电源恢复时，必须对类似这样损坏的数据检查 恢复损坏数据的过程类似于恢复故障磁盘的过程 NV-R

21、AM有助于有效地检测潜在的损坏的块否则，就必须读取磁盘上所有的块，并与镜像或者奇偶校验块进行比较硬件问题（续）热对换：在系统正在运行的情况下替换磁盘，而无需关闭电源为一些硬件RAID系统所支持减少恢复时间，并极大地提高可用性许多系统保有一些在线的空闲磁盘，在检测到故障时，将立即用这些磁盘来替换故障磁盘极大地减少了恢复时间许多硬件RAID系统通过使用以下技术来保证在单点失效的情况下系统不停止工作具有后备电池组的冗余电源供应具有多个控制器和互连通路以防止控制器和交互连接出现故障光盘只读光盘存储器：Compact disk-read only memory (CD-ROM)可以向驱动器装入或者移出盘

22、片很高的存储容量（ 每张盘片640 MB ）很高的寻道时间，大约100毫秒与磁盘相比，光盘具有较高的延迟（ 3000 RPM) ）和较低的数据传输率（ 3-6 MB/s ）数字视频光盘：Digital Video Disk (DVD)DVD-5的容量为4.7 GB，而DVD-9的容量为8.5 GBDVD-10和DVD-18是双面的，容量分别为9.4 GB和17 GB其他特征类似于CD-ROMCD-R和DVD-R只能写一次，现在日益流行数据只能写一次，不能被擦除高容量和长的生命周期；用于进行归档存储现在还出现了可以多次写的CD-RW，DVD-RW和DVD-RAM磁带可以保存大量的数据和提供高的数

23、据传输率DAT (Digital Audio Tape) 格式的容量为数个 GB， DLT (Digital Linear Tape) 各式的容量为10-40 GB， Ultrium格式的容量为100 GB以上传输率从几MB到几十MB每秒是当前最廉价的存储介质磁带的价格很低，但驱动器的价格非常高与磁盘和光盘相比，磁带的存取时间非常慢因为磁带是顺序存取主要用于备份，保存不常用到的信息，和从一个系统向另外一个系统导数据时的脱机介质磁盘库可以用来提供非常巨大的容量从TB（ 1012字节）到PB（1015字节）存储访问数据库文件可以被分成多个固定长度的存储单元，称为块。块是存储分配和数据传输的基本单位

24、数据库系统的一个目标就是使在磁盘和内存之间传输的块数量最小化。我们可以通过将尽可能多的块保存在内存中来减少磁盘访问的次数缓冲区 主存储器的一部分，用于存储磁盘块的拷贝缓冲区管理器 负责在主存储器中分配缓冲区空间的子系统缓冲区管理器当程序需要从磁盘上读取块时，就调用缓冲区管理器如果需要的块已经在缓冲区中，就会向发出请求的程序返回块在主存储器中的地址如果块不在缓冲区中缓冲区管理器在缓冲区中为该块分配空间，如果需要的话，替换（或者移出） 其它一些块，以便为新块腾出空间如果被移出的块被修改过，将会把它写回到磁盘一旦在缓冲区中分配好了空间，缓冲区管理器就会将块从磁盘上读到缓冲区中，并将该块在主存储器中的

25、地址传递给发出请求的程序缓冲区替换策略大多数操作系统采用最近最少使用法来进行块替换（least recently used ，LRU）隐藏在LRU后面的思想 使用过去的块引用模式来推测未来的引用查询具有定义良好的存取模式（例如顺序扫描），并且数据库系统使用用户查询的信息来预测未来的引用对于某些存取模式（包括对数据的反复扫描），LRU可能是一种坏的策略例如，当对两个关系r和s通过嵌套循环来进行连接操作时，for each tuple tr of r dofor each tuple ts of s doif the tuples tr and ts match 缓冲区替换策略（续）钉住的块 不允

26、许些回到磁盘的内存块立即丢弃策略 只要处理完块中的最后一个元组就立即释放块所占用的空间最近最常使用策略（Most recently used，MRU） 系统必须钉住当前被处理的块。当处理完块中最后一个元组后，不再钉住该块，该块成为最近最常使用的块.缓冲区管理器可以使用有关请求将会引用某个特别关系的可能性的统计信息例如，数据字典是被频繁存取的。启发式规则：应当将数据字典块保存在主存储器缓冲区中缓冲区管理器也强迫输出块以便进行恢复文件组织数据库是存储在一个文件集合之中的，每个文件是记录的序列。记录时字段的序列一种途径：假定记录的大小是固定的每个文件只保护一种特定类型的记录用不同的文件来存储不同的关

27、系 这是最容易实现的途径；后面我们将讨论可变长纪录定长记录简单的方法：将记录i保存在距离文件开头n (i 1)字节的地方，其中，n是每个记录的大小记录存取是简单的，但记录可能会跨块修正：不允许记录跨块的边界删除记录I:将第i + 1, . . ., n条记 录移动到第i, . . . , n 1 条记录将记录n移动到 i不移动记录，而是将所有 空闲的记录链接到一个 空闲列表空闲列表将第一条被删除的记录的地址存储在文件头使用上述第一条被删除的记录来存储第二条被删除的记录，依此类推可以把这些存储的地址看作指针，因为它们指向了记录的位置更具有空间效率的的表示方法：重用空闲记录的属性空间来存储指针（在正在使用的记录中不会存储指针）可变长记录可变长记录出现在数据库系统的下列情况下：在一个文件中存储多种类型的记录记录类型允许一个或者多个字段是变长的记录