文件系统

文件¶

主存储器和外存储器¶

磁带¶

磁带带面每一横排 9 位二进制，8 位数据位 1 位奇偶校验位
磁带的存储密度 BPI
6250 BPI（=246 排/mm）、1600 BPI（=64 排/mm）、800 BPI（32 排/mm）。正常走带速度为 3～5 m/Sec
传送速度=存储密度*走带速度
应用中发使用文件进行数据处理的基本单位为（逻辑）记录，磁带上存储的为（物理）记录
在使用磁带或磁盘存放逻辑记录时，常常把若干个逻辑记录打包进行存放，把这个过程叫做 “块化”（blocking）。经过块化处理的物理记录叫做块化记录。
磁带每次启停都有一个加速与减速的过程，在这段时间内走带不稳定，只能走空带，这段空带叫做记录间间隙（块间间隙 IBG）
读写一个块的时间 \(t_{IO}=t_a+t_b\)
\(t_a\)：延时时间（读写磁头到达待读写块所需的时间）
\(t_b\)：对一个块读写的时间（数据传输时间+IBG）
磁带设备只能用于处理变化少，只进行顺序存取的大量数据。

磁盘¶

- 数据存储在盘面的磁道上，磁道划分为若干段（扇区）
- 每个盘面都有磁头，磁头同步在磁道之间移动，所处的磁道合起来称为柱面
读取：
- 电子啊线路选定盘片组
- 选定柱面，并移动磁头寻查（机械动作较慢）
- 确定读写的磁道 (即盘片。 )（电子线路）
- 确定扇区，旋转延迟（机械动作）
- 进行读写
- \(t_{io}=t_{seek}+t_{latency}+t_{rw}\)
- 平均寻查时间+平均等待时间（旋转等待）+数据传输时间（其它电子线路的控制时间可以忽略不计）
在 MS-DOS 系统中，多个扇区集结成组，称为簇，作为文件分配的最小单位。
UNIX 系统中不使用簇，文件分配的最小单位和读写的最小单位是一个扇区，称为一个块

缓冲区¶

在磁盘读写时内存需要开辟区域用于存放读入/写出的信息，即输入缓冲区和输出缓冲区。
缓冲区大小应与操作系统一次读写的块的大小相适应，这样就可以通过一次读写完成操作
如果缓冲区大小与磁盘上的块大小不适配，就会造成存储空间的浪费
缓冲区的构造可以看作一个先进先出的队列。

目标：减少磁盘 io，一次多读/多写一点

template <class T>
    void buffer<T>::OutputInfo (ostream& out, T x) {
        if (current == maxSize) {
        //一次性输出
            for (int i = 0; i < maxSize; i++) out << data[i];
            current = 0;
        }
        //存入缓冲区
        data[current] = x; current++;
    };
    template <class T>
        void buffer<T>::InputInfo (istream& in, T& x) {
        //存入缓冲区
            if (current < maxSize) {
                x = data[current];
                current++;
            }
            else {
            //一次性读取
                for (int i = 0; i < maxSize; i++) in >> data[i];
                current = 0;
            }
        };

文件组织¶

文件是存储在外存上的数据结构，一般是在逻辑上具有完整意义的一组相关信息项的有序序列。
操作系统文件：流式文件，没有结构的字符流，按物理记录读写
数据库文件：具有结构的数据集合，按页块读写

文件的组成¶

文件由记录组成（文件存取的基本单位），记录由数据项（文件可使用的基本单位）组成
文件记录分为逻辑记录和物理记录。前者是面向用户的基本存取单位，后者是面向外设的基本存取单位。
能够唯一标识一个记录的数据项或数据项集称为主关键码项，其值称为主关键码；
不唯一标识一个记录的数据项或数据项集称为次关键码项，其值称为次关键码。
文件结构：逻辑结构、存储结构、操作
- 文件的逻辑结构是线性的
- 文件的存储结构：顺序存储、直接存取组织（散列函数）、索引组织
- 操作定义在逻辑结构、实现在存储结构
评价文件组织的效率
- 执行文件操作所花费的时间
- 文件组织所需要的空间
顺序存取设备：磁带
直接存取设备：磁盘

顺序文件¶

顺序文件中的记录按它们进入文件的先后顺序存放，其逻辑顺序与物理顺序一致
如果按主关键码有序，则称为顺序有序文件，否则为顺序无序文件
在顺序存取设备上只能顺序搜索存取，存放在直接存取设备上时才能进行折半搜索等操作
顺序文件的存取方式
- 连续文件：记录顺序的存放在外存的连续区域
  - 速度快、存储利用率高
  - 不能扩充区域大小
- 串联文件：成块存放，但块与块之间可以不连续，通过块状指针顺序链接
  - 文件可以扩充、存储利用率高
  - 影响了存取和修改的效率。

直接存取文件（散列文件）¶

即散列文件，利用散列组织文件，记录的逻辑顺序与物理顺序不一定相同，通过记录的关键码可直接确定该记录的地址
使用散列函数把关键码集合映射到地址集合
冲突和处理
按桶散列
- 记录成组存放，若干组构成桶
- 若一个桶能存放 m 个记录，则 m 个互为同义词的记录可以存放在同一地址的桶中。当第 m+1 个同义词出现时，发生溢出。
- 溢出链：将第 m+1 个同义词存放到“溢出桶”。并称存放前 m 个同义词的桶为“基桶”。溢出桶和基桶大小相同。当在基桶中检索不成功，就循指针到溢出桶中检索。
  - 删除记录时，因为可能需要重新链接，所以只需做一个逻辑删除标记即可，待系统做周期性重构时再做物理删除。
- 分布式溢出空间：
  - 溢出桶按照一定的间隔分布在基桶之间。如果有一个基桶溢出了，系统就将记录存放在下一个溢出桶中。如果溢出桶溢出了，则溢出到下一个溢出桶
- 相继溢出法：
  - 不设置溢出桶，当发生溢出时，溢出记录直接存方到下一个相继的桶中（下一个不是已满的桶中）
  - 优点是对溢出不需要漫长的寻找。紧邻的桶通常相距不多于一次磁盘旋转。但当邻近的多个桶被挤满时，则为了查找空闲空间就需要检查许多桶。如果桶的容量很小更是如此。
可扩充散列
- 基于数字搜索树，根据桶的大小进行合并、分裂等操作
优点：随机存放、记录不需进行排序、插入删除方便、存取速度快、不需要索引区和节省存储空间等优点。
缺点：不能顺序存取，只能按关键码随机存取。在经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况。此时需要重新组织文件。

索引文件¶

由索引表和数据表（主文件） 组成，索引表指示逻辑记录与物理记录的对应关系，是按关键码有序的表
索引顺序文件：主文件也按关键码有序。此时可对主文件分组，一组记录对应一个索引项。称这种索引表为稀疏索引。
- 即一个索引项对应数据表中的一组记录
索引非顺序文件：主文件中记录未按关键码有序。此时，每一个主文件记录必须对应一个索引项。称这种索引表为稠密索引
静态索引：多级索引结构，每一级索引都是一个有序表，结构简单，但是不方便修改，修改需要重组索引
- 数据装入时就已经定型，在整个运行期间，结构不发生变化。
动态索引：动态调整的平衡搜索树结构，方便插入搜索删除
- 在整个系统运行期间, 结构随数据的增删及时调整, 以保持最佳的搜索效率。
搜索的时间代价取决于访问外存的次数，即索引树的高度
索引顺序文件
- 先在索引表搜索给定的值 k, 使 i 满足 \(ID[i-1].max\_key<K<ID[i].max\_key\) 得到子表项
- 在第 i 个子表中搜索记录
- 根据存储的方式，可以使用顺序搜索或折半搜索
索引顺序文件的搜索成功平均搜索长度 \(ASL_{IndexSeq}=ASL_{Index}+ASL_{SubList}\)
- 搜索子表位置的平均搜索长度+子表内搜索的平均搜索长度
- 把长度为 n 的表分成均等的 b 个表，每个表 s 个记录，则 \(ASL_{IndexSeq}=\frac{b+1}{2}+\frac{s+1}{2}\)
- 其中 \(b=\left\lceil \frac{n}{s} \right\rceil\) ，因而 \(l=\sqrt{ n }\) 时取得最小长度

倒排表¶

用主关键码建立索引叫主索引
- \(key|addr\)
只使用关键码有时无法回答根据存储内容进行筛选的查询，使得只能进行低效率的顺序搜索
- 因此除了主关键码外可以把经常搜索的属性设定为次关键码，并针对次关键码的属性，建立次索引
- 次索引中列出属性的取值，对取值建立有序链表，把具有相同属性值得记录按存放地址/主关键码的顺序连接。由次关键码、链表长度、链表本身三部分组成。
- 通过此索引得到链并进行布尔运算就可以通过属性实现查询
倒排表是次索引的一种实现。在表中所有次关键码的链都保存在次索引中，仅通过搜索次索引就能找到所有具有相同属性值的记录。
在倒排表中各个属性链表的长度大小不一, 管理比较困难。为此引入单元式倒排表。
- 索引项中不存放记录的存储地址, 而是存放该记录所在硬件区域（即存储区域）的标识。（一次 I / O 操作能存取的存储空间作为硬件区域）
- 为使索引空间最小, 在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数, 整个次索引形成一个 (二进制数的) 位矩阵
- 二进位的值为 1 的硬件区域包含具有该次关键码的记录。（即状态压缩）
- 针对一个查询：按照此索引抽取属性的位相量，按位进行布尔运算，就求得满足查询要求的记录在哪些硬件区域中，再读入这些硬件区域，从中查找所需的数据记录。

多级索引结构¶

数据记录比较大时索引表也会太大，可以建立索引的索引
二级索引可以常驻内存，二级索引中一个索引项对应一个索引块，登记该索引块的最大关键码及该索引块的存储地址。
多级索引结构用 m 叉树表示，称为 m 路搜索

静态索引结构（ISAM 索引顺序存取方法文件）¶

典型的例子是对磁盘上的数据文件建立盘组、柱面、磁道三级地址的多级索引。
ISAM 文件用柱面索引对各个柱面进行索引。一个柱面索引项保存该柱面上的最大关键码 （最后一个记录）以及柱面开始地址指针。
- 如果柱面太多，可以建立柱面索引的分块索引，即主索引。主索引不太大，一般常驻内存。
在每个柱面上，所有数据记录存放于基本区，此外保留一部分磁道作为溢出区。
所有记录在基本区按关键码升序排列，后一磁道所有记录的关键码均大于前一磁道所有记录的关键码。（用于选择统一柱面不同盘面上的磁道）
- 通过位于每个柱面第 0 号磁道上的磁道索引进行搜索
- 基本区索引项：它包含本磁道在基本区最大的关键码和该磁道基本区的开始地址指针。
- 溢出区索引项：它存放的是本磁道在溢出区的最大关键码和溢出记录链的头部指针。
在某一磁道插入一个新记录时，如果原来该磁道基本区记录已经放满，则根据磁道索引项指示位置插入新记录后，把最后的溢出记录（具有最大关键码）移出磁道基本区，再根据溢出索引项将这个溢出记录放入溢出区，并以有序链表插入算法将溢出记录链入。

动态索引结构（m 路搜索树）¶

m 路搜索树的定义
- 一棵空树，或者是一个满足以下性质的节点结构的树：
- 根节点最多有 m 棵子树，并具有以下结构：
  (n, P0, K1, P1, K2, P2, …, Kn, Pn)
  其中：
  - Pi 是指向子树的指针，满足 0 ≤ i ≤ n < m；
  - Ki 是关键码，满足 1 ≤ i ≤ n < m 且 Ki < Ki+1 对于 1 ≤ i < n。
- 对于任意节点内部的关键码和指针的关系满足：
- 在子树 Pi 中的所有关键码 K 都满足 Ki < K < Ki+1 对于 0 < i < n；
- 在子树 Pn 中的所有关键码都大于 Kn；
- 在子树 P0 中的所有关键码都小于 K1。、
- 每个子树 Pi 也是一个 m 路搜索树，满足 0 ≤ i < n。
每个节点最多有 \(m-1\) 个关键码，高度为 h 的 m 路搜索树中关键码最大数目为 \(m^h-1\)
提高搜索树的路数 m, 可以改善树的搜索性能。对于给定的关键码数 n，如果搜索树是平衡的，可以使 m 路搜索树的性能接近最佳。

搜索算法：

const int MaxValue = ……;
//关键码集合中不可能有的最大值
template <class T>
    struct MtreeNode {
        //树结点定义
        int n;
        //索引项个数
        MtreeNode<T> *parent;
        //父结点指针
        T key[m+1]; //key[m]为监视哨，key[0]未用
        int *recptr[m+1];
        //索引项记录起始地址指针
        MtreeNode<T> *ptr[m+1];//子树结点指针，ptr[m]在插入溢出时使用
    };
template <class T>
    //搜索结果三元组
    struct Triple {
        MtreeNode<T> *r;
        //结点地址指针
        int i;
        //结点中关键码序号i
        int tag;
        //tag=0,成功; =1,失败
    };
template <class T>
    class Mtree {
        //m叉搜索树定义
        protected:
        MtreeNode<T> *root;
        //根指针
        int m;
        //路数
        public:
        Triple<T> Search(const T& x);
        //搜索
    };
template <class T>
    Triple<T> Mtree<T>::Search (const T& x) {
        //tag = 0, 表示 x 在结点r中找到, 该结点的k[i]等于x;
        //tag = 1, 表示没有找到x, 可插入结点为r, 插入到该
        //结点的k[i]与k[i+1]之间。
        Triple result;
        //记录搜索结果三元组
        GetNode (root);
        //从盘上读取结点root
        MtreeNode<T> *p = root, *q = NULL;
        //p是扫描指针,q是p的父结点指针
        int i = 0;
        while (p != NULL) {
            //从根开始检测
            i = 0; p->key[(p->n)+1] = MaxValue;
            while (p->key[i+1] < x) i++;
            //在结点内搜索
            if (p->key[i+1] == x) {
                //搜索成功
                result.r = p; result.i = i+1; result.tag = 0;
                return result;
            }
            q = p; p = p->ptr[i];
            //本结点无x, q记下当前结点, p下降到子树
            GetNode(p);
            //从磁盘上读取结点p
        }
        result.r = q; result.i = i; result.tag = 1;
        return result;
        //搜索失败,返回插入位置
    };

B 树 #难点¶

在大规模数据存储中，二叉查找树的深度会过大，当内存无法存储所有节点数据时，需要读取磁盘，进行 IO 操作，从而树的高度越高，I/O 操作次数越多，效率也就越低。所以诸如之前所讲的红黑树，AVL 树因为树的高度太高而不适合这种需要大量 IO 操作的查询。所以，B 树通过多叉的实现来降低树的高度，从而减少 IO 操作的次数。
与红黑树对比
应用：
- B 树：常用于数据库和文件系统中，因为它们可以大大减少磁盘 I/O 操作（层数少）。由于磁盘的寻址时间相对较长，B 树设计的目标是确保树的高度尽可能地短，从而减少磁盘读/写操作。
- 红黑树：常用于内存中的数据结构，例如在很多语言的库中实现的集合和映射。它们提供了最坏情况下的时间复杂度较好的性能，对于那些需要频繁插入、删除和查找的应用程序来说是非常有价值的。
效率：
- B 树：因为设计用于磁盘存储，B 树更关心存储空间和磁盘 I/O 操作的效率。它们减少了树的高度并优化了磁盘访问。
- 红黑树：因为设计用于内存操作，红黑树更关心时间效率，特别是插入、删除和查找的最坏情况下的性能。

B (-)树¶

定义：或者是空树, 或者是满足下列性质的树：
- 根节点至少有两个子女，其它所有节点至少有 \(\left\lceil \frac{m}{2} \right\rceil\) 个子女
- 所有失败节点 (搜索失败到达的节点，这些节点并不存在，指向他们的指针为 NULL) 位于同一层
- 符合 m 路搜索树的所有定义
所有数据都存储在非叶节点
使用 \(key[i]\) 指向节点；\(recptr[i]\) 指向实际记录的存放地址
每个节点的关键码个数 \(\left[ \left\lceil \frac{m}{2} \right\rceil -1,m-1\right]\)，对应子节点 \(\left[ \left\lceil \frac{m}{2} \right\rceil,m\right]\)
叶节点也称为终端节点
B 树搜索算法
- 继承了 m 路搜索树 Mtree 上的搜索算法
- B 树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程。
- B 树的搜索时间与 B 树的阶数 m 和 B 树的高度 h 直接有关
- 搜索成功的时间取决于关键码所在的层次，不成功的时间取决于树的高度
- 关键码总数有 \(N\leq m^h-1\) 即 \(h\geq \lceil \log_{m}(N+1) \rceil\)
  - 由于 B 树的定义还有
- 失败节点位于第 \(h+1\) 层，失败节点的数目为 \(N+1\)
- 即第 \(h+1\) 层节点数 \(N+1 \geq 2 \left\lceil \frac{m}{2} \right\rceil^{h-1}\)
- \(h{\leq}\log_{\lceil{\mathbf{m}}/2\rceil}({{(N+1)/2)+1}}\)
m 的选择
- 提高 m 可以可以减少 h 的高度，但是 m 很大一个节点的内容超出内存时反而增加了读盘次数，降低了效率
- 选择 m 使得 B 树种找到关键码 x 的时间总量最小
- 包含从磁盘种读入节点的时间+节点中进行搜索的时间
B 树的插入
- 插入总是在某个叶节点进行的, 之后自底向上分裂节点
- 如果插入后不会破坏定义（关键码数目不超过 m-1 ），则直接插入
- 如果插入后关键字数目大于 \(m-1\) 则要对插入后的节点进行分裂操作：\(\lceil m/2\rceil\) 关键字放入父节点中，其左侧节点留在原先的子树中，右侧节点放入新节点中。（这是一个递归操作）
B 树的删除
- 首先先通过搜索找要删除的关键码的位置
- 终端节点
- 若删除后关键字数目仍符合要求（分为根节点和不是根节点），可以直接删除
- 若删除后关键字数目过少，且兄弟够借（临近的兄弟节点的关键字个数 \(>=\lceil m/2 \rceil\) 则从兄弟节点借一个关键字
  - 将双亲结点中刚刚大于被删除关键码的关键字下移
  - 将右兄弟 (或左兄弟) 结点中的最小 (或最大) 关键码上移到双亲结点的 Ki 位置；
  - 将右兄弟 (或左兄弟) 结点中的最左 (或最右) 子树指针平移到被删关键码所在结点中最后 (或最前) 子树指针位置；
  - 在右兄弟 (或左兄弟) 结点中，将被移走的关键码和指针位置用剩余的关键码和指针填补、调整。再将结点中的关键码个数减 1
- 兄弟不够借，则删除关键字，并与一个不够借的兄弟节点合并
  - 若要合并 p 中的子树指针 Pi 与 Pi+1 所指的结点, 且保留 Pi 所指结点, 则把 p 中的关键码 Ki+1 下移到 Pi 所指的结点中。
  - 把 p 中子树指针 Pi+1 所指结点中的全部指针和关键码都照搬到 Pi 所指结点的后面。
  - 在结点 p 中用后面剩余的关键码和指针填补关键码 Ki+1 和指针 Pi+1。
  - 修改结点 p 和选定保留结点的关键码个数。在合并结点的过程中, 双亲结点中的关键码个数减少了。如果关键码减少数目不再符合条件，需要继续向上进行修复
- 非终端节点
- 使用右子树中最小关键码（被删除节点的后继节点）代替被删除的关键码，再从子树中删除最小关键码
- 这就转化为删除终端节点的问题

B+树¶

B+树是应文件系统所需而出的一种 B-树的变型树,MySQL 中实际使用
定义：
- 每个节点最多 m 个子树
- 根节点最少 1 棵，其它节点至少 \(\left\lceil \frac{m}{2} \right\rceil\) 棵，一棵子树对应一个关键码
差异
有n 棵子树的结点中含有n 个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
- 非叶子结点的子树指针 P[i]，指向关键字值属于[K[i], K[i+1])的子树
- 上层的非叶结点的关键码是其子树中最大（或最小）关键码的复写。
所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。\((K_{i} ,P_{i})\) 表示关键码与实际记录存储地址的映射
- 为所有叶子结点增加一个链指针；
所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。\((K_{i} ,P_{i})\) 表示自述中最大关键码与索引项的对应关系
B+树只有达到叶子结点才命中
处理指向根节点的指针外，还有一个指向叶节点的指针，B+ 树支持遍历叶节点顺序搜索，以及从根节点随机访问
插入
如果节点中有多余的空间放入元素，则直接插入即可。
如果插入后叶节点关键码个数大于 m，则将其分裂为两个节点，并将其中间元素的索引放入到父节点中
如果是叶子节点的话，拷贝中间元素的索引到父节点中（因为叶子节点需要包含所有的元素）
如果是非叶子节点，则是上移节点的中间元素到父节点中。
删除
仅在叶节点中删除元素，如果节点还满足 B+树的要求，则直接删除。
如果元素个数过少，并且其邻近兄弟节点有多余的元素，则从邻近兄弟节点中借一个元素，并修改父节点中的索引使其满足新的划分。
如果其邻近兄弟节点也没有多余的元素，则将其和邻近兄弟节点合并，并且我们需要修改其父节点的索引以满足新的划分。
并且如果父节点的索引元素太少不满足要求，则需要继续看起兄弟节点是否多余，如果没有多余则还需要与兄弟节点合并，如此不断向上，直到根节点。如果根节点中元素也被删除，则把根节点删除，并由合并来的节点作为新的根节点，树的高度减 1。
使用在文件系统的优势
叶子节点串成链表，非常适合范围查找
B+树的非叶子节点并没有指向关键字具体信息的指针，因此其内部节点相对 B 树更小，如果把所有同一内部节点的关键字存放在同一盘块中，盘块所能容纳的关键字数量也越多，具有更好的空间局部性，一次性读入内存的需要查找的关键字也越多，相对的 IO 读写次数也就降低了。
由于所有数据值都存储在叶子节点中，当新数据插入或旧数据删除时，B+树的大小变化较为稳定。

外排序 #难点¶

待排序的记录数目太多，无法在内存中一次处理，必须以文件形式存放于外存，排序过程中一部分一部分调入内存进行处理，这种基于外部存储设备的排序就是外排序。
外排序大多使用归并排序
外排序的基本过程
- 首先建立内存缓冲区，并根据内存缓冲区的大小对文件进行划分，对每一段数据分别进行排序，得到初始归并段，写回到外存
- 按照归并树的模式对初始归并段进行归并，不断扩大归并段，最终归并为一个大的归并段
把内存区域划分为 3 个缓冲区，两个输入缓冲区一个输出缓冲区。读取两个输入归并段，放在输入缓冲区，在内存中进行两路归并，并将结果输出到输出缓冲区。
若记录个数为 n ，磁盘上每个页块容纳 b 个记录，内存缓冲区可容纳 i 个页块，则每个初始归并段的长度为 \(len=i*b\) 可以生成 \(m=\left\lceil \frac{n}{len} \right\rceil\) 个等长的初始归并段
做两路归并时第一趟从 \(m\) 个初始归并段得到 \(\left\lceil \frac{m}{2} \right\rceil\) 个归并段，总归并次数为 \(\lceil \log_{2}m \rceil\)
\(t_{ES}=m^{*}t_{IS}+d^{*}t_{IO}+S^{*}n^{*}t_{mg}\)
- \(t_{io}\) 是从硬盘进行读写（注意读写分开算两次），是时间瓶颈；\(t_{mg}\) 则是从内存进行读写
因此想要提高外排序的效率要尽可能减小 d
- 增大归并路数可以减少归并趟数，有效减少 d
- 归并趟数为 \(\lceil \log_{k}m \rceil\)

多路（k）平衡归并¶

假设每趟归并 n 个元素，则一次大致进行 \((n-1)*(k-1)\) 次比较
- 即总共进行约 \((n-1)*(k-1)*\lceil \log_{k}m \rceil\)
- 也就是说 k 增大会使得内部归并的时间增大
- 使用败者树优化（获取最大元素复杂度 \(\log_{2}k\) ）复杂度变为 \(\lceil \log_{2}m \rceil*(n-1)\) 与 k 无关
归并路数 k 不是越大越好。归并路数 k 增大, 相应需增加输入缓冲区个数。如果可供使用的内存空间不变, 势必要减少每个输入缓冲区的容量, 使内外存交换数据的次数增大。

败者树¶

败者树是完全二叉树
每个叶结点存放各归并段在归并过程中当前参加比较的记录；
- 败者树在节点中存放败者
- 胜者树存放胜者
每个非叶结点存放它两个子女结点中记录排序码大的结点 (即败者)；（假设需要按从小到大排序）
- 败者树记录败者，但仍然派胜者继续向上
根结点的上一层另外增加一个结点，存放树中当前记录排序码最小的结点 (最小记录)。
- 这个额外节点存储的就是最终胜者（最小记录）
败者树叶结点 key[]有 k+1 个, key[0]到 key[k-1]存放各归并段当前参加归并的记录的排序码， key[k]是辅助工作单元, 在初始建立败者树时使用: 存放一个最小的在各归并段中不可能出现的排序码: -MaxValue。
败者树非叶结点 loser[]有 k 个, 其中 loser[1]到 loser[k-1] 存放各次比较的败者的归并段号 , loser[0]中是最后胜者所在归并段号。另外还有一个存放各归并段参加归并记录的数组 r[k]。
每选出一个当前排序码最小的记录, 就需要在将它送入输出缓冲区之后, 从相应归并段的输入缓冲区中取出下一个参加归并的记录, 替换已经取走的最小记录, 再从叶结点到根结点, 沿某一特定路径进行调整, 将下一个排序码最小记录的归并段号调整到 loser[0]中。
段结束标志 MaxNum 升入 loser[0], 排序完成
要注意的是初始化时是全为 -inf ，每个输入缓冲区的末尾是 inf 。
败者树的高度为 \(\lceil \log_{2}k \rceil+1\)
- 每次调整时做 \(\lceil \log_{2}k \rceil\) 次比较（这是优于堆的最坏情况的）
在内存中应为每一个归并段分配一个输入缓冲区, 其大小应能容纳一个页块的记录, 编号与归并段号一致。每个输入缓冲区应有一个指针, 指示当前参加归并的记录。
在内存中还应设立一个输出缓冲区, 其大小相当于一个页块大小。它也有一个缓冲区指针, 指示当前可存放结果记录的位置。每当一个记录 i 被选出, 就执行 OutputRecord (i)操作, 将记录存放到输出缓冲区中。
多路归并的具体过程 ![[多路合并.pdf]]