db_7 存储管理与索引

物理存储系统

数据只有放入内存才能被处理

DBMS设定数据库的基本存储是在磁盘上，DBMS管理内存与外存数据的交换

DBMS存储管理的目标：！！！！！！！！！！！

==最小化磁盘存取次数==（实现手段是在主存中保持尽量多的块，使得上层要访问一个块时，它在主存中的概率最大）

磁盘块/块：由若干个连续的扇区构成，是存储分配和检索的逻辑单元，

块是存储分配和数据传输的单位

大小一般在4K-16K之间，数据以块为单位在磁盘和主存之间传输。页面（page）通常指块

磁盘访问时间：

时间=寻道时间+旋转时间+传输时间

物理存储管理器（磁盘管理器）：

是DBMS结构的最底层，隔离上层模块和底层的软、硬件平台
以页/块为单位组织数据
负责数据在磁盘和主存之间的移动，主要操作包括页/块读、写、申请和释放
- 利用操作系统的文件系统
- DBMS自己实现，可以支持跨平台，以及操作系统不提供的功能

数据库的存储结构

概述

数据库存储结构主要是文件的组织结构

数据库：由若干文件组成，这些文件采用专有的格式。操作系统不能获取这些文件内容的任何信息
文件：由若干个定长的存储单元/存储块/页构成
页/块：存储分配和数据传输的单位
DBMS中的存储管理器负责
- 维护这些数据库文件，将文件组织为块/页的集合
- 跟踪页的数据读取/写入
- 跟踪可用的空间

文件结构

数据库的表映射到底层存储中的文件
一个文件在逻辑上被组织为记录的序列，记录被映射到磁盘块上
文件在存储中由若干磁盘块构成，块是存储分配和数据传输的单位
一个块可以包含几个记录，每条记录被完全包含在单个块中
每个记录有唯一的标识符ID(由块号和记录在块中的位置构成)

表/文件所占磁盘块的分配方法

连续分配—数据块被分配到连续的磁盘块上
链接分配—数据块中包含指向下个数据块的指针
按簇分配—簇是连续的几个磁盘块，簇之间指针连接
索引分配—索引块中存放指向数据块的指针

页/块/磁盘块结构

页/块是固定大小的数据块

可以包含元组/记录，元数据，索引，log记录等
每个页有唯一标识符（ID）DBMS将页ID映射为页的物理位置

结构

Header+Data
Header 包含了页中数据的元数据（页大小、Checksum 、DBMS 版本）
分槽(slot)页结构：！！！！！！！！！！！
- Header记录了已使用的槽数，以及最后一个被用槽的起始位置偏移量，以及一个槽数组
- 槽数组保存了每个元组的起始位置偏移量
- 槽数组从开始到尾部的方向增长
  
  记录数据则从数据区的尾部到开始的方向增长
  
  当槽数组与元组数据连接到一起时，认为页满
- 便于存储变长记录

记录结构

记录是字节序列，DBMS负责将该序列解释为属性类型和值
记录头部：包含元组的元数据，例如加锁信息等
记录数据：属性的实际数据。属性一般按表定义中的顺序存储

多数DBMS不允许一个记录大小超过一个页
唯一标识符ID
- 每个记录被分配了一个ID
- 最常见的形式：页ID+（offset或槽）
- 应用程序不能依赖该ID进行唯一性标识

文件中的记录组织

堆文件组织

记录可以存放在文件空间中的任何位置
链表方式：
- header页面存储了空白页链表头指针和数据页链表头指针
- 每个页记录了当前包含的空槽数
页目录方式：
- DBMS维护特殊页保存文件中的数据页的位置
- 记录每个页中空槽数

顺序文件组织

文件中的记录按搜索码排序排列

搜索码：用于在文件中查找记录的任意属性或属性集合

通过指针把记录链接起来，每个记录的指针指向按搜索码排列的下一条记录

可以高效按某个搜索码处理记录

索引文件组织

索引是指记录的关键字与相应记录的存储地址的对照表

索引文件由主文件和索引表构成

索引表必须按关键字有序
主文件本身可以按主关键字有序组织（即索引顺序文件）或无序组织（即索引非顺序文件）

散列文件组织

散列文件的存储单位称为桶(Bucket)

桶号可以是相对块号，最终可以转换为外存空间上的物理地址

处理冲突方法：在散列值的个数多于一个桶时，形成一个主桶和多个溢出桶的列表

二次检索：先利用哈希函数h确定项所在的主桶，再根据链表逐一找到每个溢出桶

聚集文件组织

具有相同或相似属性值的记录存储于连续的磁盘块中

聚集码是一种属性，它定义了哪些记录被存储在一起

多表聚集：将多个关系存储于一个文件中，在每个块中存储两个或更多关系的相关记录

可以加快特定的连接查询，但会使单个表的访问变慢

缓冲区管理

概述

缓冲区：是主存中可以存储磁盘块副本的区域

缓冲区管理器

负责缓存空间分配，内外存交换！！！！！！！！

Execution engine需要操作磁盘块时，资源管理器调用缓冲区管理

如果该块在缓冲区中，则缓冲区管理器返回该块在内存的地址
如果不在缓冲区，则缓冲区管理器为该块在缓冲区中分配空间（这可能替换某个块，如果被替换的块修改过，需要将其写回磁盘），将块从磁盘读进缓冲区，并将内存地址返回给调用者

缓冲区组织管理（*）

缓冲区被组织为一个固定大小页面数组，每个元素称为帧，存放磁盘上的一个页/块

缓冲区元数据是页表：

跟踪当前内存中所有页的访问情况，并保存了每个页的元数据

Dirty Flag：由修改页的线程设置，通知存储管理器该页必须写回磁盘
Pin/Reference 计数器:在一页被进程读写操作前要钉住(pin),防止该页被移出，操作结束后解除钉（计数器减1）

只有计数器=0时，才能被移出或写回磁盘

缓冲区中的共享锁与排它锁：

缓冲区管理器提供封锁系统，允许数据库进程以共享或排他模式封锁页，在完成操作后释放封锁
并发控制，读操作加共享锁，更新操作加排他锁
一次只能由一个进程获得排它锁，共享锁与排它锁不能同时加，多个进程可以同时持有共享锁

缓冲区替换策略：

索引

概述

索引记录/索引项，是索引文件的记录，包括两个域：

索引域（搜索码）：存储数据文件中一个或一组域（属性）
指针：指向索引域值为K的记录所在磁盘块的地址。

多级索引

外层索引：基本索引的稀疏索引
内层索引：基本索引文件

二叉树可能会失去平衡

B树（平衡树）

限制了每个节点放置关键字与指针的最小和最大个数

根节点有[2,n]个子节点
中间节点有[n/2, n]个子节点
叶节点有[(n–1)/2,n-1]个记录指针

所有的叶节点都在同一层上

B树的关键字是散布在各层上

B+树

把树中所有关键字都按递增次序从左到右安排在叶节点上，并且链接起来

能同时进行随机查找和顺序查找

B+树节点结构

每个节点最多包含

n-1个搜索码/索引码/关键字值K1 ，K2. . .,Kn–1
- Ki 是索引码的值
- K1 < K2 < K3 < . . .< Kn–1
n个指针P1 ，P2. . ., Pn
- Pi 对于非叶子节点是指向子节点的指针
- 对于叶子节点P1 ，P2. . . , Pn-1是指向记录或记录桶的指针，Pn指向下个叶子节点

查询
- 从树的根节点开始，通过比较查询码值v与节点的ki 值，向下遍历树，直到到达包含指定值的叶节点为止
- 如果在叶子节点中找到ki=v,则返回目标记录指针pi；否则关系中不存在该值的记录
插入
- 采用查询算法定位插入的叶节点l，如果有空间则插入，否则需要拆分
- 拆分：将节点l的n个码值的前[n/2]放在l中，剩下值放在新节点中
- 将新节点插入l的父节点中。如此自底向上递归处理，直到插入不再产生拆分或建立了一个新根节点为止
删除
- 采用查询算法定位删除的叶节点l进行删除，如果l的码值个数低于下限，可能导致节点合并或重新分配
- 合并或重新分配：如果删除后节点l太小，将其与兄弟节点合并，并从父节点中删除，如此自底向上递归处理，直到根节点。
  
  如果在合并时，新节点码值数超过上限，则需要该节点与其兄弟节点之间重新分配指针

B+树文件组织

叶节点存储的是记录而不是记录的指针
用B+树索引解决索引顺序文件组织（索引项的顺序与文件记录的顺序一致）的性能下降问题
叶节点半满，而最大记录数要小于中间节点的指针数

Hash索引

哈希表实现key到value的映射，存放记录的数组叫做哈希表

Hash 函数：通过键值映射到表中一个位置来访问记录

Hash函数
- 将很大的key空间映射到比较小的域，用于计算桶/槽数组的元素序号
- 非用于加密算法的哈希函数
- 计算速度快且碰撞率低
哈希方案（scheme）
- 解决一个哈希值对应多条记录
- 最常使用溢出链接(Chaining)法

静态哈希：哈希表的大小是固定的
- 文件增大时，太多的溢出桶将降低访问性能
- 数据规模缩小时，会造成空间浪费
动态哈希：允许哈希表的大小动态修改
- 定期重哈希：创建新的大的哈希表，把原表上的key重新哈希到新表上
- 线性哈希：以一种递增的方式重新哈希

周期性重组的开销大
适用于检索哈希码等于特定值的记录检索。不适用于区间值的检索
适用于部分匹配检索
有很多重复值的列，不适于做key