记录的存储结构记录是目前商用数据库的基本数据单元.PPT

第五章 数据库的存储结构 5.1 数据库存储介质的特点 采用多级存储器，用的最多的辅存是磁盘。 光盘由于速度和价格上的原因，近期无法取代硬盘。 磁带是顺序存取存储器，通常用作后备存储器。 活动头磁盘的存取时间由三部分组成：寻道时间、等待时间以及传输时间。 磁盘上的数据划分为大小相等的物理块。磁盘与内存间的数据交换以物理块为单位。 一般，在磁盘和内存之间设立缓冲区以解决二者的速度不匹配问题。 5.2 记录的存储结构 记录是目前商用数据库的基本数据单元，有定长和变长之分。 记录的存储结构 5.2.2 记录在物理块上的分配 磁盘上，记录必须分配到物理块中。 　 5.2.3 物理块在磁盘上的分配 早期的DBMS中，通常由操作系统分配数据库所需的物理块，逻辑上相邻的数据可能被分散到磁盘的不同区域。使得访问数据时，性能下降。 现代DBMS中，都改由DBMS初始化时向操作系统一次性的申请所需的存储空间。 1、连续分配法（contiguous allocation） 3、簇集分配法（clustered allocation） 上述两种方法的结合。 数据压缩技术 5.3 文件结构和存取路径 5.3.1 访问文件的方式 5.3.2 数据库对文件的要求 一些DBMS就以OS的的文件管理系统作为其物理层的基础，更多的DBMS不用OS的文件管理系统，而是独立设计其存储结构。原因如下： 5.3.3 文件的基本类型 不同类型的访问各有其使用的文件结构和存取路径。DBMS通常提供多种文件结构，供数据库设计者选用。 1.堆文件 最简单、最早使用的文件结构。记录按其插入的先后次序存放（所有记录在物理上不一定相邻接） 堆文件插入容易、查找不方便（所提供的唯一存取路径就是顺序搜索） 2.直接文件 直接文件中，将记录的某一属性用散列函数直接映射成记录的地址，被散列的属性称为散列键。 3.索引文件 非稠密索引与稠密索引 示例 查找索引键为211的记录的存储地址 稠密索引（dense index） 每个键值对应一个索引项——稠密索引。 稠密索引的预查找功能（用记录的地址代替记录参与集合运算，减少I/O次数）。 索引溢出的问题 1.稠密索引中，若键值不唯一，则在最低级索引中，每个键值对应的可能是一个地址集（对应多个记录）。如果这些记录分散在不同的物理块内，稠密索引的优点并不能体现出来（并不一定能减少I/O）。 常用索引总结 5.4 动态索引 从数据结构角度看：静态索引是个多分树；动态索引是一种平衡多分树（即B-树），常用B+树。 要找键值KX所对应的记录时，从索引树的根开始，按下面的规则自上而下地搜索： 索引集与顺序集的联系 B+树实现的主索引稍加修改后也可用于次索引（把顺序集结点的tid换成指针，因为一个键值可能对应多个tid）。 B+树实现的各种索引都是稠密索引（非稠密索引的概念源于静态索引），提供了顺序搜索的功能，这是它的优点。 搜索B+树所需的I/O次数决定于其级数。 B+树提供3种存取路径： 1.通过索引集进行树形搜索 2.通过顺序集进行顺序搜索 3.先通过索引找到入口，再沿顺序集顺 序搜索 索引相当于一个映射机构，把关系中相应记录的某个（些）属性的键值转换为该记录的存储地址（或地址集）。 @addr1 @addr2 @addr3 … … SNO Address 学生表的索引文件 900412 @addr2 900417 @addr1 900418 @addr3 存储空间 900418 周力 … 计算机系 900412 李林 … 计算机系 900417 陈燕 … 计算机系 … … 索引与散列的区别——索引文件有记录才占用 存储空间，使用散列空文件也占用全部文件空间。 索引本省占用空间，但索引一般较记录小得多 针对非散列键和非索引属性的访问，都不能有效发挥直接文件或索引文件的优势。散列或索引失效时，两者谁的访问代价更大？ 1.主索引——以主键为索引键(primary index)。 2.次索引——以非主键为索引键(secendary index)，建立次索引可以提高查询的效率，但增加了索引维护的开销。 3.倒排文件——主索引+次索引的极端情况（文件的所有属性上都建立索引），有利于多属性值的查找，但数据更新时开销很大。 为了便于检索，索引项总是按索引键排序。 受按门牌号找住户的启示（住户在“物理”上按门牌号码排序），提出非稠密索引。 注意：索引项?记录,并不是文件中的记录按索引键排序 文件中的记录按索引键排序吗？ 1.不为每个键值设立索引项的索引——非稠密索引 2.可