《数据库实现》-- 第二章 存储概述

第二章 存储概述

存储层次

cpu cache  几纳秒
内存     10纳秒～ 100ns
本地磁盘/san     10ms    通常是非易失性
第三级存储  秒级 – 如光盘/磁带等

cache 和内存之间， 以line 为单位， 通常32个字节
磁盘到内存 相互之间数据传输， 通常会划分成块或页  4～64kb

为了优化性能， line 内的指令能被顺序执行或者需要， 这要cache 命中率高， cpu流水线指令效率高。

磁盘

存取延迟

1. 寻道时间
2. 旋转延迟

为了提高数据的存取效率， 因此，很多优化手段

1. 使用上通常会使用电梯算法， 强化顺序读取或写入， 减少额外的寻道时间和旋转延迟。
2. 磁盘内部， 关联数据放到同一柱面，减少寻道和旋转时间
3. 并行 – 多个磁盘同时获取数据， 常用raid算法
4. 数据预取

故障

1. 磁盘是有寿命限制， 可出现间歇性故障或介质损耗，最严重是磁盘崩溃
2. 校验和， 利用额外的附加位来存储扇区的校验和
   1. 奇偶校验和。 
   2. crc /md5 等其他校验和
3. 稳定存储
   1. 冗余扇区， 当写一个扇区是，写入正常数据或校验和， 检验校验和是否正确， 如果错误， 写入另一份存储
   2. raid 算法
4. 平均失效时间 mean time to failure
5. raid 算法
   1. raid0 无冗余
   2. raid1 镜像
   3. raid4

 

1. raid5， 非固定盘的奇偶校验
2. raid6， 海明码纠错码
   1. 2(power k) -1 块盘， k为冗余盘， 2（power k） - k - 1 为数据盘。

 

数据格式

定长记录

物理地址：

1. 主机地址
2. 磁盘标识符
3. 柱面号
4. 磁道号
5. 扇区号

逻辑地址

1. 通常使用逻辑地址， 然后通过映射表映射逻辑地址道物理地址， 物理地址比较长，而且物理地址可能由于扩容或故障发生一些变更， 而上层直接使用逻辑地址
2. 一种是， 逻辑地址是offset， 结合物理地址一起使用， 物理地址到块地址

变长字段

1. 当是变长字段时， 比如varchar时， 我们会在记录头上记录长度， 指向变长字段起始处

2. 当出现重复字段， 如果定长字段f出现次数可变， 在记录头， 放起始地址，

 

另外一种方式， 分开存储， 

可变格式的记录， 比如xml

类似kv的记录， key 一个变长记录， value 一个变长记录

当不能装入一个块时， 通常需要跨块记录， 对于一个跨块记录格式

1. 头，首先需要标识， 记录是否为一个块
2. 如果记录跨块， 必须标识，当前块是记录的第几个片段
3. 记录尾得含有下个块的指针。 
4. 

记录的增删改

插入

插入通常会直接修改偏移量来做到， 尤其是当记录是按主键排序时， 

很多系统都是使用系统自增的id， 保证系统都是只做append操作。

对于跨块操作， 会留一个指针指向下一个block， 

删除

如果可以移动偏移量表， 则可以直接操作偏移量表。
如果不能移动偏移量， 需要一个空间列表，标识记录是否有效或否。 
一种方式，在记录的某块地方标识这个记录是否有效或已经被删除
当删除记录时， 有的时候，需要对这个记录的指针进行处理， 可以将指针指向删除记录地址处的新记录。

修改

对于定长记录，可以直接进行修改
对于非定长记录， 一种方式转化为insert和delete 组合。
一种方式还是原地修改，但当记录长度变长时， 需要进行跨块处理。