1、6.1 6.1 数据库的物理存储介质数据库的物理存储介质6.2 6.2 文件组织文件组织6.3 6.3 文件中记录的组织文件中记录的组织6.46.4索引技术与散列技术索引技术与散列技术第第6 6章章 数据库存储技术数据库存储技术6.1.1 6.1.1 数据库的物理存储介质数据库的物理存储介质6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构6.1 6.1 数据库数据库的物理存的物理存储储介介质质 如图如图6.16.1所示，计算机系统中的数据存储所示，计算机系统中的数据存储是按照层次组织的。顶层是主存储器，它是由是按照层次组织的。顶层是主存储器，它是由高速缓存储器和主存组合，提供数据的
2、快速访高速缓存储器和主存组合，提供数据的快速访问；接下来是第二级存储器，它是由磁盘等较问；接下来是第二级存储器，它是由磁盘等较慢的设备组成；第三级存储器是最慢的存储设慢的设备组成；第三级存储器是最慢的存储设备，如光盘和磁带等。与同样数量的磁盘相比，备，如光盘和磁带等。与同样数量的磁盘相比，主存的价格昂贵得多，而磁带却比磁盘更便宜。主存的价格昂贵得多，而磁带却比磁盘更便宜。因为数据库需要存储大量的数据，所以像磁盘因为数据库需要存储大量的数据，所以像磁盘和磁带这样较慢的存储设备在数据库系统中具和磁带这样较慢的存储设备在数据库系统中具有重要地位。主要的存储介质有：有重要地位。主要的存储介质有：6.1
3、.1 6.1.1 数据库的物理存储介质数据库的物理存储介质6.1.1 6.1.1 数据库的物理存储介质数据库的物理存储介质CPU高速缓存主存磁带磁盘数据请求满足请求的数据主存储器第二级存储器第三级存储器图6.1存储层次1.高速缓存高速缓存 高速缓冲存储器是最快最昂贵的存储介质。高速缓冲高速缓冲存储器是最快最昂贵的存储介质。高速缓冲存储器一般很小，它的使用由操作系统来管理。在数据库存储器一般很小，它的使用由操作系统来管理。在数据库系统中，我们将不考虑高速缓冲存储器的存储管理。系统中，我们将不考虑高速缓冲存储器的存储管理。2.主存主存 主存又称内存或主存储器，用于存放可被处理的数据，主存又称内存或
4、主存储器，用于存放可被处理的数据，它是计算机机器指令执行操作的地方。由于其存储量小它是计算机机器指令执行操作的地方。由于其存储量小（一般以（一般以MB为单位）、成本高、存储时间短，而且发生为单位）、成本高、存储时间短，而且发生电源故障或者系统崩溃时，里面的内容一般会丢失，因此电源故障或者系统崩溃时，里面的内容一般会丢失，因此它在数据库中仅作为数据存储的辅助实体，如作为工作区它在数据库中仅作为数据存储的辅助实体，如作为工作区（work area）(数据加工区数据加工区)、缓冲区（、缓冲区（buffer area）(磁磁盘与主存的交换区盘与主存的交换区)等。等。6.1.1 6.1.1 数据库的物理
5、存储介质数据库的物理存储介质3.快闪存储器快闪存储器 也叫电可擦可编程只读存储器（也叫电可擦可编程只读存储器（EEPROM）。快）。快闪存储器不同于主存储器的地方是在电源故障发生时闪存储器不同于主存储器的地方是在电源故障发生时数据可被保存下来。从快闪存储器读数据的时间小于数据可被保存下来。从快闪存储器读数据的时间小于100纳秒，大致等于从主存储器中读数据的时间。然纳秒，大致等于从主存储器中读数据的时间。然而，向快闪存储器写数据是非常复杂的而，向快闪存储器写数据是非常复杂的数据写入数据写入一次，大约需要一次，大约需要410微秒，而且数据不能被直接覆盖。微秒，而且数据不能被直接覆盖。要想覆盖已经被
6、写过的快闪存储器，必须一次性擦除要想覆盖已经被写过的快闪存储器，必须一次性擦除整个快闪存储器，然后它才可以再被写入一次。快闪整个快闪存储器，然后它才可以再被写入一次。快闪存储器的另一个缺点是它只支持有限的擦除次数，其存储器的另一个缺点是它只支持有限的擦除次数，其范围从范围从100001百万。在低成本计算机系统中，例如百万。在低成本计算机系统中，例如在嵌入至其他设备的计算机系统中，快闪存储器作为在嵌入至其他设备的计算机系统中，快闪存储器作为磁盘的替代物来存储少量数据（磁盘的替代物来存储少量数据（5MB10MB）已经非）已经非常流行。常流行。6.1.1 6.1.1 数据库的物理存储介质数据库的物理
7、存储介质4.磁盘磁盘 磁盘存储器又称二级存储器或次级存储器。由于磁盘存储器又称二级存储器或次级存储器。由于它存储量大（一般以它存储量大（一般以GB为单位），能长期保存又有一为单位），能长期保存又有一定的存取速度且价格合理，因此早已成为数据库真正定的存取速度且价格合理，因此早已成为数据库真正存放数据的物理实体。通常整个数据库都存储在磁盘存放数据的物理实体。通常整个数据库都存储在磁盘上。为了能够访问到数据，必须将数据从磁盘移到主上。为了能够访问到数据，必须将数据从磁盘移到主存储器。完成操作后，被修改的数据必须写回磁盘。存储器。完成操作后，被修改的数据必须写回磁盘。磁盘存储器为直接存取存储器，因为在
8、磁盘上可以按磁盘存储器为直接存取存储器，因为在磁盘上可以按任意顺序读取数据（与顺序存取的存储器不同）。在任意顺序读取数据（与顺序存取的存储器不同）。在发生电源故障或者系统崩溃时，磁盘存储器不会丢失发生电源故障或者系统崩溃时，磁盘存储器不会丢失数据。数据。6.1.1 6.1.1 数据库的物理存储介质数据库的物理存储介质5.光盘光盘 光盘存储器最流行的形式是只读光盘（光盘存储器最流行的形式是只读光盘（CD-ROM）。）。数据通过光学方法存储在光盘上，并且可以被激光器读取。数据通过光学方法存储在光盘上，并且可以被激光器读取。用于用于CD-ROM存储器的光盘是不可写的，但是可以提供预存储器的光盘是不可
9、写的，但是可以提供预先记录的数据，并且可以装入驱动器或从驱动器中移走。先记录的数据，并且可以装入驱动器或从驱动器中移走。另一种光盘存储器是另一种光盘存储器是“一次写，多次读一次写，多次读”（WORM）光盘，）光盘，它允许写入数据一次，但是不允许擦除和重写这些数据。它允许写入数据一次，但是不允许擦除和重写这些数据。这种介质用于数据的归档存储。此外还有磁光结合的存储这种介质用于数据的归档存储。此外还有磁光结合的存储设备，可使用光学方法读取以磁方法编码的数据，并且允设备，可使用光学方法读取以磁方法编码的数据，并且允许对旧数据进行覆盖。许对旧数据进行覆盖。6.1.1 6.1.1 数据库的物理存储介质数
10、据库的物理存储介质6.磁带磁带 磁带具有较大的容量（从磁带具有较大的容量（从GB到到TB），价格便宜），价格便宜并可以脱机存放。因为磁带必须从头顺序存取，是一并可以脱机存放。因为磁带必须从头顺序存取，是一种顺序存取存储器，因此数据存取也比磁盘慢的多。种顺序存取存储器，因此数据存取也比磁盘慢的多。磁带一般用于存储磁盘或主存中的拷贝数据，它是一磁带一般用于存储磁盘或主存中的拷贝数据，它是一种辅助存储设备，也称为三级存储器。种辅助存储设备，也称为三级存储器。6.1.1 6.1.1 数据库的物理存储介质数据库的物理存储介质6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构 由于磁盘是数据库数
11、据存储的主要物理存储体，因由于磁盘是数据库数据存储的主要物理存储体，因此本节主要介绍磁盘及其结构。此本节主要介绍磁盘及其结构。磁盘为现代计算机系统提供了大容量的辅助存储，磁盘为现代计算机系统提供了大容量的辅助存储，其存储容量极大，大约在几个其存储容量极大，大约在几个GBGB到几十个到几十个GBGB，甚至几百，甚至几百个个GBGB之间。一个典型的大型商业数据库需要数百个磁盘。之间。一个典型的大型商业数据库需要数百个磁盘。磁盘结构如图所示。磁盘结构如图所示。6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构磁盘存储器由磁盘盘片与
12、磁盘驱动器两部分组成。磁盘存储器由磁盘盘片与磁盘驱动器两部分组成。1.1.磁盘盘片磁盘盘片 磁盘盘片是一种扁平的圆盘。它的两个表面都覆盖着磁磁盘盘片是一种扁平的圆盘。它的两个表面都覆盖着磁性物质，信息就记录在表面上。盘片由硬金属或玻璃制成，性物质，信息就记录在表面上。盘片由硬金属或玻璃制成，被磁性物质覆盖（通常是两面）。盘片的表面被逻辑地划分被磁性物质覆盖（通常是两面）。盘片的表面被逻辑地划分为磁道为磁道(track)(track)，磁道又被划分为扇区（，磁道又被划分为扇区（sectorsector），它又称），它又称磁盘块（磁盘块（blockblock），磁盘块是从磁盘读出和写入信息的最小）
13、，磁盘块是从磁盘读出和写入信息的最小单位。根据磁盘的不同类型，一个扇区的大小可从单位。根据磁盘的不同类型，一个扇区的大小可从324096324096字节不等，但通常是字节不等，但通常是512512字节。每个磁道有字节。每个磁道有432432个扇区，每个扇区，每个盘片表面有个盘片表面有201500201500个磁道。个磁道。一个磁盘存储器往往由若干个盘片（一个磁盘存储器往往由若干个盘片（611611片）组成一个片）组成一个盘片组，固定在一个主轴上，以每个盘片磁道为注视点可以盘片组，固定在一个主轴上，以每个盘片磁道为注视点可以构成一个无形的同心圆柱体，从内到外层层相套。每个圆柱构成一个无形的同心圆
14、柱体，从内到外层层相套。每个圆柱体从上到下有若干个磁道围绕其上。体从上到下有若干个磁道围绕其上。6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构2.2.磁盘驱动器磁盘驱动器 磁盘驱动器由活动臂、读写头等组成。每个盘面有磁盘驱动器由活动臂、读写头等组成。每个盘面有两个臂，分别对应上、下两面，每个臂的尽头是一个读两个臂，分别对应上、下两面，每个臂的尽头是一个读/写头（或称磁头），用它可以读取（或写入）盘片中写头（或称磁头），用它可以读取（或写入）盘片中的数据。一个由的数据。一个由n n个磁盘片所组成的盘片组对应有个磁盘片所组成的盘片组对应有2n2n个个活动臂，它们组合在一起构成臂组合件
15、，这种组合件可活动臂，它们组合在一起构成臂组合件，这种组合件可以自由伸缩活动，它以磁道为单位向前推进或向后退缩，以自由伸缩活动，它以磁道为单位向前推进或向后退缩，用它可以对磁道定位，由于它是组合方式以全体活动臂用它可以对磁道定位，由于它是组合方式以全体活动臂为单位作进退，因此它的推进或后退实际上是对圆柱体为单位作进退，因此它的推进或后退实际上是对圆柱体定位。定位。6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构3.3.磁盘存储器磁盘存储器 一个磁盘存储器是由盘片组以及磁盘驱动器组成，其一个磁盘存储器是由盘片组以及磁盘驱动器组成，其中盘片组以轴为核心作不间断的旋转，速度以中盘片组以轴
16、为核心作不间断的旋转，速度以6060、9090、120120或或150150转不等，而活动臂组合件则以圆柱体为单位做前转不等，而活动臂组合件则以圆柱体为单位做前进或后退操作。这样，一个磁盘存储器上的任何一个磁盘进或后退操作。这样，一个磁盘存储器上的任何一个磁盘块都可由下面三个部分定位。块都可由下面三个部分定位。（1 1）圆柱体号：确定圆柱体（由活动臂移动定位）。）圆柱体号：确定圆柱体（由活动臂移动定位）。（2 2）读）读/写头号：确定圆柱体中磁道（由选择组合件中活写头号：确定圆柱体中磁道（由选择组合件中活动臂定位）。动臂定位）。（3 3）磁盘块号：确定磁道中的盘块号（由盘片组旋转定）磁盘块号：
17、确定磁道中的盘块号（由盘片组旋转定位）。位）。6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构4.4.磁盘存储器的磁盘存储器的I/OI/O操作操作 为进行有效管理，系统对磁盘作统一编址，编址按圆为进行有效管理，系统对磁盘作统一编址，编址按圆柱体号、磁道号及盘块号编码，编码规则如下：柱体号、磁道号及盘块号编码，编码规则如下：（1 1）圆柱体号：设有）圆柱体号：设有n n个圆柱体，则编号自柱面的外层至个圆柱体，则编号自柱面的外层至内层，从内层，从0n-10n-1。（2 2）磁道号：设一个圆柱体有）磁道号：设一个圆柱体有m m个磁道，则磁道号统一编个磁道，则磁道号统一编码从上到下顺序编号
18、，从码从上到下顺序编号，从0nm-10nm-1个。个。（3 3）磁盘块号：设一个磁道有）磁盘块号：设一个磁道有r r个盘块，则磁盘块号也是个盘块，则磁盘块号也是统一编码，从统一编码，从0nmr-10nmr-1个。个。6.1.2 6.1.2 磁盘存储器及其结构磁盘存储器及其结构 磁盘在投入使用前都要进行格式化，目的是在各盘块磁盘在投入使用前都要进行格式化，目的是在各盘块的头部加注该块地址，包括该块所在的圆柱体号，读的头部加注该块地址，包括该块所在的圆柱体号，读/写写头号，盘块号以及某些状态标志。在具体操作时用户给出头号，盘块号以及某些状态标志。在具体操作时用户给出磁盘地址，此时活动臂组合件作机械
19、运动并定位于指定圆磁盘地址，此时活动臂组合件作机械运动并定位于指定圆柱体，同时系统选择指定的读柱体，同时系统选择指定的读/写头以确定磁道，最终读写头以确定磁道，最终读/写头跟踪旋转的磁道，并读出旋转时每磁盘块的地址。当写头跟踪旋转的磁道，并读出旋转时每磁盘块的地址。当用户给出的地址与磁盘地址一致时则表示地址已找到，此用户给出的地址与磁盘地址一致时则表示地址已找到，此时系统就将该地址中的数据读入内存中的磁盘缓冲区（或时系统就将该地址中的数据读入内存中的磁盘缓冲区（或从磁盘缓冲区将数据写入指定磁盘地址），这就完成了一从磁盘缓冲区将数据写入指定磁盘地址），这就完成了一次磁盘读次磁盘读/写操作或称写操
20、作或称I/OI/O操作。操作。6.2.1 6.2.1 文件的定长记录文件的定长记录6.2.2 6.2.2 文件的变长记录文件的变长记录6.2 6.2 文件组织文件组织 一般在文件中的记录都是有固定长度的，这种长度一般都由文件记一般在文件中的记录都是有固定长度的，这种长度一般都由文件记录型确定。例如某个关系模式录型确定。例如某个关系模式“物资编码表物资编码表”：WzbmbWzbmb（WzbmWzbm，WzmcWzmc，XhggXhgg，JldwJldw，PricePrice），它可以设计成一个定长文件。文件中的各个记），它可以设计成一个定长文件。文件中的各个记录定义如下：录定义如下：TYPE W
21、zbmb-TYPE=RECORDTYPE Wzbmb-TYPE=RECORD Wzbm Wzbm：VARCHAR2VARCHAR2（6 6）；）；WzmcWzmc：VARCHAR2VARCHAR2（1616）；）；XhggXhgg：VARCHAR2VARCHAR2（1616）；）；JldwJldw：VARCHAR2VARCHAR2（6 6）；）；PricePrice：NUMBERNUMBER（8 8，2 2）；）；ENDEND 如果假设每个字符占如果假设每个字符占1 1个字节，那么每个个字节，那么每个WzbmbWzbmb记录定长为记录定长为5252个字节。个字节。6.2.1 6.2.1 文件的
22、定长记录文件的定长记录 文件中的记录有时其长度是可以变化的，变长记文件中的记录有时其长度是可以变化的，变长记录出现在数据库系统中的下述情况中：录出现在数据库系统中的下述情况中：（1 1）多种记录型在一个文件中存储。）多种记录型在一个文件中存储。（2 2）记录型允许一个或多个字段是变长的。）记录型允许一个或多个字段是变长的。（3 3）记录型允许可重复的字段。）记录型允许可重复的字段。6.2.2 6.2.2 文件的变长记录文件的变长记录 6.2.2 6.2.2 文件的变长记录文件的变长记录例如，把例如，把6.2.16.2.1中的关系模式作如下文件结构定义：中的关系模式作如下文件结构定义：TYPE
23、Wzbmb-LIST=RECORDTYPE Wzbmb-LIST=RECORD Wzmc Wzmc：VARCHAR2VARCHAR2（1616）；）；Wzbm-INFOWzbm-INFO：ARRAY1ARRAY1，OFOF RECORD RECORD Wzbm Wzbm：VARCHAR2VARCHAR2（6 6）；）；XhggXhgg：VARCHAR2VARCHAR2（1616）；）；JldwJldw：VARCHAR2VARCHAR2（6 6）；）；PricePrice：NUMBERNUMBER（8,28,2）；）；ENDENDENDEND 变长记录的表示有两种形式：变长记录的表示有两种形式：
24、（1 1）字节流字节流 实现变长记录的一个简单方法是在每个记录的末尾附实现变长记录的一个简单方法是在每个记录的末尾附加一个特殊的记录终止符号，这样可以把每个记录作为一加一个特殊的记录终止符号，这样可以把每个记录作为一个连续的字节流来存储。另一种字节流表示方法是在每个个连续的字节流来存储。另一种字节流表示方法是在每个记录的开始处存储记录的长度，而不再使用记录终止符号。记录的开始处存储记录的长度，而不再使用记录终止符号。（2 2）定长的表示方法定长的表示方法 另一种在文件系统中有效实现变长记录的方法是使用另一种在文件系统中有效实现变长记录的方法是使用一个或多个定长记录来代表一个变长记录。一个或多个
25、定长记录来代表一个变长记录。6.2.2 6.2.2 文件的变长记录文件的变长记录使用定长记录实现变长记录文件的技术有两种：使用定长记录实现变长记录文件的技术有两种：保留空间。如果设置一个永远不会被超过的最大记录保留空间。如果设置一个永远不会被超过的最大记录长度，我们就可以使用长度为这个最大记录长度的定长长度，我们就可以使用长度为这个最大记录长度的定长记录。如对那些比最大空间短的记录，则未使用的空间记录。如对那些比最大空间短的记录，则未使用的空间用特殊的空值或记录终结符号来填充。用特殊的空值或记录终结符号来填充。指针。变长记录用一系列通过指针链接起来的定长记指针。变长记录用一系列通过指针链接起来
26、的定长记录来表示。在该形式中，每个定长记录后加一个指针字录来表示。在该形式中，每个定长记录后加一个指针字段，该字段指出是否有指针以及如果有指针则给出下一段，该字段指出是否有指针以及如果有指针则给出下一个定长记录的地址，这种方法即是用若干个定长记录来个定长记录的地址，这种方法即是用若干个定长记录来拼成一个变长记录。拼成一个变长记录。6.2.2 6.2.2 文件的变长记录文件的变长记录 一般的记录组织有如下几种方式一般的记录组织有如下几种方式:1.1.堆文件组织（堆文件组织（heap fileheap file）在这种组织方式中，一条记录可以放在文件中的任何地在这种组织方式中，一条记录可以放在文件
27、中的任何地方，只要那个地方有空间存放这条记录。记录是没有顺序的。方，只要那个地方有空间存放这条记录。记录是没有顺序的。通常一个关系是一个单独的文件。通常一个关系是一个单独的文件。2.2.顺序文件组织（顺序文件组织（sequential filesequential file）顺序文件是为了高效处理按搜索码排序的记录而设计的。顺序文件是为了高效处理按搜索码排序的记录而设计的。为了快速地按搜索码获取记录，在这种文件中每个记录增加为了快速地按搜索码获取记录，在这种文件中每个记录增加一个指针字段，通过指针把记录链接起来。每个记录的指针一个指针字段，通过指针把记录链接起来。每个记录的指针指向在搜索码顺序
28、上的下一个记录。此外，为了减少顺序文指向在搜索码顺序上的下一个记录。此外，为了减少顺序文件处理中的块访问的次数，我们在物理上按搜索码顺序或尽件处理中的块访问的次数，我们在物理上按搜索码顺序或尽可能的按搜索码顺序存储记录。可能的按搜索码顺序存储记录。6.3 6.3 文件中记录的组织文件中记录的组织 3.3.散列文件组织（散列文件组织（hashing filehashing file）在这种组织方式中，对各个记录的同一属性计算一个散在这种组织方式中，对各个记录的同一属性计算一个散列函数。散列函数的结果作为记录的存储地址（即块号）。列函数。散列函数的结果作为记录的存储地址（即块号）。4.4.聚集文件
29、组织（聚集文件组织（clustering fileclustering file）很多关系数据库系统将各个关系存储在一个个独立的文很多关系数据库系统将各个关系存储在一个个独立的文件中，不同关系中有联系的数据是通过关系间的联接操作得件中，不同关系中有联系的数据是通过关系间的联接操作得到的，但是当数据的数量比较大时，这种方法速度会很慢。到的，但是当数据的数量比较大时，这种方法速度会很慢。而在聚集文件组织方式中，一个文件可以存储多个关系的记而在聚集文件组织方式中，一个文件可以存储多个关系的记录，不同关系中有联系的记录存储在一起可以提高查找速度。录，不同关系中有联系的记录存储在一起可以提高查找速度。6
30、.3 6.3 文件中记录的组织文件中记录的组织例如设物资管理系统中关系例如设物资管理系统中关系R1R1和和R3R3中有下面的查询：中有下面的查询：SELECT R1.DwbmSELECT R1.Dwbm，R1.DwmcR1.Dwmc，R3.WzbmR3.Wzbm，R3.QlsR3.Qls，R3.SfsR3.SfsFROM R1FROM R1，R3R3WHERE R1.Dwbm=R3.DwbmWHERE R1.Dwbm=R3.Dwbm 当关系当关系R1R1和和R3R3数量很大时，要做联接的查询速度是数量很大时，要做联接的查询速度是比较慢的。但是如果把比较慢的。但是如果把R1R1和和R3R3放在一
31、个聚集文件中，那放在一个聚集文件中，那么在读单位信息时能够同时把单位领料编码以及领料数么在读单位信息时能够同时把单位领料编码以及领料数量一起读入。图量一起读入。图6.46.4为一个聚集文件的例子。为一个聚集文件的例子。6.3 6.3 文件中记录的组织文件中记录的组织6.3 6.3 文件中记录的组织文件中记录的组织DwbmDwbmDwmcDwmcDwbmDwbmWzbmWzbmRqRqQlsQlsSfsSfs01010101一分厂一车间一分厂一车间010101010201010201012002/12/012002/12/015 55 501020102一分厂二车间一分厂二车间010101010
32、104010104012002/12/012002/12/0110108 802210221二分厂生产科二分厂生产科010101010101010101012002/12/022002/12/0220202020010101010201020201022002/12/022002/12/025 55 5010101010201010201012002/12/022002/12/0210101010010201020103010103012002/12/022002/12/028 88 8010201020201010201012002/12/022002/12/023 33 302210221
33、0202010202012002/12/022002/12/0220201515 （a a）关系）关系R1 R1 （b b）关系）关系R3 R3 6.3 6.3 文件中记录的组织文件中记录的组织01010101一分厂一车间一分厂一车间01010101010101010101010101010101010101010201010201010104010104010101010101010201020201020201010201012002/12/012002/12/012002/12/012002/12/012002/12/022002/12/022002/12/022002/12/02200
34、2/12/022002/12/025 5101020205 510105 58 820205 5101001020102一分厂二车间一分厂二车间01020102010201020103010103010201010201012002/12/022002/12/022002/12/022002/12/028 83 38 83 302210221二分厂生产科二分厂生产科022102210202010202012002/12/022002/12/0220201515 （c c）聚集文件）聚集文件图图6.4 6.4 聚集文件示例聚集文件示例6.4.1 6.4.1 文件的定长记录文件的定长记录6.4.2
35、 6.4.2 文件的变长记录文件的变长记录6.4.3 6.4.3 散列技术散列技术6.4 6.4 索引技术与散列技术索引技术与散列技术 在索引技术中对文件（一般用顺序文件）的查找在索引技术中对文件（一般用顺序文件）的查找采用类似书刊中目录的方法，即对文件中记录的指定采用类似书刊中目录的方法，即对文件中记录的指定项（称索引项）的项值给出其记录的地址，它们称索项（称索引项）的项值给出其记录的地址，它们称索引，索引一般也用文件表示，其结构如图引，索引一般也用文件表示，其结构如图6.46.4所示所示:6.4.1 6.4.1 索引技术索引技术索引项值索引项值对应记录地址对应记录地址 因此，索引技术中一个
36、索引文件一般由主文件与因此，索引技术中一个索引文件一般由主文件与索引两部分组成，其中主文件存放数据，而索引则存索引两部分组成，其中主文件存放数据，而索引则存放数据地址。放数据地址。图6.5索引结构主索引主索引 主索引是索引中最常用的一种，它一般可以分主索引是索引中最常用的一种，它一般可以分为以下三类：为以下三类：（1 1）稠密索引稠密索引所谓稠密索引（所谓稠密索引（dense indexdense index）是指对主）是指对主文件索引项的每个文件索引项的每个“项值项值”建立一个索引项值，即索引建立一个索引项值，即索引记录包括索引项中的所有项值以及指向该值的记录链表记录包括索引项中的所有项值以
37、及指向该值的记录链表中第一个记录的指针，图中第一个记录的指针，图6.56.5给出了稠密索引的一个例给出了稠密索引的一个例子。子。6.4.1 6.4.1 索引技术索引技术（2 2）稀疏索引稀疏索引稀疏索引（稀疏索引（sparse indexsparse index）是指只对主文件）是指只对主文件索引项的部分项值建立索引记录，这些部分项值的选择索引项的部分项值建立索引记录，这些部分项值的选择具有一定的稀疏特征，即每隔一定距离选择一个。每个具有一定的稀疏特征，即每隔一定距离选择一个。每个索引记录也包括一个项值和指向该项值的第一个数据记索引记录也包括一个项值和指向该项值的第一个数据记录的指针。录的指针
38、。（3 3）多级索引多级索引当索引本身数量很大时，还有一种办法是采当索引本身数量很大时，还有一种办法是采用多级索引，即对索引本身采用索引。图用多级索引，即对索引本身采用索引。图6.76.7给出了二给出了二级索引的例子。级索引的例子。6.4.1 6.4.1 索引技术索引技术6.4.1 6.4.1 索引技术索引技术 索引索引 主文件主文件图6.5稠密索引示例7070WzbmWzbm指针指针WzbmWzbmWzmcWzmcJldwJldwPricePrice010101010101铍铜合金铍铜合金Kg010301010301铅锑合金铅锑合金Kg010401010401锆镁合金锆镁合金Kg020101
39、02010125铜管材铜管材根根02010202010220铜管材铜管材根根02020102020125铝管材铝管材根根02020202020210铝管材铝管材根根60608080909012001200100010008008006.4.1 6.4.1 索引技术索引技术 2.2.辅助索引辅助索引 由于主索引中具有相同索引项值的记录在同一地址或相由于主索引中具有相同索引项值的记录在同一地址或相邻地址中，因而查找速度慢，有时还需要使用辅助索引。采邻地址中，因而查找速度慢，有时还需要使用辅助索引。采用辅助索引查找速度快，一般采用下面的方法：即仍采用索用辅助索引查找速度快，一般采用下面的方法：即仍采
40、用索引记录（索引项值与对应的指针），不过此时指针指向的不引记录（索引项值与对应的指针），不过此时指针指向的不是主文件记录地址而是指向一个桶（是主文件记录地址而是指向一个桶（bucketbucket），桶内存放指），桶内存放指向具有同一索引项值的指针。如在前稀疏索引示例中，建立向具有同一索引项值的指针。如在前稀疏索引示例中，建立以以JldwJldw为索引项的辅助索引。如图为索引项的辅助索引。如图6.86.8所示，在这种结构中，所示，在这种结构中，以辅助索引为中介，可以通过二层指针方便地查到对应的主以辅助索引为中介，可以通过二层指针方便地查到对应的主文件地址。文件地址。6.4.1 6.4.1 索引
41、技术索引技术 1.B+1.B+树的结构树的结构 B+B+树索引是一个多级索引，但是其结构不同于多级索树索引是一个多级索引，但是其结构不同于多级索引顺序文件。引顺序文件。B+B+树的索引结构是树的形式，最上一级索引树的索引结构是树的形式，最上一级索引是树的根结点，最下一级索引是树的叶结点。该级索引指是树的根结点，最下一级索引是树的叶结点。该级索引指针指向主文件的记录地址，一般采用稠密索引；而非叶的针指向主文件的记录地址，一般采用稠密索引；而非叶的其他结点（包括根结点）的索引指向下一级结点的地址，其他结点（包括根结点）的索引指向下一级结点的地址，一般为稀疏索引。一般为稀疏索引。6.4.2 B+6.
42、4.2 B+树索引文件树索引文件6.4.2 B+6.4.2 B+树索引文件树索引文件6.4.2 B+6.4.2 B+树索引文件树索引文件 典型的典型的B+B+树结点结构如图树结点结构如图6.96.9所示，其中所示，其中P P为指针，为指针，K K为为索引项值，每个结点中的索引项值按次序存放，即如果索引项值，每个结点中的索引项值按次序存放，即如果ijij，那么那么KiKjKiKj。6.4.2 B+6.4.2 B+树索引文件树索引文件P1K1P2K2PiKiP n-1Kn-1Pn图图6.9典型的典型的B树结点树结点 各叶结点中值的范围互不相交。因此，如果各叶结点中值的范围互不相交。因此，如果LiL
43、i和和LjLj是两是两个叶结点，且个叶结点，且ijij，那么，那么LiLi中所有的索引项值都小于中所有的索引项值都小于LjLj中的中的所有索引项值。既然叶结点指针指向主文件的记录地址，因所有索引项值。既然叶结点指针指向主文件的记录地址，因此如要使叶结点是稠密索引，则每个索引项值都必须出现在此如要使叶结点是稠密索引，则每个索引项值都必须出现在某个叶结点中。在叶结点中指针某个叶结点中。在叶结点中指针PnPn的作用是把叶结点按索引的作用是把叶结点按索引项顺序串在一起，即叶结点项顺序串在一起，即叶结点LiLi的的PnPn指向叶结点指向叶结点Li+1Li+1的第一个的第一个指针指针P1P1。图图6.10
44、6.10给出了一个给出了一个B+B+树的例子，每个大写字母代表索树的例子，每个大写字母代表索引项值。为简单起见，省略了空指针和指向主记录的指针。引项值。为简单起见，省略了空指针和指向主记录的指针。6.4.2 B+6.4.2 B+树索引文件树索引文件2.B2.B树上的查询树上的查询 假设要查询索引项值为假设要查询索引项值为K K的所有记录，查询方法为：的所有记录，查询方法为：（1 1）检查根结点，找到大于）检查根结点，找到大于K K的最小索引值，假设为的最小索引值，假设为K K，那么顺着那么顺着P P走到第二层结点。如果找不到这样的值，就沿着走到第二层结点。如果找不到这样的值，就沿着P P走到第
45、二层结点。走到第二层结点。（2 2）在走到的第二层结点中用类似（）在走到的第二层结点中用类似（1 1）的方法找到相）的方法找到相应指针并到达第三层。应指针并到达第三层。（3 3）如此重复，最终到达一个叶结点。如果该结点中有）如此重复，最终到达一个叶结点。如果该结点中有某个索引项值某个索引项值K K等于等于K K，那么指针，那么指针P P指向我们所需要的记录，指向我们所需要的记录，如果在该叶结点中找不到值如果在该叶结点中找不到值K K，则不存在索引项值为，则不存在索引项值为K K的记录。的记录。6.4.2 B+6.4.2 B+树索引文件树索引文件 提高数据库查找速度的另一种方法是散列（提高数据库
46、查找速度的另一种方法是散列（hashhash）技术。其基本原理是利用一种散列函数建立起主文件中技术。其基本原理是利用一种散列函数建立起主文件中指定项值与磁盘物理块间的映射联系，这样只要给出指指定项值与磁盘物理块间的映射联系，这样只要给出指定项的值立即可通过散列函数得到其对应的存储物理块定项的值立即可通过散列函数得到其对应的存储物理块地址。在对散列的描述中，将使用术语桶（地址。在对散列的描述中，将使用术语桶（bucketbucket）来）来表示能存储一条或多条记录的一个存储单位。通常一个表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块，但也可能小于或者大于一个磁盘块。桶就是一个磁
47、盘块，但也可能小于或者大于一个磁盘块。形式化地，令形式化地，令K K表示所有指定项值的集合，令表示所有指定项值的集合，令B B表示表示所有桶地址的集合，散列函数所有桶地址的集合，散列函数H H就是一个从就是一个从K K到到B B的函数。的函数。我们用我们用H H表示散列函数。表示散列函数。6.4.3 6.4.3 散列技术散列技术 散列技术的具体实现方法如下：散列技术的具体实现方法如下：（1 1）建立主文件的指定项）建立主文件的指定项K K以及该项值的集合以及该项值的集合 K1 K1，K2K2 Kn Kn。（2 2）建立磁盘物理存储单位桶以及桶地址的集合）建立磁盘物理存储单位桶以及桶地址的集合B
48、1B1，B2B2BnBn。（3 3）建立散列函数）建立散列函数H H（KiKi），它建立主文件指定项的），它建立主文件指定项的值与桶间的对应关系，对应一个值与桶间的对应关系，对应一个KiKi必通过必通过H H（KiKi）找到惟）找到惟一的一个桶地址。一的一个桶地址。6.4.3 6.4.3 散列技术散列技术 还可以将散列与索引相结合形成还可以将散列与索引相结合形成“散列索引散列索引”，从，从而使其效果更为有效。散列索引将索引项及相应指针组而使其效果更为有效。散列索引将索引项及相应指针组织成散列文件结构。散列索引的构造如下：将散列函数织成散列文件结构。散列索引的构造如下：将散列函数作用于索引项以确
49、定对应的桶，然后将此索引项及相应作用于索引项以确定对应的桶，然后将此索引项及相应指针存入此桶中。指针存入此桶中。例如，用图例如，用图6.66.6中的主文件建立散列索引。以中的主文件建立散列索引。以WzbmWzbm为指定项，首先建立索引记录（见图为指定项，首先建立索引记录（见图6.66.6），所用散列），所用散列函数为函数为WzbmWzbm各位数字之和后模各位数字之和后模4 4。该散列索引有四个桶，。该散列索引有四个桶，每个桶大小为每个桶大小为3 3（现实中索引的桶大小当然会大的多）。（现实中索引的桶大小当然会大的多）。经计算建立起如图经计算建立起如图6.126.12所示的一个散列索引。所示的一个散列索引。6.4.3 6.4.3 散列技术散列技术6.4.3 6.4.3 散列技术散列技术图图6.11 6.11 索引散列示例索引散列示例
