文件组织和索引

大家好，我是讯享网，很高兴认识大家。

文件组织和索引（File Organization and Indexing）

文件组织

数据库存储为操作系统文件(file) 的集合，每个文件是一连段记录(record) 序列，记录是一连段字段(field)序列
从O/S的角度来看，每个文件都由固定长度的块(blocks)（也称为物理记录(physical record)）组成。块是存储分配和数据传输的单元(units)
一种方法:假设记录大小是固定的，每个文件都有一种特定类型的记录，只有不同的文件用于不同的关系

固定长度的记录

简单的方法

从字节n*(i-1)开始存储记录i,其中n是记录的内存大小
记录访问很简单，但记录可能跨越块. 修改：不允许记录跨越块边界

在这里插入图片描述
讯享网
删除记录i：不同的选择：

移动记录i + 1，…，n到i，…，n-1
移动记录n到i
不移动记录，但链接所有自由记录到一个自由链表上

在这里插入图片描述

文件中的记录的组织

堆(heap)-记录可以放置在文件中有空间的任何地方
顺序记录(sequential)-根据每个记录的搜索键的值，按顺序存储记录
在一个多表集群文件(multitable clustering file organization)中，多个不同关系的组织记录可以存储在同一个文件中. 动机：将相关记录存储在同一块上，以最小化I/O
B+树文件组织(B+tree file organization) 有序的存储，即使有插入/删除
哈希(hashing) 根据搜索键计算的哈希函数；结果指定应将记录放置在文件的哪个块中

顺序文件组织

顺序和二进制搜索

对于N个项目的顺序搜索，比较的平均次数E (X)为≈N/2
假设每一项具有相同的为要求项的概率（即1/N），则第一项的概率为1/N为要求项，第二项的概率为1/N为要求项，以此类推，在找到要求项后，搜索将终止：
$\frac{1}{N}+ \frac{2}{N}+...+ \frac{N}{N}\\ \frac{1}{N} \sum_{i=1}^N k = \frac{N+1}{2}$

二进制搜索N个排序项，最大比较次数k为 $log_2N$
考虑一条长度为N的线，并一直将长度划分为两个，直到只剩下一个项
$\frac{N}{2^k} = 1 \Rightarrow N = 2^k \Rightarrow k = log_2N$

删除-使用指针链

插入-定位要插入的记录的位置

如果有可用空间，则插入其中
如果没有可用空间，则在溢出块中插入记录。
在任何一种情况下，都必须更新指针链

需要不时地重新组织文件，以恢复顺序和顺序

在这里插入图片描述

多表集群文件组织

使用多表群集文件组织在一个文件中存储多个关系
在这里插入图片描述

适用于涉及部门(department) $\Join$ 讲师(instructor)查询，以及涉及单个部门及其讲师的查询
不利于只涉及部门的查询
在可变大小的记录中产生的结果
可以添加指针链来链接一个特定关系的记录吗

存储器存取

块是存储分配和数据传输的单位
数据库系统试图最小化磁盘和内存之间的块传输的数量。我们可以通过在主存中保留尽可能多的块来减少磁盘访问的次数
缓冲区(buffer)-可用于存储磁盘块副本的主存部分
缓冲区管理器(buffer manager)-负责在主内存中分配缓冲区空间的子系统

块的缓冲

双缓冲区可用于读取连续的块流
使用两个缓冲区，A和B，为从磁盘读取
超过2个缓冲区可以使用

在这里插入图片描述

索引条目(index entry)

索引机制用于加快对所需数据的访问速度。例如:图书馆的作者目录
搜索键(search key)-指向用于查找文件中的记录的一组属性。
索引(index)是一个由指针-搜索键形式的记录(称为索引条目(index entry))组成的文件(file)
索引文件通常比原始文件要小得多

有序的索引

在有序索引中，索引条目存储在搜索键值上进行排序
主索引： 在按顺序排列的文件中，其搜索键指定文件的顺序. 主索引的搜索键通常是主键，但不一定是主键
二级索引： 搜索键指定与文件搜索顺序不同的顺序. 关键值可能是唯一的，也可能不是唯一的
索引顺序文件(ISAM – Indexed Sequential Access
Method)：在搜索键上排序的顺序文件，在搜索键上带有索引

密集的索引文件

密集索引: 显示针对文件中的每个搜索键值的索引记录，例如讲师(instructors)关系的ID属性上的索引
在这里插入图片描述
在dept_name上的密集索引，教师文件按dept_name排序

稀疏索引： 仅包含某些搜索键值的索引记录。适用于在搜索键上按顺序排序的记录
要找到搜索键值为K的记录，我们先找到索引中搜索键值比K小的最大值的记录，从索引记录指向的记录依次开始
在这里插入图片描述

二级索引(Secondary Index)

指导教师工资领域的二级指标

在这里插入图片描述

索引记录指向一个桶，该桶包含指向具有该特定搜索键值的所有实际记录的指针。

主索引

在这里插入图片描述

聚类索引

聚类字段: 记录在非键字段上进行物理上的排序，每个记录都没有不同的值

在这里插入图片描述

Dept_number上的聚类索引，它是雇员(Employee)文件的排序非键字段

密集二级索引

文件的非排序键字段上的密集二级索引（和块指针）。
在这里插入图片描述

多级索引

如果索引不适合于内存，访问将变得昂贵
解决方案：将保存在磁盘上的索引视为一个顺序文件，并在其上构造一个稀疏索引
外部索引-基本索引的稀疏索引
内部索引-基本索引文件
如果是外部索引太大，无法容纳主存，则可以创建另一个级别的索引，以此类推
在从文件中插入或删除时，必须更新所有级别的索引

两级ISAM（(indexed sequential access method, 索引顺序访问方法）组织.

在这里插入图片描述