第6章-数据存储与查询优化ppt课件.ppt

《第6章-数据存储与查询优化ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章数据存储与查询优化数据库原理及应用郑轶（2010）目录6.1物理存储6.2索引结构6.3查询处理过程6.4代数优化6.5物理优化6.1物理存储6.1.1物理存储介质概述存储介质可以根据数据存取的速度、购买介质时每单位数据的成本和介质的可靠性来分类。主要的介质有：磁带、光盘等磁盘内存cache一级存储二级存储三级存储磁盘读写磁盘数据步骤：移动磁盘臂，确定磁道；寻道时间。旋转盘片，确定扇区；旋转时间。读写数据；传输时间。磁盘访问时间=寻道时间+旋转时间+传输时间数据预存：读取指定数据的同时预先读取与其相邻

2、的一定范围内的数据。按块传输：块大小1-8KB6.1.2缓冲区管理缓冲区是内存的一部分，用于存储磁盘块的内容。缓冲区管理器管理内存中缓冲区空间的分配。缓冲区管理器使用不同的技术（比如缓冲区替换策略、牵制的块、缓冲区高速缓存等）来有效地为数据库系统服务。最近最少使用替换策略（LeastRecentlyUsed，LRU）6.1.3记录的存储数据通常是以记录的形式存储的。记录又由字段组成。由于字段类型分为定长和变长两种，文件也可分为：定长记录和变长记录两种。定长记录中，所有的字段都是定长的，只需将所有字段按既定的顺

3、序连续存放，所有字段的地址相对于记录首地址的偏移都可以由计算得到。6.1.3记录的存储变长记录中每个字段相对于记录首地址的偏移不固定。内部格式通常有两种：用特殊的分割符将记录的各字段分开。在记录首部存储各个字段的偏移量。块格式数据文件的重整超长记录和记录的跨块存储跨块存储提高了磁盘空间的利用率。跨块存储的记录分布于不同的块中，在物理上不连续，需要用一个链表维护同一记录的不同部分。6.1.4文件组织方式在DBMS中常用的文件组织方式有：堆文件：记录间没有次序关系，新加入的记录可以存储在文件中任何有空间的地方。顺

4、序文件：记录按搜索键排序。哈希文件：对记录的某些字段进行哈希运算，运算的结果决定记录存储在文件中的哪一块。聚集文件：将同种类或相关的来自于不同关系的记录存放在同一块中，以减少同时获取这些记录的I/O操作。6.2索引从理论上来说，只要记录被正确地存储于书记文件中，DBMS就可以正常工作；但实际上，单纯依赖数据文件处理查询有时效率非常低。索引是一个表或数据结构，用于确定文件中满足某些条件的行（记录）的位置。索引键（索引字段）B+树索引、哈希索引6.3查询处理过程查询处理过程包括三步：语法分析、查询优化、执行。查询

5、总代价=I/O代价+CPU代价+内存代价+通信代价（分布式数据库）例：求选修了课程C2的学生姓名。其SQL语句：SELECTS.SnameFROMS,SCWHERES.Sno=SC.SnoANDSC.Cno=‘C2’;假定学生－课程数据库中有1000个学生记录，10000个选课记录，其中选修C2课程的选课记录为50个。系统可用多种等价的关系代数表达式来完成这一查询：Q1=πSname(σS.Sno=SC.Sno∧SC.Cno=‘C2’（S×SC）)Q2=πSname(σSC.Cno=‘C2’（S∞SC）)Q3

6、=πSname(S∞σSC.Cno=‘C2’（SC）)一个实例Q1=πSN(σS.S#=SC.S#∧SC.C#=‘C2’（S×SC))1、计算广义笛卡儿积设一个块能装10个S元组或100个SC元组，在内存中存放5块S元组1块SC元组，则读取总块数为：1000/10＋10000/100×(1000/10)/5＝2100块其中读S表100块，读SC表20遍，每遍100块，若每秒读20块，则总计要花105秒。连接以后的元组数为1000×10000，设每块能装10个元组，则写出这些块要花106/20＝5×104秒。E

7、1xE2代价估计主要是从磁盘读块和中间结果写盘的时间考虑，而对主存中数据的处理时间忽略不计。E1xE2读块总数=E1的块数+E2的块数×读E2的遍数2、作选择操作依次读入连接后的元组，按照选择条件选取满足要求的记录，假定内存处理时间忽略。这一步读取中间文件花费的时间需5×104秒(同写中间文件一样)。满足条件的元组假设仅50个，均可放在内存。3、作投影操作把第2步的结果在SN上作投影输出，得到最终结果。内存操作，忽略。Q1的查询代价≈2×(5×104)＋105≈105秒Q1=πSname(σS.Sno=SC.

8、Sno∧SC.Cno=‘C2’（S×SC))1、计算自然连接读取S和SC表的策略不变，总的读取块数仍为2100块花费105秒；但自然连接的结果比第一种情况大大减少，为10000个；平均每人选10门课，故写出这些元组时间104/10/20＝50秒。2、读取中间文件块，执行选择运算花费时间也为50秒。3、把连接结果投影输出Q2的查询代价≈105＋50＋50≈205秒Q2=πSname(σSC.Cno=‘