存储与索引

存储介质

在DBMS中, 存在两个非常重要的问题: 1. 如何高效地组织非常大量的数据; 2. 如何高效地访问数据, 即最小化输入/输出操作.

它对于存储介质的要求有: 数据库需要保存到持久存储中, 例如硬盘和固态硬盘. 尽管内存的价格逐渐降低, 但是新兴应用程序对海量存储能力的需求日益增长, 远远超过了内存的容量. 硬盘和内存的比较可见图.

对于DBMS来说, 主要关注的是硬盘, 因为大多数的操作都是在磁盘和内存之间进行的读写操作, 这意味着IO操作的性能对系统的整体性能影响很大. 相比之下, 与IO相关的限制更为显著, 因此数据库系统的性能优化更倾向于减少IO操作而不是提高CPU的计算效率.

数据块

数据块是磁盘和内存之间传输的基本单位, 它的大小是由操作系统在初始化的时候定义的, 通常会跨越多个扇区(sector). 例如, 块的大小可以是4096字节(4K), 8K等. 关于数据块, 扇区, 磁道, 柱面在磁盘中的具象化表示请见图.

在磁盘上是没有逻辑记录的概念的, 它只能识别块, 并不关系这些块中包含的是怎样的数据, 当数据从磁盘上的一个块被读取并加载到内存中的缓冲区的时候, DBMS会对块中的原始数据进行解析, 将其划分为有意义的结构化数据单元, 即逻辑记录, 就是"元祖", 表中的一行行记录.

阻塞因子

阻塞因子, blocking factor, 记录的是块大小和记录大小之间的关系, 公式为b=块大小/记录大小. 它表示的是一个块能够容纳多少个记录. 当b<1的时候, 块大小小于记录大小, 这意味着一个记录不能完整地放入一个块中, 这会导致"记录跨块", record spanning, 即需要多个块来存储一个记录. 由于记录跨块对性能的影响十分明显, 防止这种现象的发生对于DBMS的高效存储和检索非常重要.

IO时间

对于磁盘来说, 其读取/写入时间, 即IO时间主要由3部分组成:

寻道时间: 磁头移动到正确的磁道的时间
旋转延迟: 当磁头定位到正确的磁道后, 还需要等待磁盘旋转到正确的位置的时间, 取决于磁盘的旋转速度
传输时间: 当磁头到达正确的位置后, 实际读取或写入过程开始, 数据从磁盘读取或写入的时间

缓存管理

注意, 整个数据库是无法放到内存里面的, 但是内存能够提供一个数据块的缓冲区. 由于磁盘IO是极其耗费时间的, 所以我们会尽量保证数据库放在内存中以便后续快速读取/写入.

为了提高效率, 需要设计策略来"预测"应用程序可能会请求哪些块, 以便在请求的时候这些块已经存在于缓冲区中, 从而减少IO操作的频率. 缓存管理器负责管理这些策略. 如当缓冲区满, 程序需要一个数据块的时候, 缓冲区中的哪一个数据块应该被替换掉, 即, 最好的替换算法是什么?

主要有两种算法: LRU(Least Recently Used)和MRU(Most Recently Used).

例子

假设现在有两个关系: Borrower和Customer, 假设每个关系都存储在单独的文件中. 它们唯一共同的属性是customer_name. 现在, 要执行一个自然连接的操作, 对于每一个Borrwer都要遍历一遍所有的Customer记录, 查找记录的customer_name是否一致, 然后加入到新表中.

假设缓存区有的容量为三个数据块, 而Customer关系有4条记录, c1, c2, c3, c4, 每个记录刚好占用一个块. 那么哪种缓存策略更加合适?

LRU: 最近最少使用, 这种策略替换最久没有被使用的块. 按照这个例子, 先存储c1, c2, c3, 在读取c4的时候, 最久未使用的是c1, 因此将c1替换为c4. 接着对于下一个Borrower, 读取c1, 所以又要将c2替换出去, 到此为止, 出现了2次页面置换, page faults
MRU: 最近最常使用, 这种策略替换最近刚使用的块. 在读取c4的时候, 最近使用的块是c3, 因此将c3替换为c4. 接着操作读取c1, 不需要进行替换操作, 所以到此为止, 出现了1次页面置换

因此, 在这个特定的操作中, 使用MRU的策略会更好, 因为它比LRU导致的页面置换更少.

平均故障时间

平均故障时间, Mean Time To Failure, MTTF是一个统计值, 用来描述硬盘在出现故障前的平均运行时间. 根据硬盘型号的不同, MTTF通常在一百万小时, 约114年到250万小时, 约285年之间. 硬盘随时会发生故障, 因此需要定时备份和使用RAID配置来防止数据丢失.

例子

在实际中, 当有大量硬盘的时候, MTTF可以帮助估算故障的频率. 例如, 如果MTTF为一百万小时且有一万个硬盘, 那么每小时可能会有一个硬盘发生故障, 如果硬盘数量减少到1000个, 那么在相同MTTF下, 每1000小时可能会有一个硬盘发生故障.

数据传输的关键优化方法

物理传输可以通过一些方法进行优化:

块传输: 通过以固定大小的块为单位进行数据传输, 从而减少单个数据传输的开销
基于柱面访问: 这种方法减少了磁头移动的距离, 通过优先访问同一个柱面上的数据, 可以减少磁头在磁盘表面移动的次数
多磁盘: 使用多个磁盘并行操作来增加数据的吞吐量
磁盘调度: 通过优化磁盘的读写请求顺序来减少磁头移动, 常见的调度算法有先来先服务, FCFS; 最短寻道时间优先, SSTF等
预取/双缓冲: 在需要时提前读取数据到内存或者使用双缓冲技术以减少等待时间, 确保磁盘在一个任务完成时可以立即开始下一个任务

廉价磁盘冗余阵列

廉价磁盘冗余阵列, Redundant Array of Inexpensive Disks, RAID, 是一种磁盘组织技术, 将大量磁盘抽象成一个逻辑盘. 它的优点包括高容量, 高速和高可靠性. 不同的RAID方案通过磁盘条带化(striping)和奇偶检验位的组合来以较低的成本实现冗余, 不同的RAID级别在成本, 性能和可靠性方面具有不同的特点.

数据的组织和存储

在DBMS中, 表被存储为记录的集合, 并称之为一个文件. 一个文件由一个或多个页面组成, 每个页面存储的记录都来自一个表, 页面是内存中用于管理数据的最小单元, 缓存管理器负责管理这些页面. 磁盘空间管理器负责将页面请求转换为磁盘块请求, 每个页面可能由一个或多个磁盘块组成.

信息

在接下来的讲解中, 默认情况下, 一个页面等于一个磁盘块, 除非另有说明.

例子

假设我们在一张关系中由2000000条记录, 每个记录的大小是200bytes(如图). 每页的大小为4k bytes, 其中250字节用于页头和记录指针数组, 所以实际可用于存储记录的字节数为3846字节. 每条记录为200字节, 所以每页可以容纳3846/200=19条记录(取整, 不能存放部分记录, 如图所示, 剩余46bytes). 那么, 所需要的页数为2000000/19=105264页(向上取整, 因为需要完整存储所有记录, 最后一个页面包含3个记录, 如图所示).

需要的大小是2000000*200=400000000bytes. 而实际给出的大小是105264*4096=431161344bytes. 所以有(431161344-400000000)/400000000=7.79%的overhead.

填充因子

填充因子, occupancy. 我们用一个例子来解释. 假设每个数据页的大小为4KB, 4096字节. 每个页有250字节用于页头和记录指针数组, 这些空间用于存储元数据, 所以实际可用的空间为3846字节. 假设填充因子设置为80%, 这意味着我们希望每个页的80%空间用于存储数据, 剩下的20%空间预留为空闲, 用于将来插入新数据时候的扩展, 80%的填充因子意味着在3846字节中, 我们会使用3846*0.8=3076字节来存储数据, 剩下的3846*0.2=770字节被保留下来.

设置occupancy小于100%能够为未来地插入和更新预留了足够地空间, 有助于提高写操作的效率, 并降低索引树的高度增长和系统碎片化. 因此, 设定较低的填充因子是一种权衡性能和空间利用率的做法, 以提高数据库整体的操作效率.

例子

在上面的例子中, 假设填充因子为75%. 那么原先每页能存19条记录, 现在每页只能存19*75%=14.25, 14条记录. 那么现在总共有2000000/14=142858条记录, 那么总共有142858*4096=585146368bytes. 根据之前计算overhead的公式, 它有46.28%的overhead.

文件组织

对于数据库中的一张表或者一个文件来说, 其记录可以采用不同的索引方式存储在磁盘上, 这些方式会显著影响数据的检索和更新效率.

无序文件: 表中的记录没有特定的顺序存储, 数据插入的时候会存放在任何可用的空间中. 适合批量读取或需要描述整个表的情况
排序文件: 表中的记录按照某个字段排序存储. 这样可以加快基于该字段的检索(如二分查找), 但是插入和删除操作较为耗时, 因为需要保持排序状态
索引: 为表中的一个或者多个字段创建索引, 以便加快基于这些字段的搜索. 索引类似于一本书的目录, 通过索引可以快速定位到特定记录. 更新操作相对高效, 因为不需要重新排列整个表的数据

这和我们下一小节要将的内容有关.

访问路径

访问路径, 即DBMS如何检索记录的方式, 它由文件组织和算法(如下所示)组成, 不同的文件组织都需要用到不同的算法来访问.

线性扫描: 对于无序文件来说, 从头到尾注意扫描所有记录, 直到找到目标记录
二分查找: 对于排序文件来说, 使用二分查找可以更快速地找到特定记录
索引扫描: 通过索引结构(B树或者哈希表)快速定位到目标记录

Tip

物理数据独立性: 在执行SQL语句地时候, 选择地访问路径不会影响语句的语义, 即查询的结果不会改变. 例如对于SELECT * FROM Student WHERE sid = 5309650这个查询, 无论使用线性扫描, 二分查找, 还是索引扫描, 结果都是相同的.

尽管访问路径的选择不影响查询的语义, 但是它对查询的执行时间有很大影响. 不同的访问路径可能导致查询的执行效率差异极大, 进而影响数据库的性能. 因此, 合理选择访问路径对于提高查询速度非常重要.

线性扫描

无序文件是一种最简单的文件组织, 包含的记录没有特定的顺序, 通常存储在堆中. 这种文件组织的访问方法是线性扫描. 平均来讲文件中一半的页都会被扫到, 但是在最坏情况下整个文件都会被读取.

对于每一个数据页, 将页加载到主内存中(一次IO的成本), 然后检查页中的每个记录是否匹配查询条件.

例子

假设一个表(文件)有140351个页, 讨论两种查询类型的IO成本:

等值查询(SELECT * FROM Relation WHERE tuplekey=715). 如果这个tuplekey是唯一的话, 可以在找到第一个匹配的时候立即终止搜索. 如果有匹配记录的话, 平均情况下需要查找一半的页数, 即70176次IO; 如果这个tuplekey不是唯一的话或者根本找不到, 需要检索所有页, 需要140351次IO
范围查询(SELECT * FROM Relation WHERE attribute1 BETWEEN 100 AND 119). 这个需要查询所有页中的记录, 需要140351次IO

二分查找

排序文件根据一些属性对记录进行排序. 对它进行访问的方法是二分法.

例子

假设我们现在要搜索特定岁数的人群, 记录已经根据年龄排序., 如图所示. 最坏情况下, IO成本是log_2(B)加上任何包含被检索记录的额外页数(B是文件的总页数), 例如, 如果B=140351页, 那么检索包含表中第一个记录的页的IO成本为log_2(140351).

当然, 二分查找也有缺点, 那就是在插入记录的时候维护排序的成本非常高: 在插入新的数据后, 需要移动后续记录为新纪录腾出空间. 所以, 一般商业DBMS很少纯粹地使用排序文件, 而是使用索引组织文件.

索引扫描

索引是一种将搜索键映射到数据库表中记录集合的数据结构. 搜索键可以是字段的任意子集, 并不一定是关系的键. 索引的主要作用是加速数据查找和检索操作, 通常比线性扫描快得多.

典型的索引类型有:

哈希索引: 只能用于等值查询, 不能用于范围查询
B+树索引: 适合用于范围搜索, 但由于结构复杂, 可能需要更多的空间

索引的缺点有:

索引需要额外的存储空间来存放索引页
访问索引页会产生额外的IO开销, 除非索引足够小, 可以完全放入内存中
当表被修改时, 索引也需要更新, 不同的索引结构对修改的敏感程度不同, 某些结构可能导致较高的维护成本

虽然索引扫描存在上述缺点, 但是其带来的性能提升远大于其劣势. 因此, 索引在商业DBMS中被广泛应用, 被认为是DBMS中用于提升性能的最重要功能之一.

B+树索引

主要思想是通过维护一个逻辑排序的文件组织, 文件的页在物理上没有连续存储. 实现B+树索引主要分为3步:

创建一个逻辑排序文件

例子

假设一个表存储在一个包含140351个页面的数据文件中, 每个页面的搜索键为tuplekey. 每个页面的记录在物理上是按照tuplekey排序的, 这确保了页面内部的数据有序. 页面之间是逻辑排序的, 这意味着页面i中的所有记录的tuplekey都小于页面i+1中的记录. 但是, 这些页面的磁盘上可能并不是连续存储的, 即物理位置上不一定紧邻, 这种物理上的非连续存储并不会影响逻辑上的有序性.

我们将这样的文件称为逻辑排序文件. 该表就存储在这样一个逻辑排序文件中, 包含140351个页面, 每个页面都有一个搜索键tuplekey作为这个页面的唯一标识.
创建索引条目

为逻辑排序文件的每个页面都创建一个索引条目, 每个索引条目包含两个部分:
- 搜索键: 用于确定页面的顺序
- 行指针: 指向对应的数据页, 32bit
可见示意图.
创建索引页

和数据页不同, 存放索引的页面叫做索引页.

例子

假设每个索引页的总可用空间是3846字节(其中保留了250字节). 因此, 每个索引页最多可以存放3846/8=480条索引. 假设页面的填充因子为75%, 则每个索引页的平均条目数为480*75%=360. 由于索引条目总数等于数据页的数量140351, 每页存放360条, 所以需要的索引页数为140351/360=390.

我们甚至可以将这390个索引页再搞一个逻辑排序文件, 并在其上递归构建索引, 从而实现更高效的查找, 类似套娃🪆的操作, 见下方构建B+树索引.
构建B+树索引

例子

每个索引页的平均条目数为360个. 第一级索引包含390个索引条目, 因此🪆, 需要390/360=2页来存储这些条目. 顶级索引页包含两条索引, 只需要1个顶级索引页.

我们来计算一下总的索引页数, 叶子索引页390, 第二层索引页2, 顶级索引页1, 所以总共是390+2+1=393页. 相比于140351个数据页面, 393个索引页面仅仅增加了0.2%的存储需求.
在B+树上搜索

例子

如图是一个在B+树上搜索tuplekey=14的过程. 如图是一个搜索tuplekey=29的过程. 查找的开销等于B+树的深度+在特定数据页上查找的iterations. 注意B+树中从根到任何一个叶子的路径长度都是相等的.

例子

分析一下SELECT * FROM Relation WHERE tuplekey=715背后的IO次数.

将顶级索引页载入内存, 1*IO
找到第二层索引的索引页
将第二层索引的索引页载入内存, 1*IO
找到第三层索引的索引页
将第三层索引的索引页载入内存, 1*IO
找到对应的数据页
将数据页载入内存, 1*IO
检查数据页中的每条记录是否和要求相符

总共4次IO, 如果使用无序文件组织的话, 平均需要70176次IO操作, 可以看到巨大提升.

注意

对于范围搜索来说, 现有的索引无法起作用. 如SELECT * FROM Relation WHERE attribute1 BETWEEN 100 AND 119;, 为了找到符合条件的数据, 仍然需要顺序检查每一个数据页, 导致总共需要140351次IO.

复合索引

复合索引是指用于索引的搜索键由多个属性构成.

例子

例如, (age, salary)表示首先按照age排序, 然后在相同age的记录中按照salary排序. 注意, (age, salary)和(salary, age)的排序顺序不同, 因此这两个复合键生成的索引页不同, 无法相互替代.

给定一个(age, salary)的复合索引, 下面是各种查询条件的适用性情况:

age = 22: ✅, 因为age是索引的第一个字段
age >= 22: ✅, 因为索引可以帮助找到age大于等于某个值的范围
age = 22 AND salary = 2000: ✅, 复合索引的顺序
age = 22 AND salary >= 2000: ✅, 复合索引的顺序
salary = 2000: ❌, 因为索引首先按照age排序, 没有按照salary排序
salary >= 2000: ❌, 因为salary不是第一个索引字段

所以说, 复合索引的字段顺序会影响查询的适用性, 只有符合字段顺序的查询才能使用索引进行优化, 而其他不符合顺序的查询则无法利用该索引.