物理存储结构PPT课件.

第八章 物理存储结构生物医学软件工程本章概要v数据库存储设备v文件与文件记录v无序文件v有序文件vHASH文件v索引文件vB_树和B_+树索引结构8.1 数据库存储设备v磁盘存储器v磁盘容量的计算公式: 硬盘容量=面数(道数/面)(扇数/道) (字节数/扇).v使用磁头存取磁盘数据的时间称为存取时间，由三部分组成： 存取时间=寻道时间+旋转延迟+数据传输 前两项机械运动的时间为主要部分v磁盘缓冲处理技术v磁盘驱动器和CPU可并行工作，在主存设置多个缓冲区，当磁盘驱动器与一个缓冲区交换数据时，CPU同时处理另一个缓冲区中的数据。读数据a入第i块读数据b入块i+1读数据a入块i+2读数据b入块i+3在第i块处理a在块i+1处理b在块i+2处理a在块i+3处理b磁盘驱动器工作CPU工作时间缓冲区1缓冲区2主存磁盘CPUv磁盘的调度策略v磁盘读写效率主要取决于寻道和旋转操作，磁盘的调度策略的目的是减少机械运动。 v以下是优化寻道时间的几个策略： 先来先服务 近者优先 全程移动扫描 移动扫描 分组扫描 间歇式扫描v磁盘容错技术v磁盘可能会出现故障，当发生故障时，如果数据没有备份到另一个介质中，数据将会被永久的丢失。这就需要磁盘冗余技术来解决。v以下是常用的RAID策略： 简单RAID策略 RAID4策略 RAID5策略 RAID6策略本章概要v数据库存储设备v文件与文件记录v无序文件v有序文件vHASH文件v索引文件vB_树和B_+树索引结构8.2 文件与文件记录v记录：记录是数据的一种存储形式。它由一组相关的数据项排列而成。每个数据项称为记录的一个域。每个域都具有名字和数据类型。v记录型：一组域名字及其对应的数据类型构成了记录型。v文件：文件是具有相同记录型的记录序列。v定长记录文件：记录长度一致的文件。v变长记录文件：记录长度不一致的文件。v记录存储方式 跨块存储记录方式 非跨块存储记录方式允许一个记录储存在不同磁盘块。若记录长度大于磁盘块容量，则存储于由磁盘块组成的链表。不允许一个记录跨块储存。连续存储ii+1i+2ijk链接存储索引存储ijk删除操作三种方法：(1)逐个磁盘块读进内存缓冲区搜索，找到符合条件的记录即将其删除，然后把带空泡的块写回磁盘。(2)在前法中对记录增设标记位，对删除记录作出标识并作周期处理。(3)在定长记录的情况下，把文末记录移动到被删除记录的位置。插入：在文件头获得末块地址，将末块读入内存追加新记录，然后将文件块写回到磁盘查询：采用顺序搜索法，即逐个文件块读入内存，逐条记录检验条件。若文件占B个磁盘块，满足条件的记录只有一条，则平均搜索(B+1)/2个块修改：经查找，把含目标记录的文件块读入内存，修改记录后，把文件块写回磁盘。8.3 无序文件删除操作：同样需要移动记录。但若使用删除标记和周期整理磁盘空间的方法，则可提高效率。修改操作：若修改非排序域，对记录定位后，连块读入内存，修改后把块写回磁盘；若修改排序域，可采用先删除后插入的方法。插入操作：需要将插入位置之后的记录依次后移，腾出空间存储新记录。记录移动量平均是总记录数的一半。查找操作：若查询条件不定义在排序域，则只能象无序文件那样采用顺序搜索法；若查询条件定义在有序文件的排序域，则可用二分法寻找记录，查询的时间复杂性O(log2N)，其中N是文件的记录数。8.4 有序文件8.5 HASH文件vHASH文件是一种支持快速存取的文件存储方法。 需要指定文件的一个域为hash域，域上的每个值都对应一个磁盘块的地址。v介绍三种HASH方法： 简单HASH方法 动态HASH方法 可扩展的HASH方法索引的创建vCreate index on (列名, );vAlter table add index on(列名,.);v在创建表的时候直接指定索引v普通索引v唯一索引：unique，与普通索引类似，但索引列的值必须唯一，且可以有空值；如果是组合索引，则列值的组合必须唯一。v主键索引：是一种特殊的唯一索引，不允许有空置，一般是在建表的时候，同时创建主键索引。v组合索引：是与单列索引对比而言的。v索引是按对象特征借助索引文件获取存储指针的快速查询技术。用这种方法查询的基本步骤是： 根据查询条件，在数据文件选定一个或一组域(称之为索引域)； 建立索引文件，该文件包括两个域：索引域和块指针，索引文件的记录称为索引项，全体索引项按索引域排序； 用户按索引域值借助索引文件，获取块指针并读取记录。v因为索引文件是有序文件，能应用两分查找法等算法，故能提高查找速度。数据文件越大，索引查找的效益就越明显。v索引项数与数据记录数之比可以是1:n，也可以是1:1 ；v数据文件可以按索引域排序，也可以是无序文件。8.6 索引文件何时创建索引？v一般，在where中出现的列需要建立索引v在mysql中，只对, , =, between , in, 及某些时候的like才使用索引。索引有那些不足之处？v提高了查询速度，降低更新表的速度。更新表时，不仅有保存数据文件，还要保存索引文件v建立索引会生成索引文件，占用磁盘空间。一般这种问题不严重，但如果在一个大表创建了多种组合索引，索引文件会膨胀很快。使用索引的注意事项：v索引中不会包含有null值v使用短索引vLike语句操作v不要在列上进行运算v不使用not in 和 操作vMysql 中不区分聚集索引和非聚集索引主索引文件：有序文件索引域是键聚集索引：有序文件索引域是一个非键域辅助索引：索引域建立在数据文件非排序域多级索引本章概要v数据库存储设备v文件与文件记录v无序文件v有序文件vHASH文件v索引文件vB_树和B_+树索引结构8.7 B_树和B_+树索引结构vB_树和B+_树是树型数据结构的特例，是重要的动态文件索引结构，用于数据库的多级索引。 B_树最早出现于1972年。v由于这种结构具有高效、易变、平衡和独立于硬件结构的优点，因而在数据库系统中得到广泛的应用，成为最重要的动态文件索引结构。 B_+树是B_树的改进。v本节介绍： 索引树、B_树、B_+树一、索引树v索引树是一种特殊的树型数据结构。上节介绍的多级索引结构可视作索引树。P1K1Ki-1PiKiKq-1PqXXXXK1Ki-1XKiKq-1Xv定义：秩为P的索引树是一个满足下述条件的树形数据结构:v每个结点存储如下的信息: (p1,k1, p2,k2,pq-1,kq-1 ,pq), qP.每个pi是一个指向子结点的指针或空指针，ki是来自有序集合的索引值,k1k2 kq-1vpi 所指子树中的所有值x满足：当1iq时有ki-1xki；当i=1时xkq-1.369178512v索引树满足动态文件要求，但有如下缺点： 树不平衡，叶结点层次深度不统一； 删除记录的操作使某些结点接近于空，使空间利用率低。v后边介绍的B_树概念通过对树增加约束，克服了这两个缺点。二、B_树索引结构v为克服索引树的缺点，对它增加约束，于是得到B_树的概念。vB_树定义：以键为索引域、秩为D的B_树是树形数据结构，且满足： 每结点对应一个索引块，存储树指针Ti和索引项的信息： (T1,T2,Tq-1,Tq),k1k2kq-1 内结点树指针Ti指向的子树中,每个索引值x满足：当1iq-1有ki-1xki ; 当i=1有xkq-1 每个非根结点的索引项数是D/2D，若根结点不是唯一结点，其索引项数是1D； 每个结点的树指针数比索引项数多1；TP1(K1,DP1)(Ki-1,DPi-1)TPi(Ki,DPi)(Kq-1,DPq-1)PqXXXXK1Ki-1XKiKq-1XB_树查找算法按索引域值k，在B_树检索数据，返回找到的记录。P:=根结点的磁盘块地址；WHILE P不是空指针 DO 读P指向的结点 (T1,T2,Tq-1,Tq) 到主存； IF 存在一个i使得Ki=k THEN 读由Di指向的磁盘块到主存缓冲区buff ； 在buff中找出索引值为k的记录； 返回找到的记录 ； ELSE IF kKq-1 THEN P:=Tq ENDIF ； IF 存在一个i使得Ki-1kKi THEN P:=Ti ENDIF ； ENDIF;ENDWHILE;返回记录不存在.B_树插入记录算法 设索引域是键，先把r插入到数据文件的磁盘块Dt，然后按索引值k在B树找到(类似查找算法)插入的叶结点。若该结点未满，则把索引项插入其中，否则对该点实行分裂取中操作： 把旧结点的索引项集等分两半， 按序分配在两个新结点中， 并把处于中间位置的索引项移升到父结点。 若父结点也满，则又要对其作分裂处理， 这个过程可能持续到根结点，此时树的高度加1。B_树删除记录算法 先按索引值k在B树找到结点及索引项， 按Dt找到数据块并把记录r删除，然后更新树： 若在叶点，则仅在点内删除， 否则把树内右紧邻的索引项移来覆盖。 若改动过的叶结点索引项数小于秩D，则须与父结点某些索 引项合并到兄弟结点，原则上先考虑左兄弟结点。若合并过 程延续下去波及到根结点，则树高减1.下边是在秩4的B_树插入记录的过程例子(设索引项是键)：考虑B_树的一个状态(符号A、B、M表示10、11、22)现要在7号结点插入索引域值E。直接插入使7号结点成为BCDEF，索引项数超限。于是作分裂取中处理：把中间项D移升到(父)3号节点，左半部分BC留在原结点，右半部分EF存入新结点即71号结点：.A.4.7.G.K.1.2.3.5.6.8.9.B.C.D.F.H.I.J.L.M.123456789.A.4.7.D.G.K.1.2.3.5.6.8.9.B.C.H.I.J.L.M.E.F.77112345689因秩是4，故非根节点的索引项数是24下边是在秩4的B_树删除记录的过程例子(设索引域是键)：考虑B_树的一个状态(符号A、B、M表示10、11、22).A.4.7.D.G.K.1.2.3.5.6.8.9.B.C.H.I.J.L.M.E.F.77112345689.A. .D.G.K.BC EF HIJ LM .4.123 5679.D.4.A.G.K.1.2.3.5.6.7.9.B.C.H.I.J.L.M.E.F.7711234589现要在6号结点删除索引域值8。删除后结点成为9，索引项数2。于是和父点的索引值7合并到左兄弟点，使2号点索引项数2。于是把2号点连同父点的索引值A合并到右兄弟，再分裂取中便完成删除因秩是4，故非根节点的索引项数是24.D.4.A.G.K.1.2.3.5.6.7.9.B.C.H.I.J.L.M.E.F.7711234589.D.4.A.G.J.1.2.3.5.6.7.9.B.C.H.I.L.M.E.F.7711234589现要在3号点删索引域值K。删后，右紧邻的L补上，使9号点成为M，索引项数2。于是把9号点连同父点的索引值L合并到左兄弟点，得HIJLM.索引项数超限，对其作分裂取中处理便完成删除。D 4A123 5679 BC GLEF HIJ M再考虑一个秩4的B_树删除记录的过程例子(设索引域是键)：给出B_树的一个状态(符号A、B、M表示10、11、22)因秩是4，故非根节点的索引项数是24创建索引v创建索引，例如 CREATE INDEX ON tablename (列的列表); v修改表，例如ALTER TABLE tablename ADD INDEX 索引的名字 (列的列表);v创建表的时候指定索引，例如CREATE TABLE tablename ( ., INDEX 索引的名字 (列的列表) );