教学第6章-数据库存储技术课件

6.1数据库的物理存储介质6.2文件组织6.3文件中记录的组织6.4索引技术与散列技术第6章数据库存储技术6.1数据库的物理存储介质第6章数据库存储技术6.1.1数据库的物理存储介质6.1.2磁盘存储器及其结构6.1数据库的物理存储介质6.1.1数据库的物理存储介质6.1数据库的物理存储介如图6.1所示，计算机系统中的数据存储是按照层次组织的。顶层是主存储器，它是由高速缓存储器和主存组合，提供数据的快速访问；接下来是第二级存储器，它是由磁盘等较慢的设备组成；第三级存储器是最慢的存储设备，如光盘和磁带等。与同样数量的磁盘相比，主存的价格昂贵得多，而磁带却比磁盘更便宜。因为数据库需要存储大量的数据，所以像磁盘和磁带这样较慢的存储设备在数据库系统中具有重要地位。主要的存储介质有：6.1.1数据库的物理存储介质如图6.1所示，计算机系统中的数据存储是按照层次组织6.1.1数据库的物理存储介质CPU高速缓存主存磁带磁盘数据请求满足请求的数据主存储器第二级存储器第三级存储器图6.1存储层次6.1.1数据库的物理存储介质CPU高速缓存主存磁带磁盘1.高速缓存高速缓冲存储器是最快最昂贵的存储介质。高速缓冲存储器一般很小，它的使用由操作系统来管理。在数据库系统中，我们将不考虑高速缓冲存储器的存储管理。2.主存主存又称内存或主存储器，用于存放可被处理的数据，它是计算机机器指令执行操作的地方。由于其存储量小（一般以MB为单位）、成本高、存储时间短，而且发生电源故障或者系统崩溃时，里面的内容一般会丢失，因此它在数据库中仅作为数据存储的辅助实体，如作为工作区（workarea）(数据加工区)、缓冲区（bufferarea）(磁盘与主存的交换区)等。6.1.1数据库的物理存储介质1.高速缓存6.1.1数据库的物理存储介质3.快闪存储器也叫电可擦可编程只读存储器（EEPROM）。快闪存储器不同于主存储器的地方是在电源故障发生时数据可被保存下来。从快闪存储器读数据的时间小于100纳秒，大致等于从主存储器中读数据的时间。然而，向快闪存储器写数据是非常复杂的——数据写入一次，大约需要4~10微秒，而且数据不能被直接覆盖。要想覆盖已经被写过的快闪存储器，必须一次性擦除整个快闪存储器，然后它才可以再被写入一次。快闪存储器的另一个缺点是它只支持有限的擦除次数，其范围从10000~1百万。在低成本计算机系统中，例如在嵌入至其他设备的计算机系统中，快闪存储器作为磁盘的替代物来存储少量数据（5MB~10MB）已经非常流行。6.1.1数据库的物理存储介质3.快闪存储器6.1.1数据库的物理存储介质4.磁盘磁盘存储器又称二级存储器或次级存储器。由于它存储量大（一般以GB为单位），能长期保存又有一定的存取速度且价格合理，因此早已成为数据库真正存放数据的物理实体。通常整个数据库都存储在磁盘上。为了能够访问到数据，必须将数据从磁盘移到主存储器。完成操作后，被修改的数据必须写回磁盘。磁盘存储器为直接存取存储器，因为在磁盘上可以按任意顺序读取数据（与顺序存取的存储器不同）。在发生电源故障或者系统崩溃时，磁盘存储器不会丢失数据。6.1.1数据库的物理存储介质4.磁盘6.1.1数据库的物理存储介质5.光盘光盘存储器最流行的形式是只读光盘（CD-ROM）。数据通过光学方法存储在光盘上，并且可以被激光器读取。用于CD-ROM存储器的光盘是不可写的，但是可以提供预先记录的数据，并且可以装入驱动器或从驱动器中移走。另一种光盘存储器是“一次写，多次读”（WORM）光盘，它允许写入数据一次，但是不允许擦除和重写这些数据。这种介质用于数据的归档存储。此外还有磁光结合的存储设备，可使用光学方法读取以磁方法编码的数据，并且允许对旧数据进行覆盖。6.1.1数据库的物理存储介质5.光盘6.1.1数据库的物理存储介质6.磁带磁带具有较大的容量（从GB到TB），价格便宜并可以脱机存放。因为磁带必须从头顺序存取，是一种顺序存取存储器，因此数据存取也比磁盘慢的多。磁带一般用于存储磁盘或主存中的拷贝数据，它是一种辅助存储设备，也称为三级存储器。6.1.1数据库的物理存储介质6.磁带6.1.1数据库的物理存储介质6.1.2磁盘存储器及其结构由于磁盘是数据库数据存储的主要物理存储体，因此本节主要介绍磁盘及其结构。磁盘为现代计算机系统提供了大容量的辅助存储，其存储容量极大，大约在几个GB到几十个GB，甚至几百个GB之间。一个典型的大型商业数据库需要数百个磁盘。磁盘结构如图所示。6.1.2磁盘存储器及其结构由于磁盘是数据库数据6.1.2磁盘存储器及其结构6.1.2磁盘存储器及其结构6.1.2磁盘存储器及其结构磁盘存储器由磁盘盘片与磁盘驱动器两部分组成。1.磁盘盘片磁盘盘片是一种扁平的圆盘。它的两个表面都覆盖着磁性物质，信息就记录在表面上。盘片由硬金属或玻璃制成，被磁性物质覆盖（通常是两面）。盘片的表面被逻辑地划分为磁道(track)，磁道又被划分为扇区（sector），它又称磁盘块（block），磁盘块是从磁盘读出和写入信息的最小单位。根据磁盘的不同类型，一个扇区的大小可从32~4096字节不等，但通常是512字节。每个磁道有4~32个扇区，每个盘片表面有20~1500个磁道。一个磁盘存储器往往由若干个盘片（6~11片）组成一个盘片组，固定在一个主轴上，以每个盘片磁道为注视点可以构成一个无形的同心圆柱体，从内到外层层相套。每个圆柱体从上到下有若干个磁道围绕其上。6.1.2磁盘存储器及其结构磁盘存储器由磁盘盘片与磁盘驱6.1.2磁盘存储器及其结构2.磁盘驱动器磁盘驱动器由活动臂、读写头等组成。每个盘面有两个臂，分别对应上、下两面，每个臂的尽头是一个读/写头（或称磁头），用它可以读取（或写入）盘片中的数据。一个由n个磁盘片所组成的盘片组对应有2n个活动臂，它们组合在一起构成臂组合件，这种组合件可以自由伸缩活动，它以磁道为单位向前推进或向后退缩，用它可以对磁道定位，由于它是组合方式以全体活动臂为单位作进退，因此它的推进或后退实际上是对圆柱体定位。6.1.2磁盘存储器及其结构2.磁盘驱动器6.1.2磁盘存储器及其结构3.磁盘存储器一个磁盘存储器是由盘片组以及磁盘驱动器组成，其中盘片组以轴为核心作不间断的旋转，速度以60、90、120或150转不等，而活动臂组合件则以圆柱体为单位做前进或后退操作。这样，一个磁盘存储器上的任何一个磁盘块都可由下面三个部分定位。（1）圆柱体号：确定圆柱体（由活动臂移动定位）。（2）读/写头号：确定圆柱体中磁道（由选择组合件中活动臂定位）。（3）磁盘块号：确定磁道中的盘块号（由盘片组旋转定位）。6.1.2磁盘存储器及其结构3.磁盘存储器6.1.2磁盘存储器及其结构4.磁盘存储器的I/O操作为进行有效管理，系统对磁盘作统一编址，编址按圆柱体号、磁道号及盘块号编码，编码规则如下：（1）圆柱体号：设有n个圆柱体，则编号自柱面的外层至内层，从0~n-1。（2）磁道号：设一个圆柱体有m个磁道，则磁道号统一编码从上到下顺序编号，从0~nm-1个。（3）磁盘块号：设一个磁道有r个盘块，则磁盘块号也是统一编码，从0~nmr-1个。6.1.2磁盘存储器及其结构4.磁盘存储器的I/O操作6.1.2磁盘存储器及其结构磁盘在投入使用前都要进行格式化，目的是在各盘块的头部加注该块地址，包括该块所在的圆柱体号，读/写头号，盘块号以及某些状态标志。在具体操作时用户给出磁盘地址，此时活动臂组合件作机械运动并定位于指定圆柱体，同时系统选择指定的读/写头以确定磁道，最终读/写头跟踪旋转的磁道，并读出旋转时每磁盘块的地址。当用户给出的地址与磁盘地址一致时则表示地址已找到，此时系统就将该地址中的数据读入内存中的磁盘缓冲区（或从磁盘缓冲区将数据写入指定磁盘地址），这就完成了一次磁盘读/写操作或称I/O操作。6.1.2磁盘存储器及其结构磁盘在投入使用前都要6.2.1文件的定长记录6.2.2文件的变长记录6.2文件组织6.2.1文件的定长记录6.2文件组织一般在文件中的记录都是有固定长度的，这种长度一般都由文件记录型确定。例如某个关系模式“物资编码表”：Wzbmb（Wzbm，Wzmc，Xhgg，Jldw，Price），它可以设计成一个定长文件。文件中的各个记录定义如下：

TYPEWzbmb-TYPE=RECORDWzbm：VARCHAR2（6）；Wzmc：VARCHAR2（16）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8，2）；END

如果假设每个字符占1个字节，那么每个Wzbmb记录定长为52个字节。6.2.1文件的定长记录一般在文件中的记录都是有固定长度的，这种长度一般都由文件中的记录有时其长度是可以变化的，变长记录出现在数据库系统中的下述情况中：（1）多种记录型在一个文件中存储。（2）记录型允许一个或多个字段是变长的。（3）记录型允许可重复的字段。6.2.2文件的变长记录文件中的记录有时其长度是可以变化的，变长记录出现在数

6.2.2文件的变长记录例如，把6.2.1中的关系模式作如下文件结构定义：TYPEWzbmb-LIST=RECORDWzmc：VARCHAR2（16）；Wzbm-INFO：ARRAY[1，]OFRECORDWzbm：VARCHAR2（6）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8,2）；ENDEND

6.2.2文件的变长记录例如，把6.2.1中的关系模式作如变长记录的表示有两种形式：（1）字节流实现变长记录的一个简单方法是在每个记录的末尾附加一个特殊的记录终止符号，这样可以把每个记录作为一个连续的字节流来存储。另一种字节流表示方法是在每个记录的开始处存储记录的长度，而不再使用记录终止符号。（2）定长的表示方法另一种在文件系统中有效实现变长记录的方法是使用一个或多个定长记录来代表一个变长记录。6.2.2文件的变长记录变长记录的表示有两种形式：6.2.2文件的变长记录使用定长记录实现变长记录文件的技术有两种：①保留空间。如果设置一个永远不会被超过的最大记录长度，我们就可以使用长度为这个最大记录长度的定长记录。如对那些比最大空间短的记录，则未使用的空间用特殊的空值或记录终结符号来填充。②指针。变长记录用一系列通过指针链接起来的定长记录来表示。在该形式中，每个定长记录后加一个指针字段，该字段指出是否有指针以及如果有指针则给出下一个定长记录的地址，这种方法即是用若干个定长记录来拼成一个变长记录。6.2.2文件的变长记录使用定长记录实现变长记录文件的技术有两种：6.2.2文件的一般的记录组织有如下几种方式:1.堆文件组织（heapfile）在这种组织方式中，一条记录可以放在文件中的任何地方，只要那个地方有空间存放这条记录。记录是没有顺序的。通常一个关系是一个单独的文件。2.顺序文件组织（sequentialfile）顺序文件是为了高效处理按搜索码排序的记录而设计的。为了快速地按搜索码获取记录，在这种文件中每个记录增加一个指针字段，通过指针把记录链接起来。每个记录的指针指向在搜索码顺序上的下一个记录。此外，为了减少顺序文件处理中的块访问的次数，我们在物理上按搜索码顺序或尽可能的按搜索码顺序存储记录。6.3文件中记录的组织一般的记录组织有如下几种方式:6.3文件中记录的组3.散列文件组织（hashingfile）在这种组织方式中，对各个记录的同一属性计算一个散列函数。散列函数的结果作为记录的存储地址（即块号）。4.聚集文件组织（clusteringfile）很多关系数据库系统将各个关系存储在一个个独立的文件中，不同关系中有联系的数据是通过关系间的联接操作得到的，但是当数据的数量比较大时，这种方法速度会很慢。而在聚集文件组织方式中，一个文件可以存储多个关系的记录，不同关系中有联系的记录存储在一起可以提高查找速度。6.3文件中记录的组织3.散列文件组织（hashingfile）6.3例如设物资管理系统中关系R1和R3中有下面的查询：SELECTR1.Dwbm，R1.Dwmc，R3.Wzbm，R3.Qls，R3.SfsFROMR1，R3WHERER1.Dwbm=R3.Dwbm当关系R1和R3数量很大时，要做联接的查询速度是比较慢的。但是如果把R1和R3放在一个聚集文件中，那么在读单位信息时能够同时把单位领料编码以及领料数量一起读入。图6.4为一个聚集文件的例子。6.3文件中记录的组织例如设物资管理系统中关系R1和R3中有下面的查询：6.3文6.3文件中记录的组织DwbmDwmcDwbmWzbmRqQlsSfs0101一分厂一车间01010201012002/12/01550102一分厂二车间01010104012002/12/011080221二分厂生产科01010101012002/12/02202001010201022002/12/025501010201012002/12/02101001020103012002/12/028801020201012002/12/023302210202012002/12/022015（a）关系R1（b）关系R36.3文件中记录的组织DwbmDwmcDwbmWzbmRq6.3文件中记录的组织0101一分厂一车间010101010101010101010201010104010101010201020201012002/12/012002/12/012002/12/022002/12/022002/12/025102051058205100102一分厂二车间010201020103010201012002/12/022002/12/0283830221二分厂生产科02210202012002/12/022015（c）聚集文件图6.4聚集文件示例6.3文件中记录的组织0101一分厂一车间010102016.4.1文件的定长记录6.4.2文件的变长记录6.4.3散列技术6.4索引技术与散列技术6.4.1文件的定长记录6.4索引技术与散列技术在索引技术中对文件（一般用顺序文件）的查找采用类似书刊中目录的方法，即对文件中记录的指定项（称索引项）的项值给出其记录的地址，它们称索引，索引一般也用文件表示，其结构如图6.4所示:6.4.1索引技术索引项值对应记录地址

因此，索引技术中一个索引文件一般由主文件与索引两部分组成，其中主文件存放数据，而索引则存放数据地址。图6.5索引结构在索引技术中对文件（一般用顺序文件）的查找采用类似书主索引主索引是索引中最常用的一种，它一般可以分为以下三类：（1）稠密索引所谓稠密索引（denseindex）是指对主文件索引项的每个“项值”建立一个索引项值，即索引记录包括索引项中的所有项值以及指向该值的记录链表中第一个记录的指针，图6.5给出了稠密索引的一个例子。6.4.1索引技术主索引主索引是索引中最常用的一种，它一般可以分为以下三类：（2）稀疏索引稀疏索引（sparseindex）是指只对主文件索引项的部分项值建立索引记录，这些部分项值的选择具有一定的稀疏特征，即每隔一定距离选择一个。每个索引记录也包括一个项值和指向该项值的第一个数据记录的指针。（3）多级索引当索引本身数量很大时，还有一种办法是采用多级索引，即对索引本身采用索引。图6.7给出了二级索引的例子。6.4.1索引技术（2）稀疏索引稀疏索引（sparseindex）是指只对主6.4.1索引技术

索引主文件图6.5稠密索引示例

70Wzbm指针

WzbmWzmcJldwPrice010101010101铍铜合金Kg010301010301铅锑合金Kg010401010401锆镁合金Kg02010102010125铜管材根02010202010220铜管材根02020102020125铝管材根02020202020210铝管材根608090120010008006.4.1索引技术索引6.4.1索引技术6.4.1索引技术2.辅助索引由于主索引中具有相同索引项值的记录在同一地址或相邻地址中，因而查找速度慢，有时还需要使用辅助索引。采用辅助索引查找速度快，一般采用下面的方法：即仍采用索引记录（索引项值与对应的指针），不过此时指针指向的不是主文件记录地址而是指向一个桶（bucket），桶内存放指向具有同一索引项值的指针。如在前稀疏索引示例中，建立以Jldw为索引项的辅助索引。如图6.8所示，在这种结构中，以辅助索引为中介，可以通过二层指针方便地查到对应的主文件地址。6.4.1索引技术2.辅助索引6.4.1索引技术1.B+树的结构B+树索引是一个多级索引，但是其结构不同于多级索引顺序文件。B+树的索引结构是树的形式，最上一级索引是树的根结点，最下一级索引是树的叶结点。该级索引指针指向主文件的记录地址，一般采用稠密索引；而非叶的其他结点（包括根结点）的索引指向下一级结点的地址，一般为稀疏索引。6.4.2B+树索引文件1.B+树的结构6.4.2B+树索引文件6.4.2B+树索引文件6.4.2B+树索引文件6.4.2B+树索引文件6.4.2B+树索引文件典型的B+树结点结构如图6.9所示，其中P为指针，K为索引项值，每个结点中的索引项值按次序存放，即如果i<j，那么Ki<Kj。6.4.2B+树索引文件P1K1P2K2

…PiKi

…Pn-1Kn-1Pn图6.9典型的B树结点

各叶结点中值的范围互不相交。因此，如果Li和Lj是两个叶结点，且i<j，那么Li中所有的索引项值都小于Lj中的所有索引项值。既然叶结点指针指向主文件的记录地址，因此如要使叶结点是稠密索引，则每个索引项值都必须出现在某个叶结点中。在叶结点中指针Pn的作用是把叶结点按索引项顺序串在一起，即叶结点Li的Pn指向叶结点Li+1的第一个指针P1。典型的B+树结点结构如图6.9所示，其中P为指针，K图6.10给出了一个B+树的例子，每个大写字母代表索引项值。为简单起见，省略了空指针和指向主记录的指针。6.4.2B+树索引文件图6.10给出了一个B+树的例子，每个大写字母代表索2.B树上的查询假设要查询索引项值为K的所有记录，查询方法为：（1）检查根结点，找到大于K的最小索引值，假设为K，那么顺着P走到第二层结点。如果找不到这样的值，就沿着P走到第二层结点。（2）在走到的第二层结点中用类似（1）的方法找到相应指针并到达第三层。（3）如此重复，最终到达一个叶结点。如果该结点中有某个索引项值K等于K，那么指针P指向我们所需要的记录，如果在该叶结点中找不到值K，则不存在索引项值为K的记录。6.4.2B+树索引文件2.B树上的查询6.4.2B+树索引文件提高数据库查找速度的另一种方法是散列（hash）技术。其基本原理是利用一种散列函数建立起主文件中指定项值与磁盘物理块间的映射联系，这样只要给出指定项的值立即可通过散列函数得到其对应的存储物理块地址。在对散列的描述中，将使用术语桶（bucket）来表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块，但也可能小于或者大于一个磁盘块。形式化地，令K表示所有指定项值的集合，令B表示所有桶地址的集合，散列函数H就是一个从K到B的函数。我们用H表示散列函数。

6.4.3散列技术提高数据库查找速度的另一种方法是散列（hash）技术散列技术的具体实现方法如下：（1）建立主文件的指定项K以及该项值的集合{K1，K2…Kn}。（2）建立磁盘物理存储单位桶以及桶地址的集合{B1，B2…Bn}。（3）建立散列函数H（Ki），它建立主文件指定项的值与桶间的对应关系，对应一个Ki必通过H（Ki）找到惟一的一个桶地址。6.4.3散列技术散列技术的具体实现方法如下：6.4.3散列技术还可以将散列与索引相结合形成“散列索引”，从而使其效果更为有效。散列索引将索引项及相应指针组织成散列文件结构。散列索引的构造如下：将散列函数作用于索引项以确定对应的桶，然后将此索引项及相应指针存入此桶中。例如，用图6.6中的主文件建立散列索引。以Wzbm为指定项，首先建立索引记录（见图6.6），所用散列函数为Wzbm各位数字之和后模4。该散列索引有四个桶，每个桶大小为3（现实中索引的桶大小当然会大的多）。经计算建立起如图6.12所示的一个散列索引。6.4.3散列技术还可以将散列与索引相结合形成“散列索引”，从而使其效6.4.3散列技术图6.11索引散列示例6.4.3散列技术图6.11索引散列示例6.1数据库的物理存储介质6.2文件组织6.3文件中记录的组织6.4索引技术与散列技术第6章数据库存储技术6.1数据库的物理存储介质第6章数据库存储技术6.1.1数据库的物理存储介质6.1.2磁盘存储器及其结构6.1数据库的物理存储介质6.1.1数据库的物理存储介质6.1数据库的物理存储介如图6.1所示，计算机系统中的数据存储是按照层次组织的。顶层是主存储器，它是由高速缓存储器和主存组合，提供数据的快速访问；接下来是第二级存储器，它是由磁盘等较慢的设备组成；第三级存储器是最慢的存储设备，如光盘和磁带等。与同样数量的磁盘相比，主存的价格昂贵得多，而磁带却比磁盘更便宜。因为数据库需要存储大量的数据，所以像磁盘和磁带这样较慢的存储设备在数据库系统中具有重要地位。主要的存储介质有：6.1.1数据库的物理存储介质如图6.1所示，计算机系统中的数据存储是按照层次组织6.1.1数据库的物理存储介质CPU高速缓存主存磁带磁盘数据请求满足请求的数据主存储器第二级存储器第三级存储器图6.1存储层次6.1.1数据库的物理存储介质CPU高速缓存主存磁带磁盘1.高速缓存高速缓冲存储器是最快最昂贵的存储介质。高速缓冲存储器一般很小，它的使用由操作系统来管理。在数据库系统中，我们将不考虑高速缓冲存储器的存储管理。2.主存主存又称内存或主存储器，用于存放可被处理的数据，它是计算机机器指令执行操作的地方。由于其存储量小（一般以MB为单位）、成本高、存储时间短，而且发生电源故障或者系统崩溃时，里面的内容一般会丢失，因此它在数据库中仅作为数据存储的辅助实体，如作为工作区（workarea）(数据加工区)、缓冲区（bufferarea）(磁盘与主存的交换区)等。6.1.1数据库的物理存储介质1.高速缓存6.1.1数据库的物理存储介质3.快闪存储器也叫电可擦可编程只读存储器（EEPROM）。快闪存储器不同于主存储器的地方是在电源故障发生时数据可被保存下来。从快闪存储器读数据的时间小于100纳秒，大致等于从主存储器中读数据的时间。然而，向快闪存储器写数据是非常复杂的——数据写入一次，大约需要4~10微秒，而且数据不能被直接覆盖。要想覆盖已经被写过的快闪存储器，必须一次性擦除整个快闪存储器，然后它才可以再被写入一次。快闪存储器的另一个缺点是它只支持有限的擦除次数，其范围从10000~1百万。在低成本计算机系统中，例如在嵌入至其他设备的计算机系统中，快闪存储器作为磁盘的替代物来存储少量数据（5MB~10MB）已经非常流行。6.1.1数据库的物理存储介质3.快闪存储器6.1.1数据库的物理存储介质4.磁盘磁盘存储器又称二级存储器或次级存储器。由于它存储量大（一般以GB为单位），能长期保存又有一定的存取速度且价格合理，因此早已成为数据库真正存放数据的物理实体。通常整个数据库都存储在磁盘上。为了能够访问到数据，必须将数据从磁盘移到主存储器。完成操作后，被修改的数据必须写回磁盘。磁盘存储器为直接存取存储器，因为在磁盘上可以按任意顺序读取数据（与顺序存取的存储器不同）。在发生电源故障或者系统崩溃时，磁盘存储器不会丢失数据。6.1.1数据库的物理存储介质4.磁盘6.1.1数据库的物理存储介质5.光盘光盘存储器最流行的形式是只读光盘（CD-ROM）。数据通过光学方法存储在光盘上，并且可以被激光器读取。用于CD-ROM存储器的光盘是不可写的，但是可以提供预先记录的数据，并且可以装入驱动器或从驱动器中移走。另一种光盘存储器是“一次写，多次读”（WORM）光盘，它允许写入数据一次，但是不允许擦除和重写这些数据。这种介质用于数据的归档存储。此外还有磁光结合的存储设备，可使用光学方法读取以磁方法编码的数据，并且允许对旧数据进行覆盖。6.1.1数据库的物理存储介质5.光盘6.1.1数据库的物理存储介质6.磁带磁带具有较大的容量（从GB到TB），价格便宜并可以脱机存放。因为磁带必须从头顺序存取，是一种顺序存取存储器，因此数据存取也比磁盘慢的多。磁带一般用于存储磁盘或主存中的拷贝数据，它是一种辅助存储设备，也称为三级存储器。6.1.1数据库的物理存储介质6.磁带6.1.1数据库的物理存储介质6.1.2磁盘存储器及其结构由于磁盘是数据库数据存储的主要物理存储体，因此本节主要介绍磁盘及其结构。磁盘为现代计算机系统提供了大容量的辅助存储，其存储容量极大，大约在几个GB到几十个GB，甚至几百个GB之间。一个典型的大型商业数据库需要数百个磁盘。磁盘结构如图所示。6.1.2磁盘存储器及其结构由于磁盘是数据库数据6.1.2磁盘存储器及其结构6.1.2磁盘存储器及其结构6.1.2磁盘存储器及其结构磁盘存储器由磁盘盘片与磁盘驱动器两部分组成。1.磁盘盘片磁盘盘片是一种扁平的圆盘。它的两个表面都覆盖着磁性物质，信息就记录在表面上。盘片由硬金属或玻璃制成，被磁性物质覆盖（通常是两面）。盘片的表面被逻辑地划分为磁道(track)，磁道又被划分为扇区（sector），它又称磁盘块（block），磁盘块是从磁盘读出和写入信息的最小单位。根据磁盘的不同类型，一个扇区的大小可从32~4096字节不等，但通常是512字节。每个磁道有4~32个扇区，每个盘片表面有20~1500个磁道。一个磁盘存储器往往由若干个盘片（6~11片）组成一个盘片组，固定在一个主轴上，以每个盘片磁道为注视点可以构成一个无形的同心圆柱体，从内到外层层相套。每个圆柱体从上到下有若干个磁道围绕其上。6.1.2磁盘存储器及其结构磁盘存储器由磁盘盘片与磁盘驱6.1.2磁盘存储器及其结构2.磁盘驱动器磁盘驱动器由活动臂、读写头等组成。每个盘面有两个臂，分别对应上、下两面，每个臂的尽头是一个读/写头（或称磁头），用它可以读取（或写入）盘片中的数据。一个由n个磁盘片所组成的盘片组对应有2n个活动臂，它们组合在一起构成臂组合件，这种组合件可以自由伸缩活动，它以磁道为单位向前推进或向后退缩，用它可以对磁道定位，由于它是组合方式以全体活动臂为单位作进退，因此它的推进或后退实际上是对圆柱体定位。6.1.2磁盘存储器及其结构2.磁盘驱动器6.1.2磁盘存储器及其结构3.磁盘存储器一个磁盘存储器是由盘片组以及磁盘驱动器组成，其中盘片组以轴为核心作不间断的旋转，速度以60、90、120或150转不等，而活动臂组合件则以圆柱体为单位做前进或后退操作。这样，一个磁盘存储器上的任何一个磁盘块都可由下面三个部分定位。（1）圆柱体号：确定圆柱体（由活动臂移动定位）。（2）读/写头号：确定圆柱体中磁道（由选择组合件中活动臂定位）。（3）磁盘块号：确定磁道中的盘块号（由盘片组旋转定位）。6.1.2磁盘存储器及其结构3.磁盘存储器6.1.2磁盘存储器及其结构4.磁盘存储器的I/O操作为进行有效管理，系统对磁盘作统一编址，编址按圆柱体号、磁道号及盘块号编码，编码规则如下：（1）圆柱体号：设有n个圆柱体，则编号自柱面的外层至内层，从0~n-1。（2）磁道号：设一个圆柱体有m个磁道，则磁道号统一编码从上到下顺序编号，从0~nm-1个。（3）磁盘块号：设一个磁道有r个盘块，则磁盘块号也是统一编码，从0~nmr-1个。6.1.2磁盘存储器及其结构4.磁盘存储器的I/O操作6.1.2磁盘存储器及其结构磁盘在投入使用前都要进行格式化，目的是在各盘块的头部加注该块地址，包括该块所在的圆柱体号，读/写头号，盘块号以及某些状态标志。在具体操作时用户给出磁盘地址，此时活动臂组合件作机械运动并定位于指定圆柱体，同时系统选择指定的读/写头以确定磁道，最终读/写头跟踪旋转的磁道，并读出旋转时每磁盘块的地址。当用户给出的地址与磁盘地址一致时则表示地址已找到，此时系统就将该地址中的数据读入内存中的磁盘缓冲区（或从磁盘缓冲区将数据写入指定磁盘地址），这就完成了一次磁盘读/写操作或称I/O操作。6.1.2磁盘存储器及其结构磁盘在投入使用前都要6.2.1文件的定长记录6.2.2文件的变长记录6.2文件组织6.2.1文件的定长记录6.2文件组织一般在文件中的记录都是有固定长度的，这种长度一般都由文件记录型确定。例如某个关系模式“物资编码表”：Wzbmb（Wzbm，Wzmc，Xhgg，Jldw，Price），它可以设计成一个定长文件。文件中的各个记录定义如下：

TYPEWzbmb-TYPE=RECORDWzbm：VARCHAR2（6）；Wzmc：VARCHAR2（16）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8，2）；END

如果假设每个字符占1个字节，那么每个Wzbmb记录定长为52个字节。6.2.1文件的定长记录一般在文件中的记录都是有固定长度的，这种长度一般都由文件中的记录有时其长度是可以变化的，变长记录出现在数据库系统中的下述情况中：（1）多种记录型在一个文件中存储。（2）记录型允许一个或多个字段是变长的。（3）记录型允许可重复的字段。6.2.2文件的变长记录文件中的记录有时其长度是可以变化的，变长记录出现在数

6.2.2文件的变长记录例如，把6.2.1中的关系模式作如下文件结构定义：TYPEWzbmb-LIST=RECORDWzmc：VARCHAR2（16）；Wzbm-INFO：ARRAY[1，]OFRECORDWzbm：VARCHAR2（6）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8,2）；ENDEND

6.2.2文件的变长记录例如，把6.2.1中的关系模式作如变长记录的表示有两种形式：（1）字节流实现变长记录的一个简单方法是在每个记录的末尾附加一个特殊的记录终止符号，这样可以把每个记录作为一个连续的字节流来存储。另一种字节流表示方法是在每个记录的开始处存储记录的长度，而不再使用记录终止符号。（2）定长的表示方法另一种在文件系统中有效实现变长记录的方法是使用一个或多个定长记录来代表一个变长记录。6.2.2文件的变长记录变长记录的表示有两种形式：6.2.2文件的变长记录使用定长记录实现变长记录文件的技术有两种：①保留空间。如果设置一个永远不会被超过的最大记录长度，我们就可以使用长度为这个最大记录长度的定长记录。如对那些比最大空间短的记录，则未使用的空间用特殊的空值或记录终结符号来填充。②指针。变长记录用一系列通过指针链接起来的定长记录来表示。在该形式中，每个定长记录后加一个指针字段，该字段指出是否有指针以及如果有指针则给出下一个定长记录的地址，这种方法即是用若干个定长记录来拼成一个变长记录。6.2.2文件的变长记录使用定长记录实现变长记录文件的技术有两种：6.2.2文件的一般的记录组织有如下几种方式:1.堆文件组织（heapfile）在这种组织方式中，一条记录可以放在文件中的任何地方，只要那个地方有空间存放这条记录。记录是没有顺序的。通常一个关系是一个单独的文件。2.顺序文件组织（sequentialfile）顺序文件是为了高效处理按搜索码排序的记录而设计的。为了快速地按搜索码获取记录，在这种文件中每个记录增加一个指针字段，通过指针把记录链接起来。每个记录的指针指向在搜索码顺序上的下一个记录。此外，为了减少顺序文件处理中的块访问的次数，我们在物理上按搜索码顺序或尽可能的按搜索码顺序存储记录。6.3文件中记录的组织一般的记录组织有如下几种方式:6.3文件中记录的组3.散列文件组织（hashingfile）在这种组织方式中，对各个记录的同一属性计算一个散列函数。散列函数的结果作为记录的存储地址（即块号）。4.聚集文件组织（clusteringfile）很多关系数据库系统将各个关系存储在一个个独立的文件中，不同关系中有联系的数据是通过关系间的联接操作得到的，但是当数据的数量比较大时，这种方法速度会很慢。而在聚集文件组织方式中，一个文件可以存储多个关系的记录，不同关系中有联系的记录存储在一起可以提高查找速度。6.3文件中记录的组织3.散列文件组织（hashingfile）6.3例如设物资管理系统中关系R1和R3中有下面的查询：SELECTR1.Dwbm，R1.Dwmc，R3.Wzbm，R3.Qls，R3.SfsFROMR1，R3WHERER1.Dwbm=R3.Dwbm当关系R1和R3数量很大时，要做联接的查询速度是比较慢的。但是如果把R1和R3放在一个聚集文件中，那么在读单位信息时能够同时把单位领料编码以及领料数量一起读入。图6.4为一个聚集文件的例子。6.3文件中记录的组织例如设物资管理系统中关系R1和R3中有下面的查询：6.3文6.3文件中记录的组织DwbmDwmcDwbmWzbmRqQlsSfs0101一分厂一车间01010201012002/12/01550102一分厂二车间01010104012002/12/011080221二分厂生产科01010101012002/12/02202001010201022002/12/025501010201012002/12/02101001020103012002/12/028801020201012002/12/023302210202012002/12/022015（a）关系R1（b）关系R36.3文件中记录的组织DwbmDwmcDwbmWzbmRq6.3文件中记录的组织0101一分厂一车间010101010101010101010201010104010101010201020201012002/12/012002/12/012002/12/022002/12/022002/12/025102051058205100102一分厂二车间010201020103010201012002/12/022002/12/0283830221二分厂生产科02210202012002/12/022015（c）聚集文件图6.4聚集文件示例6.3文件中记录的组织0101一分厂一车间010102016.4.1文件的定长记录6.4.2文件的变长记录6.4.3散列技术6.4索引技术与散列技术6.4.1文件的定长记录6.4索引技术与散列技术在索引技术中对文件（一般用顺序文件）的查找采用类似书刊中目录的方法，即对文件中记录的指定项（称索引项）的项值给出其记录的地址，它们称索引，索引一般也用文件表示，其结构如图6.4所示:6.4.1索引技术索引项值对应记录地址

因此，索引技术中一个索引文件一般由主文件与索引两部分组成，其中主文件存放数据，而索引则存放数据地址。图6.5索引结构在索引技术中对文件（一般用顺序文件）的查找采用类似书主索引主索引是索引中最常用的一种，它一般可以分为以下三类：（1）稠密索引所谓稠密索引（denseindex）是指对主文件索引项的每个“项值”建立一个索引项值，即索引记录包括索引项中的所有项值以及指向该值的记录链表中第一个记录的指针，图6.5给出了稠密索引的一个例子。6.4.1索引技术主索引主索引是索引中最常用的一种，它一般可以分为以下三类：（2）稀疏索引稀疏索引（sparseindex）是指只对主文件索引项的部分项值建立索引记录，这些部分项值的选择具有一定的稀疏特征，即每隔一定距离选择一个。每个索引记录也包括一个项值和指向该项值的第一个数据记录的指针。（3）多级索引当索引本身数量很大时，还有一种办法是采用多级索引，即对索引本身采用索引。图6.7给出了二级索引的例子。6.4.1索引技术（2）稀疏索引稀疏索引（sparseindex）是指只对主6.4.1索引技术

索引主文件图6.5稠密索引示例

70Wzbm指针

WzbmWzmcJldwPrice010101010101铍铜合金Kg010301010301铅锑合金Kg010401010401锆镁合金Kg02010102010125铜管材根02010202010220铜管材根02020102020125铝管材根02020202020210铝管材根608090120010008006.4.1索引技术索引6.4.1索引技术6.4.1索引技术2.辅助索引由于主索引中具有相同索引项值的记录在同一地址或相邻地址中，因而查找速度慢，有时还需要使用辅助索引。采用辅助索引查找速度快，一般采用下面的方法：即仍采用索引记录（索引项值与对应的指针），不过此时指针指向的不是主文件记录地址而是指向一