《数据库系统内幕》读书笔记(持续阅读ing)

《数据库系统内幕》读书笔记

一、 简介与概述

1.1. 数据库架构

image-20220412202555614

对于数据库的架构,其实不难理解,比如你请求MySQL了一条sql语句,其实也就是通过客户端发送一条命令到服务端,服务端又由好几部分构成,会先由查询处理器解析sql,使其成为AST语法树,再优化一把,再制定查询计划交由执行引擎处理,执行引擎负责收集本地和远程操作的执行结果。本地查询则交由存储引擎处理,事务管理器和锁管理器负责控制并发,访问方法管理磁盘上的数据访问和组织磁盘上的数据。缓冲区管理器负责将数据页缓存在内存中。恢复管理器负责还原故障。

1.2. 内存数据库与磁盘数据库

内存数据库:存储空间相对较贵(想一想你电脑内存和磁盘的大小就知道了),数据结构多样,随记访问速度快

磁盘数据库:存储空间相对便宜,数据结构大多为宽树和矮树,随机访问速度较慢(想一想硬盘寻道的样子就知道为什么会慢啦)

磁盘数据库较内存数据库的性能花销主要体现在:序列化格式&数据布局

1.3. 面向列与面向行的数据库

如何决定使用面向列还是面向行的存储?基于访问模式。如果所读取的记录大多数都是需要的,并且负载工作主要由单条记录查询和范围扫描组成,则选择面向行的存储;如果需要在列的子集上进行计算聚合,列的存储结构更实用。

宽列式存储:列被分组为列族,并且在每个列族中,数据被逐行存储。

下图树宽列式存储的逻辑模式和物理模式。

image-20220412214832810

image-20220412214845412

1.4. 数据文件和索引文件

聚簇索引:数据记录的顺序遵循搜索键顺序。通常聚簇索引的数据记录和索引存储在同一个文件。

非聚簇索引:数据存储在单独文件中,且其顺序不遵循键顺序。

a:聚簇索引;b:非聚簇索引

image-20220412215526785

间接的主索引的两种形式简单认识一下:

image-20220412220004166

1.5. 缓冲、不可变性和有序性

存储结构由三个常见变量:是否实用缓冲、使用不可变还是可变的文件,以及是否按顺序存储值。

个人理解:

  1. 缓冲:添加内存缓冲区以减轻I/O压力(不至于梭哈全写进磁盘里);
  2. 不可变性:文件结构只能顺序写追加;
  3. 有序性:数据记录按键顺序存储在磁盘上的页中。(这里的顺序存储是指逻辑顺序还是物理顺序???)

二、 B树基础知识

2.1. 二分搜索树

AVL如果作为磁盘存储的数据结构,需要磁盘相当频繁的执行平衡操作、重新定位节点并更新指针。这些维护成本使得AVL作为存储在磁盘上的数据结构变得不切实际。具体问题如下:

  1. 局部性:由于元素是以随机顺序添加,所以不能保证新创建的节点在父节点附近写入,这意味着节点子指针可能跨越多个磁盘页
  2. 树高:AVL扇出为2,定位元素时需要O(logn)次【以2为底】的磁盘传输

所以更适合磁盘实现的树必须具备:高扇出、低高度的特点

2.2. 基于磁盘的结构

类型SSD(固态硬盘)HDD(机械硬盘)
优势没有需要旋转的磁盘,也没有为读取而必须移动的磁头;随机I/O和顺序I/O延迟差异不大;有GC,且会做活页迁移价格便宜;顺序I/O成本较低
劣势价格较为昂贵机械硬盘的寻道增加了随机读写的成本,因为其需要磁盘旋转和机械磁头运动来将读/写磁头定位到期望的位置
最小单元页:2KB~16KB扇区:512B~4KB
示意图image-20220413220239565

虽然说SSD的最小可编程/可读/可写单元是页,但磁盘操作的最小单元是块,这也是我们设计时的需要考虑到的限制和条件。

2.3. 无处不在的B树

帮助理解的博客:B树详细图解与Java完整实现

B树层次结构:

image-20220418211343016

由于B树是一种页组织技术(即用于组织和导航固定大小的页的技术),所以节点和页这两个术语在描述中可相互替换。

节点容量与其实际持有的键的个数之间的关系称为占用率。

B树节点分裂:

image-20220418212249930

image-20220418212312039

这里有个疑问:为什么叶子节点和非叶子节点的分裂情况不一致?非叶子节点的分裂键会被提升到父级,而叶子节点的分裂键则不仅会被提升到父级,还会被保留在叶子节点!

B树节点合并:

删除16

image-20220418212420314

删除10

image-20220418212635696

我们可以利用这些知识在内存中构建一个B树。为了实现一个基于磁盘的B树,我们需要深入了解如何在磁盘上布局B树的节点,以及如何使用数据编码格式来构建磁盘上的布局。

三、 文件格式

3.1. 动机

需要构建一种文件格式存储B树的节点。

3.2. 二进制编码

编解码的时候需要使用相同的字节序

  1. 大端:从最高位字节(MSB)开始,从高位到低位依次排序,即最高有效字节具有最低的地址;
  2. 小端:从最低有效字节(LSB)开始,从低位到高位依次排序。

image-20220422204720483

还介绍了浮点数、字符串、变长数据和按位打包的数据(布尔值、枚举值和标志),这里就不提了。

3.3. 通用原理

文件通常以定长的头部开始,可能以一个定长的尾部结束。尾部包含需要被快速访问的辅助信息或解析文件其余部分必须的信息。文件的其余部分被分成多个页。

image-20220422210055931

3.4. 页的结构

原始的B树论文描述了一种简单、用于定长数据记录的页组织方式,每个页仅是一连串的三元组,如下图所示,k表示键,v表示相关联的值,p表示指向子页的指针。

image-20220422210445511

这个方案有一些缺点:

  1. 除非在最右侧,否则插入键的时间复杂度是O(n)
  2. 无法有效管理或访问变长记录,只适用于定长数据

3.5. 分页槽

为了简化变长记录的空间管理问题,我们可以将页分成固定大小的段,这样做可以为需要变长的数据预留足够的空间。

但这里我有个疑问,如果变长数据又超过了预留的空间怎么办?是再分配空间嘛,如果是的话,是在紧跟着原始的数据还是挑选空闲区域添加;还是整理后再单独拎出来追加。

我们需要一种页结构,它需要有如下特点:

  1. 以最小开销存储变长记录
  2. 回收已删除记录所占用的空间
  3. 引用页中的记录,无论这些记录具体在什么位置

分页槽的特性满足了上述三个特点:

image-20220422212032830

  1. 最小开销:分槽页唯一的额外开销是一个指针数组,用于保存记录实际所在位置的偏移量。
  2. 空间回收:通过页进行碎片整理和重写,就可以回收空间。
  3. 动态布局:从页外部,只能通过槽ID来引用槽,而确切的位置是由页内部决定的。

3.6. 单元格布局

变长键单元格布局:

image-20220422212618094

键值单元格布局:

image-20220422212809071

3.7. 将单元格放进分槽页

image-20220422212926616

3.8. 管理变长数据

image-20220422213044647

适配策略:

  1. 首次适配优先
  2. 最佳适配优先

3.9. 版本&校验和

因为加入新功能或修复bug或性能问题,会修改二进制文件的格式,所以才有了版本的概念。大多数时候,任一版本的存储引擎都要支持不止一种序列化格式(以实现向后兼容)。为此,我们必须能够确定当前文件是什么版本的。

磁盘上的文件可能会由于软件错误或硬件故障而损坏。为了识别这些问题,避免扩散,我们可以使用校验和以及循环冗余校验(CRC)。(CRC的主要目标是确保数据没有非人为、意外的变化,而非用于抵御攻击或人为的修改。)

四、 B树的实现

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×