第五数据库存储结构.ppt

键所映射的地址范围固定（地址范围设的太大或太小都不好,为什么？）。 上述原因导致直接文件目前在数据库系统中使用不多。 直接文件存在的问题： 地址重叠问题（处理地址重叠增加了开销）。 直接文件只对散列键的访问有效。 不便于处理变长记录。 对于通用的DBMS很难找到通用的散列函数。 3.索引文件 索引相当于一个映射机构，把关系中相应记录的某个（些）属性的键值转换为该记录的存储地址（或地址集）。 @addr1 @addr2 @addr3 … … SNO Address 学生表的索引文件 900412 @addr2 900417 @addr1 900418 @addr3 存储空间 900418 周力 … 计算机系 900412 李林 … 计算机系 900417 陈燕 … 计算机系 … … 索引与散列的区别——索引文件有记录才占用 存储空间，使用散列空文件也占用全部文件空间。 索引本省占用空间，但索引一般较记录小得多 针对非散列键和非索引属性的访问，都不能有效发挥直接文件或索引文件的优势。散列或索引失效时，两者谁的访问代价更大？ 1.主索引——以主键为索引键(primary index)。 2.次索引——以非主键为索引键(secendary index)，建立次索引可以提高查询的效率，但增加了索引维护的开销。 3.倒排文件——主索引+次索引的极端情况（文件的所有属性上都建立索引），有利于多属性值的查找，但数据更新时开销很大。 为了便于检索，索引项总是按索引键排序。 受按门牌号找住户的启示（住户在“物理”上按门牌号码排序），提出非稠密索引。 注意：索引项?记录,并不是文件中的记录按索引键排序 文件中的记录按索引键排序吗？ 非稠密索引与稠密索引 1.不为每个键值设立索引项的索引——非稠密索引 2.可以节省索引的存储空间，代价是文件要按索引键排序 3.对一个文件，只能为一个索引键（一般为主键）建立非稠密索引（为什么？） 4.非稠密索引中，若干个记录组成一个单元存储区，单元存储区中的记录按索引键排序。 5.单元存储区装满后，可向溢出区溢出（用指针指向溢出区），但溢出太多时，指针链接次数增加，将导致数据库性能下降。 6.可以建立多级非稠密索引（通常最高一级索引应尽量保证可以常驻内存）。 1 2 3 4 5 6 7 8 9 10 11 12 121 134 167 182 203 211 223 229 231 237 241 13 14 15 16 … 255 259 267 271 … 单元存储区 182 4 201 223 7 223 241 12 251 271 16 271 289 19 289 311 24 311 419 28 419 430 31 430 单元存储区 最高键值 单元存储最高键值相对地址 最高键值 271 430 601 191 201 249  251 示例 溢出区 溢出链头 指针 相对地址 索引键 第五数据库存储结构 5.1 数据库存储介质的特点 采用多级存储器，用的最多的辅存是磁盘。 光盘由于速度和价格上的原因，近期无法取代硬盘。 磁带是顺序存取存储器，通常用作后备存储器。 数据库是大量、持久数据的集合，在现阶段 用内存作为数据库的存储介质是不合适的。 活动头磁盘的存取时间由三部分组成：寻道时间、等待时间以及传输时间。 磁盘上的数据划分为大小相等的物理块。磁盘与内存间的数据交换以物理块为单位。 以物理块为交换单位的优点： 1).减少I/O的次数，从而减少寻道和等待的时间。 2).减少间隙的数目，提高磁盘空间利用率。 物理快的大小由OS决定。 一般，在磁盘和内存之间设立缓冲区以解决二者的速度不匹配问题。 由于有多个缓冲块可供申请使用，磁盘的读写操作和读写数据的处理可以重叠进行。 读出： i块?缓冲块A 处理： 处理A中i块 i+1块?缓冲块B i+2块?缓冲块A 处理B中i+1块 OS与DBMS都有各自的缓冲区。 不少DBMS采用延迟写与提前读技术，减少I/O，改善性能。 5.2 记录的存储结构 记录是目前商用数据库的基本数据单元，有定长和变长之分。 记录的存储结构 1.定位法——每个字段按其最大可能长度分配定长的 位置 LIbbb MINGbbb MALEbb 1967 5 12 18 2.相对法——每个字段没有固定的长度，而是用特 殊的字符分隔开 LI? MING? MALE? 1967# 问题：字段中也需要用到这些分隔符时，如何进行表示？ 3.计数法——每个字段的开始加上表示该字段长度