数据库存储与架构技术解析

# 数据库存储与架构技术解析 ## 1. 哈希压缩与存储技术 ### 1.1 哈希槽生成 在数据库存储中，有一些关键参数用于哈希槽的生成。设定 `HW = 8`，`H = 10`，`OW = 5`。通过将压缩后的键值 `k` 除以哈希除数 `HD = KMAX / HMAX = 40` 来生成哈希槽 `h`，即 `h = k / HD`。 例如，若原始键值为 `A2505`，经压缩后其等效值为 `1500`，那么其主哈希槽的计算方式为： \[ \frac{1505}{40} + 1 = 38 \text{（将第一个槽计为 1）} \] ### 1.2 插入规则 当要插入一个新的键值时，若第 38 个哈希槽中的 `C < H`（这里 `H = 10`），则将这个新的键值插入到合适的位置；若 `C = H`，则会分配一个溢出哈希槽。 ### 1.3 技术优势 这种技术能确保在最少的磁盘访问次数内找到所需的槽。主页面只需一次磁盘访问即可访问。通过谨慎选择 `HW`，大多数溢出可以位于主页面上，从而减少全局溢出的需求。通过定期重组，可以控制全局溢出。若允许 10% 的记录处于全局溢出状态，那么在哈希树中平均需要 1.1 次磁盘访问，而在 B - 树中则需要 `(n - 1)` 次磁盘访问，对于 3 层及以上的 B - 树，这种节省非常显著。不过，B - 树的自重组能力带来的便利性也需要考虑。 ### 1.4 操作步骤 1. 对原始键值应用压缩技术，得到压缩后的键值。 2. 根据 `h = k / HD` 计算哈希槽。 3. 检查对应哈希槽的 `C` 值，根据 `C` 与 `H` 的大小关系决定插入位置。 ## 2. 数据页拆分技术 ### 2.1 基本原理 该技术基于哈希和页面拆分，用于按主键顺序存储记录，以提供通过该键的快速随机和顺序访问。首先使用合适的算法对主键值进行哈希处理，确定一个数据页，在该数据页中，哈希后产生该值的记录按严格的主键顺序存储。 ### 2.2 页面处理 - **下溢情况**：若出现下溢，页面上未使用的空间会被浪费。 - **溢出情况**：若出现溢出，会附加一个新的空页面作为溢出页。然后将记录按严格的主键顺序重新分配到这两个页面（原页面和溢出页），每个页面接收原页面一半的记录。每次页面溢出时，都会进行这样的拆分和记录重新分配。 ### 2.3 溢出索引 为每个哈希值维护一个小的溢出索引，该索引保存每个溢出页上主键值的范围。要放置一条记录时，先对其主键值进行哈希处理，然后借助溢出索引找到所需的页面。若索引足够小可以保存在内存中，那么通过主键可以在一次磁盘访问中随机检索到记录。 ### 2.4 优缺点分析 - **优点**：该技术按主键顺序存储记录，并能提供非常快速的按此顺序的访问。 - **缺点**： - 存储利用率可能较低，大概在 70% 左右。 - 在包含许多页面和溢出的大文件中，溢出索引可能太大而无法放入内存。 - 对于二级键访问存在问题。若支持 `(二级键, 存储位置)` 索引，每次页面拆分后该索引都需要大量重组；若使用 `(二级键, 主键)` 索引，除非主键较小，否则二级键索引可能会变得很大且效率低下。 ### 2.5 适用场景 数据页拆分技术在主键较短或二级键访问不太重要的相对小文件中可以有效使用。 ### 2.6 操作步骤 1. 对主键值进行哈希处理，确定数据页。 2. 检查页面是否溢出或下溢。 3. 若溢出，附加溢出页并重新分配记录。 4. 维护溢出索引，通过索引和哈希值定位记录。 ## 3. 数据库架构的三个基本层次 ### 3.1 概念模式 数据库设计的第一步是分析实体的特征，包括数据、数据关系和使用约束等，并将其分类以便深入理解，然后将这种理解转化为基于类型和相关规则的正式描述，这个正式描述就是概念模式，它代表了感兴趣的信息模型。 ### 3.2 内部模式 在考虑相关的计算机存储结构和操作效率时，设计者需要关注如何将概念模式中描述的实体特征高效地组织和存储在具有固定结构硬件（通常是磁盘）的计算机中。这个过程的最终结果是存储或内部模式，它将概念模式的内容映射到计算机的实际情况。内部模式的很多部分相当于 COBOL 程序的文件描述，由操作系统进行处理。 ### 3.3 外部模式 为了让用户程序能够访问数据库，引入了用户视图或外部模式。外部模式描述了特定应用所需的数据（并非数据库的所有数据），并以对该应用最方便的形式呈现。 ### 3.4 层次关系 这三个层次（概念、内部和外部）构成了现代数据库架构的基础。只有一个概念模式和一个内部模式，但可以有多个外部模式，每个外部模式对应一种需求类型。 ### 3.5 操作步骤 1. 分析实体特征，构建概念模式。 2. 根据概念模式设计内部模式，考虑存储和操作效率。 3. 为不同应用设计外部模式，实现用户程序与数据库的接口。 ## 4. 实体特征分析 ### 4.1 基本概念 #### 4.1.1 实体 实体是我们存储数据的对象，如人、书、地点、事件、想法甚至关系都可以是实体。相似的实体组成实体类型，例如“人”这个实体类型涵盖了所有的人，而一个具体的人（如名为 Smith 的人）则是一个实体实例。实体的定义取决于我们的主观判断和感知，一个颜色可以是实体（当我们关注其属性时），也可以是另一个实体的属性。 实体之间存在依赖关系，可分为外在依赖和内在依赖。例如，在一个组织中，员工实体的存在依赖于部门实体的存在，这是外在依赖；而学生和课程之间的关系实体只有在学生和课程这两个相关实体都存在时才能存在，这是内在依赖。实体还可以呈现层次结构，如铅笔、橡皮、钢笔等可以归为文具实体。 #### 4.1.2 属性 我们收集的关于实体的数据就是其属性，每个属性是一个属性类型的值。对于“人”这个实体类型，人名、部门编号、员工编号、驾照编号、工资、职位头衔等都是属性类型，由各自的属性名称描述。对于名为 Smith 的具体人，其对应的属性值可以是 `Smith`、`Dept10`、`E10`、`SMT3812314001`、`6000` 和 `programmer`。属性可以唯一标识实体，如员工编号和驾照编号通常是唯一标识，但人名通常不是。如果员工编号仅在部门内唯一，那么 `(部门编号, 员工编号)` 组合将是唯一标识符。我们可以选择一个唯一标识符来代表实体，这个标识符可以是复合的，称为实体标识符。实体记录是实体属性的集合。 当实体记录在计算机中表示时，同一个属性名可能有不同的属性名称，例如“员工编号”在不同的记录类型中可能被命名为 `ENO`、`EMPNO` 或 `ENUM`，属性名与属性名称之间存在一对多的关系。属性还可以呈现层次结构，如“日期”可以由日、月、年三个属性构成，也可以由日编号和年两个属性构成。 #### 4.1.3 关联 关联表示实体之间的一对一（`1:1`）、一对多（`1:n`）和多对多（`m:n`）关系，如父亲和母亲之间是 `1:1` 关系，部门和员工之间是 `1:n` 关系，学生和课程之间是 `m:n` 关系。关联体现了逻辑关系，一个实体可以参与多个关联。实体之间还存在关联层次结构，例如组织中的部门和员工之间的关联可以形成层次结构。 #### 4.1.4 类型或类 实体和属性被分类为类型或类，如员工、部门、员工编号、部门编号、工资等。所有描述同一类型实体的实体记录属于同一类型的实体记录，对应地，实体类型之间也存在关联类型。每个类型的对象需要有唯一的类型名称用于标识，因此有实体记录名称和关联名称。同一类型的所有项构成其总体，任何单个项是该类型的值、实例或出现。 ### 4.2 进一步特征 实体类型和属性类型之间存在多对多关系。例如，“人”这个实体类