第14讲数据库的存储管理

1、第6章 数据库的存储管理 第第14讲讲 数据库的存储管理数据库的存储管理数据库的存储管理数据库的存储管理 文件的组织结构 逻辑文件中的数据在物理文件中如何存储逻辑文件中的数据在物理文件中如何存储 文件的存储结构 逻辑文件中的数据在磁盘存储器上如何存放逻辑文件中的数据在磁盘存储器上如何存放 文件的存取方法 针对某种存储结构的文件怎样去查找、插入和针对某种存储结构的文件怎样去查找、插入和删除记录等问题。删除记录等问题。第第14讲讲 数据库的存储管理数据库的存储管理数据库的存储管理数据库的存储管理 数据库存储管理的数据 磁盘上数据的存储 文件的组织结构 文件的存储结构 索引文件的概念第第14讲讲 数

2、据库的存储管理数据库的存储管理数据库存储管理的数据数据库存储管理的数据 数据库系统实现的一个重要问题 如何以最优的形式组织和存放数据库中大量有如何以最优的形式组织和存放数据库中大量有结构的综合性的持久数据结构的综合性的持久数据 最优是指最优是指 存储效率高，节省空间存储效率高，节省空间 存取效率高，代价低存取效率高，代价低第第14讲讲 数据库的存储管理数据库的存储管理数据库存储管理的数据数据库存储管理的数据 数据库的存储管理的基本问题 数据库是大量有结构的相关的持久数据集合。数据库是大量有结构的相关的持久数据集合。 存储在存储介质上的数据被组织为记录文件存储在存储介质上的数据被组织为记录文件

3、每个记录是数据值的一个集合每个记录是数据值的一个集合 数据值描述了有关实体、实体属性及其联系数据值描述了有关实体、实体属性及其联系 存储存储4个方面的数据个方面的数据 数据描述数据描述，即数据外模式、模式、内模式，即数据外模式、模式、内模式 数据本身数据本身 数据之间的联系数据之间的联系 存取路径存取路径第第14讲讲 数据库的存储管理数据库的存储管理数据库存储管理的数据数据库存储管理的数据 数据库系统存储的数据 数据描述数据描述 系统运行时所涉及的各种系统运行时所涉及的各种对象及其属性对象及其属性的描述信息的描述信息 描述数据库结构及其约束的数据库模式、视图、存描述数据库结构及其约束的数据库模

4、式、视图、存取路径（索引、散列等）、访问权限以及数据库状取路径（索引、散列等）、访问权限以及数据库状态信息的记录和统计。态信息的记录和统计。 系统中系统中对象之间关系对象之间关系的描述信息的描述信息 包括各级模式间的映射关系、用户与子模式间的对包括各级模式间的映射关系、用户与子模式间的对应关系等应关系等第第14讲讲 数据库的存储管理数据库的存储管理数据库存储管理的数据数据库存储管理的数据 数据库系统存储的数据 数据描述数据描述 有关数据的描述（称为元数据）存储在数据库的数有关数据的描述（称为元数据）存储在数据库的数据字典中。据字典中。 数据字典是数据库系统运作的基础，任何数据库操数据字典是数据

5、库系统运作的基础，任何数据库操作都要参照数据字典的内容。作都要参照数据字典的内容。 关系数据库中数据字典的组织通常与数据本身的组关系数据库中数据字典的组织通常与数据本身的组织相同。织相同。 按内容的不同在逻辑上组织为若干张表，在物理上按内容的不同在逻辑上组织为若干张表，在物理上就对应若干文件而不是一个文件。由于每个文件中就对应若干文件而不是一个文件。由于每个文件中存放数据量不大，可简单地用顺序文件来组织。存放数据量不大，可简单地用顺序文件来组织。第第14讲讲 数据库的存储管理数据库的存储管理数据库存储管理的数据数据库存储管理的数据 数据库系统存储的数据 数据及数据间的联系数据及数据间的联系 在

6、在RDBMS中数据和数据之间的联系两者组织方式中数据和数据之间的联系两者组织方式相同。相同。 数据和数据之间的联系都用一种数据结构数据和数据之间的联系都用一种数据结构“表表”来表示。来表示。 在数据库的物理组织中，每一个表通常对应一种文在数据库的物理组织中，每一个表通常对应一种文件存储结构。件存储结构。 文件存储结构是定义一个关系表文件中记录的特定文件存储结构是定义一个关系表文件中记录的特定组织形式组织形式 。第第14讲讲 数据库的存储管理数据库的存储管理数据库存储管理的数据数据库存储管理的数据 数据库系统存储的数据 存取路径存取路径 是实现数据访问和存储的基本手段。在关系数据库是实现数据访问

7、和存储的基本手段。在关系数据库中是指访问一个关系表文件中记录集合的特殊技术中是指访问一个关系表文件中记录集合的特殊技术。 存取路径基于表存储结构，或基于所选择的表上可存取路径基于表存储结构，或基于所选择的表上可用的索引。用的索引。 索引是附属的数据库结构，可能是单独存储的一个索引是附属的数据库结构，可能是单独存储的一个文件，它支持对表中行的快速访问。文件，它支持对表中行的快速访问。 存取路径的物理组织通常采用存取路径的物理组织通常采用B+树类文件结构和树类文件结构和HASH类文件结构。类文件结构。 在关系数据库中，存取路径和数据是分离的，对用在关系数据库中，存取路径和数据是分离的，对用户是隐蔽

8、的。户是隐蔽的。第第14讲讲 数据库的存储管理数据库的存储管理数据库存储管理的数据数据库存储管理的数据 数据库系统存储的数据 存储存储4个方面的数据个方面的数据 数据描述数据描述，即数据外模式、模式、内模式，即数据外模式、模式、内模式 数据本身数据本身 数据之间的联系数据之间的联系 存取路径存取路径 数据库系统中的这些数据都要采用一定的文件数据库系统中的这些数据都要采用一定的文件组织来组织、存储起来组织来组织、存储起来 第第14讲讲 数据库的存储管理数据库的存储管理 SQL Server的的存储架构存储架构数据库存储管理的数据数据库存储管理的数据第第14讲讲 数据库的存储管理数据库的存储管理

9、SQL Server的存储架构数据库存储管理的数据数据库存储管理的数据第第14讲讲 数据库的存储管理数据库的存储管理 SQL Server的存储架构数据库存储管理的数据数据库存储管理的数据第第14讲讲 数据库的存储管理数据库的存储管理数据库的存储管理数据库的存储管理 数据库存储管理的数据 磁盘上数据的存储 文件的组织结构 文件的存储结构 索引文件的概念第第14讲讲 数据库的存储管理数据库的存储管理磁盘上数据的存储磁盘上数据的存储 计算机存储系统的层次结构寄存器寄存器高速缓存高速缓存主存储器主存储器磁盘缓存磁盘缓存固定磁盘固定磁盘可移动存储介质可移动存储介质第第14讲讲 数据库的存储管理数据库的

10、存储管理 磁盘的物理特性S磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管理 磁盘的物理特性 容量容量 磁盘的总容量磁盘的总容量=盘面数盘面数每盘面的磁道数每盘面的磁道数每磁道的扇区数每磁道的扇区数每扇区的字节数。目前磁盘的容量可以达到每扇区的字节数。目前磁盘的容量可以达到1TB 。 存取时间存取时间 从发出读从发出读/写请求到数据传输开始这一段时间写请求到数据传输开始这一段时间 数据传输速率数据传输速率 磁头传输数据的速率，取决于盘片的旋转速度和盘片表面的位磁头传输数据的速率，取决于盘片的旋转速度和盘片表面的位密度。每秒可达几十兆字节。密度。每秒可达几十兆字节。

11、磁盘的可靠性磁盘的可靠性 用平均故障时间来说明磁盘无故障连续运行的特性。一般在用平均故障时间来说明磁盘无故障连续运行的特性。一般在38万小时（万小时（3.49.1年）内不出故障。年）内不出故障。磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管理 磁盘的物理特性 存取时间存取时间 寻道时间（磁头定位）寻道时间（磁头定位） 磁头定位于包含扇区磁头定位于包含扇区S的柱面的柱面上方所用的时间。平均寻道时上方所用的时间。平均寻道时间是间是110ms。 旋转延迟时间旋转延迟时间 磁头处于柱面的上方到定位扇磁头处于柱面的上方到定位扇区区S的开始处的上方。平均约的开始处的上方。平均

12、约需转半圈的时间，需转半圈的时间，110ms。 传输时间传输时间 盘片旋转经过扇区盘片旋转经过扇区S所花费的所花费的时间，受旋转时间的限制。时间，受旋转时间的限制。1msS磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管理 磁盘上数据的缓冲存取磁盘上数据的缓冲存取 磁盘是一种低速设备磁盘是一种低速设备 通常情况下，访问一个扇区的时间是通常情况下，访问一个扇区的时间是10ms级。级。 CPU可以利用访问一个扇区的时间执行成百上千条指令。可以利用访问一个扇区的时间执行成百上千条指令。 优化主存和磁盘之间的信息流以优化一个数据库系统的优化主存和磁盘之间的信息流以优化一个数

13、据库系统的性能。性能。 DBMS通过在内存中开辟通过在内存中开辟“缓冲区缓冲区”，采用，采用“预先读延预先读延迟写迟写”的磁盘缓冲存取技术来匹配磁盘和内存的存取速的磁盘缓冲存取技术来匹配磁盘和内存的存取速度。度。 磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管理 磁盘上数据的缓冲存取磁盘上数据的缓冲存取 磁盘块和磁盘缓冲区磁盘块和磁盘缓冲区 数据在磁盘上以称为数据在磁盘上以称为“块块”的定长存储单位形式的定长存储单位形式组织。组织。 块是一个磁道上顺序存储的多个相邻扇区。只需块是一个磁道上顺序存储的多个相邻扇区。只需一次时间延迟来将磁头定位于包含该块的起始处一次时

14、间延迟来将磁头定位于包含该块的起始处。 块（也称作块（也称作“页页”）是内、外存数据交换的基本）是内、外存数据交换的基本单位。单位。 磁盘中的块称为磁盘中的块称为“物理磁盘块物理磁盘块”（或（或“磁盘块磁盘块”），内存中临时存放磁盘块内容的块称为），内存中临时存放磁盘块内容的块称为“缓冲缓冲块块”，所有的内存，所有的内存“缓冲块缓冲块”组成了组成了“磁盘缓冲磁盘缓冲区区”。 磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管理 磁盘上数据的缓冲存取磁盘上数据的缓冲存取 磁盘块和磁盘缓冲区磁盘块和磁盘缓冲区 典型的磁盘块的大小为典型的磁盘块的大小为464KB 磁盘块应足

15、够大，以便能容得下特定应用所要访问的记磁盘块应足够大，以便能容得下特定应用所要访问的记录从而避免对磁盘的另一次访问。录从而避免对磁盘的另一次访问。 磁盘块增大，数据的传输时间会增加，大的磁盘块要求磁盘块增大，数据的传输时间会增加，大的磁盘块要求内存中有大的缓冲区，而且也可能大大地超出应用实际内存中有大的缓冲区，而且也可能大大地超出应用实际要访问的信息（如超出一个表所包含的信息）。要访问的信息（如超出一个表所包含的信息）。磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管理 磁盘上数据的缓冲存取磁盘上数据的缓冲存取 缓冲区管理器缓冲区管理器 负责为数据库上的查询等处理过

16、程提供内存缓冲负责为数据库上的查询等处理过程提供内存缓冲区空间分配和管理的子系统。区空间分配和管理的子系统。 职责是使处理过程得到它们所需的内存，并且尽职责是使处理过程得到它们所需的内存，并且尽可能缩小延迟和减少不可满足的要求。可能缩小延迟和减少不可满足的要求。磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管理数据库缓冲区数据库缓冲区DiskMemoryX InputOutputI/O操作操作程序工作区程序工作区 Read（X) Write(X)X 磁盘上数据的缓冲存取磁盘上数据的缓冲存取 缓冲区管理器缓冲区管理器 磁盘上数据的存储磁盘上数据的存储缓冲区管理器缓冲区

17、管理器第第14讲讲 数据库的存储管理数据库的存储管理 磁盘上数据的缓冲存取磁盘上数据的缓冲存取 缓冲区管理器缓冲区管理器 使用缓冲使用缓冲-替换策略对磁盘缓冲区进行维护。替换策略对磁盘缓冲区进行维护。 原则：最近被访问的磁盘块是活动的，它在不久的将来被原则：最近被访问的磁盘块是活动的，它在不久的将来被再次引用的概率很高，所以这个磁盘块应保存在磁盘缓冲再次引用的概率很高，所以这个磁盘块应保存在磁盘缓冲区中。区中。 最近最少使用（最近最少使用（LRU，Least Recently Used）策略其规）策略其规则就是丢出最长时间没有读或写过的块。一般来说，长时则就是丢出最长时间没有读或写过的块。一般

18、来说，长时间没有使用的缓冲块比那些最近被访问过的缓冲块有更小间没有使用的缓冲块比那些最近被访问过的缓冲块有更小的最近访问的可能性，的最近访问的可能性，LRU是一个有效的策略。是一个有效的策略。 近年来在主要的操作系统和数据库系统中，一种改进的自近年来在主要的操作系统和数据库系统中，一种改进的自适应缓存管理替换算法适应缓存管理替换算法LIRS（Low Inter-Reference recency Set）及其近似实现方法逐步取代了）及其近似实现方法逐步取代了LRU，更新，更新了存储管理的关键技术。了存储管理的关键技术。磁盘上数据的存储磁盘上数据的存储第第14讲讲 数据库的存储管理数据库的存储管

19、理 磁盘上数据的缓冲存取磁盘上数据的缓冲存取 缓冲区管理器缓冲区管理器 I/O 操作操作（Input或或Output操作）是由操作系统中的操作）是由操作系统中的文件系统完成的，数据库管理系统只需要调用操作文件系统完成的，数据库管理系统只需要调用操作系统的这一功能。系统的这一功能。 数据库存储在一个数据库存储在一个Megatron 747磁盘上，它能够以磁盘上，它能够以11ms级别的时间读取级别的时间读取16KB的磁盘块。在的磁盘块。在11ms中，一个现代处中，一个现代处理器可以执行几百万的指令。因此在主存中执行搜索的附理器可以执行几百万的指令。因此在主存中执行搜索的附加时间将比块访问时间的加时

20、间将比块访问时间的1%还要少，可以安全地忽略之还要少，可以安全地忽略之。 磁盘上数据的存储磁盘上数据的存储 加速数据库操作，提高数据库的性能的关键技术是安加速数据库操作，提高数据库的性能的关键技术是安排好数据，使得当某一个磁盘块中有数据被访问时，大排好数据，使得当某一个磁盘块中有数据被访问时，大约在同时很有可能该块上的其他数据也需要被访问。约在同时很有可能该块上的其他数据也需要被访问。 第第14讲讲 数据库的存储管理数据库的存储管理 数据库系统所要解决的问题数据库系统所要解决的问题 记录如何存储在数据文件中，使得应用所要访问的记记录如何存储在数据文件中，使得应用所要访问的记录尽量在相同的磁盘块

21、上，应用访问所需的磁盘录尽量在相同的磁盘块上，应用访问所需的磁盘I/O操操作次数最少；作次数最少； 怎样尽快找到记录所在的磁盘块，使得找到该记录所怎样尽快找到记录所在的磁盘块，使得找到该记录所需磁盘需磁盘I/O操作次数最少。操作次数最少。磁盘上数据的存储磁盘上数据的存储文件存储结构文件存储结构文件存取方法文件存取方法第第14讲讲 数据库的存储管理数据库的存储管理数据库的存储管理数据库的存储管理 数据库存储管理的数据 磁盘上数据的存储 文件的组织结构 文件的存储结构 索引文件的概念第第14讲讲 数据库的存储管理数据库的存储管理 在磁盘上，数据库以文件形式组织，文件由记录组成。 记录表示一个数据对

22、象（例如元组）在磁盘块记录表示一个数据对象（例如元组）在磁盘块中的连续字节存放。中的连续字节存放。 每条记录由一些字段（相关数据值或数据项）集合每条记录由一些字段（相关数据值或数据项）集合组成。字段名及其相应数据类型的值集合即构成了组成。字段名及其相应数据类型的值集合即构成了一个记录类型或记录格式定义。一个记录类型或记录格式定义。 表示数据库（关系）中数据对象的记录放在一表示数据库（关系）中数据对象的记录放在一个或多个磁盘块中。个或多个磁盘块中。文件的组织结构文件的组织结构第第14讲讲 数据库的存储管理数据库的存储管理文件的组织结构文件的组织结构 记录的物理表示 定长记录定长记录 定长记录是最

23、基本、最常见的记录存储方式。定长记录是最基本、最常见的记录存储方式。 在定长记录中，记录的每个字段的长度都是固定的在定长记录中，记录的每个字段的长度都是固定的。系统可以确定每个字段相对于记录开始位置的起。系统可以确定每个字段相对于记录开始位置的起始字节位置，定位字段值。始字节位置，定位字段值。 变长记录变长记录 文件中的不同记录的大小（字节数）不同文件中的不同记录的大小（字节数）不同 。第第14讲讲 数据库的存储管理数据库的存储管理文件的组织结构文件的组织结构 定长记录对于关系模式对于关系模式 S（SNO，SN，SEX，SB，SD）若进行如下定义：若进行如下定义：CREATE TABLE S（

24、SNO CHAR （10）PRIMARY KEY， SN CHAR（20） NOT NULL， SEX CHAR（2），）， SB DATETIME， SD CHAR（20），）， CHECK （SEX IN （男男，女女） ）；）； 第第14讲讲 数据库的存储管理数据库的存储管理文件的组织结构文件的组织结构 定长记录一个定长的S记录的格式 第第14讲讲 数据库的存储管理数据库的存储管理文件的组织结构文件的组织结构 定长记录定长记录在磁盘块中的一种存储方式 块首部存储如下一些信息：与一个或多个其他相关块的链接。与一个或多个其他相关块的链接。块中的元组属于哪个关系的信息。块中的元组属于哪个关系的

25、信息。一个给出每一条记录在块内的偏移量的一个给出每一条记录在块内的偏移量的“目录目录”；指明最后一次修改和指明最后一次修改和/ /或存取块的时间戳。或存取块的时间戳。第第14讲讲 数据库的存储管理数据库的存储管理文件的组织结构文件的组织结构 变长记录 文件记录均属于同一记录类型，但有一个或多文件记录均属于同一记录类型，但有一个或多个字段是大小变化的个字段是大小变化的 不同类型的相关记录在磁盘块中聚集存储，文不同类型的相关记录在磁盘块中聚集存储，文件包含不同的记录类型的记录等。件包含不同的记录类型的记录等。第第14讲讲 数据库的存储管理数据库的存储管理文件的组织结构文件的组织结构 变长记录 在变

26、长记录中的字段存在如下不同格式：在变长记录中的字段存在如下不同格式： 大小变化的数据项大小变化的数据项 重复字段重复字段 如果在一个对象的记录中存储关联的对象的记录，则有多少对象如果在一个对象的记录中存储关联的对象的记录，则有多少对象被关联到指定对象，则在该记录中就会存储多少关联的记录。被关联到指定对象，则在该记录中就会存储多少关联的记录。 可变格式的记录可变格式的记录 有时无法事先确定记录的字段是什么，或每一个字段出现多少次有时无法事先确定记录的字段是什么，或每一个字段出现多少次。比如表示一个。比如表示一个XML元素的一条记录，该元素的一条记录，该XML元素可没有任何约元素可没有任何约束，或

27、可能有重复的子元素和可选属性等。束，或可能有重复的子元素和可选属性等。 极大的字段极大的字段 现代现代DBMS支持属性值非常大的属性，字段可能是一些非结构化支持属性值非常大的属性，字段可能是一些非结构化的大对象数据，如图像、数字视频或音频流，或者自由文本，被的大对象数据，如图像、数字视频或音频流，或者自由文本，被称为称为BLOB（Binary Large Objects，二进制大对象）。，二进制大对象）。 例如，一个电影记录可能有一个例如，一个电影记录可能有一个2G大小的大小的MPEG编码字段，还有编码字段，还有一些普通的字段，比如电影标题等。一些普通的字段，比如电影标题等。第第14讲讲 数据

28、库的存储管理数据库的存储管理文件的组织结构文件的组织结构 变长记录对于关系模式对于关系模式 S（SNO，SN，SEX，SB，SD）若进行如下定义：若进行如下定义：CREATE TABLE S（SNO CHAR （10）PRIMARY KEY， SN VARCHAR（20） NOT NULL， SEX CHAR（2），）， SB DATATIME， SD VARCHAR（20），）， CHECK （SEX IN （男男，女女） ）；）； 第第14讲讲 数据库的存储管理数据库的存储管理文件的组织结构文件的组织结构 变长记录 具有变长字符串的S记录格式 第第14讲讲 数据库的存储管理数据库的存储管理

29、文件的组织结构文件的组织结构 变长记录变长记录在磁盘块中的一种有偏移量表的存储方式 第第14讲讲 数据库的存储管理数据库的存储管理数据库的存储管理数据库的存储管理 数据库存储管理的数据 磁盘上数据的存储 文件的组织结构 文件的存储结构 索引文件的概念第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 数据库文件的存储结构形式 堆文件堆文件 顺序文件顺序文件 聚集文件聚集文件 散列文件散列文件第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 堆文件 最简单的数据文件结构。最简单的数据文件结构。 数据记录之间没有特定的顺序，文件行的顺序数据记录之间

30、没有特定的顺序，文件行的顺序是任意的。是任意的。 将一条新记录插入到文件中，只需找到一个有一些将一条新记录插入到文件中，只需找到一个有一些空闲空间的块，或当块没有空闲空间时就找一个新空闲空间的块，或当块没有空闲空间时就找一个新块，然后将记录存储在那里。块，然后将记录存储在那里。 对于新建立的文件，记录按照其插入的先后顺序存对于新建立的文件，记录按照其插入的先后顺序存放，新产生的记录行能有效地追加在文件的尾部。放，新产生的记录行能有效地追加在文件的尾部。 第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 堆文件 优点优点 实现简单，不需要特殊处理。实现简单，不需要特殊处

31、理。 适用于对表的查询涉及所有行，且行的访问顺序并适用于对表的查询涉及所有行，且行的访问顺序并不重要的访问。不重要的访问。 缺点缺点 查询效率低，对常见的两类查询（等值查询和范围查询效率低，对常见的两类查询（等值查询和范围查询）无任何优势。查询）无任何优势。 删除操作只是加一个删除标记，导致存储空间的浪删除操作只是加一个删除标记，导致存储空间的浪费，搜索时间变长。费，搜索时间变长。 第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 堆文件 用用F表示一个文件所占的磁盘块数，插入、删除和查表示一个文件所占的磁盘块数，插入、删除和查询的平均磁盘询的平均磁盘I/O次数为次数

32、为F/2。若表中没有相同的记录。若表中没有相同的记录存在，需要磁盘存在，需要磁盘I/O次数将是次数将是F。 【例】设一个关系有106个元组，在每个磁盘块中可存放10个这样的元组记录，则该关系大约占用105个磁盘块。 若该关系中的元组构成了一个堆文件，进行记录定位所若该关系中的元组构成了一个堆文件，进行记录定位所需要的磁盘需要的磁盘I/O次数为：次数为： 105 /2或或 105第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 顺序文件 按关系中某些属性值的排序顺序存储记录的文按关系中某些属性值的排序顺序存储记录的文件称为顺序文件，排序所基于的属性称为排序件称为顺序文件

33、，排序所基于的属性称为排序属性（字段）。属性（字段）。关系表S按属性SNO进行顺序存储 第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 顺序文件 优点优点 如果查找条件是基于排序属性的值，可对磁盘文件如果查找条件是基于排序属性的值，可对磁盘文件进行二分查找，得到比线性查找更快的存取速度。进行二分查找，得到比线性查找更快的存取速度。假设文件共有假设文件共有F块，二分查找一般只需存取块，二分查找一般只需存取log2F 。 如果查找属性与排序属性相同，则可高效地完成等如果查找属性与排序属性相同，则可高效地完成等值查询和范围查询。值查询和范围查询。第第14讲讲 数据库的存储

34、管理数据库的存储管理 【例例】设一个关系有设一个关系有106个元组，在每个磁盘块中个元组，在每个磁盘块中可存放可存放10个这样的元组，则该关系大约占用个这样的元组，则该关系大约占用105个磁盘块。个磁盘块。 若该关系中的元组已经按照主键值从小到大的若该关系中的元组已经按照主键值从小到大的顺序构成了一个顺序文件。顺序构成了一个顺序文件。 按照一个主键值进行记录定位所需要的磁盘按照一个主键值进行记录定位所需要的磁盘I/O次数为：次数为： log2105 16.6 17 顺序文件文件的存储结构文件的存储结构第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 顺序文件 缺点缺点

35、 插入和删除操作要保持插入和删除操作要保持记录的存储是有序的记录的存储是有序的，代价很大。，代价很大。 在块中滑动记录以在合适的地点得到所需的空间，将新记在块中滑动记录以在合适的地点得到所需的空间，将新记录插入到块中，并在此块的偏移量表中添加指向此记录的录插入到块中，并在此块的偏移量表中添加指向此记录的新指针。如果块中没有空间用于新记录的存储，可能就要新指针。如果块中没有空间用于新记录的存储，可能就要到到“邻近块邻近块”中找空间或创建一个溢出块。如果要删除一中找空间或创建一个溢出块。如果要删除一个记录，则执行相反的操作，回收记录空间，记录在块中个记录，则执行相反的操作，回收记录空间，记录在块中

36、滑动，让块中间总有一个未用的区域。滑动，让块中间总有一个未用的区域。 不能滑动记录，则需要在块首部维护一个可用空间列表，不能滑动记录，则需要在块首部维护一个可用空间列表，当向块中插入一条新记录时，可知道可用区域在哪里。删当向块中插入一条新记录时，可知道可用区域在哪里。删除记录时，通常的方法是在记录处放一个删除标记，并一除记录时，通常的方法是在记录处放一个删除标记，并一直保留到对整个数据库进行重构。直保留到对整个数据库进行重构。 第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 顺序文件 缺点缺点 插入和删除操作要保持插入和删除操作要保持记录的存储是有序的记录的存储是有

37、序的，代价，代价很大。很大。在文件中，为每个记录增加一个指针字段，根据在文件中，为每个记录增加一个指针字段，根据属性值的大小用指针把记录连接起来。属性值的大小用指针把记录连接起来。 对于删除操作，可通过修改指针实现。而将被删记录对于删除操作，可通过修改指针实现。而将被删记录链接成一个自由空间，以便插入新记录时使用。链接成一个自由空间，以便插入新记录时使用。 对于插入操作，在指针链中找到插入的位置（应插到对于插入操作，在指针链中找到插入的位置（应插到哪个记录的前面），在找到记录的块内，如果有自由哪个记录的前面），在找到记录的块内，如果有自由空间，那么就在该位置插入新记录，并加入到指针链空间，那么

38、就在该位置插入新记录，并加入到指针链中；如果无自由空间，那么就只能插入到溢出块中。中；如果无自由空间，那么就只能插入到溢出块中。第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 顺序文件 顺序文件初始建立时，一般存储记录的物理顺顺序文件初始建立时，一般存储记录的物理顺序和排序键值的顺序一致，以便访问数据时减序和排序键值的顺序一致，以便访问数据时减少对磁盘块的操作次数。少对磁盘块的操作次数。 多次插入和删除操作后，很难维持这种一致的多次插入和删除操作后，很难维持这种一致的状态。此时应该对文件重组，使其物理顺序和状态。此时应该对文件重组，使其物理顺序和排序键值的顺序一致，

39、以提高查找速度。排序键值的顺序一致，以提高查找速度。 第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 聚集文件 聚集，又称聚簇（聚集，又称聚簇（cluster）。）。 文件中元组紧缩到能存储这些元组的尽可能少文件中元组紧缩到能存储这些元组的尽可能少的块中。通常聚集文件把某个或某些属性（称的块中。通常聚集文件把某个或某些属性（称为聚集码，为聚集码，cluster key）上具有相同值的元组）上具有相同值的元组集中存放在连续的物理块中。集中存放在连续的物理块中。 聚集功能可以大大提高按聚集码进行查询的效聚集功能可以大大提高按聚集码进行查询的效率。率。 第第14讲讲 数据

40、库的存储管理数据库的存储管理文件的存储结构文件的存储结构 聚集文件 聚集功能不但适用于单个关系，也适用于经常聚集功能不但适用于单个关系，也适用于经常进行连接操作的多个关系。即把多个连接关系进行连接操作的多个关系。即把多个连接关系的元组按连接属性值聚集存放（连接属性为聚的元组按连接属性值聚集存放（连接属性为聚集码），从而大大提高连接操作的效率。集码），从而大大提高连接操作的效率。SELECT S.SNO，SN，CNO，GRADE FROM S，SC WHERE S.SNO=SC.SNO；第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 聚集文件第第14讲讲 数据库的存储

41、管理数据库的存储管理文件的存储结构文件的存储结构 散列文件 根据记录的属性值根据记录的属性值K（一般为主键（一般为主键)，使用一，使用一个散列函数个散列函数h（hash function，又称哈希函，又称哈希函数）计算得到的函数值数）计算得到的函数值h(K)确定确定记录的地址记录的地址，对记录进行存储和访问。该属性称为散列，对记录进行存储和访问。该属性称为散列键（或散列字段）。键（或散列字段）。第第14讲讲 数据库的存储管理数据库的存储管理 散列文件 使用桶（使用桶（bucket）作为基本的存储单位，桶可）作为基本的存储单位，桶可以是磁盘中的块，也可以是比较大的空间。以是磁盘中的块，也可以是比

42、较大的空间。文件的存储结构文件的存储结构H(Ki)H(Ki)H(Ki)一个桶中存放散一个桶中存放散列函数值相同的列函数值相同的多个记录多个记录桶内记录的散列键桶内记录的散列键值可能是不相同的值可能是不相同的第第14讲讲 数据库的存储管理数据库的存储管理文件的存储结构文件的存储结构 散列文件 优点优点 根据散列键值可以直接得到记录的磁盘块地址，根据散列键值可以直接得到记录的磁盘块地址，I/O操作次数少，访问性能很高。操作次数少，访问性能很高。 如果绝大多数桶都只由单个块组成，那么一般的查如果绝大多数桶都只由单个块组成，那么一般的查询只需一次磁盘询只需一次磁盘I/O，文件的插入和删除也只需要两，文

43、件的插入和删除也只需要两次磁盘次磁盘I/O。 缺点缺点 只适用于按散列键访问记录。只适用于按散列键访问记录。 存在地址冲突问题。存在地址冲突问题。 在实际应用中，记录在散列键值上的分布往往是不在实际应用中，记录在散列键值上的分布往往是不均衡的，在某些桶中存在空间浪费现象，而在另外均衡的，在某些桶中存在空间浪费现象，而在另外一些桶中则存在空间溢出问题。一些桶中则存在空间溢出问题。第第14讲讲 数据库的存储管理数据库的存储管理数据库的存储管理数据库的存储管理 数据库存储管理的数据 磁盘上数据的存储 文件的组织结构 文件的存储结构 索引文件的概念第第14讲讲 数据库的存储管理数据库的存储管理索引文件

44、的概念索引文件的概念 索引的概念 关系数据文件中某属性（组）上的索引是一关系数据文件中某属性（组）上的索引是一种种数据结构数据结构，它提供了在，它提供了在该属性（组）上该属性（组）上快快速查找具有某个特定值的元组的方法。速查找具有某个特定值的元组的方法。 索引可以建立在记录的某一属性或者属性组索引可以建立在记录的某一属性或者属性组上，这个属性或者属性组就被称为上，这个属性或者属性组就被称为索引键索引键。 针对某个属性建立索引，就是根据此属性值针对某个属性建立索引，就是根据此属性值将记录进行将记录进行逻辑排序逻辑排序（有序索引）。（有序索引）。第第14讲讲 数据库的存储管理数据库的存储管理索引文

45、件的概念索引文件的概念 索引的概念 索引结构可以存储在一个单独的文件中，索引结构可以存储在一个单独的文件中，该文件称为索引文件。该文件称为索引文件。 存放记录的索引键值以及指向记录本身的指针存放记录的索引键值以及指向记录本身的指针(记录的存储地址记录的存储地址)，并且按照索引键值的顺序，并且按照索引键值的顺序进行排序。进行排序。 索引文件的每一条记录被称为索引文件的每一条记录被称为索引项索引项，索引项，索引项是一个索引键值和一个记录指针构成的键是一个索引键值和一个记录指针构成的键-指指针对针对 第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 索引的作用 使用索引可以

46、明显加快数据查询的速度。使用索引可以明显加快数据查询的速度。 索引记录中只含有索引键值和地址指针，索引文件索引记录中只含有索引键值和地址指针，索引文件所占磁盘块数量通常比数据文件的少，一般可一次所占磁盘块数量通常比数据文件的少，一般可一次读入内存。读入内存。 索引项是经过排序的，可以使用二分查找法来查找索引项是经过排序的，可以使用二分查找法来查找索引键值所在记录。索引键值所在记录。 通过索引可以大大减少了对磁盘的通过索引可以大大减少了对磁盘的I/O操作次数，节操作次数，节约处理查询的时间，加快查询速度。约处理查询的时间，加快查询速度。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念

47、索引文件的概念 索引的概念 【例例】 考虑在例考虑在例4-1中的中的“学生学生-课程课程”数据库数据库中进行如下查询：中进行如下查询：SELECT *FROM SWHERE SEX=女女 AND SD=计算机系计算机系；关系中可能存在关系中可能存在10000个学生元组，但只有大约个学生元组，但只有大约200人是计算机系的，其中女同学只有人是计算机系的，其中女同学只有50个左右。个左右。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 索引的概念 【例例】在例在例4-1中的中的“学生学生-课程课程”数据库中增加数据库中增加一个专业系的关系模式一个专业系的关系模式D（DN

48、，DD），其中），其中DN为专业系名称，为专业系名称，DD为系主任姓名。对于如为系主任姓名。对于如下查询下查询SELECT DDFROM S，DWHERE SNO=s06 AND S.SD=D.DN； 查询要求找出学号为查询要求找出学号为“s06”的学生所在系主的学生所在系主任的名字。任的名字。 第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 索引的分类 聚集索引和非聚集索引聚集索引和非聚集索引 稠密索引和稀疏索引稠密索引和稀疏索引 多级索引多级索引第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚集索引和非聚集索引 如果在数据文件的相同

49、的属性或属性组上，索如果在数据文件的相同的属性或属性组上，索引记录和数据记录都是有序的，则称该有序索引记录和数据记录都是有序的，则称该有序索引为引为聚集索引聚集索引（聚簇索引，（聚簇索引，Clustered Index），否则就称之为），否则就称之为非聚集索引非聚集索引（非聚簇索引，（非聚簇索引，Unclustered Index）。）。 “聚集索引聚集索引”的建立会使数据文件中记录的物的建立会使数据文件中记录的物理顺序与索引记录的排列顺序一致。理顺序与索引记录的排列顺序一致。 数据文件最多只能在数据文件最多只能在一个排序键一个排序键上排序，上排序，最多最多只有只有一个聚集索引，聚集索引通常又

50、称做一个聚集索引，聚集索引通常又称做主索主索引引，非聚集索引通常称做，非聚集索引通常称做辅助索引辅助索引（或次索引（或次索引）。）。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚集索引和非聚集索引聚集索引 非聚集索引 第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 在聚簇索引中，在聚簇索引中， 物理位置上相近的索引项在一定物理位置上相近的索引项在一定程度上预示相应数据记录的索引键值也很近。程度上预示相应数据记录的索引键值也很近。 可加快按某属性列进行范围查询的效率。可加快按某属性列进行范围查询的效率。【例例】一个

51、数据文件可能存储在一个数据文件可能存储在10000个磁盘块上，但对一个特定的查询个磁盘块上，但对一个特定的查询（等值查询或范围查询）来说，只有（等值查询或范围查询）来说，只有100条记录满足条件。条记录满足条件。如果数据存储在如果数据存储在没有索引文件的堆文件没有索引文件的堆文件中，可能需要中，可能需要1000010000次次I/OI/O操作；操作；如果在这个查询的如果在这个查询的WHERE WHERE 子句的查找属性上有一个子句的查找属性上有一个非聚集索引非聚集索引是可用的，那么检是可用的，那么检索这个数据文件最多只需要索这个数据文件最多只需要100100次次I/OI/O操作。操作。如果在查

52、找属性上有一个如果在查找属性上有一个聚集索引聚集索引是可用的，且每个磁盘块平均包含是可用的，且每个磁盘块平均包含2020条数据记条数据记录，可能只需要录，可能只需要5 5次次I/OI/O操作，检索操作，检索5 5个磁盘块。个磁盘块。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 某些数据库系统中聚簇索引总是与数据文件集某些数据库系统中聚簇索引总是与数据文件集成为一种存储结构。成为一种存储结构。 索引项包含数据记录，由语句索引项包含数据记录，由语句CREATE TABLE创建创建表时同时创建。表时同时创建。 非聚簇索引存储在一个单独的文件中，由语

53、句非聚簇索引存储在一个单独的文件中，由语句CREATE INDEX来创建。来创建。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 定义基本表同时创建索引的语句格式为定义基本表同时创建索引的语句格式为 CREATE TABLE( |AS ,) PRIMARY KEY CLUSTERED|NON CLUSTERED 定义该属性列为主键并建立聚簇或非聚簇索引。定义该属性列为主键并建立聚簇或非聚簇索引。 PRIMARY KEY CLUSTERED |NONCLUSTERED () 定义定义为表为表的主键并建立聚簇或非聚簇索引。的主键并建立聚簇或非聚簇索

54、引。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 建立索引的语句格式建立索引的语句格式CREATE UNIQUE CLUSTERDE INDEX ON (,.) 其他参数其他参数; UNIQUE表示该索引的每一索引值只对应唯一的数据记录。表示该索引的每一索引值只对应唯一的数据记录。 CLUSTER表示要建立的索引是聚簇索引。表示要建立的索引是聚簇索引。 “其他参数其他参数”是与物理存储有关的参数。是与物理存储有关的参数。 PAD-INDEX：为每一内部结点页指定分配空间大小。：为每一内部结点页指定分配空间大小。 FILEFACTOR=:指定叶

55、子数和索引的充满度。指定叶子数和索引的充满度。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 按照索引对数据库记录的覆盖程度按照索引对数据库记录的覆盖程度 稠密索引（稠密索引（Dense Indices） 稀疏索引（稀疏索引（Sparse Indices）第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引

56、的定义（一）稠密索引的定义（一） 索引键为数据文件的候选键，可为数据文件中的索引键为数据文件的候选键，可为数据文件中的每一条记录建立一个索引记录（索引项）。每一条记录建立一个索引记录（索引项）。 基于堆文件的候选键建立的稠密索引 （非聚集索引）基于候选键排序的顺序文件上的稠密索引 （聚集索引）第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引的定义（二）稠密索引的定义（二） 索引键为数据文件的非候选键，且数据文件为索索引键为数据文件的非候选键，且数据文件为索引键上的顺序文件，则为数据文件中具有相同索引键上的顺序文件，则为数据文件中具有相同索

57、引键值的记录建立一个索引记录，索引记录包括引键值的记录建立一个索引记录，索引记录包括索引键值和指向具有该值的记录链表中第一个记索引键值和指向具有该值的记录链表中第一个记录的指针。录的指针。基于非候选键排序的顺序文件上的稠密索引（聚集索引） 第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引的定义（三）稠密索引的定义（三） 索引键为数据文件的非候选键，且数据文件为非索引键为数据文件的非候选键，且数据文件为非顺序文件（堆文件），或数据文件中记录顺序由顺序文件（堆文件），或数据文件中记录顺序由其他属性上主索引确定的，而不是按辅助索引的其他属性上主

58、索引确定的，而不是按辅助索引的索引键顺序物理存储的，因此索引文件中要存放索引键顺序物理存储的，因此索引文件中要存放指向数据文件中具有该索引键值的所有记录的指指向数据文件中具有该索引键值的所有记录的指针。针。基于堆文件的非候选键建立的稠密索引 （辅助索引）第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引的定义（三）稠密索引的定义（三） 通过在稠密索引和数据文件之间加一个记录指针通过在稠密索引和数据文件之间加一个记录指针桶（桶（bucket）来节省存储空间）来节省存储空间 。 可以在不访问数据文件记录的前提下利用桶的指针来帮助回答一些查询和减

59、少一些I/O开销。 比如，当查询有多个条件，而每个条件都有一个可用的辅助索引时，可通过在主存中将指针集合求交来找到满足所有条件的指针，然后只需要检索交集中指针指向的记录。第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稀疏索引的定义稀疏索引的定义 对于顺序数据文件，可以在索引文件中只为数据文对于顺序数据文件，可以在索引文件中只为数据文件的每个磁盘块设一个键件的每个磁盘块设一个键-指针对，来记录该磁盘块指针对，来记录该磁盘块中第一条数据记录的索引键值及该磁盘块的首地址中第一条数据记录的索引键值及该磁盘块的首地址。基于候选键排序的顺序文件上的稀疏索引

60、（聚集索引） 基于非候选键排序的顺序文件上的稀疏索引 （聚集索引）第第14讲讲 数据库的存储管理数据库的存储管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稀疏索引稀疏索引 稀疏索引必须是聚集的稀疏索引必须是聚集的有序文件才允许定位不被索引引用的记录。有序文件才允许定位不被索引引用的记录。 查找一条键值为查找一条键值为K的记录，首先在索引文件中找到的记录，首先在索引文件中找到索引键值小于等于索引键值小于等于K的索引项中索引键值最大的索的索引项中索引键值最大的索引项。然后根据这个索引项的指针找到记录所在磁引项。然后根据这个索引项的指针找到记录所在磁盘块，在调入内存的磁盘块中进行搜索，以找到