开发者学堂课程【从0到1数据库内核实战教程：【视频】数据库存储基础】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1083/detail/16097
【视频】数据库存储基础
内容介绍：
一、存储器层次结构
二、磁盘存储器
三、块与记录组织
四、变长数据和记录
五、记录的修改
一、 存储器层次结构
1.存储器层次
上图是典型的存储层次组织图，从下往上按照存储的速度以及大小进行编排的，最下面是高速缓存，这个概念并不陌生，一般买电脑有一个 CPU 缓存这个指标就是高速缓存，高速缓存直接跟 CPU 打交道，存储空间比较小，一般只有几个兆的大小，往上是一个主存储器，一般叫主存或内存，用过 Windows 系统的可能会遇到主存不足的问题。往上是二级存储器，主要是磁盘存储器，磁盘两边有虚拟存储器和文件系统，其实都是建立在磁盘系统之上的一个文件系统，再往上是第三级存储器，一般有 DVD 光盘，特点是存储容量大。
主要存储器
高速缓存存储器：
空间有几个兆，容量1-6MB，高速缓存和处理器间速度为<10纳秒，高速缓存和主存储器间速度为10- 100纳秒
主存储器(内存)：
容量能够达到10GB以上，辅助存储器，访问时间10-100纳秒
辅助存储器：
磁盘主要有机械硬盘和固态硬盘SSD
随机访问
数据传输：一次<10ms，速率在毫秒级别，
容量: 1TB-10TB，容量大
第三级存储
磁带存储器，DVD光盘，容量大(PT级别)、成本低、速度慢(s/min)
2.虚拟存储器
（1）虚拟存储器的特点
解决内存资源瓶颈问题，在内存中缓存磁盘的数据
32位的虚拟存储器为4GB
虚拟存储器由硬件提供，大部分内容保存在硬盘上
主存数据库系统是通过虚存来管理它的数据
先介绍一下虚拟地址空间，经常在启动时，操作系统会分配虚拟地址空间，最大是四个 G，假如不止一个呢？有两个或者不止一个？那么此时不可能每个都配备4G 大小的容量，毕竟总内存就10个 G，此时便用虚拟地址解决分配问题，通过虚拟地址空间和物理地址空间建立的临时关系来操控实际的物理内存，虚拟地址和物理地址之间是通过一个叫 MNU 的结构来管理临时关系的，MNU 把虚拟地址发出的转换成物理地址。如上图所示，假如 CPU 发起对虚拟地址的访问请求，此时页表中有序列号如果都能在物理内存中找到相对应的话，那么是一个比较理想的过程，但现实生活中可能遇到一些缺页错误，图中黄色的是没有配对到物理内存的地址，再建立物理内存，根据关系来填补缺页的错误。因此使用虚拟地址来分配和管理物理地址的物理内存，通过交换内存和释放的数据来实现空间扩用的方式。虚拟存储器的实现可以理解成一种解决问题的思路，即最大化结合内存找到适合能力的提升。
二、 磁盘存储器
1.磁盘的物理模型
（1）基本概念
盘面(side)
磁头(head)
扇区(Sector)
磁道(Track)
柱面(Cylinder)
簇(Cluster)
上图描述了磁盘的整体结构，有多个盘片组成，每个盘片分成正反两个盘面，盘片的每个盘面被划分成不同的同心圆，即磁道，每个磁道被划分成若干段弧段，即扇区。在不同的盘面上相同的磁道编号的一个组合组成的圆柱体叫做柱面，，簇是若干个扇区连接而成的连续的空间。
2.磁盘的存储特性
（1）磁盘的容量计算
盘面数量
磁道数量
扇区数量
扇区大小
（2）例如，某磁盘具有以下属性
8个盘片，16个盘面
每个盘面2^16=65536个磁道(tracks)
每个磁道256个扇区(sectors)
每个扇区4096个字节
（3）那么总的大小为:
ize=16 X 65536 X 256 X 4096 Bytes = 1TB 
磁盘的存取性能
平时在使用磁盘时，特别在读写磁盘操作时，偶尔听到磁盘里冒出噪声，这些噪声就是磁道在高速旋转的噪声。磁盘性能受一下因素影响，
（1）寻道时延
磁臂移动到指定磁道所需要的时间
（2）旋转时延
把扇区移动到磁头下面的时间
（3）存取时延
从磁盘读出或将数据写入磁盘的时间
（4）时延Latency =寻道时间Seek Time +旋转延迟Rotational Delay +传输时间Transfer Time
假设磁盘转速很高的话，那么旋转时间比较慢。
3.存储器的加速访问
思路
减少磁盘访问I0
缓存磁盘数据到主存，通过操控主存的数量且定期批量的放到里面保存，此时会高效地访问磁盘的数据。
优化磁盘访问算法
降低寻道时间/旋转时间
使用多盘
所有方法原则是怎么降低释放 IO，或者提高数据访问。
4.故障
（1）间断性故障
可能访问到磁盘，但不是一次性的，反复读取间断性成功
读取磁盘扇区时介质损坏
（2）存储介质损坏，数据丢失，这种失败没办法重复上面的读取
写故障
（3）不能正常写入到磁盘里面去，不能写入扇区，也不能检索写过的扇区
（4）磁盘崩溃
整个磁盘不能读写，错误性最严重
磁盘读取错误的故障有一些校验机制来解决故障问题。例如现在有技术叫校验技术，原理是在数据的最后加上某种数学叠加的计算的结果。
图中有一个二进制数01101000，假如在数字的最后加上一位奇偶
位1，假如二进制里有三个1，则有奇数个1，叫做有奇数奇偶位，后面记一个1，则叫做有偶数奇偶位，最后记一个0。只有一个奇偶位判断是否读取正确的几率是百分之五十，假如现在有两个数位发生变化，以01101000为例，假设数值有两个发生了变化，因为是五个一，所以还是奇数奇偶位，所以最终在奇偶位上记一个1。但其实对比变化之前有两个位发生了变化，读取时发生了故障，因此只用一个奇偶位无法判断数值是否发生变化。此时可以使用多个奇偶位来表明这一个数值到底有没有发生变化。假设用八个奇偶位，那么校验的错误率会减少到一除以二的八次方，数位越多，校验核的直觉性越高。
校验和技术叫做奇偶校验和，图中有一个
校验和( checksum)
判断读取的数据是否正确
稳定存储
数据冗余容错，假如有一个扇区，在读取扇区时，用了两个扇区来作为一个存储的介质，然后这两个扇区分别承担一个数据，当 XL 读扇区发生错误时，还可以再读 XR 的数据，这种方式跟数据库里面读副本的方式类似，通过多份数据去容错一些场景。
三、块与记录组织
1.关系模型中的数据存储方式
了解过数据库的同学都知道什么是记录?
由多个字段组合而成的数据元素
下面有一个语句，建了一张表，表里面有 salary、birthdate 等字段，这些字段按照一定的编排方式来进行聚合成一行的东西叫做记录
CREATE TABL E MovieStar(
name CHAR(30) PRIMARY KEY，
salary INTEGER，
address VARCHAR(255)，
gender CHAR(1)，
birthdate DATE
）；
什么是数据块?
由多个数据元素组成的数据集合，在存储空间上的话是连续的地址空间，总而言之是一个数据块里有若干个数据记录，一个数据记录里有若干字段。
2.记录的类型
（1）定长类型
数据字段的长度固定，例如int, short, date
（2）变长类型
数据字段的长度非固定，例如varchar，blob，text
3.记录的存储结构
一条记录是怎么保存的？
假设在32位操作系统的存储以4字节对齐
在块内部从起始地址的4倍数字节处开始存储一条记录。假设存储的 name 这一个字段，存储空间是从0到30，建表的话，假设是30，是没有对齐的，下面的图是对齐之后的，是从零到三十二，比没有对齐之前扩充了两个字节的内容，其他字段以此类推，为什么
要对齐？跟 CPU 的访问数据有关，对齐后的访问比对齐前的要快，有兴趣的同学可以自行了解一下数据的对齐。
记录中所有的字段都从与记录起始偏移量为4的倍数的字节处开始。
一条记录的完整格式
除了 name、address、gender、birthdate 之外，还会记一些额外的信息，比如指向模式指针、长度、时间戳等。不同的场景存储的数据不一样，前面的几个叫 header，后面的叫 dater。所以一条完整的数据记录，按照 header 加 dater 重组的。
4.块的存储结构
一个完整块的格式，其首部主要存储关于块的元数据信息，与其他块之间的连接，块在存储层级结构中的位置，例如块ID，每一条记录的起始地址在块中的偏移，块的最后一次修改或存取时间戳。块的首部里保存每个记录的篇集，只要是利于数据的管理和维护的信息都可以记录。
5.块和记录的存储地址
块在主存缓冲区时，记录的是虚拟存储器地址(主存/磁盘映射)块在二级存储器时，使用一个字节序列描述块在整个数据系统中的地址
磁盘设备ID，柱面号等
记录时是从块的末端往中间，未使用空间是从块的首部之后的空间往中间增长的。比如现在有四条记录，记录1最先插入，4最后插入，为什么要做这样的数据存放呢？方便对块的空间进行管理，假设块的总空间是100，不包括首部，假设一条记录是10，那么很容易算出块里面最多能存十条记录，但若块里存的记录不仅有定长还有变长，变长一般存在块的后面，按照块的偏移，最终算出定长的数据，假设从前往后查数据，首先记录有偏移是知道的，偏移等于未使用空间的大小，那么变长记录很直观，知道变长记录是否能插入到块的未使用空间里。如果插入进去的话，再重新找一个新的块把数据插进去。方便了块的空间管理，所以插记录时从后往前插。
三、变长数据和记录
1. 变长数据定义和类型
大小变化的数据项，比如 varchar 这样的字段，这个字段记录的叫变长记录；
重复字段指这记录里有几个字段是重复的且重复次数是不确定的，这也是变长的体现；
可变格式记录指这一条记录里不知道具体的字段的类型，没有固定的字段类型，可能有两个或三个，是不知道的；
大字段指比如 text 这种可能会需要几个块来存储，这个变长记录了大字段。
2. 具有变长字段的记录
存储时把变长字段放在定长字段后，便于变长字段的存储。varchar 在存储中一般是定向，最后存 address，存一个 指向 address 的偏移，再存具体长度，最后访问时可以找到 address 的变长的偏移，从偏移开始访问到偏移的记录长度，最后得出 address 具体的内容。
3.具有重复字段的记录
需要记录重复字段出现的首个偏移需要记录重复字段的个数
它的存储方式跟变长字段的存储方式类似，保存指向重复字段的指针，保存记录的长度和次数，最终可以通过指向重复字段的指针找到记录的首地址，再根据记录的长度以及重复的次数来把后面全部重复的东西编辑出来。
通过类似一种索引的方式分块存储在块 A 上存储定长内容和变长指针在块 B 上存储变长内容假设现在有两个块，块 A 和块 B，块 A 上存储的是定长的内容，包括变长字段的指针，这个指针是定长的，最终指针指向另外的块的地址，通过变长跟定长之间的，这种访问有好处也有坏处。好处是在管理记录时，可以管一个纯定长的结构，方便数据的访问，最终访问数据的时候要访问到两个块，访问到块 A 再到块 B。
4.具有可变格式的记录
格式的记录通俗来讲记录没有固定模式，假如有一个属性有名字、高度、职业、房产等，但这些每一列都不一样，有些可能没房产，有些没职业，所以这两个记录所需的字段不一样，那么针对这种类型的数据存储时一般会存这些数据的特征，比如存名字存 N，14为长度，存 R 代表餐馆，以此类推，这种方法和核心思想是解析的过程，解析记录时不需要额外的表结构，去比对，去根据表结构的类型进行访问，例如 XML 文件；
标记字段序列。
5.具有最大值类型的记录（跨块记录）
记录片段的 header 需要记一个二进制位指名是否为片断
记录片段的 header 需要几个位指名是所属记录的第几个片断
记录片断的 header 需要有指向其他片断的指针
需要进行分块存储，那么在存储这个记录时会把这个记录分成多个片，每个片的开头位置记一些属性，比如大致类型具有哪几个片，比如记录了2-a，假设叫片 number 1，另一个叫2-b，叫片 number 2。或者说在片的位置记一个标记，或者记一个指针，这个指针指向下一个分片的地址。根据最终的地址连接起来，组成一个完整的片，组成完整的记录。
6.BLOB 二进制大对象（Binary Large Object）
常见的BLOB：音视频文件
BLOB的存储
存储在连续块，或块的链表
通过分散保存到不同的盘，存储在多个磁盘，提高检索效率，比如在看电影时，电影的数据不会全部加载到内存里面去，在播放到某一个片段之前，把对应的数据从磁盘加载到内存，或者快进到某个片段的时候，能够快速地把这个片段对应的内容加进来，这里建立了一个 BLOB 的索引
BLOB的检索
按需检索，一次返回部分数据块
快速检索，建立合适的索引结构
7.列存储
大部分数据库以行存为基础，什么是行存？简单来说是按行存储。右侧的表中有 X Y Z，表中插入了三行记录，如果使用行存的话，左上角的图可以看到是具体的行存的形式，按照行来进行存储，什么是列存呢？列存是可以按照表结构的列来进行存储，左下角图的列存有三列，如果按照列存会不会导致一个列的数据非常大？是有可能的。一个列的记录可能有好几个块，好几个磁盘这么大小。列存优势是什么？假如我需要读取某一列的数据，这样子列存天然满足读取的要求，如果只需要返回到某一列的数据，不需要返回其他列的数据，这样做的方式无形中可以加快一个数据的读取，或者现在按照某一列进行压缩，因为列里面的类型是同一个类型，因此压缩的时候可以压缩到一个比较紧实的程度，因为类型都一样，所以是很好的优点。这个优点可以大大减少我们的存储成本。
四、变长数据和记录
列存储优缺点
优点：
按需读取列，减少非必要数据的访问
列字段类型统一，非常利于做压缩
利于做列的聚合操作
适合做大数据分析，AP性能好
缺点：
写入/更新耗时相对行存较长，TP性能差
不适合做频繁的删除操作
五、记录的修改
1.数据的插入
找到空闲块
插入块的空闲位置
维护 offset
如上图，假设已经插入到记录四了，要插入记录五，从未使用的空间里找到一个空闲的地方，把这个地方算出一个偏移，把偏移记录到偏移列表里面，在 header 之后的空间里面记录下来，之后再把记录插入到偏移之后的地址里。
2.数据的删除
在记录的头部信息中记上一个删除标记
数据删除是立刻把记录删除掉，但其实很多数据库的做法并不是立马把它删除的，而是删除时会在记录的头部使用一个字节等做一个标记，这个标记使这个记录被访问到，那么这个记录什么时候会删除呢？可能有些做法是在访问到数据库的时候，在做扫描，访问到这条记录时发现是一条删除的记录，然后对这个记录进行一个具体的实际的查除。还有一种做法是定期检测有哪些数据被删除了，再根据删除的记录，再把具体的内容抹掉，对这个块进行重整。
3.记录的修改
定长记录的修改
变长记录的修改
定长记录修改比变长记录修改简单，因为记录都是定长，可以把记录读出来，做修改，之后在原来的位置上重新写下去，变长的话不太可行，因为变长修改完之后的记录可能长度发生变化，因此先在变长记录开头先打上一个标记，说明记录已经被删除了，然后再在块里找一个空闲的位置，再把这个修改完后重新插进去。为了规避记录修改完之后长度可能不一致，所以要复杂一点。
