《第二讲 数据组织存储与索引》由会员分享，可在线阅读，更多相关《第二讲 数据组织存储与索引（36页珍藏版）》请在金锄头文库上搜索。
1、第二部分：数据存贮及索引技术第二部分：数据存贮及索引技术一、一、 存储介质及访问策略存储介质及访问策略 二二 、数据文件的组织、数据文件的组织 三三 、索引结构、索引结构教材第教材第2-3章的内容章的内容一：存储介质及访问策略一：存储介质及访问策略1 1 存储器层次存储器层次高速缓冲存储器主存储器二级存储器（磁盘）三级存储器备份归档备份归档存储存储计算计算速度速度DBMSDBMS主要与磁盘进行交互。所以我们主要讨论磁盘的主要与磁盘进行交互。所以我们主要讨论磁盘的 存储及访问策略。一般讲，存储及访问策略。一般讲，DBMSDBMS自己管理的磁盘块。自己管理的磁盘块。2 2 磁盘的存储特性磁盘的存储
2、特性与磁盘相关的参数与磁盘相关的参数: : * * 磁盘的容量：片数，磁道数，扇区数磁盘的容量：片数，磁道数，扇区数实际应用中，使用逻辑单元实际应用中，使用逻辑单元-磁盘块磁盘块 一个磁盘块包含一个或几个扇区一个磁盘块包含一个或几个扇区3 3 磁盘的访问特性磁盘的访问特性磁盘的访问过程以及速度磁盘的访问过程以及速度 访问过程：访问过程： 定位：将磁头移到目标块所在的柱面定位：将磁头移到目标块所在的柱面 旋转：磁盘旋转，将第一个扇区移至磁头下面旋转：磁盘旋转，将第一个扇区移至磁头下面 读或写数据读或写数据 访问速度：存取时间（延迟），指从发出数据请求到访问速度：存取时间（延迟），指从发出数据请求
3、到 内容出现在主存中。内容出现在主存中。A.A.处理器与控制器处理请求所花的时间处理器与控制器处理请求所花的时间 B.B.寻道时间：将磁头定位到合适的柱面所花的时间，寻道时间：将磁头定位到合适的柱面所花的时间， 一般用平均寻道时间一般用平均寻道时间. . C.C.旋转时间：磁头转到组成块的第一个扇区所需时间旋转时间：磁头转到组成块的第一个扇区所需时间 D.D.数据传输时间：在块内读或写数据所需时间。数据传输时间：在块内读或写数据所需时间。存取时间存取时间= =寻道时间寻道时间+ +旋转时间旋转时间+ +数据传输时间数据传输时间 注：这个时间与磁盘的物理特性密切相关，不同类型注：这个时间与磁盘的
4、物理特性密切相关，不同类型 的磁盘，时间不同。的磁盘，时间不同。4 4 磁盘存取优化策略磁盘存取优化策略按柱面组织数据按柱面组织数据 将所需要的数据存储在同一个磁道或同一个柱面上。将所需要的数据存储在同一个磁道或同一个柱面上。使用磁盘臂调度算法使用磁盘臂调度算法电梯算法电梯算法 处理大量块请求的非常有效的算法处理大量块请求的非常有效的算法使用多磁盘使用多磁盘并行处理方法并行处理方法 将数据分配到多个磁盘上将数据分配到多个磁盘上磁盘镜像技术磁盘镜像技术 通过选择寻道时间最短的磁盘来提高读速度。通过选择寻道时间最短的磁盘来提高读速度。预取与大规模缓冲技术预取与大规模缓冲技术 通过预测将所需数据块先
5、装入缓存，从而减少等待通过预测将所需数据块先装入缓存，从而减少等待 时间。或者使用较好的缓冲策略尽量减少磁盘的访问时间。或者使用较好的缓冲策略尽量减少磁盘的访问 次数等。次数等。5 5 数据存储稳定的策略数据存储稳定的策略RAIDRAID技术技术用用N N个磁盘代替一个磁盘进行数据存储，提高数据可靠性的一个磁盘代替一个磁盘进行数据存储，提高数据可靠性的一 类磁盘组织方法。类磁盘组织方法。RAID1RAID1：一些做数据盘：一些做数据盘, ,一些做冗余盘。一些做冗余盘。并行写入并行写入135246135246Disk1Disk2Disk3Disk4并 行 读 出（1）写入操作并行化，并有冗余。
6、（2）没有错误校验。 （3）适用大记录和需要大量I/OI/O操作的应用。RAID2RAID2：内存风格的纠错码，按字节纠错：内存风格的纠错码，按字节纠错1a 2a 3a1b 2b 3bEccEccEccEccEccEccDisk1Disk2Disk3Disk4读跨越 所有数 据盘（1）每个记录被拆分，分布在不同数据盘。 （2）错误校验码（ECC）被拆分放在冗余盘。 （3）每个读/写操作并行地使用数据盘。 （4）可利用冗余盘进行数据重建一次写 横跨所 有磁盘RAID3RAID3：位交叉奇偶校验组织，以扇区为单位进行校验：位交叉奇偶校验组织，以扇区为单位进行校验1a 2a 3a1b 2b 3b1c
7、 2c 3cEccEccEccDisk1Disk2Disk3Disk4读跨越 所有数 据盘（1）每个记录被拆分，分布在不同数据盘。 （2）一个磁盘用于存放错误校验码（ECC）。 （3）每个读/写操作并行地使用数据盘。 （4）可利用冗余盘进行数据重建一次写 横跨所 有磁盘RAID4RAID4：块交叉奇偶校验组织，以块为单位进行校验：块交叉奇偶校验组织，以块为单位进行校验并行写 入磁盘147258369EccEccEccDisk1Disk2Disk3Disk4读一个 块只涉 及一个 数据盘， 可以并 行读多 种数据（1）数据所使用块级拆分，分布在不同数据盘。 （2）一个磁盘用于存放错误校验码（EC
8、C）。 （3）每个读/写操作只涉及一个数据盘。 （4）可利用冗余盘进行数据重建RAID5RAID5：块交叉分布奇偶校验组织，以块为单位进行校验：块交叉分布奇偶校验组织，以块为单位进行校验159Ecc2610Ecc3711Ecc4812EccDisk1Disk2Disk3Disk4（1）数据所使用块级拆分，分布在所有磁盘。 （2）每个磁盘有一部分空间用于存放错误校验码（ECC）。 （3）每个读/写操作只涉及一个数据盘。 （4）利用程序并行操作不同的数据并行写 入磁盘并行读 数据RAIDRAID级别的选择主要考虑以下因素：级别的选择主要考虑以下因素： * * 磁盘带来的资金开销磁盘带来的资金开销
9、* * I/OI/O操作数量方面的需求操作数量方面的需求 * * 数据重建过程中的性能数据重建过程中的性能一般来说要在一般来说要在RAID1RAID1和和RAID5RAID5之间进行选择，之间进行选择，RAID1RAID1提供好提供好 的写操作性能，在的写操作性能，在DBSDBS的日志文件存储中使用比较多的日志文件存储中使用比较多; ;在读多在读多 写少的应用中，的写少的应用中，的RAID5RAID5是一个不错的选择。是一个不错的选择。二：数据文件的组织方式二：数据文件的组织方式1 1 字段的表示字段的表示SQLSQL中各种数据类型均被表示成一定长度的字节序列：中各种数据类型均被表示成一定长度
10、的字节序列： 整型整型2/42/4个字节个字节 浮点浮点4/84/8个字节个字节 char(n)char(n)n n个字节的数组个字节的数组 VarChar(n)VarChar(n)n+1n+1个字节的数组个字节的数组 2 2 记录的表示记录的表示 * * 定长记录：它所包含的所有字段均为定长定长记录：它所包含的所有字段均为定长Create table movie(Create table movie( name char(30),name char(30), address varchar(255),address varchar(255), gender char(1),gender ch
11、ar(1), birthdate DATE)birthdate DATE)namenameaddressaddressgendergenderbirthdatebirthdate030286287297namenameaddressaddressgendergenderbirthdatebirthdate指向模式的指针 记录长度 时间戳12443003043160* * 变长记录：允许它包含变长字段变长记录：允许它包含变长字段, ,有多种表示方法。有多种表示方法。genderbirthdatenameaddress记录长度 指向address其它首部信息3 3 多个记录的集合构成块，数据以块的
12、形式在磁盘与多个记录的集合构成块，数据以块的形式在磁盘与 主存间进行移动。主存间进行移动。块首部块首部 记录记录1 1记录记录2 2与其它块链接的指针 块属于哪个关系 每条记录的偏移量目录 块ID 最后修改的时间戳4 4 数据文件的组织方式数据文件的组织方式组织方法：组织方法： * * 堆文件组织堆文件组织 * * 顺序文件组织顺序文件组织 * * 散列文件组织散列文件组织文件形式：文件形式： * * 顺序文件：每块存贮一个关系，按某种顺序进行顺序文件：每块存贮一个关系，按某种顺序进行 * * 聚簇文件：每块可存贮多个有关联的关系聚簇文件：每块可存贮多个有关联的关系A217Brighton75
13、0A101Downtown500A102mianus600A215Redwood700顺序文件顺序文件cnamecstreetccityHayesMainBrigTunermianusstamecnameanumberHayesA102TunerA215HayesMainBrigHayesA102HayesA101TunermianusstameTunerA215聚簇文件聚簇文件5 DBMS5 DBMS进行数据访问的过程由存储管理程序执行进行数据访问的过程由存储管理程序执行为了减少磁盘的访问量，应用合理缓冲区数据块替换算法。三：索引结构三：索引结构1 1 索引的分类索引的分类按是否按码值排序分
14、为：按是否按码值排序分为： 有序索引：基于值的排序顺序有序索引：基于值的排序顺序 散列索引：利用散列函数将值平均分布到若干个桶中散列索引：利用散列函数将值平均分布到若干个桶中 按索引是否决定记录的存贮顺序分：按索引是否决定记录的存贮顺序分： 主索引：索引顺序决定记录存储顺序主索引：索引顺序决定记录存储顺序聚集索引聚集索引 辅助索引：索引顺序不决定记录存储顺序辅助索引：索引顺序不决定记录存储顺序2 2 有序索引有序索引(1)(1)简单的主索引结构（索引顺序文件）简单的主索引结构（索引顺序文件） 文件按搜索码的顺序存储，索引记录按搜索码值排序文件按搜索码的顺序存储，索引记录按搜索码值排序注：索引记
15、录由一个搜索码值和指向具有该搜索码值的一个或注：索引记录由一个搜索码值和指向具有该搜索码值的一个或 多个记录的指针构成。多个记录的指针构成。A217Brighton750A101Downtown500A102mianus600A112Perryridge900A218Perryridge400A215Redwood700A305Roundhill260BrightonmianusRedwood此种主索引可以是稀疏的，也可以是稠密的此种主索引可以是稀疏的，也可以是稠密的A217Brighton750A101Downtown500A102mianus600A112Perryridge900A218
16、Perryridge400A215Redwood700A305Roundhill260BrightonDowntownmianusPerryridgeRedwoodRoundhill稠密索引特点：查找快，但占空间大，且不容易维护。稠密索引特点：查找快，但占空间大，且不容易维护。 稀疏索引特点：查找相对慢，但占空间小，易于维护。稀疏索引特点：查找相对慢，但占空间小，易于维护。 有时二者经常结合使用建立多级索引，即先建立稠密主索引，有时二者经常结合使用建立多级索引，即先建立稠密主索引， 然后在主索引文件上建立稀疏索引。然后在主索引文件上建立稀疏索引。(2)(2)简单的辅助索引结构简单的辅助索引结构 辅助索引是稠密索引，每个一搜索码值均有索引记录，对应辅助索引是稠密索引，每个一搜索码值均有索引记录，对应 文件中的数据记录。文件中的数据记录。A217Brighton700A101Downtown500A102mianus600A112Perryridge900A218Perryridge40
