注册网站授权书怎么写,链接制作网站,学校网站建设技术,网站建设公司电话销售客源哪里找文章目录 前言堆文件链表实现页目录实现总结系列文章 前言
还记得上次遗留的问题吗#xff1f; 以什么组织方式将数据保存在磁盘中#xff1f; 今天我们接着讨论这个问题。
首先想一个问题#xff1a;有一天#xff0c;你开着自己心爱的大型SUV去超市购物。在停车场入口看… 文章目录 前言堆文件链表实现页目录实现总结系列文章 前言
还记得上次遗留的问题吗 以什么组织方式将数据保存在磁盘中 今天我们接着讨论这个问题。
首先想一个问题有一天你开着自己心爱的大型SUV去超市购物。在停车场入口看到剩余车紧缺。你该如何先人一步找到合适的车位
假如你是这个超市的老顾客非常熟悉这里停车场的布局和规则那么你就更有可能快速找到车位。
停车场的布局和规则类似于数据库中数据文件的文件组织。 堆文件
堆文件是最常见的数据文件组织形式。
堆文件Heap File
数据库最常用的文件组织形式常用于OLTP型数据库它对页Page和记录Record没有任何顺序上的要求可以根据需求将记录插入任何合适的位置页和记录的组织方式完全由实现者自己定义
堆文件通常有两种实现方式链表和页目录。 链表实现 在链表实现中
每个数据页Data Page包含记录Record、指向下一页和上一页的指针有一个头页Header Page作为文件的开始用于将数据页划分为满页和空闲页
在链表实现的堆文件中插入一条记录可以分解为三个动作。
1. 找空位置
先找到头页顺着空闲页链表找一个合适的空位如果空闲页链表为空或者找不到合适的位置则追加一个空闲页到空闲页链表中
2. 将记录写入空位置 3. 必要时更新链表
如果当前空闲页已写满则将它从空闲页链表移动到满页链表的最前方把它移到满页链表的最前面是为了提高效率因为不用遍历整个满页链表
拿停车举例子如上图右侧所示。
假设停车场有A、B、C和D四个区域。每当一个区域停满时管理员会在区域入口放一个禁止入门的路障。这样司机可以快速找到第一个有空位的区域。
你会沿着箭头的方向找到一个适合的空闲车位
因为有路障你快速驶过A区和B区驶入第一个有空位的区域 - C区发现C区的唯一的空位太小大型SUV停不进去继续驶入下一个有空位的区域 - D区停入D区最后一个空闲车位此时管理员会在D区放置路障
页目录实现 在页目录的实现中
每个头页包含一个指向下一个头页的指针形成页目录每个头页中的记录包含指向数据页的指针和该页的空闲空间信息数据页只存储记录它们不再需要指向相邻数据页的指针
在页目录实现的堆文件中插入一条记录同样分解为三个动作。
1. 找空位置
找到第一个头页根据头页中记录包含的空闲空间信息找到一个包含合适空位的数据页如果当前头页找不到则继续遍历下一个头页如果头页链表为空或者找不到合适位置则追加新的头页和数据页
2. 将记录写入空位置
顺着头页中记录指向数据页的指针找到对应的数据页在数据页中找到对应的空位写入数据
3. 更新状态
更新头页中有关数据页空闲空间的信息
接着拿停车举例子如上图右侧所示。
假设一个停车场经过了信息化改造在停车场入口处的显示屏上显示每个区域的每个车位的状态是否被占用和信息车位尺寸。
你也会沿着箭头的方向找到一个适合的空闲车位
行驶到显示屏处找到一个合适的空位并记录位置例如D区03车位直接行使到D区03车位显示屏更新D区03车位状态变为已被占用 总结
我们先从写的角度进行对比
写入动作链表实现页目录实现找空位从第一个空闲页开始找 最差情况追加新的空闲页平均情况- 可能访问较多数据页才能找到合适空位 - 例如1号停车场中存在走冤枉路的问题顺着页目录开始找最差情况追加新的头页和数据页平均情况 - 由于空闲信息记录(包含空闲状态和空闲信息)要远小于数据记录 - 因此头页可以包含更多的空闲信息记录- 也就是说遍历更少的头页就可以找到合适的空位- 不存在走冤枉路写记录因为是直接在数据页中找空位找到空位后直接写入即可没有额外成本需要从头页中跳转到数据页中的空位存在额外成本但成本较低状态更新记录写入空位后需要更新数据页头部包含空位状态的信息 最坏情况额外需要修改数据页的指针从空闲链表移到满页链表 更新头页中的状态信息
再从删除角度对比
写入动作链表实现页目录实现找记录遍历数据页不考虑所以的情况下相同删记录在数据页头部中将对应的记录标记为删除将数据页插入到空闲页链表头部在数据页头部中将对应的记录标记为删除更新头页中的空闲信息辅助成本定期清理空间相同
由此可见
页目录的优点是插入记录通常更快。只需读取头页就可以找到空位需要执行的磁盘I/O更少因此速度更快页目录适用于频繁地写、更新和删除的场景数据页中有很多零散的空位链表实现更简单适用于写多但更新和删除较少的场景此时空闲页链表尽可能短磁盘I/O次数尽可能少找空位时间也尽可能短 系列文章
更多系列文章请参考【如此简单数据库入门系列】之思想地图 – 系列目录 如果喜欢这篇文章请不要忘记关注、点赞和收藏哦 您的鼓励将是我创作的最大动力
