数据库存储、索引与性能优化全解析

### 数据库存储、索引与性能优化全解析 #### 1. 不同文件组织形式的 I/O 成本分析 文件组织形式在数据库存储和操作中起着关键作用，不同的文件组织形式在扫描、搜索、插入和删除等操作上有着不同的 I/O 成本。下面我们来详细探讨几种常见的文件组织形式及其相关操作的成本。 ##### 1.1 聚集文件（Clustered Files） 聚集文件中，页面通常占用约 67%的空间，因此物理数据页的数量约为 1.5B。以下是不同操作的成本分析： - **扫描（Scan）**：扫描成本为 1.5B(D + RC)，因为需要检查所有数据页。这与排序文件类似，但由于数据页数量增加，成本有所调整。 - **等值选择搜索（Search with Equality Selection）**：假设等值选择匹配搜索键 `age, sal`，定位包含所需记录的第一页需要 logF 1.5B 步，每步需要一次磁盘 I/O 和两次比较。找到页面后，通过二分查找定位第一条符合条件的记录，成本为 Clog2R。总成本为 DlogF1.5B + Clog2R，比排序文件的搜索效率有显著提高。如果有多个符合条件的记录，由于按年龄排序，它们相邻，检索所有记录的成本为定位第一条记录的成本加上按顺序读取所有符合条件记录的成本。 - **范围选择搜索（Search with Range Selection）**：与等值搜索类似，先定位满足选择条件的第一条记录，然后顺序检索数据页，直到找到不满足范围选择的记录。 - **插入（Insert）**：插入记录时，先找到索引中的正确叶页，然后添加新记录。大多数情况下，叶页有足够空间，只需写出修改后的叶页。成本为搜索成本加上一次写入，即 DlogF1.5B + Clog2R + D。 - **删除（Delete）**：删除记录需要搜索记录，从页面中移除记录，并写回修改后的页面，成本分析与插入类似。 ##### 1.2 带有非聚集树索引的堆文件（Heap File with Unclustered Tree Index） 假设索引中的每个数据条目是员工数据记录大小的十分之一，考虑到索引页 67%的占用率，索引的叶页数量为 0.1(1.5B) = 0.15B，每页的数据条目数量为 10(0.67R) = 6.7R。 - **扫描（Scan）**：扫描员工记录文件时，先扫描索引的叶级，为每个数据条目从底层文件中获取相应的数据记录。读取所有数据条目的成本为 0.15B(D + 6.7RC) I/O，获取员工记录的成本为每条记录一次 I/O，总成本为 BR(D + C)，非常高。如果需要按排序顺序获取员工记录，直接扫描员工文件并排序可能更高效，排序 B 页文件的 I/O 成本为 4B。 - **等值选择搜索（Search with Equality Selection）**：假设等值选择匹配排序顺序 `age, sal`，定位包含所需数据条目的第一页需要 logF 0.15B 步，每步需要一次磁盘 I/O 和两次比较。找到页面后，通过二分查找定位第一条符合条件的数据条目，成本为 Clog26.7R。获取第一条符合条件的数据记录还需要一次 I/O。总成本为 DlogF 0.15B + Clog26.7R + D，比排序文件的搜索效率有显著提高。如果有多个符合条件的记录，它们不一定相邻，检索所有记录的成本为定位第一条符合条件的数据条目的成本加上每条符合条件记录一次 I/O。 - **范围选择搜索（Search with Range Selection）**：与等值搜索类似，先定位满足选择条件的第一条记录，然后顺序检索数据条目，直到找到不满足范围选择的数据条目。对于每个符合条件的数据条目，需要一次 I/O 来获取相应的员工记录。随着满足范围选择的记录数量增加，成本会迅速变得过高。如果 10%的数据记录满足选择条件，直接检索所有员工记录、排序并保留满足条件的记录可能更高效。 - **插入（Insert）**：先将记录插入员工堆文件，成本为 2D + C，然后将相应的数据条目插入索引。找到正确的叶页成本为 DlogF0.15B + Clog26.7R，添加新数据条目后写出叶页成本为 D。 - **删除（Delete）**：定位员工文件中的数据记录和索引中的数据条目，搜索成本为 DlogF 0.15B + Clog26.7R + D，然后写出修改后的索引页和数据文件，成本为 2D。 ##### 1.3 带有非聚集哈希索引的堆文件（Heap File With Unclustered Hash Index） 假设每个数据条目是数据记录大小的十分之一，静态哈希文件中页面保持约 80%的占用率，存储数据条目所需的页面数量为 1.25(0.10B) = 0.125B，每页的数据条目数量为 10(0.80R) = 8R。 - **扫描（Scan）**：所有数据条目可以以 0.125B(D + 8RC) I/O 的成本检索，但为每个条目获取相应的数据记录需要额外的一次 I/O，成本为 BR(D + C)，非常高，且结果无序，因此很少有人扫描哈希索引。 - **等值选择搜索（Search with Equality Selection）**：对于匹配选择，即复合搜索键 `age, sal` 中的每个字段都指定了相等条件，该操作支持得非常高效。识别包含符合条件的数据条目的页面成本为 H，假设桶只有一页，检索该页成本为 D，扫描页面成本为 0.5(8R)C = 4RC，最后从员工文件中获取数据记录成本为 D。总成本为 H + 2D + 4RC，比树索引的成本更低。如果有多个符合条件的记录，它们不一定相邻，检索所有记录的成本为定位第一条符合条件的数据条目的成本加上每条符合条件记录一次 I/O。 - **范围选择搜索（Search with Range Selection）**：哈希结构对范围选择搜索没有帮助，必须以 B(D + RC) 的成本扫描整个员工记录堆文件。 - **插入（Insert）**：先将记录插入员工堆文件，成本为 2D + C，然后定位索引中的适当页面，插入新数据条目并写回，额外成本为 H + 2D + C。 - **删除（Delete）**：定位员工文件中的数据记录和索引中的数据条目，搜索成本为 H + 2D + 4RC，然后写出修改后的索引页和数据文件，成本为 2D。 ##### 1.4 不同文件组织形式的 I/O 成本比较 | 文件类型 | 扫描（Scan） | 等值选择搜索（Equality Search） | 范围选择搜索（Range Search） | 插入（Insert） | 删除（Delete） | | --- | --- | --- | --- | --- | --- | | 堆文件（Heap） | BD | 0.5BD | BD | 2D | Search + D | | 排序文件（Sorted） | BD | Dlog2B | Dlog2B + #matching pages | Search + BD | Search + BD | | 聚集文件（Clustered） | 1.5BD | DlogF 1.5B | DlogF 1.5B + #matching pag