数据库原理与应用幻灯片.ppt

数据库原理与应用数据库原理与应用6.*第1页，共55页，编辑于2022年，星期六第六章第六章 数据存储与查询优化数据存储与查询优化n物理存储n索引结构n查询处理过程n代数优化n物理优化第2页，共55页，编辑于2022年，星期六物理存储介质物理存储介质 n现代计算机体系结构中存在着多种存储介质，按照容量、访问速度等技术指标又可分为三级，组成一个典型的金字塔结构第3页，共55页，编辑于2022年，星期六挥发性和持久性介质挥发性和持久性介质n内存等一级存储介质只在系统运行时保存数据，一旦断电，数据全部丢失，称为挥发性介质n磁盘、磁带等二、三级存储介质则在断电之后仍能保持数据的有效性，称为持久性介质n数据库中的数据必须长时间的保存，即使系统关闭也不应该影响数据库中数据的有效性。因此，数据库中的数据必须存储在二、三级持久性介质中第4页，共55页，编辑于2022年，星期六磁盘磁盘n磁盘又称为硬盘，磁盘属于第二级存储，为持久性介质，是数据库的典型存储介质n一个磁盘中包含一个或多个盘片，这些盘片由金属或玻璃等刚性介质制成，表面涂有磁性介质用来记录数据n一个盘片有上下两个盘面，可以都用来记录数据，也可以只用一个面来记录数据n对每一个用来记录数据的盘面都有一个磁盘臂，其末端的读写头通过感应或改变盘片的局部磁性来读取或写入磁盘中的数据第5页，共55页，编辑于2022年，星期六磁盘（续）磁盘（续）n一个盘面被划分为多个间距很小的同心圆，这些同心圆被称为磁道(track)，不同盘面上有相同直径的磁道构成一个柱面(cylinder)n磁道又可以进一步分为多个扇区(sector)，现有的磁盘中一个扇区的典型容量是512字节n在工作状态时，磁盘轴带动盘片以恒定的速度旋转n磁盘与操作系统之间的交互是通过磁盘控制器完成的 第6页，共55页，编辑于2022年，星期六磁盘结构磁盘结构 第7页，共55页，编辑于2022年，星期六磁盘磁盘I/O的性能的性能 n读写磁盘数据时，磁盘内部需要进行以下的一系列动作移动磁盘臂，直到读写头位于数据所在磁道的正上方通过盘片旋转，使得读写头位于所读写数据的正上方读写头读取或写入数据n磁盘进行一次数据读写操作的时间由三部分组成第一部分是移动磁盘臂所用的时间，称为寻道时间，典型值为几毫秒第二部分是旋转盘片所用的时间，称为旋转时间，典型值为5-10毫秒第三部分是读写数据所用的时间，称为传输时间，典型值为几到几十MB每秒第8页，共55页，编辑于2022年，星期六磁盘读写的优化磁盘读写的优化 n磁盘臂调度的目的是通过规划多个数据读写请求的服务顺序来减少读写头的总移动距离，从而缩短读写磁盘的平均寻道时间。一种常用的磁盘臂调度算法是电梯算法n无论读写的数据量多大，由寻道时间和旋转时间带来的额外消耗都是一定的，因此读写少量数据时的效率就比读写大量数据时的效率低得多n基于计算机系统中的局部性原理，在磁盘与操作系统之间的数据交互过程中广泛使用数据预取技术，即在读取指定数据的同时也预先读取与其相邻的一定范围内的数据n典型的数据预取技术是数据的按块传输，块是一个逻辑单位，即一个磁盘从逻辑上被划分多个连续的块。目前典型的块大小在1KB-8KB之间第9页，共55页，编辑于2022年，星期六缓冲管理缓冲管理 n在系统内存中开辟一块专用空间，称为缓冲区，用来缓存经常需要访问数据nDBMS中用来对缓冲区进行管理的模块就称为缓冲区管理器当DBMS的其它模块需要读取数据时，它们向缓冲区管理器发出请求缓冲区管理器首先查看需要读取的数据是否在缓冲区中，如果在，则缓冲区管理器直接返回缓冲区中的数据，从而免除了进行磁盘I/O的代价如果在缓冲区中找不到指定数据时，则缓冲区管理器先从磁盘将数据读入缓冲区，然后返回给请求者 第10页，共55页，编辑于2022年，星期六缓冲区管理器缓冲区管理器n缓冲区中的内容被划分为多个块，块大小与磁盘块一致。为了对缓冲区进行有效管理，需要为每个缓冲块记录以下内容：空闲位脏位，在读入之后被修改过的缓冲块称为脏块pin值：pin值有两个功能，一是防止缓冲区管理器替换出正在处理的块，二是可以指定某些块常驻内存。缓冲区在选择被替换的块时，如果发现某缓冲块的pin值不为0，则不会将它替换出去。n提供强制写出脏的缓冲块的功能，这是为了保证数据的持久化存储。一种典型情况是系统关闭时需要强制写出所有脏的缓冲块，另外为了数据库恢复的需要也要强制写出脏的缓冲块第11页，共55页，编辑于2022年，星期六缓冲区替换策略缓冲区替换策略n缓冲区通常不足以容纳数据库中的所有数据，在需要读入新的数据时，可能出现缓冲区已满的情况，这时缓冲区管理器就要选择一个缓冲块替换出去n如何选择被替换的缓冲块将影响到数据库运行过程中进行磁盘I/O的频率，一个好的缓冲区替换策略应该能够减少磁盘I/O，提高数据库的性能nLRU（Least Recently Used）替换策略的基本思想是：系统未来对数据的访问情况可由系统过去的访问情况预期，即如果一个数据块在过去很少被访问，则将来也不太可能被访问，因此在缓冲区满时可考虑将其替换出去，反之，如果一个数据块在过去经常被访问，则将来也很有可能会被再次访问，因此不应将其替换出去第12页，共55页，编辑于2022年，星期六LRU替换策略替换策略n设有一个4块的缓冲区，初始为空，以后依次访问了块1,4,8,1,5,2,3,2,4，则根据LRU替换策略缓冲区的内容如下图所示，其间共发生了三次缓冲区替换第13页，共55页，编辑于2022年，星期六记录的存储记录的存储n数据库的数据通常按记录的形式加以组织，记录又由一到多个字段组成n有些类型，如整型、浮点型、定长字符串和日期类型等，无论具体的值是什么，占用的存储空间都是一样的，称为定长类型n另一些类型，如变长字符串和文本等，占用的存储空间由实际的值决定，称为变长类型n如果一条记录中只包含定长类型的字段，则该记录称为定长记录，否则称为变长记录第14页，共55页，编辑于2022年，星期六定长记录定长记录n定长记录中所有的字段都是定长的，只需将所有字段按既定的顺序连续存放，所有字段的地址相对于记录首地址的偏移都可以计算得到第15页，共55页，编辑于2022年，星期六变长记录变长记录n变长记录中每个字段相对于记录首地址的偏移是不固定的，因此除了记录所有字段的值之外，在记录中还需要包含一些附加信息，以使得在访问时可以计算出记录中各个字段的偏移量。n变长记录的内部格式通常有两种，一种是用特殊的分隔符将记录中的各字段隔开，这种方法有两个缺点不能保证分隔符永远不会在字段的值中出现即使只访问记录中的某个字段，也必须从记录首部开始搜索，否则无法确定该字段的位置 第16页，共55页，编辑于2022年，星期六变长记录（续）变长记录（续）n另一种方法是在记录首部存储各个字段的偏移量，这种方法解决了特殊字符分隔法的缺点，因此在实际的系统中更为常用第17页，共55页，编辑于2022年，星期六块格式块格式 n块是内外存交互的单位，记录必须存储在块中。一般来说，记录的长度小于块大小，因此在一个块中可以存放多条记录，每个块中可以存放多条记录，其中f称为该数据文件的块因子。如果记录跨块存储，在访问该记录时就会导致多次磁盘I/O操作。第18页，共55页，编辑于2022年，星期六数据文件的重整数据文件的重整n在DBMS运行过程中，每删除一条记录，就在数据文件中产生一块小的空闲空间，这些小的空闲空间难以被有效利用，随着DBMS的不断运行，就会使数据文件中产生越来越多的“碎片”，从而导致DBMS性能的降低。为解决这一问题，需要定期对数据文件进行重整n数据文件的重整可以在文件范围进行，能够完全消除数据文件中的“碎片”。但文件范围的重整会导致记录在文件范围内移动，使得整个数据文件在重整过程中无法使用，也必然会影响到建立在该数据文件上的索引结构n更为常用的重整方法是块内重整，块内重整按序处理数据文件中的每个块，将该块内的记录集中存储到块尾第19页，共55页，编辑于2022年，星期六超长记录和记录的跨块存储超长记录和记录的跨块存储 n为了利用空间，可以考虑允许记录跨块存储，即当块中存不下一条完整的记录时，可以把记录的前一部分存在该块中，而把余下的部分存在后续的块中n除了为了防止空间浪费而进行跨块存储外，当记录的长度超过块的大小时，也必须进行跨块存储 第20页，共55页，编辑于2022年，星期六文件组织方式文件组织方式n堆文件：记录间没有次序关系，新加入的记录可以存储在文件中任何有空间的地方。n顺序文件：记录按某些字段的值进行排序。n哈希文件：对记录的某些字段进行哈希运算，运算的结果决定记录存储在文件中的哪一块。n聚集文件：将同种类或相关的来自于不同关系的记录存放在同一块中，以减少同时获取这些记录的I/O操作第21页，共55页，编辑于2022年，星期六顺序文件顺序文件第22页，共55页，编辑于2022年，星期六顺序文件的特点顺序文件的特点n优点按搜索键的值顺序读取记录的效率很高如果选择条件基于搜索键的值，就可以在磁盘上进行二分查找n但顺序文件在处理记录的插入上却有较大的困难，当插入一条记录时，首先要根据待插入记录的搜索键值找到记录的插入点，然后要将插入点之后的所有记录向后移动，以便为待插入记录留出空间。这样平均插入一条记录就要移动文件中一半的记录。n为改善顺序文件中记录插入操作的性能，可以在每个块中都为新记录预留出一定的存储空间 第23页，共55页，编辑于2022年，星期六聚集文件聚集文件n但对于大型或超大型的数据库，性能是最重要的因素。为提高数据库的性能，大型数据库中通常采用更复杂的文件组织方式，允许多个表中的相关记录存储在一个数据文件中，这种文件组织方式就称为聚集文件n但采用聚集文件也会使某些查询的执行效率降低，因此，是否采用聚集文件及如何进行聚集应该由在数据库运行过程中各类查询的频率决定 第24页，共55页，编辑于2022年，星期六索引索引n从理论上来说，只要记录被正确地存储于数据文件中，DBMS就可以正常工作，但实际上，单纯依赖数据文件处理查询有时候效率是非常低的 nDBMS中索引的工作方式与书后面关键词索引的工作方式是相似的nDBMS索引中与关键词相对应的概念称为索引键(或索引字段)，由一个或多个字段组成，DBMS可以借助于索引找到包含指定键值的记录的位置 nB+树索引和哈希索引第25页，共55页，编辑于2022年，星期六B+树的结构树的结构nB+树属于多级多叉平衡树，从根到每个叶节点的路径长度相等nB+树中每个节点大小相同，且拥有相似的内部结构n对于n阶的B+树，每个B+树节点最多可以包含n-1个排列有序的索引键值和n个指针。对一个节点中的键值编号为K1,K2,Kn-1，节点的键值递增排列，即K1 K2 Kn-1。指针编号为P1,P2,Pn，一个指针、索引键值对又称为一个入口项第26页，共55页，编辑于2022年，星期六B+树的结构（续）树的结构（续）nB+树节点的大小与缓冲块大小相同，因此，具有不同索引键的B+树的阶数是不同的，可由以下公式计算得到阶数=(缓冲块大小+索引键大小)/(索引键大小+指针大小)n在B+树中存在两种节点：叶节点和非叶节点，不同类型的节点具有不同的性质第27页，共55页，编辑于2022年，星期六叶节点叶节点n对于i=1,2,n-1，指针Pi指向包含键值Ki的记录的位置。如果索引键是主键，则每个索引键值只对应一条记录，指针Pi指向的是含有索引键Ki的记录。如是索引键不是主键，则可能有多条记录具有相同的索引键值，指针Pi指向的是一个包含所有具有索引键值Ki记录位置的指针桶。叶节点的最后一个指针Pn指向该它的右兄弟节点，如果该节点已经是最右的叶节点，则Pn为NULLnB+树的每个叶节点中最少需要包含 个索引键值n所有叶节点中的索引键值也递增排列，且不同叶节点中的索引键值间不重合，即若Li和Lj为叶节点，且i nr/fr，其中nr为预期的索引键值数，fr为每个块中所能存储的索引键值数。但在实际情况下通常无法达到完全平均分配，因此，在计算桶的数量时应适量放宽20%到30%第41页，共55页，编辑于2022年，星期六动态哈希动态哈希n一般说来，数据库中的数据总是随着数据库运行时间的增长而增长，这样在使用静态哈希时选择桶的数量就成了一个大问题。如果桶的数量过小，则随着数据库的运行，索引中将会产生大量溢出块，从而导致性能降低，反之，如果一开始就将桶的数量设得很大，则在很长一段时间内又会造成空间的浪费 n动态哈希技术弥补了静态哈希的上述缺陷，动态哈希技术允许文件中的桶数动态增长，同时又不需要重整。有两种常用的动态哈希：可扩展哈希和线性哈希 第42页，共55页，编辑于2022年，星期六查询处理查询处理 第43页，共55页，编辑于2022年，星期六查询优化的两种主要途径查询优化的两种主要途径 n代数优化：根据等价变换规则将初始查询树转换成另一种形式，代数优化的输入和输出都是关系代数表达式，但输出比输入更有利于于执行。代数优化一般是基于规则的优化，在代数优化过程中一般较少使用统计信息，不进行代价估计。由代数优化产生的查询树又称为最终查询树。n物理优化：为代数优化产生的最终查询树生成不同的物理执行计划，并利用统计信息对计划的执行代价进行估计，最后选择其中代价最小的计划作为输出，因此，物理优化是基于代价的优化第44页，共55页，编辑于2022年，星期六代数优化代数优化 Pnametitle=Database System ConceptsbookauthorPnametitle=Database System Conceptsbookauthor第45页，共55页，编辑于2022年，星期六代数优化的等价变换代数优化的等价变换s customer.customer_id=interest_in.customer_id interest_in.category_id=category.category_id customer.name=张三P tagcustomerinterest_incategory第46页，共55页，编辑于2022年，星期六代数优化的等价变换（续）代数优化的等价变换（续）s customer.customer_id=interest_in.customer_idP tagcustomerinterest_incategorys interest_in.category_id=category.category_ids customer.name=张三s interest_in.category_id=category.category_idP tagcustomerinterest_incategorys customer.customer_id=interest_in.customer_ids customer.name=张三第47页，共55页，编辑于2022年，星期六物理优化物理优化 n物理优化在代数优化之后进行，其过程可以概括为“枚举策略估算代价生成计划”三步 n物理优化是基于代价进行的。物理优化的思想是为每个操作考虑多种可行的执行策略，并对每种执行策略的代价进行估计，然后选择其中代价最小的作为最终的执行策略 n代价估算是物理优化的基础，在DBMS中，执行代价通常是用读写磁盘块的次数来衡量的n为了对各种操作的代价进行估算，需要在数据库记录一些附加的数据，这些数据称为统计信息，通常记录在系统的数据字典中第48页，共55页，编辑于2022年，星期六辅助信息辅助信息 nnr：关系r中的元组数。nbr：关系r的数据文件中包含的数据块数。nlr：关系r中记录的平均长度。nfr：关系r的块因子，即一个块中平均有多少条记录，fr nr/br。nV(A,r)：关系r中属性A的不同值个数。如果A是主键，则V(A,r)=nr。第49页，共55页，编辑于2022年，星期六选择操作的执行策略选择操作的执行策略 n顺序扫描：对被选择关系的数据文件进行线性扫描，判断扫描经过的每一条记录是否符合选择条件。n使用B+树索引：当在选择条件涉及的列上建有B+树索引时，可以考虑使用索引来进行选择。如果是主键上的等值选择，则代价为h+1，其中h为B+树的高；否则，代价就会与选择操作的选择率有关，设选择率为f，当f较小时，代价大约是h+bleaf*f+nr*f，当f较大时，代价大约是h+bleaf*f+br*f，其中bleaf是B+树索引中叶节点数；对于不等选择，由于选择率接近100%，一般不用索引执行。第50页，共55页，编辑于2022年，星期六联接操作的执行策略联接操作的执行策略 n嵌套循环联接 n块嵌套循环联接 n索引嵌套循环联接 n归并联接 第51页，共55页，编辑于2022年，星期六嵌套循环联接嵌套循环联接n for(关系R中的每个元组tr)n for(关系S中的每个元组 ts)n if(tr与ts符合选择条件)将trts加入到联接结果中;n n 第52页，共55页，编辑于2022年，星期六块嵌套循环联接块嵌套循环联接nfor(关系R中的每个块BR)n for(关系S中的每个块BS)n for(BR中每个元组tr)n for(BS中每个元组ts)n if(tr与ts符合选择条件)将trts加入到联接结果中;n n n n 第53页，共55页，编辑于2022年，星期六索引嵌套循环联接索引嵌套循环联接n for(关系R中的每个元组tr)n 利用索引找到S中与tr匹配的元组ts;n 将trts加入到联接结果中;n 第54页，共55页，编辑于2022年，星期六归并联接归并联接n归并联接在进行联接之前首先对参与联接的关系按联接条件中的属性进行按序，因此，在联接时只需对参与联接的关系进行一遍扫描，代价仅为bR+bS。归并联接的输出也是按联接条件中的属性按好序的。n归并联接的限制是只能用于计算自然联接和等值联接(联接条件形如R.A=S.B的联接)。第55页，共55页，编辑于2022年，星期六