数据库原理与开发第4章

《数据库原理与开发第4章》由会员分享，可在线阅读，更多相关《数据库原理与开发第4章（51页珍藏版）》请在金锄头文库上搜索。

1、第四章 数据库的物理存储,内容提要,4.1存储设备 4.1.1 外部存储器 4.1.2 数据处理方式 4.2数据存储方式 4.2.1数据文件 4.2.2 索引,存储设备,对于计算机系统而言，主要有主存和外部存储器两种存储设备。尽管有某些数据库管理系统出于快速响应的目的，将数据库存储在主存中，但是绝大部分数据库管理系统选择将数据库存储在大容量的外部存储器上。,内容提要,4.1存储设备 4.1.1 外部存储器 4.1.2 数据处理方式 4.2数据存储方式 4.2.1数据文件 4.2.2 索引,外部存储器,现在已经存在多种形式的外部存储器，比如光存储器，闪存，硬盘等等。在众多种类的外部存储器中，使用

2、最为广泛的外部存储器就是硬盘,外部存储器,通常，一块硬盘内部包含一个或多个固定在同一个旋转轴上的圆形磁性盘片（platter），每个盘片的一面或者两面涂有磁性材料，盘片上某点的磁场信息决定其记录数据的二进制取值（0或1）。盘片存储的磁性信息通过读/写头（read/write head）访问。读/写头能读取和改变盘片中某点的磁场信息（通过定位到此点上方，并改变其磁场方向的方式）。读/写头被放置在读/写臂的末端，而读/写臂固定在另一个旋转轴上（与盘片的不同），可由旋转轴驱动，使其既可以移向盘片的中心，也可以移向盘片的边缘。通过两个旋转动作的共同作用，读/写头可以定位于盘面上方的任意点。不过，读/写

3、头并不能单独运动，所有的读/写头随着读/写臂部件一致地移动,外部存储器,外部存储器,硬件的数据传输以空间上连续的一些磁点组成的整体作为基本单位进行传输。对磁盘而言，这些空间上连续的磁点组成的整体即是扇区，磁道是盘片上的同心圆，每一个磁道被分为多个扇区。所有盘片上的第i个磁道组成的存储区域称为第i个柱面,内容提要,4.1存储设备 4.1.1 外部存储器 4.1.2 数据处理方式 4.2数据存储方式 4.2.1数据文件 4.2.2 索引,数据处理方式,存储在外部存储器上的数据并不被系统处理器直接访问。要访问其中存储的数据，首先必须从外部存储器上读数据到主存中的缓冲区中，然后对缓存中的数据进行操作。

4、如果处理过程对数据进行了修改操作，那么对缓存中数据的修改结果将会写回外部存储器，并替换外部存储器中的相应数据。,数据处理方式,数据库系统为简化缓冲区的管理会在每次磁盘读写（I/O）操作中传输相同的字节数。数据库系统通常采用的传输单位是页（page）。页在磁盘上以磁盘块（简称块，block）的形式存储。,数据处理方式,从数据库的角度出发，如果假设数据表存储在数据文件之中，那么读取数据表中的某一记录R1的过程可简略表示为： 数据库系统检测文件，定位包含记录R1的页P1； 将页P1从外部存储器传输到高速缓存的一个缓冲区中； 系统确认传输完成，将R1从缓冲区中的页拷贝到应用程序的内存区域中。,数据处理

5、方式,数据存储方式,绝大部分数据库系统都使用数据文件的方式将数据存储在存储设备中，这样可以利用操作系统已有的文件管理功能,内容提要,4.1存储设备 4.1.1 外部存储器 4.1.2 数据处理方式 4.2数据存储方式 4.2.1数据文件 4.2.2 索引,数据文件,堆文件 排序文件 散列文件,堆文件,在此种文件中，行的顺序是任意的，没有专门的规则来进行限制。所以，如果向文件添加新的数据，那么一种直接而简单的方法就是将新添加的行追加到文件的尾部。堆文件所采用的这种存储结构特别适合于处理那些对行的访问顺序不敏感的全表查询。,堆文件,堆文件,可以通过对每一个页面进行格式化存储的方法来解决不定长数据问

6、题。每个页面中包含一定数量的头信息，头信息可以被理解为是一个指针数组，其中包含了指明页面中每一行的起始点和页面中未被使用的区域的内容。可以假设一个数据文件中一行的逻辑地址是由行的ID（rid）给出的，这个ID包含这行在该文件中的页数编号（page number）和行数编号（也称为槽数，slot number）。这样，行的实际位置就可以通过解析使用页的头信息的行数信息来确定。,堆文件,排序文件,在排序文件中，表中的各行并不以任意的顺序存储，而是按表中某些属性上的值对数据行进行排序。 与排序后的数组相似，针对排序文件，使用二分查找 (binary search) 会更有效：首先检索处在文件中间的页

7、。如果目标值在这个页面中，则返回查找结果；否则，在这个数据文件的前半部分(或后半部分)递归地重复查找过程。,排序文件,排序文件,排序文件对于某些范围查找的效率也比堆文件高。由于数据库系统以页为单位进行连续的数据读取，因此相邻的元组被检索时，很可能其数据就处在高速缓冲中，这样就可以大大减少对存储设备的读取次数。相对而言，某一范围内的行可能处在堆文件中不同的页面里，为找到所有这些记录，就必须扫描整个文件。,排序文件,排序文件中数据行的物理有序性在提高了某些操作的性能的同时，也带来了一些负面的影响。 无法同时针对两个属性进行排序 保持行的物理有序是很困难的,排序文件,为了尽可能避免这种负面影响，一种

8、直观的解决方案就是在创建数据文件时就为今后的插入操作事先预留出存储空间（对页面而言，就是指事先留出一些空的存储槽）。预留空间的比例可以由装填因子（fillfactor）控制。进一步的，可以采用溢出页（overflow page）方式来存储新添加数据,散列文件,数据库所采用的散列文件是利用了散列函数思想的一种文件类型。 在散列文件中，表中的各行不是按照顺序写到文件中，而是根据一个或多个属性的值计算出存储数据记录的磁盘块地址。由于散列文件中的记录是随机分布在文件中的，所以它又被称为随机文件或直接文件。,散列文件,在散列文件中，表中的各行不是按照顺序写到文件中，而是根据一个或多个属性的值计算出存储数

9、据记录的磁盘块地址。由于散列文件中的记录是随机分布在文件中的，所以它又被称为随机文件或直接文件。,散列文件,内容提要,4.1存储设备 4.1.1 外部存储器 4.1.2 数据处理方式 4.2数据存储方式 4.2.1数据文件 4.2.2 索引,索引,基本概念 多级索引 索引顺序访问方法 B+树索引 散列索引,基本概念,索引的本质思想就是利用数据记录的某些特征（属性值），使操作可以在尽量少读取数据的情况下快速地定位数据记录的存储位置。被用来建立索引的属性也被称为查找键（Search Key），对应的属性值被称为查找键值。,基本概念,一般而言，索引可以放在一个独立的数据文件中，此时索引只包含数据记录

10、中的查找键值以及指向数据记录存储位置的指针。索引也可以与所表达的表数据集成在一起。,基本概念,索引与数据记录集成的存储方式,基本概念,根据索引本身的某些特征，索引可以进行以下类型的划分： 聚簇索引与非聚簇索引 稠密索引与稀疏索引,聚簇索引与非聚簇索引,如果在相同的查找键上，索引项和数据记录的物理存储都是有序的，并且顺序一致，那么就称有序索引是聚簇索引（clustered），反之就称其为非聚簇索引（unclustered）。聚簇索引通常称作主索引（main index），非聚簇索引通常称作是辅助索引（secondary index）。,稠密索引与稀疏索引,稠密索引（dense index）是指索

11、引项与数据文件中的记录一一对应的索引。非聚簇索引一定是稠密的，而聚簇索引却不一定。因为与聚簇索引对应的属性被用于对数据文件中的数据记录物理排序，所以可以只为某些查找键值建立索引记录，此种索引即为稀疏索引（sparse index）。,稠密索引与稀疏索引,多级索引,现在的数据库管理系统所普遍采用的索引结构都是多层索引。在多层索引（或称为多级索引）中，包含数据记录的索引项被称为叶子项（leaf entry）。在叶子项的上层，索引包含称为分类符项（separator entry）的索引项。在最简单的二层索引中，分类符项集合其实就形成了对叶子项集合的稀疏索引,多级索引,二级索引示例,多层索引,二层索引

12、是多层索引的一个特例：多层索引中，级别更高的索引层次使用索引项更少的稀疏索引来进行组织，直到索引可以被包含在一个页面中为止。,索引顺序访问方法,索引顺序访问方法（ISAM）是一种简单的基于多级索引的树索引结构。ISAM的一般用途是组织数据文件的存储结构，数据记录被放在叶子索引之中。,索引顺序访问方法,分类符索引级别上，页的格式如图所示，此处假设一页中包含m个分类符项。每一个分类符项由一个查找键值ki和一个指向索引文件其它页的指针pi组成。页中的分类索引是有序的。,索引顺序访问方法,ISAM索引示例,B+树索引,B+树是最为常用的基于多级索引的树型索引结构，它支持等值查找、范围查找和部分键查找。

13、 和ISAM索引类似，B+树可用来组织数据文件中的记录。在这种情况之下，叶子项包含数据记录。不过，B+树还可以存储在独立的索引文件中。此时，叶子项包含指向数据文件记录的指针。这意味着B+树索引不仅可以作为主索引或聚簇索引存在，而且辅助索引或非聚簇索引也可以使用B+树索引来实现。,B+树索引,B+树索引采用的是平衡树（balanced tree）结构。 与ISAM索引相比，B+树索引最显著的不同之处就是：B+树本身是动态改变的，在增加和删除记录时，索引页和叶子页会进行相应的增加、删除或修改工作。,B+树索引,B+树中的页节点结构和ISAM索引中分类符级索引页结构完全一样。不过，与ISAM中的分类

14、符级索引节点不同，作为B+树中的叶子节点，此时的p0指向具有查找键值k0的记录位置，pn指向下一个“兄弟节点”,B+树索引,B+树索引示例,散列索引,与散列文件一样，散列索引将散列函数作用于某一个或多个属性（对散列索引而言即为索引键），将其用于定位对应的指针桶。和散列文件不同的是，散列索引中的桶中只用来存储索引键和数据记录的文件指针，并不存储数据记录的具体内容。,散列索引,索引的维护与更新,建立大量索引可以在进行查询时为更为广泛的查询请求提供高效支持，但是这是以更多的存储空间和更多的维护操作为代价的。毕竟，数据库系统中的数据不是一成不变的，需要经常性地进行更新。过度地使用索引就会招致过多的数据维护操作，使数据库系统的总体效率降低。这就使得数据库设计人员必须对数据的应用场合和方式进行综合性的考虑，以提高数据库总体应用性能为基本出发点，对索引的取舍进行折中。,小结,4.1存储设备 4.1.1 外部存储器 4.1.2 数据处理方式 4.2数据存储方式 4.2.1数据文件 堆文件 排序文件 散列文件 4.2.2 索引 基本概念 多级索引 索引顺序访问方法 B+树索引 散列索引,