第五章数据库的存储结构

第五章数据库的存储结构内容摘要：

标记 堆文件 记录 1 记录 2 记录 3 记录 5 记录 6 记录 4 记录 7 记录 8 堆文件 记录 1 记录 3 记录 5 记录 6 记录 4 记录 7 记录 8 记录 2 堆文件 记录 1 记录 3 记录 5 记录 7 记录 8 集中删除记录，并进行记录重排 解决方法 直接文件中，将记录的某一属性用散列函数直接映射成记录的地址，被散列的属性称为散列键。 Student(SNO,SNAME,SEX,BIRTHDATE,DEPT) 散列函数 H(SNO)=Address 900412 李林 … 计算机系 H(900412)=@addr @addr 存储空间 900412 李林 … 计算机系  键所映射的地址范围固定 （地址范围设的太大或太小都不好 ,为什么。 ）。 上述原因导致直接文件目前在数据库系统中使用不多。 直接文件存在的问题：  地址重叠问题 （处理地址重叠增加了开销）。  直接文件只对散列键的访问有效。  不便于处理变长记录。  对于通用的 DBMS很难找到通用的散列函数。 索引相当于一个映射机构，把关系中相应记录的某个（些）属性的键值转换为该记录的存储地址（或地址集）。 @addr1 @addr2 @addr3 … … SNO Address 学生表的索引文件 900412 @addr2 900417 @addr1 900418 @addr3 存储空间 900418 周力 … 计算机系 900412 李林 … 计算机系 900417 陈燕 … 计算机系 … …  索引与散列的区别 ——索引文件有记录才占用 存储空间，使用散列空文件也占用全部文件空间。  索引本省占用空间，但索引一般较记录小得多 针对非散列键和非索引属性的访问，都不能有效发挥直接文件或索引文件的优势。 散列或索引失效时，两者谁的访问代价更大。 —— 以主键为索引键 (primary index)。 —— 以非主键为索引键 (secendary index)， 建立次索引可以提高查询的效率，但增加了索引维护的开销。 —— 主索引 +次索引的极端情况（文件的所有属性上都建立索引），有利于多属性值的查找，但数据更新时开销很大。 为了便于检索，索引项总是按索引键排序。 受按门牌号找住户的启示（ 住户在 “ 物理 ”上按门牌号码排序 ），提出 非稠密索引。 注意：索引项 记录 ,并不是文件中的记录按索引键排序 文件中的记录按索引键排序吗。  非稠密索引与稠密索引 —— 非稠密索引 ，代价是文件要按索引键排序 ，只能为一个索引键（一般为主键）建立非稠密索引 （为什么。 ） ，若干个记录组成一个单元存储区，单元存储区中的记录按索引键排序。 ，可向溢出区溢出（用指针指向溢出区），但溢出太多时，指针链接次数增加，将导致数据库性能下降。 （ 通常最高一级索引应尽量保证可以常驻内存 ）。 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 单元存储。