• 8-12外部排序

    一.基本概念

    这里的外存特指磁盘，磁盘存储数据的存储单元以磁盘块为单位，操作系统也以“块”为单位对磁盘存储空间进行管理。

    在这里插入图片描述
    一个绿色部分为一块，共16块
    在这里插入图片描述
    每个磁盘块都可以存放数据，如果想要修改磁盘中的数据，需要将对应的磁盘块读入内存。

    每个磁盘块中包含三个记录。
    在这里插入图片描述
    首先要在内存开辟一片与“块”大小一致的缓冲区，然后可将其读入内存。磁盘的读写都是以块为单位进行的。
    在这里插入图片描述
    因此想要修改磁盘中的数据，需要读入磁盘、修改、再写会外存。

    二.外部排序
    在这里插入图片描述
    使用归并排序，最少需要在内容分配3块缓冲区，即可对任意文件进行排序。

    接下来用归并排序的方式对记录递增排序

    1.将前两块内容读入内存
    在这里插入图片描述

    对数据进行内部排序，使缓冲区1到2为递增次序

    在这里插入图片描述

    逐个放入输出缓冲区，输出到外存

    在这里插入图片描述
    在这里插入图片描述

    现在第一个磁盘块和第二个磁盘块记录变为递增有序，这两块成为一个“归并段”，归并段内部是递增有序的。

    在这里插入图片描述

    对剩余磁盘块两两一组进行处理，得到8个归并段

    在这里插入图片描述

    至此完成了初始归并段的构造，进行了16次读和16次写

    2.对初始归并段进行归并排序

    在这里插入图片描述
    将归并段1和归并段2中更小的块放入内存
    在这里插入图片描述

    按内部排序的二路归并，选出三个最小元素放入输出缓冲区

    在这里插入图片描述
    将其写回外存
    在这里插入图片描述

    继续25加入，26加入输出缓冲区，此时输入缓冲区1为空，将归并段1的下一个磁盘块写入

    在这里插入图片描述
    27加入，写会外存，输出缓冲区2空，归并段2的下一个磁盘块替补
    在这里插入图片描述
    凑够3个写回，再凑3个，写回。至此完成了2个归并段的归并
    在这里插入图片描述

    对其他的归并段两两一组进行归并，得到4个新的归并段

    在这里插入图片描述

    3.第二趟归并
    两个一组，将每个归并段的第一个磁盘块写入内存，同样方法对比和写回。当输入缓冲区i为空时及时用归并段i的下一个磁盘块填补
    在这里插入图片描述
    在这里插入图片描述

    完成，得到2个新的归并段

    在这里插入图片描述

    3.第三趟归并，实现整体有序

    在这里插入图片描述

    三.时间开销

    在这里插入图片描述

    外部排序的时间开销=读写外存时间（与读写磁盘次数成正比）+内部排序时间（构造初始归并段）+内部归并时间（第i趟归并）

    其中读写磁盘次数=初始块数×2（读/写）+初始块数×2×归并趟数。上例中读写磁盘次数=32+32×3

    四.优化

    1.为提高效率，可以通过增加输入缓冲区个数，进行多路归并，即增加归并路数，来减少归并趟数

    如通过四路归并，一次排好4个归并段
    在这里插入图片描述

    生成2个新的归并段

    在这里插入图片描述
    第一趟结束，第二趟将这两个归并段二路归并即可，只需要2趟即可完成

    若树高为h，可以看成归并趟数为h-1
    在这里插入图片描述
    设初始有r个归并段，在树的第h层，有 r ≤ 2 h − 1 2^{h-1} 2h−1，即 ( h − 1 ) m i n {(h-1)}_{min} (h−1)min​= ⌈ l o g 2 r log_2r log2​r⌉，因此对于k路归并形成的k叉树， ( h − 1 ) m i n {(h-1)}_{min} (h−1)min​= ⌈ l o g k r log_kr logk​r⌉=归并趟数的最小值

    k越大，r越小时 归并趟数越小，读写磁盘次数减少，效率高

    缺点：
    ①k路归并需要开辟k个输入缓冲区，内存开销较大
    ②每挑选一个关键字需要对比关键字k-1次，内部排序所需时间增加

    因此k不是越大越好

    2.增加初始归并段的长度，来减少归并段个数

    直接读入四块内容，再写回外存
    在这里插入图片描述
    构造初始归并段只有4个
    在这里插入图片描述

    五.多路平衡归并

    ①最多只能有k个段归并为一个
    ②每一趟归并中，若有m个归并段参与归并，则经过一趟处理得到⌈m/k⌉个新的归并段

  • 相关阅读:
    java虚拟机详解篇五（类的加载器）
    人工智能底层自行实现篇3——逻辑回归（上）
    耗时三年整理出来的软件测试项目实操指南与过程文档
    使用 Elastic 和 LM Studio 的 Herding Llama 3.1
    Flutter获取设备的信息
    高斯锁表导致sql报错处理
    Postgresql中ParamListInfoData的作用
    5G双域专网解决方案浅析
    LeetCode 每日一题 2023/9/4-2023/9/10
    常见的12种二次曲面方程及可视化
  • 原文地址：https://blog.csdn.net/weixin_45825865/article/details/126125703