chap数据库存储PPT课件

1、第1页/共205页提纲 物理存储介质 RAID 缓冲区管理 索引 数据库文件 存储分配第2页/共205页物理存储介质第3页/共205页物理存储介质 高速缓冲存储器（cache） 最快最昂贵的存储介质 很小，由操作系统管理 主存储器（main memory） 存放可被处理的数据的存储介质 易失，相对整个数据库太小 快闪存储器（flash memory） 读性能类似主存，写速度非常慢 电子可擦除可编程只读存储器(Electrically Erasable Programmable Read-Only Memory)第4页/共205页物理存储介质 磁盘存储器（Magnetic-disk storag

2、e） 直接读取设备，支持随机读取 非易失联机数据存储设备 访问数据时，磁盘内存；修改后的数据，内存 磁盘 光学存储器（Optical storage） 只读(CD-ROM)、一次写多次读(WORM)、多次写(CD-RW) 磁带（tape） 顺序访问，归档存储，容量大，价格便宜第5页/共205页磁盘第6页/共205页磁盘 基本构成 盘片(platter)、磁道(track)、扇区(sector)、柱面(cylinder) 读写头(read-write head)：反转磁性物质磁化的方向 磁盘臂(disk arm) 磁盘控制器(disk controller)：接受读写扇区命令，定位读写头。向扇区

3、写入数据时附加校验和(checksum)，读取时重新计算校验和第7页/共205页磁盘 扇区（sector）是盘片的最小可寻址单元，每个扇区可容纳512字节的数据，也叫磁盘块。扇区会被集合成簇（cluster），簇也叫数据块，操作系统通常以数据块为单位对硬盘进行读写。 磁道（track）在同一个盘片上以同心圆方式排列的扇区构成一个磁道，磁道的扇区数随同心圆的半径而变化，越靠外的磁道的扇区数越多。 柱面（cylinder）各盘片上位于同一位置的磁道构成一个柱面。构成硬盘的每个碟片都被划分为数目相等的磁道，并从外缘的“0”开始编号，具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面。因此硬盘的柱面数和

4、一个碟片上的磁道数是相同的。 第8页/共205页磁盘 磁盘性能度量 访问时间：从发出读写请求到数据开始传输之间的时间。为到达指定扇区，需要先移动磁盘臂，定位到正确的磁道，然后旋转磁盘，直到指定的扇区出现在读写头下方 寻道时间(seek time)：磁盘臂重定位时间，取决于目标磁道和磁盘臂当前距离，230毫秒。平均寻道时间是最大寻道时间的1/3 旋转等待时间(rotational latency tiime)：目标扇区旋转到读写头下面的时间，每转在411毫秒之间。平均旋转时间是旋转一周的1/2 数据传输率(data-transfer rate)，25100兆/秒第9页/共205页磁盘访问优化 磁

5、盘块的大小 小，更多的磁盘传输次数；大，空间浪费 调度 块在一个柱面上，按块经过读写头的顺序访问；块在不同柱面上，按使磁盘臂移动距离最短的顺序访问 电梯算法 文件组织 按与预期数据访问方式最接近的方式组织磁盘块 碎片整理 日志磁盘 顺序写，消除了寻道时间第10页/共205页磁盘的性能指标 （1）容量 磁盘上信息的存储是以同心圆的形式排列的，每一个圆称为一个磁道。半径方向单位长度内的磁道数目称为道密度Dt，沿圆周单位长度上的信息比特数称为位密度Db，道密度与位密度的乘积叫做面密度Da，即Da = DtDb。Da越大表明一个盘片上能存储的信息量就越大。但面密度的提高会使相邻磁道间的数据干扰加大，磁

6、头在磁道上进行数据读写时易发生偏离，差错机率增大。目前最新的垂直级化技术可有效地降低干扰因素。硬盘的容量与碟片数、面密度关系密切，这两项数值越大则容量越大。但是碟片数的增加会使硬盘体积增厚，因此单碟容量的大小直接关系到整个硬盘容量的大小，但随着磁碟密度的提高，磁头就必须随之越来越灵敏。第11页/共205页磁盘的性能指标 （2）转速 转速是磁盘所有指标中除了容量之外最引人注目的性能参数，以每分钟多少转（RPM）为单位。转速对于硬盘传输速度和持续传输速度至关重要，转速越快，硬盘取得及传送数据的速度也就越快。目前，硬盘转速大致有4200RPM、5400RPM、7200RPM、10000RPM和150

7、00RPM。第12页/共205页磁盘的性能指标 （4）缓存 缓存也是磁盘相当重要的一个参数，其大小也会直接影响到磁盘的整体性能。在数据的读取过程中，硬盘里的控制芯片发出指令，将系统指令正在读取的簇的相邻的下一个或几个簇的数据读入硬盘高速缓存。这样，当系统指令开始要读取下一个簇的数据的时候，硬盘便不需要重新开始一个读取动作，只需要将缓存中的数据传送到系统主存中去就行了。因此缓存容量的加大可以容纳更多的预读数据，这样大大缩短系统等待的时间。目前主流硬盘的缓存通常为8MB和16MB。第13页/共205页磁盘的性能指标 （5）传输速率 传输速率分为内传输速率与外传输速率。内传输速率是从硬盘到缓存的传输

8、速度，外传输速率是从缓存到通信接口的传输速度。内传输速率更能反映硬盘的实际表现，通常以每秒MB为单位。目前，主流硬盘的传输速度通常为50100MB/S。第14页/共205页磁盘的性能指标 （3）平均寻道时间 平均寻道时间指的是磁头到达目标数据所在磁道的平均时间，它直接影响硬盘的随机数据存取速度。影响平均寻道时间的主要决定因素是磁头读写臂的运行速度，另外也跟单碟容量有关。单碟容量越高说明单碟的磁道数越多，磁道数的增加意味着磁道间距离的缩短，而磁头从一个磁道转移到另一个磁道所需的就位时间就会缩短，这将有助于随机数据传输速度的提高。而磁道内线性磁密度的增加则和硬盘的持续数据传输速度有着直接的联系，磁

9、头技术的发展确保了这个增长不会因为磁头的灵敏度的限制而放慢速度。所以在很多时候，更高单碟容量的5400RPM硬盘会比单碟容量较低的7200RPM硬盘速度更加快。目前硬盘平均寻道时间大约在10ms左右。第15页/共205页磁盘调度（1） FCFS（先来先服务）调度 先查找先进入服务列队的数据。例：假设磁道数为0199，我们申请调度的盘块儿分别在98, 183, 37, 122, 14, 124, 65, 67 磁道上。当前硬盘磁头在第53号磁道。按照FCFS顺序：磁头从53号磁道开始移动，按照98, 183, 37, 122, 14, 124, 65, 67 的顺序依次查找，并将数据输入内存。

10、第16页/共205页磁盘调度（2） SSTF（最短查找时间优先）调度 考虑了各个请求之间的区别，总是先执行查找时间最短的那个请求。磁头从53号磁道开始移动，按照65, 67, 37, 14, 98, 122, 124, 183 的顺序依次查找，并将数据输入内存。 第17页/共205页磁盘调度（3） SCAN（扫描）调度 此种调度算法为磁臂由磁盘的一端开始，移动到磁盘的另一端，在移动过程中，为访问请求服务。然后调转方向，从此端移动到另一端。磁头从53号磁道开始移动，按照37, 14, 0, 65, 67, 98, 122, 124, 183, 199的顺序依次查找，并将数据输入内存。第18页/共

11、205页磁盘调度（4） C-SCAN（环形扫描）调度 移动臂总是从0号柱面至最大号柱面顺序扫描，然后返回0号柱面重复进行。磁头从53号磁道开始移动，按照65, 67, 98, 122, 124, 183, 199, 0, 14, 37的顺序依次查找(其中从1990的过程中不做任何操作只是快速的移动），并将数据输入内存。 第19页/共205页磁盘调度（5） LOOK（查找）调度（电梯） 电梯算法。磁臂仅移动到请求的最外道就回转。反方向查找服务。磁头从53号磁道开始移动，按照65, 67, 98, 122, 124, 183, 14, 37的顺序依次查找，并将数据输入内存。第20页/共205页RA

12、IDRAID 廉价磁盘冗余阵列（RAID） Redundant Arrays of Inexpensive Disks 是一种利用大量廉价磁盘进行磁盘组织的技术 价格上，大量廉价的磁盘比少量昂贵的大磁盘合算得多 性能上，使用大量磁盘可以提高数据的并行存取 可靠性上，冗余数据可以存放在多个磁盘上，因此一个磁盘的故障不会导致数据丢失 过去RAID是大而昂贵的磁盘的替代方法；今天，使用RAID是因为它的高可靠性和高数据传输率；因此 “I” 代表independent，而非inexpensive第21页/共205页RAIDRAID 通过冗余提高可靠性 N个磁盘组成的集合中某个磁盘发生故障的概率比特定的

13、单个磁盘发生故障的概率高很多 假定单个磁盘的MTTF是100,000小时 (约为11年)，则由100个磁盘组成的阵列的MTTF是1000小时(约为41天) 冗余（Redundancy） 存储额外的信息，以便当磁盘故障时能从中重建 MTTF( Mean Time To Failure) 平均失效等待时间 第22页/共205页RAIDRAID 镜像(Mirroring or shadowing) 一个逻辑磁盘由两个物理磁盘组成，写操作在每个磁盘上执行 如果其中一个发生故障，数据可以从另一个磁盘读出 只有第一个磁盘的故障尚未恢复，第二个磁盘也发生故障，这时才会发生数据丢失 假定一个磁盘的MTTF是1

14、00,000小时，修复时间是10小时，则镜像磁盘系统的MTTF是100,0002/（2*10）=500*106小时，约为57000年第23页/共205页RAIDRAID 通过并行提高性能 负载平衡多个小的存取操作（即页面存取），以提高这种存取操作的吞吐量 并行执行大的存取操作，以减少大的存取操作的响应时间 通过在多个磁盘上对数据进行拆分来提高传输率 比特级拆分（Bit-level striping） 将每个字节按比特分开，存储到多个磁盘上 例如，对于一个由8个磁盘组成的阵列，将每个字节的第i个比特位写到第i个磁盘上；它的存取速度是单个磁盘的8倍 对于由4个磁盘组成的阵列，将每个字节的第i个比特

15、位和第i+4个比特位写到第i个磁盘上 块级拆分（Block-level striping） 对于由n个磁盘构成的阵列，文件的第i块 存放在第(i mod n) + 1个磁盘上第24页/共205页RAIDRAID RAID级别 镜像提供高可靠性，拆分提供高数据传输率，通过利用与奇偶校验相结合的磁盘拆分想法，可以实现以较低成本提供冗余的方案 不同的RAID级别，具有不同的代价、性能和可靠性CP代表数据的第二个拷贝表示纠错位第25页/共205页RAID 0RAID 0 块级拆分且没有任何冗余（如镜像或奇偶校验位）的磁盘阵列 容错性：没有 冗余类型：没有读性能：高随机写性能：高连续写性能：高需要的磁盘

16、数：1个或多个可用容量：总的磁盘的容量 用于高性能访问并且数据丢失不十分重要的应用场合，无故障的迅速读写，要求安全性不高，如图形工作站等。 RAID 0：无冗余拆分第26页/共205页RAID 1RAID 1 带块级拆分的磁盘镜像 容错性：有 冗余类型：复制读性能：低 随机写性能：低连续写性能：低需要的磁盘数：只需2个或2*N个可用容量：只能用磁盘容量的50% 一般用于类似于数据库系统中日志文件存储的应用场合。随机数据写入，要求安全性高，如服务器、数据库存储领域。 RAID 1：无冗余拆分CCCC第27页/共205页汉明码 汉明码是一个在原有数据中插入若干校验码来进行错误检查和纠正的编码技术。

17、 以典型的4 位数据编码为例，汉明码将加入3 个校验码，从而使实际传输的数据位达到7 个（位）：第28页/共205页汉明码 例：若数据码1101，此时D8=1 、D4=1、D2=0 、D1=1 ，在P1 编码时，先将D8、D4、D1 的二进制码相加，结果为奇数3，汉明码对奇数结果编码为1，偶数结果为0，因此P1值为1，D8+D2+D1=2 ，为偶数，那么P2值为0，D4+D2+D1=2，为偶数，P3值为0。 参照位置表，汉明码处理的结果就是1010101 。在这里汉明码都是以三个数据码为基准进行编码的。图示就是它们的对应表：第29页/共205页汉明码 在校验时则把每个汉明码与各自对应的数据位值

18、相加，如果结果为偶数就是正确，如果为奇数则说明当前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。 1101，正确的编码为1010101，如果第三个数据位在传输途中因干扰而变成了1，就成了1010111 。检测时，P1+D8+D4+D1 的结果是偶数4，第一位纠错代码为0，正确。P1+D8+D2+D1 的结果是奇数3，第二位纠错代码为1，错误。P3+D4+D2+D1 的结果是奇数3，第三位纠错代码为1，错误。 那么具体是哪个位有错误呢？三个纠错代码从高到低排列为二进制编码110 ，换算成十进制就是6，也就是说第6 位数据错了，而数据第三位在汉明码

19、编码后的位置正好是第6 位。 第30页/共205页汉明码 汉明码的数量与数据位的数量之间的关系:2PP+D+1 ，其中P 代表汉明码的个数，D 代表数据位的个数。 4位数据需要3位汉明码（23 4+3+1），64 位数据需要7 位汉明码（27 64+7+1 。 汉明码加插的位置也是有规律的。汉明码的插入位置为1、2、4、8、16 第31页/共205页RAID 2RAID 2 在RAID2 中，一个硬盘在一个时间只存取一位的信息。左边的为数据阵列，右边的阵列则是存储相应的汉明码，也是一位一个硬盘。所以RAID 2 中的硬盘数量取决于所设定的数据存储宽度。 在写入时，RAID 2 在写入数据位同时

20、还要计算出它们的汉明码并写入校验阵列，读取时也要对数据即时进行校验。汉明码只能纠正一个位的错误，所以RAID 2 也只能允许一个硬盘出问题，如果两个或以上的硬盘出问题，RAID 2 的数据就将受到破坏。但由于数据是以位为单位并行传输，所以传输率也相当快。 RAID 2 是早期为了能进行即时的数据校验而研制的一种技术，针对了当时对数据即时性非常敏感的领域，如、金融服务等。但由于花费太大（数据位宽越大，用于校验阵列的相对投资就会越小，4:3 与64:7）， 成本昂贵，目前已基本不再使用，转而以更高级的即时检验RAID 所代替，如RAID 3、5 等。PPP第32页/共205页RAID 2RAID

21、2 RAID 2使用共轴同步(spindle synchronize)技术，存取数据时,整个磁盘阵列一起动作,在各个磁盘的相同位置作平行存取，有最好的存取时间(access time)，以大带宽(band wide)并行传输所存取的数据，有最好的传输时间(transfer time) 对于大型档案的存取应用，RAID 2有较好的性能，但如果档案太小，性能会下降，因为磁盘的存取是以扇区为单位，而RAID 2的存取是所有磁盘平行动作，故小于一个扇区的数据量会使其性能大打折扣 RAID 2适合于存取连续且大量数据的应用，如大型电脑、作影像处理或CAD/CAM的工作站等第33页/共205页RAID 3

22、RAID 3 Parallel transfer with parity （并行传输及校验） RAID 3 是在RAID 2 基础上发展而来的，主要的变化是用相对简单的异或逻辑运算（XOR， eXclusive OR ）校验代替了相对复杂的汉明码校验，从而也大幅降低了成本。 RAID 3效果与RAID 2一样，但只有一个磁盘的额外开销P第34页/共205页RAID 3RAID 3 RAID3校验盘只有一个，而数据与RAID 0 一样是分成条带存入数据阵列中，这个条带的深度的单位为字节而不是bit。在数据存入时，数据阵列中处于同一等级的条带的XOR 校验编码被即时写在校验盘相应的位置，所以彼此不

23、会干扰混乱。读取时，则在调出条带的同时检查校验盘中相应的XOR 编码，进行即时的ECC。由于在读写时与RAID 0很相似，所以RAID 3 具有很高的数据传输效率。 RAID 3 在RAID 2 基础上成功地进行结构与运算的简化，曾受到广泛的欢迎，并大量应用。直到更为先进高效的RAID 5 出现后，RAID 3 才开始慢慢退出市场。第35页/共205页RAID 3RAID 3D1 1 1 1 1 0 0 0 0D2 1 0 1 0 1 0 1 0D3 0 0 1 1 1 0 0 0D1 1 1 1 1 0 0 0 0D2 ? ? ? ? ? ? ? ?D3 0 0 1 1 1 0 0 0D4

24、0 1 1 0 0 0 1 0D2 1 0 1 0 1 0 1 0故障恢复D4 0 1 1 0 0 0 1 0生成校验盘第36页/共205页RAID 3RAID 3D2 1 0 1 0 1 0 1 0D4 0 0 0 0 0 1 0 0写操作D2 1 1 0 0 1 1 0 0D1 1 1 1 1 0 0 0 0D2 1 1 0 0 1 1 0 0D3 0 0 1 1 1 0 0 0读D1,D3，写D2,D4D2 1 0 1 0 1 0 1 0D2 1 1 0 0 1 1 0 00 1 1 0 0 1 1 0D4 0 1 1 0 0 0 1 0读D2,D4，写D2,D4第37页/共205页RA

25、ID 4RAID 4 Independent Data disks with shared Parity disk （独立的数据硬盘与共享的校验硬盘） 与RAID 3 相比，关键之处是把条带改成了“块”。即RAID 4 是按数据块为单位存储的。一个数据块是一个完整的数据集合，比如一个文件就是一个典型的数据块。按块存储可以保证块的完整，不受因分条带存储在其他硬盘上而可能产生的不利影响（比如当多个硬盘损坏）。 在不同硬盘上的同级数据（在每个硬盘中同一柱面同一扇区位置的数据）块也通过XOR 进行校验，结果保存在单独的校验盘。在写入时，RAID 把各硬盘上同级数据的校验统一写入校验盘，读取时再即时进行

26、校验。因此即使是当前硬盘上的数据块损坏，也可以通过XOR 校验值和其他硬盘上的同级数据进行恢复。 RAID 4 在写入时要等一个硬盘写完后才能写一下个，还要写入校验数据所以写入效率比较差，读取时也是一个硬盘一个硬盘的读，但校验迅速，所以相对速度很快。RAID 4：块交叉奇偶校验P第38页/共205页RAID 4RAID 4D2 1 0 1 0 1 0 1 0D3 0 0 1 1 1 0 0 0D4 0 1 1 0 0 0 1 0D1 1 1 1 1 0 0 0 0第39页/共205页RAID 4RAID 4D2 1 0 1 0 1 0 1 0D3 0 0 1 1 1 0 0 0D4 0 1 1

27、 0 0 0 1 0读数据：一种潜在的并行假定D1忙，其余磁盘空闲D1 1 1 1 1 0 0 0 0第40页/共205页RAID 4RAID 4第41页/共205页RAID 5RAID 5 将数据和奇偶校验位都分布到所有的N+1个磁盘上；对每个块，一个磁盘存储奇偶校验位，其余磁盘存储数据 例如由5个磁盘组成的阵列，第n块的奇偶校验位存储在第(n mod 5)+1上，其余4个磁盘的第n块存储了对应这个块的实际数据 奇偶校验块不能和这个块对应的数据存储在同一个磁盘上 所有磁盘都参与对读请求的服务，而RAID 4中奇偶校验磁盘不参与读操作 RAID 5包容了RAID 4，同时在相同成本下，提供了更

28、好的读写性能RAID 5：块交叉的分布奇偶校验PPPPP第42页/共205页RAID 6RAID 6D1D2D3D4D5D6D7111010011010101011001Hamming codeD5对应D1, D2, D3D6对应D1, D2, D4D7对应D1, D3, D4第43页/共205页RAID 6RAID 6D1 1 1 1 1 0 0 0 0D2 1 0 1 0 1 0 1 0D3 0 0 1 1 1 0 0 0D4 0 1 0 0 0 0 0 1生成校验盘D5 0 1 1 0 0 0 1 0D6 0 0 0 1 1 0 1 1第44页/共205页RAID 6RAID 6D1 1

29、 1 1 1 0 0 0 0D2 ? ? ? ? ? ? ? ?D3 0 0 1 1 1 0 0 0D4 0 1 0 0 0 0 0 1D5 ? ? ? ? ? ? ? ?D6 0 0 0 1 1 0 1 1D7 1 0 0 0 1 0 0 1故障恢复取D1,D4,D6D2 1 0 1 0 1 0 1 0取D1,D2,D3D5 0 1 1 0 0 0 1 0第45页/共205页RAID 6RAID 6写操作D2 1 0 1 0 1 0 1 0D2 0 0 0 0 1 1 1 1D21 0 1 0 1 0 1 0D2 0 0 0 0 1 1 1 11 0 1 0 0 1 0 1D50 1 1 0

30、 0 0 1 0D6 0 0 0 1 1 0 1 1D6 1 0 1 1 1 1 1 0D5 1 1 0 0 0 1 1 1第46页/共205页高性能可靠性差最佳写性能开销大高数据传输率大数据量高的总I/O率适合随机读大数据量高可靠性第47页/共205页选择合适的RAIDRAID级别 RAID 0 是最快，最有效率的阵列类型，但是不支持容错功能。 RAID 1 适合性能要求较高又需要容错功能的阵列。另外， RAID 1是在只有少于2个磁盘的环境下支持容错功能的唯一选择。 RAID 3 被用在数据加强和加速单用户对连续的长记录时的数据传输。 RAID 5 是在多用户，对数据写入的性能要求不高的环

31、境下的最好选择。然而，它要求至少3个，通常使用5个磁盘来执行。 RAID 10 集良好的可靠性和高性能于一身.第48页/共205页选择合适的RAIDRAID级别 RAID 0 无冗余拆分 RAID 1 镜像 RAID 5 拆分校验码 RAID 10 拆分镜像第49页/共205页选择合适的RAIDRAID级别Read-Intensive020000400006000080000Soft-RAID5RAID5RAID0RAID10RAID1SingleDiskThroughput (tuples/sec)第50页/共205页选择合适的RAIDRAID级别Write-Intensive0408012

32、0160Soft-RAID5RAID5RAID0RAID10RAID1SingleDiskThroughput (tuples/sec)第51页/共205页选择合适的RAIDRAID级别 日志文件 RAID 1 容错，高写输出率 临时文件 RAID 0 is appropriate. 无容错，高吞吐率 数据以及索引文件 RAID 5适合于读为主的应用 RAID 10适合于写为主的应用第52页/共205页磁盘还是内存 保持常用数据在内存，可以减少磁盘I/O，但增加内存代价 若一个页面每秒被访问n次，将它驻留在内存节省 保持一个页面在内存的代价n *price-per-disk-driveacce

33、sses-per-second-per-diskprice-per-MB-of-memorypages-per-MB-of-memory第53页/共205页磁盘还是内存 5-minute rule：如果一个被随机访问的页面的使用频率超过每5分钟一次，那么它应该被驻留在内存 1-minute rule：如果被顺序访问的页面的使用频率超过每1分钟一次，那么它应该被驻留在内存price-per-disk-drive=2000$/diskaccesses-per-second-per-disk=64accesses/second/diskprice-per-MB-of-memory=15$/MB_RA

34、Mpages-per-MB-of-memory=128pages/MB2000 * 128/15/64/=266第54页/共205页缓冲区管理 当需要访问一个磁盘块时 如果该块已经在缓冲区中，返回块在内存中的地址 如果块不在缓冲区中 缓冲区管理器为该块在缓冲区中分配空间，如果有必要，替换缓冲区中的其他块 如果被替换的块被修改过，则将其写回磁盘 将所需的块调入缓冲区，返回其在缓冲区的地址第55页/共205页缓冲区管理 被钉住的块(pinned blocks) 不允许写回磁盘的块 当一个块上的更新正在进行时，不允许写回磁盘 钉住被频繁访问的小表 块的强制输出(forced output of bl

35、ocks) 先写日志原则 检查点 提交事务的日志记录第56页/共205页缓冲区管理：替换策略 LRU(最近最少使用) 如果必须替换一个块，则替换最近最少使用的块 MRU(最近最常使用) 如果必须替换一个块，则替换最近最常使用的块SR 对于R中的每条元组tr对于S中的每条元组tsn一旦R中的一个元组处理完，就不会再使用它了，应该立即丢弃(toss immediate)n当S中的一个元组被处理完，只有其他S中的元组都被处理完后才会再用到它，应该采用MRU第57页/共205页替换策略 当使用者第一次向数据库发出查询数据的请求时，数据库会先在缓冲区中查找该数据,如果要访问的数据恰好已经在缓冲区中(称之

36、为Cache Hit),那么就直接用缓冲区中读取该数据. 反之如果缓冲区中没有使用者要查询的数据称之为Cache Miss,这种情况下数据库就会先从磁盘上读取使用者要的数据放入缓冲区,使用者再从缓冲区读取该数据. 很显然Cache Hit会比Cache Miss时存取速度快.第58页/共205页OPTIMAL/FIFO OPTIMAL：最佳置换算法。它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是

37、未来最长时间内不再被访问的，因而该算法是无法实现的，一般可以利用此算法来评价其它算法。 FIFO：先进先出置换算法。这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 第59页/共205页例 在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页次数(假设开始执行时主存中没有页面)，并比较所得结果。 (1

38、)最佳置换法(OPT) (2)先进先出法(FIFO)第60页/共205页例 最佳页面置换算法:块为3：缺页次数为7 块为3：缺页次数为6 第61页/共205页例n先进先出页面置换算法:块为3：缺页次数为9n块为3：缺页次数为10 第62页/共205页LRU LRU算法(Least recently used)的基本概念是:当内存的剩余的可用空间不够时,缓冲区尽可能的先保留使用者最常使用的数据,就是优先清除”较不常使用的数据”,并释放其空间. FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，

39、是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 第63页/共205页LRU 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 7

40、0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7 7 1 1 2 3 0 4 4 4 0 0 3 3 2 2 * * * * * * * *缺页中断次数：8第64页/共205页LFU 最近最少使用淘汰法LFU(Least Frequently Used) （记录各个页面在最近一段时间内被使用的次数，淘汰使用次数最少的页面。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0- 7 0 1 2 0 0 0 0 2 3 0 3 2 2 2 0 1 1 0 7 0 1 2 2 2 2 0 2 3 0 3 3 3 2 0 0 1 7 0 1 1 1 4 4 0

41、 2 2 0 0 0 3 2 2 2 - 7 7 3 3 3 3 4 4 4 4 1 1 1 3 7 7 * * * * * * * *缺页中断次数：8第65页/共205页缓冲区管理：SQL Server 访问内存页面 为快速找到页面，内存页面地址被散列 给定dbid-fileno-pageno标识(数据库ID, 文件号、页面号的组合)，计算其hash地址 Lazywriter(缓冲池管理器) 使用时钟算法第66页/共205页时钟算法 SQL Server 2000使用一个专门的进程，采用时钟算法进行页面置换。它为每个缓冲区设置一个计数器，每隔一段时间则顺序扫描缓冲池里的每一个缓冲区，检查计数

42、器。如果计数器为零，则说明这一缓冲区可回收使用。于是，系统先将缓冲区内脏数据写入磁盘，而后将缓中区放入自由缓冲区列表。如果计数器的值不为零，系统则将计数器的值减少。而当某个进程访问缓冲区的数据时，该缓冲区的计数器则会增加。 对于缓冲区内那些通过较高代价产生的对象，系统使用具有较高参考价值的计数器。在顺序扫描时，这些计数器的值不是简单的减少，而是以某种策略缩小（如除以4），这样可以保证它不会很快变成零，从而可以在内存中贮存较长时间。其它类似用到缓冲区的设计（当缓存不足以放下所有数据或为了节省内存），均可参考此种替换策略。第67页/共205页索引 顺序索引 基于值的顺序排序 散列索引 基于将值平均

43、分布到若干散列桶中 索引评价指标 访问类型 访问时间 插入时间 删除时间 空间开销第68页/共205页主索引和辅助索引 主索引(primary index)、辅助索引(secondary index)；聚集索引(cluster index)、非聚集索引(noncluster index)branch_namebalance第69页/共205页主索引 主索引包含表中每条记录的索引关键字并且当未指定任何其他索引作为表主索引时的默认索引。主索引禁止为产生索引关键字所指定字段或索引表达式中的重复值；因此，主索引中每个索引关键字是唯一的。每个表只能创建一个主索引。 注意：主索引是数据库表的整体部分。如果

44、从数据库中释放一个表，则主索引被移去。如果在任何包含重复数据的字段上指定主索引，将 产生一个错误。第70页/共205页唯一索引 索引还可以用于强迫字段数值的唯一性，或者是多个字段组合值的唯一性： CREATE UNIQUE INDEX name ON table (column , .); 目前，只有 B-tree 索引可以声明为唯一的。 如果索引声明为唯一的，那么就不允许出现多个索引值相同的行。 我们认为 NULL 值相互间不相等。 一个多字段唯一索引认为只有两行数据里所有被索引字段都相同的时候才是相同的，这种数据才被拒绝。 如果一个表声明了一个唯一约束或者一个主键， 那么 SQL 自动在那

45、些组成主键或者唯一字段的列上创建唯一索引(可能地话是一个多字段索引)， 以强迫这些约束。 注意: 给一个表增加唯一约束的比较好的办法是 ALTER TABLE . ADD CONSTRAINT。 我们没有必要在唯一字段上建立索引，那样做只会重复建立自动创建的索引。第71页/共205页主索引VS唯一索引 主索引一定是唯一索引； 唯一索引不一定是主索引； 主索引只有一个； 唯一索引可有多个 第72页/共205页聚集索引(Clustered Index) 聚集索引规定数据在表中的物理存储顺序：聚集索引表记录的排列顺序与索引的排列顺序一致。因此一个表只能包含一个聚集索引。但该索引可以包含多个列（组合索

46、引）。 聚集索引对于那些经常要搜索范围值的列特别有效。使用聚集索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。这样有助于提高此类查询的性能。同样，如果对从表中检索的数据进行排序时经常要用到某一列，则可以将该表在该列上聚集（物理排序），避免每次查询该列时都进行排序，从而节省成本。 第73页/共205页聚集索引 当索引值唯一时，使用聚集索引查找特定的行也很有效率。例如，使用唯一雇员 ID 列 emp_id 查找特定雇员的最快速的方法，是在 emp_id 列上创建聚集索引或 PRIMARY KEY 约束。 说明 如果该表上尚未创建聚集索引，且在创建 PRIMARY KEY 约束时

47、未指定非聚集索引，PRIMARY KEY 约束会自动创建聚集索引。 也可以在 lname（姓氏）列和 fname（名字）列上创建聚集索引，因为雇员记录常常是按姓名而不是按雇员 ID 分组和查询的第74页/共205页聚集索引 聚集索引的叶节点就是实际的数据页 在数据页中数据按照索引顺序存储 行的物理位置和行在索引中的位置是相同的 每个表只能有一个聚集索引 聚集索引的平均大小大约为表大小的5%左右 第75页/共205页聚集索引 select * from table where firstName = Ota 第76页/共205页非聚集索引 (Unclustered Index) 非聚集索引数据存

48、储在一个地方，索引存储在另一个地方，索引带有指针指向数据的存储位置。索引中的项目按索引键值的顺序存储，而表中的信息按另一种顺序存储。 SQL Server2000 在搜索数据值时，先对非聚集索引进行搜索，找到数据值在表中的位置，然后从该位置直接检索数据。这使非聚集索引成为精确匹配查询的最佳方法，因为索引包含描述查询所搜索的数据值在表中的精确位置的条目。如果基础表使用聚集索引排序，则该位置为聚集键值；否则，该位置为包含行的文件号、页号和槽号的行 ID (RID)。例如，对于在 emp_id 列上有非聚集索引的表，如要搜索其雇员 ID (emp_id)，SQL Server 会在索引中查找这样一个

49、条目，该条目精确列出匹配的 emp_id 列在表中的页和行，然后直接转到该页该行。第77页/共205页非聚集索引 非聚集索引的页，不是数据，而是指向数据页的页。 若未指定索引类型，则默认为非聚集索引 叶节点页的次序和表的物理存储次序不同 每个表最多可以有249个非聚集索引 在非聚集索引创建之前创建聚集索引(否则会引发索引重建) 第78页/共205页非聚集索引 select * from employee where lname = Green 第79页/共205页比较 聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致，聚集索引表记录的排列顺序与索引的排列顺序一致，优点

50、是查询速度快，因为一旦具有第一个索引值的纪录被找到，具有连续索引值的记录也一定物理的紧跟其后。聚集索引的缺点是对表进行修改速度较慢，这是为了保持表中的记录的物理顺序与索引的顺序一致，而把记录插入到数据页的相应位置，必须在数据页中进行数据重排，降低了执行速度。 建议使用聚集索引的场合为：a.此列包含有限数目的不同值； b.查询的结果返回一个区间的值； c.查询的结果返回某值相同的大量结果集。 第80页/共205页比较 非聚集索引指定了表中记录的逻辑顺序，但记录的物理顺序和索引的顺序不一致，聚集索引和非聚集索引都采用了B+树的结构，但非聚集索引的叶子层并不与实际的数据页相重叠，而采用叶子层包含一个

51、指向表中的记录在数据页中的指针的方式。非聚集索引比聚集索引层次多，添加记录不会引起数据顺序的重组。 建议使用非聚集索引的场合为： a.此列包含了大量数目不同的值；b.查询的结束返回的是少量的结果集； c. order by 子句中使用了该列。第81页/共205页何时使用聚集索引或非聚集索引 第82页/共205页稠密索引 文件中的每个搜索码值都有一个索引记录第83页/共205页稀疏索引 只为搜索码的某些值建立索引记录第84页/共205页多层索引 对索引建立索引第85页/共205页B+树 树结点 Ki是搜索码，Pi是指针第86页/共205页B+树 每个非叶结点有n/2到n个子女第87页/共205页

52、B+树 插入导致结点分裂插入Clearview第88页/共205页B+树第89页/共205页B+树 删除导致结点合并删除Downtown第90页/共205页B+树第91页/共205页散列索引 桶(bucket) 存储一条或多条记录的存储单元 散列(hash) K是搜索码，B是桶地址，散列函数h(K)=B 散列函数 分布是均匀的，桶包含记录的个数是均匀的 分布是随机的，散列值不能与搜索码的值呈现出相关性 桶溢出(bucket overflow) 桶不足(insufficient bucket)+偏斜(skew)第92页/共205页第93页/共205页散列索引第94页/共205页散列索引 溢出链第

53、95页/共205页位图索引 针对一些特殊的列建立索引 列中的每一个值对应一个向量中的一位 向量的长度对应与记录的条数 不适合列中值的个数太多的情况Cust Region TypeC1AsiaRetailC2EuropeDealerC3AsiaDealerC4America RetailC5EuropeDealerRecID Retail Dealer110201301410501RecIDAsia Europe America11002010310040015010Base tableIndex on RegionIndex on Type第96页/共205页位图索引 查询： Select c

54、ust From BaseTable Where Region=Asia and Type=Dealer； BitMap for Region(Asia): 10100 BitMap for Type(Dealer): 01101 查询结果：向量与操作： 00100第97页/共205页位图索引与B树的大小对比第98页/共205页位图索引 设表中有10M个记录，每个记录长800字节，每一页16K字节，则扫描此表共需50万次I/O操作 “在在美美国国加加州州有有多多少少男男性性未未申申请请保保险险？” Gender M M F M M - 800 Bytes/Row 10M ROWS State

55、NY CA CT MA CA - 传统 RDBMS 作法 传统 RDBMS 做法 Insured Y Y N Y N 800 Bytes x 10M Rows 16K /Page = 500,000 I/Os处处理理大大量量的的数数据据 经经常常进进行行全全表表扫扫描描 第99页/共205页位图索引 对于10M个记录建立三列的位图索引共占（10Mbit*3列/8)字节的空间，每页16K，则这些索引仅占235页，因此存取这些索引只要235次I/O操作 M Y CA M N CA F Y NY M N CA 1 2 4 3 Gender Insured State = 2 + + 1 1 0 1

56、1 1 0 1 0 1 0 1 10 M Bits 10 M Bits / 8 x 3 Cols 16 K Page = 235 I/Os 第100页/共205页位图索引RID Item GenderR1aFR2aMR3bFR4bFR5bMR6cFR7cMR8dMRIDMFR101R210R301R401R510R601R710R810RIDabcdR11000R21000R30100R40100R50100R60010R70010R80001基本表Item位图索引Gender位图索引第101页/共205页编码位图索引RID Item GenderR1aFR2aMR3bFR4bFR5bMR6c

57、FR7cMR8dMRIDB1 B0R100R200R301R401R501R610R710R811基本表Item编码位图索引Item值 编码值a00b01c10d11映射表第102页/共205页编码位图索引如果属性I的取值v0被编码为b1b0，检索函数被定义为x1x0，其中如果bi=1，则xi=Bi，否则xi=Bi(Bi为Bi的非)检索函数fa = B1B0 ，fb = B1B0fc = B1B0 ，fd = B1B0如果检索取值为a或b的元组， fa or fb = B1B0 or B1B0 = B1第103页/共205页位片索引(Bit-sliced Index)(Bit-sliced I

58、ndex) 位片索引是将属性列的域值按照某种方式进行垂直分割，然后以二进制位图的形式存储 Sales in binary form8bit 4bit 2bit 1bit0 1 1 01 0 0 10 1 0 11 0 1 11 0 0 10 0 1 10 1 1 11 1 0 0Sales6951193712Sales in binary form0 1 1 01 0 0 10 1 0 11 0 1 11 0 0 10 0 1 10 1 1 11 1 0 0第104页/共205页位片索引3/13/13/13/13/13/13/13/13236384143464749NYMANYCTNYRICT

59、NYAABAABBA6951193712101010011101100101011001101000111001011001111110date store state class salesstate= NYclass=Asales in binary form 8 4 2 1select sum(sales) from customerswhere state=NY and class=A第105页/共205页多维索引 空间数据第106页/共205页多维索引 空间查询 临近查询查询位于特定位置附近的对象 最近邻查询(nearest neighbor query)查询离特定位置最近的对象 K

60、NN查询离特定位置最近的k个对象 区域查询查询位于指定区域内的对象第107页/共205页空间索引 空间索引是对存储在介质上的数据位置信息的描述，用来提高系统对数据获取的效率。空间索引的提出是由两方面决定的：其一是由于计算机的体系结构将存贮器分为内存、外存 两种，访问这两种存储器一次所花费的时间一般为3040ns，810ms，可以看出两者相差十 万倍以上，尽管现在有“内存数据库”的说法，但绝大多数数据是存储在外存磁盘上的，如果对磁盘上数据的位置不加以记录和组织，每查询一个数据项就要扫描整个数据文件，这种访问磁盘的代价就会严重影响系统的效率，因此系统的设计者必须将数据在磁盘上的位置加以记录和组织，