第5章数据库存储技术.ppt

1 数据库技术及应用 第5章数据库存储技术 2 物理存储介质文件组织文件中记录的组织数据字典的存储数据库中的索引顺序索引B 树索引文件散列文件组织散列索引顺序索引和散列索引的比较多码访问小结 本章知识点 3 5 1物理存储介质 5 1 1三级存储体系5 1 2磁盘5 1 3RAID5 1 1第三级存储 4 DBMS总体结构回顾 磁盘存储器 日志 5 5 1 1物理存储介质 认识存储介质 成本与速度 随机存取顺序存取 联机与脱机 存储容量存储易失性 6 5 1 2磁盘 基本术语 7 5 1 2磁盘 磁盘的物理特性磁道 盘片的表面被逻辑地划分为磁道 扇区 磁道又被逻辑地划分为扇区 扇区是从磁盘读出和写入数据的最小单位 通常大小为512字节 物理块 一个盘片的一条磁道内几个连续的扇区构成的序列称为物理块 一般也简称块 数据在磁盘和主存储器之间以块为单位传输 8 5 1 2磁盘 磁盘的块存取磁盘的I O请求指定了要存取的磁盘地址 这个地址是以块号的形式提供的 页号与块号的对应数据库的文件管理器将块地址转换成硬件层的柱面号 盘面号和扇区号 数据库缓冲区数据库的文件管理器只负责将包含用户需要的数据所在的块缓存到主存储器里的数据库缓冲区 或者执行相反的操作 当新的数据从磁盘到缓存时 根据缓冲区替换策略来安排数据的位置 9 5 1 2磁盘 磁盘质量的度量标准容量大小存取时间 从发出读写请求到数据开始传输之间的时间 存取时间 寻道时间 旋转等待时间 数据传输率 从磁盘获得数据或者向磁盘存储数据的速率 即I O吞吐量 可靠性性价比 10 5 1 3RAID 早期的RAID经济因素是主要原因 因此 RedundantArraysofInexpensiveDisks 中文称为 廉价磁盘冗余阵列 现在的RAID价格已经不是主要因素 而磁盘的性能 数据传输率 和可靠性是考虑的主要内容 因此 RedundantArraysofIndependentDisks 中文称为 独立磁盘冗余阵列 未来的RAID 真正的百年存储 11 5 1 3RAID 如何提高磁盘的可靠性 引入冗余是解决可靠性问题的有效方法 存储一些通常情况下不需要的额外信息 这些信息可在发生磁盘故障时用于重建丢失的信息 实现冗余的方法实现冗余最简单 但最昂贵的方法 复制每一个磁盘 这种技术称为磁盘镜像或磁盘影像 一个逻辑上的磁盘由两个物理磁盘组成 并且每一个写操作都要在两个磁盘上执行 实现冗余的第二种方法是存储奇偶校验位 12 5 1 3RAID 如何提高磁盘的性能通过在多个磁盘上对数据进行拆分来提高传输率 原因是可以对多个磁盘并行存取 拆分的方法比特级拆分 数据拆分的最简单形式是将每个字节按比特位分开 存储到多个磁盘上 块级拆分 在块级拆分中 文件的块被拆分存储到多个磁盘上 如果有n个磁盘 则文件的第i块被存储到第 imodn 1个磁盘上 13 5 1 3RAID RAID级别镜像 拆分 奇偶校验构成了RAID的不同方案 14 5 1 3RAID 如何正确选择RAID级别由于RAID2和4被RAID3和5所包容 因此只需要在RAID0 1 3 5和6之间作出选择 RAID0 用于可容忍数据丢失的高性能应用 RAID1 用于存储类似数据库日志的应用 因为它提供了最好的写性能 同时又保证可靠性 RAID3 用于存储大量数据 并提供高的数据传输率 RAID5 用于存储大量数据 且随机读的效率很高 大多数数据库系统都属于这种情况 RAID6 提供比RAID5更高的可靠性 但很多RAID实现并不支持RAID6 15 5 1 4第三级存储 传统上 光盘和磁带主要用于备份和归档数据 因此它们一般都是离线 off line 的存储介质 随着数据的不断膨胀 数据越来越多 我们称之为海量信息 在当前 我们主要用光盘塔或磁带库来存储海量信息 并且使它们变成近线 near line 或在线 on line 的存储介质 也就是说 跨过二级存储设备在内存和光盘或磁带之间直接传输数据 16 5 2文件组织 5 2 1定长记录5 2 2变长记录5 2 3数据库与文件管理 17 DBMS的底层 物理层 在处理I O问题时 把数据看成是 页 的集合 具体地说 DBMS的文件管理器把数据看成是页的集合 并且提供分配 回收页和读 写页的命令 通常以磁盘块的大小作为页的大小 以便在一次磁盘I O中就能够完成一页的读 写 DBMS的高层 逻辑层和视图层 把数据看成是 记录 行 的集合 即将关系表中的元组映射成文件的逻辑记录 数据库文件采用两种逻辑记录格式 定长记录和变长记录格式存储 18 首先考虑由有关student记录组成的一个文件 该文件中的记录定义如下 typestudent recordstudent number char 10 student name char 8 department name char 22 end假设每个字符占一个字节 那么一个student记录占40个字节 指数据库文件中所有的记录具有相同 固定 的长度 5 2 1定长记录 19 定长记录的存储用文件的头40个字节存储第一个记录 接着的40个字节存储第二个记录 依次类推 这种结构的问题是 删除一条记录时要么填充被删空间要么标记被删记录 除非块的大小恰好是40的倍数 否则记录会跨块存储 5 2 1定长记录 20 定长记录的维护方案一 删除一条记录时 顺序移动其后的所有记录 插入一条记录则始终在文件的尾部进行 方案二 删除一条记录时 移动最后一条记录到此位置 而插入一条记录则始终在文件的尾部进行 5 2 1定长记录 21 定长记录的维护方案三 删除一条记录时 并不着急移动记录 而是将其加入空闲记录列表 当要插入记录时 使用空闲列表中的记录空间 若没有空闲空间就插入到文件的尾部 5 2 1定长记录 22 定长记录的数据页结构记录的移动引起记录RID变化 如果有外部引用指向被移动的记录 如索引 则这种机制就存在问题 5 2 1定长记录 23 5 2 2变长记录 24 变长记录的存储方法之一 字节流表示法在每个记录的末尾都附加特殊的记录终止符 或者是在每个记录的开头存储该记录的长度 问题 磁盘碎片删除一条记录 记录变长了 记录变短了 方案 移动记录的代价 5 2 2变长记录 25 变长记录的存储方法之二 分槽的页结构用于物理块内部的记录组织 块头部分 块中记录个数 块中空闲空间的末尾地址 描述块中每个记录的大小和位置的数组 块尾部分 实际记录从块的尾部开始连续存储 块中部分 块中空闲空间是连续的 5 2 2变长记录 26 变长记录的存储方法之二 分槽页结构的维护删除一条记录 它所占用的空间被释放 块中在此之前的记录都要移动 而空闲空间还是集中在块中间 插入一条记录 在块中空闲空间的尾部给这条记录分配空间 记录的增长和缩短 该条记录的末尾地址不变 在此记录之前的记录都要移动 块的大小有限制 移动记录的代价并不高 还要修改 5 2 2变长记录 27 变长记录的存储方法之三 定长表示法用一个或多个定长记录来表示一个变长记录 由于所采用的策略不同 定长表示法又分为以下几类 方法之三 1 保留空间法方法之三 2 指针法方法之三 3 锚块 溢出块表示法定长表示法在实际的DBMS当中很少使用 为什么 但至少可以为我们解决其他问题开拓思路 5 2 2变长记录 28 变长记录的存储方法之三 1 保留空间法假设所有的变长记录都不会超过某个长度 就为每个记录都分配这样长度的空间 缺陷 假设不合理 浪费大量存储空间 5 2 2变长记录 29 变长记录的存储方法之三 2 指针法用一系列通过指针链接起来的定长记录来表示一个变长记录 优点 与定长记录类似 变长记录是一个链表 缺点 引入额外结构 浪费存储空间 5 2 2变长记录 30 变长记录的存储方法之三 3 锚块 溢出块表示法指针法的变形 文件使用两种不同的物理块 锚块 包含记录的定长部分和变长部分的第一个分量的块 溢出块 包含记录的变长部分除第一个分量以外的其他分量的块 5 2 2变长记录 31 变长记录的数据页结构删除移动适应性 5 2 2变长记录 32 SQLSERVER2000的页数据页是表的所有非文本数据和文本数据的存储结构 数据页的固定大小为8KB 即8192字节 其中8096字节用于存储数据 其余的96字节用于存储页结构信息 数据页由3个主要的部分组成 它们是 记录不能跨页存储 它的最大长度是8060字节 33 34 在小型关系数据库管理系统中将各个关系存储在一个个独立的文件中 通常 文件中的记录都是定长的 文件结构简单 充分利用了作为OS一部分的文件系统的好处 大型数据库管理系统在文件管理方面并不直接依赖于操作系统 操作系统只分配给DBMS一个大的操作系统文件 所有关系都存储在这个大文件中 它的好处是 有利于提高系统的性能 空间的分配与管理简单 灵活 如簇集文件组织 5 2 3数据库与文件管理 35 SQLSERVER2000的数据库文件组织在MSSQLServer2000中 一个数据库是由三个操作系统文件构成的 它们分别是 主数据文件 MDF次数据文件 NDF日志文件 LDF这些信息都存放在SYSFILES系统表中SQLSERVER2000的数据库文件管理上述数据库文件的管理是由SQLServer自己负责的 而不是依赖于Windows的文件系统 SQLServer有自己的文件管理器 5 2 3数据库与文件管理 36 Oracle数据库的物理文件所有文件由Oracle的文件管理器负责管理和维护 5 2 3数据库与文件管理 Oracle数据库的物理文件有4类 数据文件日志文件控制文件参数文件 37 DBMS一般不用OS的文件管理器 而是独立设计其数据库文件的存储结构 有自己的文件管理器 这有以下5个方面的原因 更多功能与附加信息 DBMS为了实现其功能 须在文件目录 文件头 文件描述块 元数据页 物理块 页头 等部分附加一些信息 传统的文件系统是不提供这些信息的批处理与即席访问 传统的文件系统主要面向批处理 而在DBMS中 往往要求即席访问 动态修改 这就要求文件结构能适应数据的动态变化 提供快速访问路径 如 数据页之间的双向链表 5 2 3数据库与文件管理 38 3 数据共享与并发控制 传统的文件基本上是为某一用户或某类用户服务的 用途比较单一 共享的程度较低 数据库文件是供所有用户共享的 有些用途是不可预知的 这就要求数据库文件的结构能兼顾多方面的要求 提供多种访问路径 并在 并发控制故障恢复数据安全等方面提供支持 4 可移植性与实现的可能性 如果采用操作系统的文件管理器作为DBMS的物理层实现的基础 那么DBMS对操作系统的依赖性太大 不利于DBMS的移植 有些操作系统 如Unix 只提供字符流的存取功能 不提供各种文件结构和存取路径 这些只有靠DBMS自身来实现 39 5 数据的稳定性与动态变化 传统的文件一旦建立以后 数据量是比较稳定的 而且一般只用于只读的应用 数据库文件的数据量变化较大 有些文件在数据模式刚定义时几乎是个空架子 随着应用的开发 数据也不断地增长 数据库文件的结构应能适应这样的变化 数据库中的数据常常要求是可读写的 40 为了能执行每条SQL语句 还必须进一步搞清楚 文件中记录的存储方式与结构如何 文件中记录的组织方式如何 41 5 3文件中记录的组织 5 3 1堆文件组织5 3 2顺序文件组织5 3 3散列文件组织5 3 4聚集文件组织 42 一条记录可以放在文件中的任何地方 只要那个地方有空间存放这条记录 记录是没有顺序的 是堆积起来的 5 3 1堆文件组织 43 根据搜索码值的顺序来逻辑存储记录 搜索码是用于在文件中查找记录的属性或属性集 与码的概念完全不同 为了快速地按搜索码获取记录 通过指针把记录链接起来 每个记录的指针都指向在搜索码顺序上的下一个记录 同时 为了减少顺序文件处理中物理块的访问次数 在物理上也按搜索码值的顺序存储记录 或尽可能地按照搜索码值的顺序来物理存储 5 3 2顺序文件组织 44 顺序文件组织的好处 结构清晰 容易理解 对特定的查询能快速处理 顺序文件组织的问题 插入和删除记录后 首先要保证记录按搜索码的顺序重新链接起来 但是维护记录的物理顺序则将十分困难 如果靠移动记录的方式来维护记录在物理上的顺序 则代价十分昂贵 5 3 2顺序文件组织 45 删除记录 用指针链表来管理删除 插入记录 首先定位要插入的记录按搜索码值排序时它前面那条记录 如果该记录所在的物理块内有空闲空间 就在这个块中插入该记录 否则 将插入到溢出块中 如果溢出块中的记录不多 则这种方式还有效 但记录的搜索码顺序和物理顺序之间的一致性 这时 对记录的顺序处理将明显变得效率低下 随机I O 需要对文件进行重组 时机和代价 5 3 2顺序文件组织 记录的删除与插入 46 对文件中每个记录的同一属性或属性集需要计算一个散列 Hash 函数 散列函数的结果确定了记录应该存储到文件的哪个物理块中 记录虽然没有顺序 但是有去向的 5 3 3散列文件组织 47 问题的提出 假设有两个关系course和selecting 对于它们的自然连接运算 用SQL表达如下 selectstudent number course course name course locationfromcourse selectingwherecourse course name selecting course name 5 3 4簇集文件组织 48 问题的解决 把相关记录放在一个块 或临近块 中存储 一次读块操作就取得所有相关记录 减少了磁盘I O次数 提高了连接的性能 5 3 4簇集文件组织 49 50 何时才考虑使用簇集 通过簇集键进行访问或连接是该表的主要应用 当查询中包含与簇集键有关的ORDERBY GROUPBY UNION DISTINCT等语法成分时 簇集格外有用 可以省去对结果的排序 对应每个簇集键值的平均记录数既不能太少 也不能太多 太少了则簇集的效益不明显 甚至浪费块的空间 太多了就要采用多个溢出块 对提高性能不利 簇集键值应该相对稳定 以减少因修改簇集键而引起的维护开销 5 3 4簇集文件组织 51 元数据的种类到目前为止我们讨论的都是关系 数据 本身的存储问题 实际上更重要的还有有关数据的数据 即元数据的存储问题 如关系模式等 这类信息称为数据字典或系统目录 主要包括以下几大类 有关关系的元数据 有关用户的信息 有关关系的统计数据 有关索引的信息 5 4数据字典的存储 52 系统表数据字典在关系数据库中用类似下面的 被称为系统表 SystemTables 的关系来存放 Attribute schema attribute name relation name domain type position length User schema user name password group Index schema index name relation name index type index attributes SQLServer2000中的系统表sysobjects syscolumns sysindexes 5 4数据字典的存储 Oracle中的系统表 all 视图 user 视图 DBA 视图 V 视图 53 DBMS的物理存储小结 了解数据库的存储结构就必须搞清楚 数据库的文件组织 一个数据库由几个OS文件构成 文件管理器 是DBMS的还是OS自身的 数据库文件自身的结构如何 为了能执行每条SQL语句 还必须进一步搞清楚 文件中记录的存储方式与结构如何 文件中记录的组织方式如何 54 5 5数据库中的索引 5 5 1基本的索引结构5 5 2评价索引的标准 55 索引的目的就是为了能够快速地在文件中定位要访问的记录 当然 理想的做法是系统能够直接定位这些记录 为了实现这种访问数据的方式 需要一些附加结构 索引 并将索引同数据文件联系起来 56 顺序索引 基于对值的一种排序 结构 顺序文件和B树文件散列索引 基于将值平均 随机地分布到若干存储桶中 由1至32个连续的物理块构成的一种存储结构 与物理块不同的是 存储桶只能包含整记录 即记录可以跨块存储但不能跨桶存储 一个值所属的存储桶由一个函数来决定 该函数称为散列函数 也叫哈稀函数 索引结构是散列文件 5 5 1基本的索引结构 57 没有哪一种索引技术是最好的 每种索引都有自己适合的数据库应用 对索引技术的评价必须考虑以下因素 访问类型 能有效支持的数据访问类型 包括根据指定的属性值进行查询 或根据给定属性值的范围进行查询 访问时间 访问一个或多个数据项所需要的时间 插入时间 在文件中插入一个新数据项所需要的时间 包括找到插入该项的正确位置和修改索引所需要的时间 5 5 2评价索引的标准 58 没有哪一种索引技术是最好的 每种索引都有自己适合的数据库应用 对索引技术的评价必须考虑以下因素 删除时间 在文件中删除一个数据项所需要的时间 包括找到待删除项的正确位置和修改索引所需要的时间 更新时间 U D I 在位与异位 空间开销 索引结构所需要的额外存储空间 索引是用空间的代价来换取系统性能的提高 索引实现的难度决定了该索引技术是否实用 能否推广 5 5 2评价索引的标准 59 5 6顺序索引 顺序索引的作用能迅速地按顺序或随机地访问文件中的记录顺序索引的结构在逻辑上按顺序存储搜索码的值 并将搜索码值与包含该搜索码值的记录关联起来 顺序索引的特征一个文件可以有多个索引 对应于不同的搜索码 根据索引结构中搜索码值的逻辑顺序和数据文件中记录的物理存储顺序之间的关系 顺序索引分为主索引和辅助索引 60 基本概念主索引与辅助索引如果数据文件中记录按照某个搜索码指定的顺序物理存储 则该搜索码对应的索引称为主索引或簇集索引 相反 搜索码顺序与数据文件中记录的物理顺序不同的那些索引称为辅助索引或非簇集索引 显然 一个数据文件只能有一个主索引 但可以有多个辅助索引 为什么 堆文件与索引顺序文件没有主索引的数据文件就是堆文件 而拥有主索引的数据文件就是索引顺序文件 5 6顺序索引 61 数据文件中的记录按照某个搜索码值的顺序物理存储 5 6 1顺序索引文件 62 顺序索引的分类按照索引结构中搜索码值与数据文件中搜索码值的对应关系 顺序索引又分为 稠密索引稀疏索引稠密索引 对应数据文件中搜索码的每一个值在索引结构都有一个索引记录 或索引项 它包括 搜索码值 指向具有该搜索码值的第一个数据记录的指针 5 6 1顺序索引文件 63 顺序索引的分类稀疏索引 只为搜索码的部分值建立索引项 与稠密索引一样 每个索引项也包括搜索码值和指向具有该搜索码值的第一个数据记录的指针 问题 如何利用稀疏索引进行查询呢 5 6 1顺序索引文件 64 稠密索引和稀疏索引的比较利用稠密索引通常可以比稀疏索引更快地定位一个记录的位置 与稠密索引相比 稀疏索引占用空间小 插入和删除时的维护开销也小 实践中如何正确地建立稀疏索引 数据库查询的开销主要是由什么来决定的 在主存内扫描整个块的时间是可以忽略的 考虑为每个块建一个索引项的稀疏索引 这样的索引可以定位包含所要查找记录的块 5 6 1顺序索引文件 65 问题的提出 即使采用稀疏索引 索引本身有时也会变得非常庞大而难于有效处理 例如 一个文件有100000条记录 一个块存储10个记录 每个块有一个索引记录 一个块存储100个索引记录 索引过大在读索引时就必须有一部分放在磁盘上 搜索一个索引项就必须多次读磁盘块 当然在索引上可以用二分法来定位索引项 最坏需要读 log2 b 次块 假设索引占据了b个块 如果索引小到一次I O就能够放到主存里 搜索一个索引项的时间就很短 可以忽略不计 5 6 2多级索引 66 问题的解决 像对待其他任何顺序文件那样对待索引结构 即在主索引上再构造一个稀疏索引 形成一个具有内层索引和外层索引的多级索引结构 主索引结构本身就是一个顺序文件 5 6 2多级索引 67 删除数据记录 稠密索引的变化情况 删除数据文件中的 邓婉玲 记录 删除数据文件中 王小丽 的s000005记录 删除数据文件中 王小丽 的s000009记录 5 6 3索引的更新 68 删除数据记录 稀疏索引的变化情况 删除文件中搜索码为 陈舒艺 的记录 删除文件中搜索码为 陈国国 的所有记录 删除文件中搜索码为 冯蔼妍 记录 删除文件中 王小丽 的s000005记录 删除文件中 王小丽 的s000007记录 5 6 3索引的更新 69 插入数据记录 索引的变化情况 若索引是稠密的 并且待插入记录的搜索码值不在索引中 就要把该搜索码值插入到索引中 若索引是为每个块保存一个索引项的稀疏索引 只要没有新块产生 索引就无需做任何改动 在产生新块的情况下 新块中的第一个搜索码值将被插入到索引中 多级索引 删除和插入数据记录时 它的更新同上面类似 内层索引的更新同上 内层索引的变化 引起外层索引按上述算法更新 5 6 3索引的更新 70 在文件中 记录按主索引而不是辅助索引的搜索码值顺序物理存储 具有同一个辅助搜索码值的记录可能分布在文件的各个地方 例如 5 6 4辅助索引 71 5 6 4辅助索引 其结构与主索引的结构是不同的 辅助索引必须包含指向每一记录的指针 辅助索引的指针并不直接指向文件 而是每个指针指向一个包含文件指针的存储桶 存储桶中的每个指针才指向文件中的记录 72 辅助索引的优缺点 可以提高使用利用辅助搜索码查询记录的速度 但辅助索引也大大增加了数据库更新的开销 5 6 4辅助索引 73 5 7B 树索引文件 5 7 1B 树索引结构5 7 2B 树索引的缺点5 7 3B 树上的查询5 7 4B 树的更新5 7 5B 树文件组织 74 索引顺序文件的缺陷性能 索引顺序文件组织最大的缺点在于随着文件的增大 索引查找性能和顺序扫描性能都会下降 文件重组 而且随着频繁的删除和插入记录 就会不断有溢出块出现 记录的物理顺序同主搜索码顺序的一致性就遭到破坏 这样就不得不重组文件 解决方案呢 研究在插入和删除操作很频繁的情况下仍保持有效的索引结构 B 树索引就是其中的一种 5 7B 树索引文件 75 总体结构 是一个多级索引 采用平衡树结构 即每个叶结点到根的路径长度都相同 它的所有结点结构都相同 最多包含n 1个搜索码值K1 K2 Kn 1及n个指针P1 P2 Pn 每个结点中的搜索码值按次序存放 即若i j 那么一定有Ki Kj 每个非叶结点有 n 2 到n个子女 n对特定树是固定的 5 7 1B 树索引结构 76 叶结点 指针Pi i 1 2 n 1 指向具有搜索码值Ki的一个数据记录或一个指针桶 桶中的每个指针指向具有搜索码值Ki的一个数据记录 指针桶只在记录不按搜索码顺序物理存储时才使用指针Pn具有特殊的作用 每个叶结点最多可有n 1个搜索码值 最少也要有 n 1 2 个搜索码值 各个叶结点的搜索码值的范围互不相交 要使B 树索引成为稠密索引 文件中各搜索码值就都必须在某个叶结点中出现且只能出现一次 5 7 1B 树索引结构 77 叶结点 各叶结点按照所含的搜索码值有一个线性顺序 利用指针Pn将叶结点按搜索码顺序链接在一起 这种排序能高效地对文件进行顺序处理 而B 树索引的其他结构能高效地对文件进行随机处理 5 7 1B 树索引结构 78 5 7 1B 树索引结构 79 非叶结点 在含有m个指针的非叶结点中 Pi i 2 m 1 指向一棵子树 该子树的所有结点的搜索码值大于等于Ki 1而小于Ki 指针Pm指向子树中所含搜索码值大于等于Km 1的那一部分 而指针P1指向子树中所含搜索码值小于K1的那一部分 5 7 1B 树索引结构 80 根结点 根结点的结构也与叶结点的结构相同 根结点包含的指针数可能小于 n 2 除非整棵树只有一个结点 否则它至少包含两个指针 5 7 1B 树索引结构 81 5 7 2B 树索引的缺点 B 树的 平衡 Balance 特征保证了B 树索引具有良好的查找 插入和修改性能 但B 树索引也有以下缺陷 B 树索引结构会增加文件插入和删除处理的空间开销 以空间代价换取性能上的优势 B 树索引结构在极端情况下 结点可以是半空的 n 2 到n 这虽然造成了空间浪费 但却保证了性能 B 树索引技术已经被广泛地应用到商业数据库管理系统中 82 5 7 3B 树上的查询 如何利用B 树索引进行查询呢 假设要找出搜索码值为K的所有记录 首先检查根结点 找到大于K的最小搜索码值 假设是Ki 那么沿着指针Pi走到另一个结点 如果K K1 则沿着指针P1走至另一个结点 如果K Km 1 m是该结点的指针数 则沿着指针Pm走至另一个结点 对新到达的结点 重复以上步骤 最终到达一个叶结点 83 举例 利用student关系上的B 树索引 给出在该关系中查找student name为 邓婉玲 的所有记录的过程 5 7 3B 树索引上的查询 84 很烦琐 参阅 数据结构 有关内容 5 7 4B 树的更新 5 7 5B 树的组织 B 树索引通过在叶结点来组织包含真实记录的物理块来解决索引顺序文件组织随着文件的增大而性能下降的缺点 在B 树文件组织中 B 树结构不仅用做索引 同时也是文件中记录的组织者 树叶结点中存储的是记录而不是指向记录的指针 85 5 8散列文件组织 5 8 1散列文件的操作5 8 2散列函数 86 基本概念在前面介绍的索引类型中 必须访问该索引结构 才能在文件中定位记录 而基于散列 Hash 的文件组织能够避免访问索引结构 在散列文件组织中 用存储桶来表示能存储一条或多条记录的一个存储单位 通过计算搜索码上的一个函数 就可以确定包含该搜索码值的记录应该存储在哪个桶中 令K表示所有搜索码值的集合 令B表示所有桶地址的集合 散列函数h就是一个从K到B的映射 h K B或B h K 5 8散列文件组织 87 插入 为了插入一个搜索码为Ki的记录 通过计算h Ki 获得存放该记录的桶地址 于是就把这条记录存入桶中或是相应的溢出桶中 删除 如果待删除记录的搜索码值是Ki 则计算h Ki 然后在相应的桶中搜寻此记录并删除它 基于搜索码值Ki的查找 首先计算h Ki 然后在计算出地址的桶中搜索所有的记录 因为不同的搜索码值对应相同的桶地址正是散列文件组织的最大特点 5 8 1散列文件的操作 88 如果散列函数设计的不好 就有可能把所有的搜索码值都映射到同一个存储桶中 这时散列就失去了意义 因此 对散列函数的基本要求是 分布是均匀的 即每个存储桶从所有可能的搜索码值集合中分配到的值的个数差不多相同 例如将大写英文字母分配到5个存储桶中 分布是随机的 不管搜索码值的实际情况是怎样的 每个存储桶应分配到的搜索码值的个数也差不多相同 例如 假设实际的搜索码值是A B C D E五个字母 5 8 2散列函数 89 举例 假设将26个大写英文字母分布到5个存储桶中 地址从0到4 那么散列函数h该如何设计呢 假设用code A 表示A所对应的编号0 散列函数h code SearchKey mod5 5 8 2散列函数 90 问题的提出散列不仅可以用于数据文件中记录的组织 还可以用于索引中索引项的组织 散列索引 将索引项中的搜索码及相应的指针按散列文件的形式进行组织 散列索引的构造首先将散列函数作用于索引项中的搜索码以确定对应的存储桶 然后将此搜索码及相应的指针存入此存储桶中 而指针指向数据文件中的记录 5 9散列索引 91 举例 为关系student上的student number搜索码建立一个辅助的散列索引 散列函数h是学号各位数字之和后模3该散列索引共有3个桶 每个桶的大小为3 5 9散列索引 92 术语 散列文件 是指用来组织和存储文件中数据记录的散列文件结构 而散列索引是指将文件上的辅助索引的索引项按照散列文件的结构进行组织 不要将二者混淆 如果数据文件自身是按散列组织的 就认为该散列文件已经有了一个 主索引 一般不必在其上另外创建独立的索引结构 散列索引只用来组织数据文件上的辅助索引数据文件上的主索引结构不应该是散列文件索引本身的文件结构有哪些 散列索引小结 93 用索引还是散列 索引和散列都为访问数据提供了存取路径 索引需要通过值的比较 才能确定数据的位置 散列不通过值的比较 而通过值的含义来确定数据的位置的 用索引还是散列实际当中要考虑以下问题 索引或散列的周期性重组代价如何 在文件中插入和删除记录的频率如何 为了优化平均访问时间而导致最坏情况下的访问时间的做法是否可取 能够有效支持的查询类型是哪些 5 10顺序索引和散列的比较 94 散列支持的查询类型支持等值查询 或者叫点查询不支持范围检索散列与索引比较举例之一selectA1 A2 AnfromrwhereAi c顺序索引查找所需要的时间与关系r中Ai值的