数据库管理系统-从基本原理到系统构建 课件 05 数据库存储

数据库系统-存储系统1清华大学计算机系李国良第5章数据库存储2本章内容数据库系统如何存储数据数据的存储介质特性比较数据库系统如何查找数据如何提高数据访问的效率如何防止数据库数据丢失数据的最小单位数据页面数据库如何来管理缓冲区如何选择行存储和列存储数据库系统-存储系统存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统3存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统45存储概览数据库系统-存储系统SQL引擎执行器存储引擎文件组织页面组织元数据日志索引缓冲区故障恢复并发控制存储介质6存储概览数据库系统-存储系统7存储概览数据库系统-存储系统堆表WAL

record索引事务并发控制表空间管理脏页队列数据页面缓冲区WAL日志缓存WAL

recordWAL

recordWAL

record提交日志缓冲区刷脏页线程Checkpoint线程刷WAL日志线程数据文件控制文件异步写盘WAL日志文件事务提交日志垃圾回收线程WAL日志归档线程WAL日志收发线程事务提交WAL日志恢复8数据组织数据库系统-存储系统存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统910存储介质数据库系统-存储系统11存储介质介绍高速缓冲存储器存取速度最快的存储介质，而单位价格却比较昂贵DRAM主存(内存)主要用于存放程序和其处理的数据。一般为4GB～32GB（2022年）磁盘容量大、数据持久性好，存储长期数据。一般为256GB～10TB（2022年）闪存又叫固态硬盘，个人计算机闪存大小一般为128GB～1TB（2022年）非易失性主存速度能DRAM相媲美，字节级寻址，在断电时不会丢失数据数据库系统-存储系统12存储介质特性比较存储介质访问速度存储空间单位价格数据持久性高速缓存快小高易失DRAM较快中等中等易失非易失性主存中等中等较高非易失闪存较慢较大较低非易失磁盘慢大低非易失数据库系统-存储系统13磁盘接口SATA（SerialATA）500MB/s～600MB/s存储区域网络（StorageAreaNetwork

，SAN）网络附属存储（NetworkAttachedStorage

，NAS）

非易失性主存主机控制器接口规范（Non-VolatileMemoryExpress

，NVMe）磁盘阵列（RedundantArraysofIndependentDisks

，RAID）～3500MB/s数据库系统-存储系统14磁盘结构盘片覆盖磁性物质，通过改变磁性物质的磁场方向来存储二进制的0和1，高速旋转每分钟5400转至7200转磁头改变磁性物质状态并且读写数据磁道盘片上的圆环区域柱面纵向对齐的多个磁道数据库系统-存储系统15磁盘结构

磁盘读写时延寻道时延：磁头移动时延10ms旋转时延：盘片旋转时延5400转/分钟的磁盘平均时延是60*1000/5400*0.5=5.56毫秒数据读写时延：100MB/秒的磁盘读写4KB：4KB/100MB*1000=0.04毫秒读写1MB：1MB/100MB*1000=10毫秒

顺序读写：快（只有读写时延）随机读写：慢（寻道+旋转+读写）数据库系统-存储系统尽量顺序读写避免随机读写16磁盘性能与优化访问时间系统发出读写指令后到磁盘开始返回数据的时间数据传输率每秒钟磁盘读写的数据量磁盘访问优化技术缓冲预读调度文件组织数据库系统-存储系统17磁盘调度技术：电梯算法电梯算法把磁头看作是在做横跨磁盘的扫描从柱面最内圈到最外圈，然后再返回正如电梯做垂直运动，从最底层再到顶层，然后再返回来。数据库系统-存储系统磁盘访问序列：98，183，37，122，14，124，65，67。读写头起始位置：53先来先服务最短距离存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统1819存储结构数据库系统-存储系统20存储结构数据块存储介质上的数据最小存储单位页面统一大小来管理数据一般为8KB、16KB数据库系统-存储系统21数据表空间管理数据表空间由段（segment）、区（extent）、页（page）组成。数据段、索引段、回滚段分别存储一次申请一个区（多个连续页），让相邻页的物理位置也相邻，方便实现顺序I/O。数据库系统-存储系统22申请新页面假设所有的页面都满时，要继续插入记录的话就需要申请新的页面每次申请固定数量的区（extent）为了页面尽量连续数据库系统-存储系统存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统2324页面组织元组管理数据库系统-存储系统PageHeaderRecordRecordRecordRecordRecord追加日志管理25页面组织页面大小为8KB或者16KB，一般为2的整数次幂一个页面往往包含了多条记录数据库系统-存储系统26页面组织：定长记录vs变长记录

定长记录：长度固定，页面中记录数目固定，易于定位一个页面的记录位置例如年龄short，学号char（10）变长记录：长度可变，页面中记录数目不固定，难以直接计算并定位记录位置例如姓名varchar，院系varchar数据库系统-存储系统27定长记录记录的长度（占用空间）固定学号，char，10字节姓名，char，20字节姓别，char，4字节院系，char，40字节绩点，decimal，4字节数据库系统-存储系统记录组织方式记录头：事务信息、NULL值bitmap每个属性值28定长记录页面内组织形式页面头记录数量Checksum：防止读写错误上下页面指针（PageID）页面在文件的offset页面类型：索引、数据空闲空间记录内容数据库系统-存储系统29记录添加如果页面可以容纳新纪录，添加到页面最后数据库系统-存储系统30记录删除删除记录，并依次将后续记录向前移动数据库系统-存储系统31记录删除将最后一条记录向前移动数据库系统-存储系统32记录删除可用空闲位置链表插入记录时快读定位第一个空位数据库系统-存储系统33定长记录（bitmap）数据库系统-存储系统页头记录1记录2记录3记录4记录5Bitmap记录:

(Page2,Record4)Bitmap位图：标记记录是否存在Insert插入：找到第一个空槽Delete删除：清楚槽标志位Bitmap数目根据页面大小和记录长度计算34变长记录记录中的变长属性通过偏移量和长度定位学号，char，10字节姓名，varchar，变长

姓别，char，4字节院系，varchar，变长

绩点，decimal，4字节数据库系统-存储系统35变长记录vs定长记录变长记录组织记录头：事务信息、NULL值bitmap属性槽位：起始位置和长度数据库系统-存储系统36页面组织-变长记录页面内记录组织页面头：页类型、状态槽位：记录起始地址、长度（索引会指向槽位）两头挤：页面、槽位等页面内从前往后；记录从后往前数据库系统-存储系统37页面组织-变长记录数据库系统-存储系统槽位

页面位置和长度删除：删除槽位插入：找到空闲槽位插入记录3删除记录238页面组织思考如何处理记录长度大于页面大小？记录跨页链接专门存储方式如何处理一条记录有很多NULL值？利用bitmap对NULL值进行压缩数据库系统-存储系统存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统3940文件组织数据文件中页面之间的组织方式目标：高效的数据页面访问（插入、删除、查找）

主要的文件组织方法堆表顺序表哈希表B+树多表聚簇数据库系统-存储系统41文件组织数据库系统-存储系统(3,

Lucy)(5,

Tom)(1,

Andy)(4,

Bob)

DataPageDataPage……堆表(1,

Andy)(3,

Lucy)(4,

Bob)(5,

Tom)DataPageDataPage……顺序表(3,

Lucy)(1,

Andy)(4,

Bob)(5,

Tom)DataPage……哈希表%342堆表记录的顺序没有限制，将记录简单排列在文件中数据库系统-存储系统43堆表的多级空闲空间数组快速找到空闲空间的位置从高到低扫描各级空闲空间数组也可以用大根堆替代空闲空间数组，维护各页面空闲空间比例数据库系统-存储系统空闲空间编码可用字节数00~31132~63……2558164~819244顺序表记录按某个或某些字段的大小顺序存储数据库系统-存储系统45顺序表-插入记录按某个或某些字段的大小顺序存储，使用链表连接文件中的记录删除记录2后插入记录7结果如下数据库系统-存储系统46顺序表-插入到新页面页面已满直接插入记录7结果如下数据库系统-存储系统47哈希表使用哈希表将记录存储到不同的页面或者不同的页面集合数据库系统-存储系统48B+树平衡多叉树数据库系统-存储系统49文件组织方法性能对比文件组织方法复杂度增删改点查询范围查询堆表简单堆表+B+树复杂顺序表中等顺序表+

B+树复杂哈希表中等数据库系统-存储系统

页面数目结果页面数目哈希链长度

结果记录数目

B树阶数50多表聚簇文件组织多个相关的表中的数据存储在同一个文件/页面中数据库系统-存储系统51空闲空间管理插入一条长为x的记录，应该插入到哪个页面？堆表需要找到合适的页面（空闲空间大于x的页面）1记录每个页面空间空间大小数据库系统-存储系统52空闲空间管理插入一条长为x的记录，应该插入到哪个页面？堆表需要找到合适的页面（空闲空间大于x的页面）1记录每个页面空间空间大小2利用倒排列表3用小顶堆维护空闲空间数据库系统-存储系统空闲空间编码可用字节数Page

IDs00~31Page2,

Page12132~63Page8,

Page15……Page7,

Page142558164~8192Page9,

Page1353插入记录–有空闲页面数据库系统-存储系统54插入记录–无空闲页面数据库系统-存储系统55查询记录–无索引数据库系统-存储系统56查询记录–有索引数据库系统-存储系统57删除和更新记录删除一条记录：首先查找到该条记录，然后删除定长：bitmap置为0变长：槽位清零更新一条记录：首先查找到该条记录，然后更新定长：直接可以原位更新变长：如果新纪录不长于老记录，原位更新，更新槽位如果新纪录长于老记录，槽位清零，插入新纪录本页面可以容纳，则插入本页面本页面不可以容纳，则插入其他页面数据库系统-存储系统存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统5859元数据关系表本身的属性表名，即关系表名称列名，即关系表的属性名属性的域和长度视图的名称和定义完整性约束，例如外键约束关系表的属性的统计信息，可用于辅助查询优化索引信息数据库系统-存储系统60元数据的关系模式像存储关系表一样来存储元数据数据库系统-存储系统存储概览存储介质存储结构页面组织文件组织元数据存储缓冲区行存储与列存储

目录数据库系统-存储系统6162缓冲区将存储于磁盘的数据同时存储于主存，减少磁盘访问数据库系统-存储系统63缓冲区数据主要包含缓存的磁盘数据页面、索引、日志等。日志可用于故障恢复。数据库系统-存储系统内存缓冲区数据页面日志索引日志页面日志页面磁盘日志页面0页面1页面3页面4索引页面2页面5页面0页面2页面5缓存数据故障恢复写日志写回脏页缓冲区组成(页面ID，槽位)64缓冲区管理更新缓冲区页面更新缓冲区索引更新缓冲区日志更新磁盘日志返回提交成功异步刷新数据和索引页面数据库系统-存储系统65缓冲区管理器为数据访问提供读取、修改和写入接口页面替换过程：当程序请求访问磁盘页面时1.如果该页面已经在缓冲区中，则返回缓冲区中的页面数据2.如果该页面不在缓冲区中，则从磁盘上读取该页面(1)如果缓冲区未满，则将数据写入缓冲区(2)如果缓冲区已满，则根据缓冲区页面替换策略挑选其他页面剔除或写回到磁盘上，再读入新页面数据库系统-存储系统66缓冲区——读取页面1.如果该页面已经在缓冲区中，则返回缓冲区中的页面数据数据库系统-存储系统内存缓冲区数据页面日志索引日志页面日志页面磁盘日志页面0页面1页面3页面4索引页面2页面5页面0页面2页面5缓存数据故障恢复写日志写回脏页①读页面267缓冲区——读取页面2.如果该页面不在缓冲区中，则从磁盘上读取该页面➡️(1)如果缓冲区未满，则将数据写入缓冲区(2)如果缓冲区已满，则根据缓冲区页面替换策略挑选其他页面剔除或到磁盘上，再读入新页面数据库系统-存储系统内存缓冲区数据页面日志索引日志页面日志页面磁盘日志页面0页面1页面3页面4索引页面2页面5页面0页面2页面5页面3①缓存数据故障恢复写日志写回脏页②读页面368缓冲区——读取页面2.如果该页面不在缓冲区中，则从磁盘上读取该页面(1)如果缓冲区未满，则将数据写入缓冲区➡️(2)如果缓冲区已满，则根据缓冲区页面替换策略挑选其他页面剔除或到磁盘上，再读入新页面数据库系统-存储系统内存缓冲区数据页面日志索引日志页面日志页面磁盘日志页面0(写回)页面1页面3页面4索引页面2页面5页面3页面2页面5页面4②缓存数据故障恢复写日志①写回脏页③读页面369缓冲区——写入页面2.写页面时

(1)如果该页面在缓冲区中，则写入缓存、日志和索引 (2)如果该页面不在缓冲区中，则从磁盘上读取该页面，再写入页面到缓存、日志和索引数据库系统-存储系统内存缓冲区数据页面②日志③索引日志页面日志页面磁盘日志页面0页面1页面3页面4索引页面2页面5页面0页面2页面5缓存数据④写日志⑤写回脏页①写页面270缓冲区——写入页面2.写页面时

(1)如果该页面在缓冲区中，则写入缓存、日志和索引 (2)如果该页面不在缓冲区中，则从磁盘上读取该页面，再写入页面到缓存、日志和索引数据库系统-存储系统内存缓冲区数据页面②日志③索引日志页面日志页面磁盘日志页面0页面1页面3页面4索引页面2页面5页面0页面2页面5缓存数据④写日志⑤写回脏页①写页面2日志页面71缓冲区——写入页面2.写页面时

(1)如果该页面在缓冲区中，则写入缓存、日志和索引 (2)如果该页面不在缓冲区中，则从磁盘上读取该页面，再写入页面到缓存、日志和索引数据库系统-存储系统内存缓冲区数据页面②日志③索引日志页面日志页面磁盘日志页面0页面1页面3页面4索引页面2页面5页面0页面2页面5缓存数据④写日志⑤写回脏页①写页面2日志页面72预写日志与故障恢复为什么使用日志：如果缓冲区中的脏页面在写回到磁盘过程中发生故障，则无法保证写入的数据的正确性。页面随机写

日志的顺序写数据库使用预写日志

（write-aheadlog，WAL）来备份数据的修改以防丢失写入数据前先写入日志，日志包含即将写入的页面编号和写入的内容，也可以包含原先页面中的内容作为备份以供恢复。在日志写入到磁盘后再进行事务的提交，保证事务的持久性。故障并重启时，扫描日志来判断每个操作的成功与失败，并决定撤销或者重做这些操作。数据库系统-存储系统73缓冲区页面固定和锁当一个进程正在读取或写入某个页面时，该页面不应该被剔除，否则会读取或写入错误的数据因此需要将使用中的页面暂时固定（pin）住共享锁（sharedlocks）和排他锁（exclusivelocks）页面共享锁使多个进程可同时读取页面页面排他锁保证一个进程在修改页面时其他进程不可访问页面数据库系统-存储系统页面进程1进程2共享锁读写读页面进程1进程2排他锁读写❌74缓冲区页面替换策略管理页面替换，最大化缓冲区命中率，最小化访问磁盘次数最近最少使用策略LRU前1次使用时间越晚（越近期）的页面将来越有机会被使用，越不应该被替换最不经常使用策略LFU使用频率越高的页面将来越有机会被使用，越不应该被替换LRU-K策略前第K次访问的时间越晚的页面将来越有机会被使用，越不应该被替换数据库系统-存储系统75缓冲区页面替换策略最近最少使用策略LRU前1次使用时间越晚（越近期）的页面将来越有机会被使用，越不应该被替换数据库系统-存储系统访问12314536槽位111111116槽位2

2222555槽位3

333333槽位4

4444绿色为命中缓冲区不需要读取磁盘，蓝色格子为需要读取磁盘操作。

76缓冲区页面替换策略最近最少使用策略LRU顺序扫描时的缺陷：顺序扫描的数据大于缓存大小时，LRU命中率降低。数据库系统-存储系统访问12345123槽位111115555槽位2

2222111槽位3

333322槽位4

44443绿色为命中缓冲区不需要读取磁盘，蓝色格子为需要读取磁盘操作。

77缓冲区页面替换策略最不经常使用策略LFU使用频率越高的页面将来越有机会被使用，越不应该被替换数据库系统-存储系统访问1231245312槽位11111111111槽位2

222222222槽位3

33335555槽位4

44333绿色为命中缓冲区不需要读取磁盘，蓝色格子为需要读取磁盘操作。

78故障恢复刷新日志后（写盘），但是还没有刷新数据页面，系统宕机如何恢复？如何保障故障正确性？数据库系统-存储系统Insert

(A,

2);

Insert

(B,

3);

Insert

(C,

4);

Insert

(D,

5)

CRASH

Redo

All

Page1newPage2

newPage3

oldPage4oldPage5

newPage6new日志Page

1Page

3(A,2)

(B,3)Log(A,2),(B,3),

(C,4)

,(D,5)内存磁盘Page7newPage8emptyPage

6Page

4(C,4)

(D,5)79故障恢复刷新日志后（写盘），但是还没有刷新数据页面，系统宕机如何恢复？如何保障故障正确性？数据库系统-存储系统Insert

(A,

2);

Insert

(B,

3);

刷盘Insert

(C,

4);

Insert

(D,

5)

CRASH

Redo

4,5Page1newPage2

newPage3