数据库的物理组织

《数据库的物理组织》由会员分享，可在线阅读，更多相关《数据库的物理组织（44页珍藏版）》请在金锄头文库上搜索。

1、本讲（第六章）简要说明本讲（第六章）简要说明授课目的与要求授课目的与要求：掌握无序文件，顺序文 件，：掌握无序文件，顺序文 件，HASH文件的文件组织方法。文件的文件组织方法。授课难点授课难点：支持文件空间动态变化的：支持文件空间动态变化的 HASH技术。技术。作业安排作业安排：p.206 1,2,5,9系统定义需求收集与分析数据库与应用程序设计定义数据库 编写程序、装入数据测试、运行系统定义需求收集与分析数据库与应用程序设计定义数据库 编写程序、装入数据测试、运行范围和边界；范围和边界；用户视图。用户视图。为每个主要的用户视图收集以下信息： 对使用或产生的数据的描述； 数据如何使用和产生的细

2、节； 数据库应用程序的额外需求。为每个主要的用户视图收集以下信息： 对使用或产生的数据的描述； 数据如何使用和产生的细节； 数据库应用程序的额外需求。概念数据库设计（概念数据库设计（ER) 逻辑数据库设计（模式）逻辑数据库设计（模式） 物理数据库设计（约束、物理数据库设计（约束、 文件组织、文件组织、安全保密措施）安全保密措施） 设计界面和各功能模块等设计界面和各功能模块等数据库规划数据库规划任务描述；任务描述；任务目标。任务目标。文件组织和存储结构文件组织和存储结构为数据库存储模式设计提供多种可供选 择的为数据库存储模式设计提供多种可供选 择的文件组织文件组织方法是本讲要解决的问题。按一定的

3、逻辑结构（如顺序、树）组织 关联的数据记录（逻辑文件），并用体现逻 辑结构的物理存储形式存到物理设备上。方法是本讲要解决的问题。按一定的逻辑结构（如顺序、树）组织 关联的数据记录（逻辑文件），并用体现逻 辑结构的物理存储形式存到物理设备上。目标：目标：根据用户和系统设计要求，组织根据用户和系统设计要求，组织时空 综合性能时空 综合性能最佳，易于最佳，易于维护维护的文件，为数据库 提供方便、灵活的的文件，为数据库 提供方便、灵活的文件访问文件访问。Optical Disk ,TAPECPUCACHEMAIN MEMORYMAGNETIC DISKPrimary storageSecondary

4、storageTertiary storage硬盘（第二级存储）， 是连机存储数据、程序 的主要存储设备。掉电 后，数据不丢失（硬盘（第二级存储）， 是连机存储数据、程序 的主要存储设备。掉电 后，数据不丢失（非易 失非易 失），是一种直接存取 存储设备。硬盘被逻辑 分），是一种直接存取 存储设备。硬盘被逻辑 分块（块（block), 块大小为块大小为 4KB-56KB。 容量容量为几十为几十GB-几百几百 GB。 磁盘。 磁盘I/O, 访问速度访问速度 在毫秒级在毫秒级10-2。 磁盘阵 列磁盘阵 列，是近年来用于提高 数据库性能和可靠性的 一种技术。，是近年来用于提高 数据库性能和可靠性的

5、 一种技术。主存储器，常为动态随机 访问存储器主存储器，常为动态随机 访问存储器(DRAM)，它 为，它 为CPU提供保存程序和数 据的工作区，数据库系统 只用它存储从外存调入主 存需要处理的那部分数 据。掉电后，主存中的数 据丢失（易失）。容量为 几百提供保存程序和数 据的工作区，数据库系统 只用它存储从外存调入主 存需要处理的那部分数 据。掉电后，主存中的数 据丢失（易失）。容量为 几百MB-几几GB; 访问速 度为访问速 度为10-8-10-7秒。 是主存数据库（实际用 的是虚存）的主要存储介 质。秒。 是主存数据库（实际用 的是虚存）的主要存储介 质。CPU寄存器，寄存器，CPU缓存

6、存储器，高速缓存存储 器。它们一般用来存放将 要执行的机器指令和有关 操作数据，缓存 存储器，高速缓存存储 器。它们一般用来存放将 要执行的机器指令和有关 操作数据，容量容量为为 128KB-512KB;访问速度 为纳秒级：访问速度 为纳秒级：10-9-10-8秒。 由操作系统使用和管理。 数据库管理系统不考虑它 们。秒。 由操作系统使用和管理。 数据库管理系统不考虑它 们。磁带（第三级存储）， 是顺序存取设备，常脱 机作为数据归档的存储 设备。磁带（第三级存储）， 是顺序存取设备，常脱 机作为数据归档的存储 设备。访问速度访问速度约为几 秒约为几 秒-几分，几分，容量容量为为GB- TB。

7、光盘，有只读和可擦写 光盘。 光盘，有只读和可擦写 光盘。 CPU不能对辅存中的数 据进行操作，必须首先 把数据复制到主存。不能对辅存中的数 据进行操作，必须首先 把数据复制到主存。Flash Memory闪存是使用电可擦写可编 程只读存储器技术的设 备，优点是速度快，非易 失，容量从数闪存是使用电可擦写可编 程只读存储器技术的设 备，优点是速度快，非易 失，容量从数M到数到数G， 缺点是必须整块擦除或写 入。， 缺点是必须整块擦除或写 入。6.1数据的物理存储数据的物理存储 6.1.1存储介质存储介质Storage Size10-910-610-310-0103 access time (s

8、ec)101510131011109107105103cacheelectronic mainelectronic secondarymagnetic optical disks online tapenearline tape zhanghua; wuyi; 2）记录长度指示器3）记录位置表?Microsoft Office Access将存储在表中的数据划分 成大小为2 K的数据页，每个页面包含了一个或多个 记录，但记录不能跨越页面。Microsoft Office Access将存储在表中的数据划分 成大小为2 K的数据页，每个页面包含了一个或多个 记录，但记录不能跨越页面。?Acces

9、s采用可变长记录作为标准存储方法，并且可 以通过主关键字来对记录进行排序。因为长度可 变，所以每个记录都只占据了存储它的实际数据所 需的空间。Access采用可变长记录作为标准存储方法，并且可 以通过主关键字来对记录进行排序。因为长度可 变，所以每个记录都只占据了存储它的实际数据所 需的空间。?每个页都包含一个头指针，用以创建数据页链表。 头指针中包含了两个指针，一个指向它的前驱页 面，另一个指向它的后续页面。每个页都包含一个头指针，用以创建数据页链表。 头指针中包含了两个指针，一个指向它的前驱页 面，另一个指向它的后续页面。?新的数据将被添加到表的最后一页，这个页面被填 满后，则再增加一个页

10、面。新的数据将被添加到表的最后一页，这个页面被填 满后，则再增加一个页面。?Memo和OLE Object字段在页中可以跟记录中的其余 部分分开存储。Memo和OLE Object字段在页中可以跟记录中的其余 部分分开存储。6.2 文件的组织方式?无序文件?顺序文件?散列文件一、无序文件无序文件1.结构结构：按数据记录到达文件的 时间顺序依次存储数据。：按数据记录到达文件的 时间顺序依次存储数据。 2.查找查找: 顺序扫描。顺序扫描。 插入插入: 新纪录从未用空间始 地开始存放。新纪录从未用空间始 地开始存放。 删除删除: 作删除标记。作删除标记。 3.用途用途：日志文件，临时文件， 数据装入

11、的初始文件。：日志文件，临时文件， 数据装入的初始文件。未用 空间二、顺序文件二、顺序文件逻辑上按某一关键字（一般为主关键字）顺 序排列的文件。逻辑上按某一关键字（一般为主关键字）顺 序排列的文件。 1.物理结构物理结构 1）向量结构，地址连续的空间，地址 顺序实现逻辑顺序。）向量结构，地址连续的空间，地址 顺序实现逻辑顺序。 2）链结构，指针维持逻辑顺序。）链结构，指针维持逻辑顺序。 3）块链结构，块中地址顺序表示逻辑 顺序，块间指针链接维持逻辑顺序。）块链结构，块中地址顺序表示逻辑 顺序，块间指针链接维持逻辑顺序。2. 查找1）顺序扫描（）顺序扫描（向量结构、链结构、块链结构）向量结构、链

12、结构、块链结构） 2）分块查找（）分块查找（向量结构、块链结构）向量结构、块链结构） 3）折半查找（）折半查找（向量结构）向量结构） 4）探查（）探查（向量结构）向量结构）顺序文件3. 维护维护块中后续记录 前移 块合并修改指针后续记录上移 删除标记删除移动块中后续 记录 块分裂修改指针移动后续记录 溢出指针 预留空间插入块链链向量结构块中后续记录 前移 块合并修改指针后续记录上移 删除标记删除移动块中后续 记录 块分裂修改指针移动后续记录 溢出指针 预留空间插入块链链向量结构顺序文件顺序文件三、HASH文件三、HASH文件1. 基本思想为基本思想为HASH文件准 备的存储空间分为主 数据区、

13、溢出区。 主数据区由文件准 备的存储空间分为主 数据区、溢出区。 主数据区由M个桶 组成， 编号：个桶 组成， 编号： 0，1，-,M1 利用记录的关键 字利用记录的关键 字k, 计算 该记录应存 储的桶号计算 该记录应存 储的桶号H(k)，是一 种关键字变地址的文 件组织方法。，是一 种关键字变地址的文 件组织方法。M1210地址桶号主数据区溢出区HASH文件HASH文件2. HASH方法的步骤方法的步骤 3. 溢出处理溢出处理开寻址列 分离溢出区 分布溢出区开寻址列 分离溢出区 分布溢出区 4. 溢出分析溢出分析 5. 主要主要HASH算法算法M1210地址桶号地址桶号主数据区主数据区溢出

14、区溢出区6. 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术1）动态）动态HASH2）可扩展）可扩展HASH3）线性）线性 HASHHASH文件文件两个基本点：两个基本点：00110101(a) 使用使用b位哈希函数值的高位哈希函数值的高i位：位： b h(K) use i 随时间增长 随时间增长.(b) 用目录用目录h(K)i to bucket.有两种实现方法有两种实现方法6. 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术桶号以二进制整数表示，开始时所有 记录放在一个桶中。当一个桶溢出时分裂 为两个桶：桶号最高位为0的放在一个桶 中，桶号最高位为1的放在另一个

15、桶中。当 这些桶中又有某个溢出时，该桶又分裂为 两个桶按次高位为0的放在一个桶中，次高 位为1的放在另一个桶中。桶号以二进制整数表示，开始时所有 记录放在一个桶中。当一个桶溢出时分裂 为两个桶：桶号最高位为0的放在一个桶 中，桶号最高位为1的放在另一个桶中。当 这些桶中又有某个溢出时，该桶又分裂为 两个桶按次高位为0的放在一个桶中，次高 位为1的放在另一个桶中。1）动态）动态HASH目录数据桶0 0 0 - - -0 0 1 - - -0 1 - - -1 0 0 - - -1 0 1 - - -1 1 - - -000001 11 1 16. 支持文件空间动态变化的支持文件空间动态变化的HA

16、SH技术技术2）可扩展）可扩展HASH其思想与动态HASH差不多，它维持 一个数组目录，相当于动态HASH二叉树 目录的叶结点集合。其思想与动态HASH差不多，它维持 一个数组目录，相当于动态HASH二叉树 目录的叶结点集合。目录局部深度数据桶目录局部深度数据桶d=3d=3d=2d=3d=3d=21 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0全局深度全局深度d=3 6. 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术Example: h(k) is 4 bits; 2 keys/bucketi=11100011001 1100Insert 10101 11001010New directory200011011i=221 00012 1001 10102 1100Insert:01110000000110112i =Example continued011100000111000122000110112i=2