数据库系统概念：存储和文件结构.pdf

数据库系统概念：存储和⽂件结构 ⽂章⽬录 1、基本概念 1、内存数据库与磁盘数据库的特征⽐较 内存数据库 内存数据库 磁盘数据库 磁盘数据库 存取时间 s 量级 s 量级 数据存储 不需要连续存储 连续存储 缓冲管理 不需要 需要 索引结构 哈希，AVL树，T树，B树 B树，B+树，Hash 并发控制 ⼤粒度锁 细粒度锁加锁，解锁，死锁检测 查询优化 基于处理器代价以及 cache 代价 基于 I/O 代价 2、LRU： Least Recently Used，该算法的设计原则是，如果⼀个数据在最近⼀段时间没有被访问到，那么在将来它被访问的可能性也很 ⼩，也就是说，当限定的空间已经存满数据时，应当把最久没有被访问到的数据淘汰。 2、⽂件组织 ⼀个数据库被映射到多个不同的⽂件，这些⽂件由底层的操作系统来维护。⽂件在逻辑上是数据记录的集合，⽂件的结构取决于所属的⽂件 系统。 块（block） 是数据在⽂件中存储和读取的基本单元，其⼤⼩固定，⼤多数数据库默认使⽤ 4~8KB 的块⼤⼩，在创建数据库实例时，有些 数据库允许指定块的⼤⼩，要根据数据的特征来决定多个的块更合理。 ⼀个块可能包含多条记录，对于⼤数据，⽐如图⽚，视频等，⽐块要⼤得多，需要单独存储，并在记录中保存指向⼤数据的指针。 每条记录都存储在相同的块中，不能⼀部分在 A 块中，另⼀部分在 B 块中，这样的设计能简化并加速数据访问。 关系型数据库中，不同表的记录通常具有不同的⼤⼩，这时数据库可以选择映射到多个⽂件中，同⼀⽂件中只存储固定长度的记录；也可以 构建特殊的⽂件，⽀持容纳不定长度的记录。很显然，后者实现起来更复杂。 2.1 定长记录 定长记录占⽤固定⼤⼩的存储空间，管理上⽐较简单，有两点需要注意： 单条记录不能跨 块 存储，⼀个块上只能存储整数个记录； ⽂件中的记录是连续存储的，在删除记录后，需要对剩余的记录进⾏整理，不然会出现⼤量零碎的空闲空间。 记录整理⼤体有两个⽅向： 1. 移动填充： 当删除记录时，移动剩余的记录，使存储保持连续；可以把后续的记录往前移，使⽂件中存储的记录依然保持连续；也可 以把最后⼀个移过来，填充删除的记录所在的位置。 2. 空闲列表： 在⽂件头维护⼀个空闲列表，在删除记录时，将其所在的位置添加到空闲列表中，在下⼀个记录插⼊时再填充。 10 8 10 3 对定长记录⽂件的插⼊和删除是容易实现的，因为被删除记录留下的可⽤空间恰好是插⼊记录所需的空间。 2.2 变长记录 数据库⽂件中使⽤变长记录的场景： 1. 多种记录类型在⼀个⽂件中存储； 2. 允许⼀个或多个字段是变长的记录类型； 3. 允许可重复字段的记录类型，例如数组或多重集合； 实现变长记录需要解决两个问题： 1. 如何存取块中的记录：在块中如何存储变长记录，使得块中的记录可以轻松地抽取； 2. 如何存取记录中的属性：如何描述⼀条记录，使得单个属性可以轻松地抽取； . 1、下⾯是⼀条变长记录，它包含了四个部分； 空值位图⽤来表⽰记录中的按个属性是空值， 0000 表⽰四个属性都不为空， 0010 表⽰第三个属性的值为空。这⾥需要注意，空值位图之 前的部分为记录的 定长部分 ，⽆论哪个属性为空，这个结构的⼤⼩从始⾄终都是不变的，当某个属性为空值时，只表明可以忽略其所对应 的 定长部分 对应的值。 也有⼀些设计中，空值位图存储在记录的开头，并且对空属性不存储数据（值或偏移量/长度），这种⽅式是典型的 时间换空间 设计，对于 稀疏型记录⽐较有效。 2、分槽的页结构（slotted-page structure）⼀般⽤于在块中组织记录： 分槽页结构 是 变长记录 的存储管理技术中的⼀种，⽤于在块中组织记录。 每个块的开始处有⼀个块头，块头中包含的信息有： 块头中已经存储的记录的条⽬个数； 块中空闲空间的末尾地址； 条⽬数组，每个条⽬中存储了该条⽬所对应变长记录的⼤⼩和地址； 记录在块中是从后往前连续存储的， 空闲空间 处于 块头 和 记录 之间，当插⼊新的记录时，记录的 (⼤⼩，位置) 对应的 entry 添加 到块头的末尾，记录本⾝的值添加空闲空间的末尾。 2.3 ⽂件中记录的组织 ⽂件中记录组织的⼏种⽅式： 堆⽂件组织（heap file organization）：⼀条记录可以放在⽂件中的任何地⽅，只要那个地⽅有空间存放这条记录，记录是没有顺序 的，通常每个关系使⽤⼀个单独的⽂件。 顺序⽂件组织（sequential file organization）：记录根据其 search key 的值顺序存储。 散列⽂件组织（hashing file organization）： 在每条记录的某些属性上计算⼀个散列函数，散列的结果确定了记录应放到⽂件的哪 个块中。 通常，每个关系的记录⽤⼀个单独