09级数据库系统实现复习提纲

《09级数据库系统实现复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据库管理系统主要包括存储管理器、查询处理器和事务管理器等几个子系统。DBMS从接受查询请求到返回结果的整个运行过程。存储管理器负责管理的数据包括目标数据、元数据、索引和统计信息等，这些数据保存在磁盘上。------------------------------------------------------------一次磁盘访问（I/O）的时间包括寻道时间、定位时间和读取时间，相互关系。访问时间从发出请求到数据开始传输之间的时间寻道时间（Seektime）磁盘臂定位时间，即磁盘臂移动到正确的磁道所需时间与移动距离成正比，平均寻道时间是最坏时间的1/3（4-10m

2、s）旋转等待时间（Rotationallatency）寻道结束后，等待被存取的扇区出现在读写头下面的时间平均旋转等待时间是磁盘旋转一周时间的1/2（2-5ms）数据传输率从磁盘获得数据或向磁盘存储数据的速率（4-8MB/秒）平均故障时间预期系统无故障连续运行的时间（30,000-800,000小时，即3.4-91年）RAID具有提高性能和提高可靠性两方面的作用------------------------------------------------------。重点掌握RAID4、RAID5和RAID6优缺点RAID4块级拆分，在一个独立的磁盘上为其他N个磁盘上

3、对应的块保留一个奇偶校验块读取一个块只访问一个磁盘每个存取操作的传输率低，但可以并行地执行多个读操作，从而产生较高的总的I/O率读取大量数据的操作有很高的传输率，因为所有磁盘可以并行地读RAID5将数据和奇偶校验位都分布到所有的N+1个磁盘上；对每个块，一个磁盘存储奇偶校验位，其余磁盘存储数据例如由5个磁盘组成的阵列，第n块的奇偶校验位存储在第(nmod5)+1上，其余4个磁盘的第n块存储了对应这个块的实际数据奇偶校验块不能和这个块对应的数据存储在同一个磁盘上所有磁盘都参与对读请求的服务，而RAID4中奇偶校验磁盘不参与读操作RAID5包容了RAID4，同时在相同成本

4、下，提供了更好的读写性能RAID6类似于RAID5，存储了额外的冗余信息不采用奇偶校验位的方法，使用类似Reed-Solomon码的编码对每4位数据存储2位冗余信息可以容忍两个磁盘发生故障-------------------------------------------------------顺序文件组织中，为什么在进行大量插删改后需要重组？如果需要存储在溢出块中的记录相当的少，这种方法会工作得很好。然而，搜索码顺序和物理顺序之间的一致性最终将完全丧失，在这种情况下，顺序处理将变得效率十分低下。此时，文件应该被重组，使得它再一次在物理上顺序存放。这种重组的代价是很

5、高的，并且必须在系统负载很低的时候执行。需要重组的频率依赖于新记录插入的频率。--------------------------------------------------------------搜索码是用于在文件中查找记录的属性或属性集。索引是支持对于所要求的数据进行快速定位的附加的数据结构。----------------------------------------------------------B+树的树结点的大小一般取决于块的大小。B+树的构造方法，插入、删除方法，效率。--------------------------------------

6、-----动态散列索引的实现原理思想原理动态散列技术允许散列函数动态改变，通过桶的合并和分解实现数据库的增大或缩小的需求，这样既继承了散列高效查找效率又保持了良好的空间压缩率。动态散列是逐步扩充散列值的位数来构造索引，它通过位比较来实现散列值的定位，这种比较方式计算机通过几个CPU机器指令即可实现，故它的效率很高。------------------------------------------------------------------在位图索引中，从位向量得到压缩编码位向量的方法以及从压缩编码位向量重新构造实际的位向量的方法查询优化是为关系代数表达式的计算选

7、择最有效的查询计划的过程。------------------------------------------------------外部排序的算法（初始归并段的数目、归并的趟数）趟数=「logM-1(br/M)「代价=2br+2br「logM-1(br/M)「－br=br(2「logM-1(br/M)「+1)------------------------------------------------------------各种连接算法及其代价分析（嵌套循环连接算法、块嵌套循环连接算法、归并连接算法、排序-归并连接算法）重点掌握散列连接方法对于基