参考

miniob_lecture
知乎-B+树看这一篇就够了
MySQL索引背后的数据结构及算法原理

磁盘存储

存储大小：盘面——磁道——扇区
延时：寻道时间——旋转延迟——数据传输时间

  • 增加奇偶位来判断数据是否正确

数据要进行字节对齐
记录和块都有一个header来对时间戳或者偏移量来进行存储，便于数据的查找和维护，数据块对记录的存储是朝向header的栈
变长记录的存储：

  • 变长字段：首地址(address) + 字段长度 （注意变长字段一般在定长字段之后存储）
  • 重复字段：首地址 + 字段长度 + 重复次数

文件使用堆文件，记录能插则插，为了保证页面一致性所以通常一个堆文件是一种关系

页

主流操作系统对文件的处理是将文件视为无结构的流文件，只关心数据的传输而不关心数据的格式，而DBMS将流文件划分为页(虚拟分页)来进行内存和磁盘数据的交换
文件分页，同一关系的文件放到一个页里
DBMS有一个间接层，将页面ID映射成文件路径和偏移量，单文件只映射成偏移量
数据库页是硬件页的整数倍(所以DBMS要保证一致性问题)，是缓冲和磁盘交换的基本单位
页头存储页面元数据，有些数据库要求页头自包含，数据区对每个记录的存储方式是采用插槽

记录存储

记录以插槽方式存储，插槽个数维护在页头中，维护：

  • 最后一个使用的插槽的起始位置
  • 插槽数组数
  • 已使用的槽的数量
    插槽个数是变化的，记录插入也是变化的，所以槽数组(指的是页头)从前向后增长，而被插入的记录数据则是从页尾向前增长，顶到就是满了(啊哈~)

记录组织结构，对于变长记录有两种：

  • 记录头存储第一个变长字段的起始位置，以及除第一个以外所有变长字段的偏移量
  • 字段定长，维护一个溢出表，字段指针指向，当存储大数据的时候也要用溢出表(但是会增加IO)

buffer

DBMS为了实现数据的永久存储，面向的是磁盘，但是要以内存作为数据交换的媒介，所以将内存作为缓冲区，将数据以页为单位从磁盘提到内存中，这个过程由缓冲区管理器实现
缓冲池是内存用于缓冲页的空间，缓冲池管理器是给内存分配缓冲空间的子系统

内存会维护一个页表，用于记录页面的磁盘映射和顺序关系，同时也维护了两种：

  • 脏标志：表示有线程更新了磁内存中的页，需要从内存取出来更新磁盘
  • 引用计数器：表示引用内存中的页的数量，大于0则不允许取出内存，相当于加锁

这个缓冲池和操作系统的缓冲区很像，但是在内存中是分开的，会对OS的缓冲IO进行绕过来加速和简化DBMS对数据的访问处理

缓冲区的页面替换算法：

  • LRU-K：记录几次历史的最近使用时间(时间戳放在页表)，以及时间间隔，来预测使用可能 (感觉很多os问题的解决方法就是空间换时间，没有什么很巧妙的方法)
  • 淘汰局部化：对每个查询进行局部页面淘汰
  • 优先级：根据页面上下文来判断其重要性

对脏页的写回(后台写)：
DBMS定期扫描页表，发现脏页进行安全写回(保证没在被使用)，然后取消脏标志
淘汰页面时对脏页的处理可能是一个很重要的优化点

缓冲池优化：
多缓冲池：

  • 每个数据库一个缓冲池
  • 不同缓冲池量身定制不同的策略
  • 对象ID，需要扩展元数据，使其包含关于每个缓冲池正在管理哪些数据库对象的信息，然后通过对象ID，就可以实现从对象到特定缓冲池的映射
  • 散列，DBMS散列页面ID以选择访问哪个缓冲池
    预取：
    在处理第一组页面时，系统可以将第二组页面预取到缓冲池中

B+ tree

一颗，简单的，多路平衡树，但是代表了树的精华
B+ tree中的数据指针都存储在叶子结点上，指针指向的是磁盘区域，数据均以键值对形式存储，便于高效查找和维护，查找磁盘中的内容是按照键值key来进行查找的
B+ tree的阶：代表了每个内部节点能拥有的最大子节点个数m，能容纳的最大数据为m-1，阶太大的话会提高删除和增加节点的复杂性，阶太小的话会增加输的高度
B+ tree的结点数据个数最小不能小于[m/2]
内部节点存储的是用于查询的关键字，不一定要存储所有
这里的B+ tree根节点包含最大值

插入

几种情况：

  • 叶节点数据值指针个数小于阶数，直接插入
  • 叶节点数据值指针个数等于阶数，父节点数据指针个数小于阶数，分裂后插入，并将[m/2]的叶节点提到父节点作为索引
  • 叶节点数据值指针个数等于阶数，父节点数据指针个数等于阶数，叶节点分裂一次，父节点再分裂一次，不断向上直到有未满阶的内部节点
  • 插入值大于最大值，则根节点和内部节点替换目前的最大值，然后正常插入分裂等

删除

  • 删除以后所在的叶子结点数据个数大于[m/2]，直接删除
  • 删除最大最小值，直接全部替换次大次小值
  • 删除以后所在的叶子结点数据个数小于[m/2]，像兄弟节点借一个，然后改变一下父节点
  • 如果兄弟节点没有多余的关键字可以借，那删除之后合并，并回溯更改所有内部节点关键字
  • 如果回溯的时候存在不满足B+ tree要求的情况，依照以上步骤进行处理

复杂度

$\log_m (N)$

SQL引擎结构

parser : 将sql语句翻译成语法树
resolver : 对parser语法树进行进一步的约束检查和属性提取(会翻译成另一种数据结构)
parser和resolver
transformer&optimizor : 基于代价和基于改写的查询优化

关系运算：常使用的有笛卡尔积和自然连接，查询的本质就是对集合关系的数学表达，查询优化要找到计算代价最小的集合关系计算方法