北京师范大学数据结构教学资料 第10章-文件、外部排序与外部搜索

文件、外部排序与外部搜索北京师范大学数据结构课程第10章Contents本章内容概览文件、外部排序与外部搜索——从存储结构到算法设计的系统性知识框架。01主存储器与外存储器02文件组织与管理03多级索引结构04外部排序算法05外部搜索技术Chapter01主存储器与外存储器理解内存与外存的本质差异，为外部排序算法设计奠定基础Chapter10·StorageHierarchy主存与外存的核心差异外存储器相比内存具有价格低廉和永久存储的优势，但访问速度慢5-6个数量级，这一根本性差异决定了外部排序与搜索算法的核心设计原则——最小化外存I/O次数。外存储器物理形态—服务器机房存储设备01主存储器（内存）访问速度快但容量有限且断电数据丢失，适合存放当前正在处理的数据和程序02外存储器（磁盘、磁带等）价格较低且具备永久存储能力，是大规模数据长期保存的主要介质03外存访问速度比内存慢5-6个数量级，一次磁盘I/O可能需要10ms而内存访问仅需10ns级别10msvs10ns04算法设计核心原则：必须使外存访问次数达到最少，这是衡量外排序和外搜索算法效率的关键指标MinimizeI/OSTORAGEDEVICE磁带存储设备的工作原理磁带作为顺序存取设备，其启停机制和间隙特性决定了必须采用块化策略来提高存储效率，逻辑记录打包为物理块是磁带数据组织的核心方法。01顺序存取与磁道结构：磁带数据记录在9个磁道上（8位数据+1位校验位），存储密度以BPI为单位，典型值有6250/1600/800BPI02记录间间隙IRG/IBG：每次启停有加减速过程，不稳定期间形成的空带称为记录间间隙，长度约0.3–0.75英寸03块化策略：将若干逻辑记录打包为物理块存储，大幅减少IRG/IBG对存储空间的浪费，提升磁带利用率04数据传输速度：等于存储密度乘以走带速度，正常走带速度3–5m/s，传输速度可达700,000–1,250,000字/秒不同存储密度下磁带容量对比存储密度从800BPI到6250BPI提升近8倍EXTERNALSTORAGE磁盘存储设备的访问特性磁盘作为直接存取设备，其访问时间由寻道时间、旋转延迟和传输时间三部分组成，其中寻道时间是主要瓶颈，减少磁头移动是磁盘排序优化的核心策略。磁盘访问时间构成~10ms寻道时间：磁头移动到目标磁道所需时间，通常为几毫秒到十几毫秒，是磁盘I/O中最大的时间开销4.17ms旋转延迟：等待目标扇区转到磁头下方，平均为磁盘旋转半圈的时间，7200转/分磁盘约4.17ms≪寻道传输时间：实际读写数据的时间，取决于数据量和磁盘传输速率，通常远小于寻道和旋转延迟磁盘与磁带对比RANDOM磁盘：支持直接存取（随机访问），可跳转到任意位置读写，适合需要频繁随机访问的排序和搜索场景SEQUENTIAL磁带：仅支持顺序存取，必须从头开始逐一经过记录，适合批量备份和顺序处理场景BLOCKI/O页块组织：磁盘按页块（block/page）组织数据，每次I/O读写一个完整页块，算法设计需充分利用页块内的全部数据CHAPTER02文件组织与管理从逻辑结构到物理存储，掌握文件组织的核心方法与效率分析数据结构·文件与外部排序文件的基本概念与组成结构文件由记录组成、记录由数据项组成，理解逻辑记录与物理记录的区别以及操作系统文件与数据库文件的差异，是掌握文件组织方法的前提。文件的层次结构01文件与记录文件（File）由若干记录（Record）组成，记录是文件存取的基本单位，如一条学生信息或一笔交易记录Record文件的层次结构02记录与数据项记录由若干数据项（DataItem/Field）组成，数据项是文件可使用的最小单位，如姓名、学号、成绩等DataItem逻辑记录与物理记录03逻辑vs物理记录逻辑记录是应用程序视角的数据单位，反映数据的语义结构；物理记录是操作系统实际读写的数据块逻辑↔物理逻辑记录与物理记录04文件类型与存储操作系统文件是流式文件（无结构字符流），数据库文件是具有结构的数据集合，按页块（block/page）存储和读写Block/PageSEQUENTIALFILE顺序文件的组织方式与特性顺序文件按关键字顺序排列记录，结构简单且适合批量处理，但随机查找需顺序扫描、插入删除需移动大量数据，在大型文件场景下效率受限。01有序存储：记录按关键字值的大小顺序排列存储，支持高效的顺序扫描和批量处理操作。02查找操作：顺序查找平均需扫描n/2个记录；折半查找仅需O(logn)次比较，但要求文件存储在可直接存取的设备上。03维护代价：插入需找到正确位置并移动后续所有记录，删除需填补空位或标记删除，维护有序性代价较高。04适用场景：数据相对稳定、以批量顺序处理为主的系统，如工资核算、月度统计报表、日志归档等。数据中心服务器机架与磁带库——顺序文件在大规模存储系统中的典型应用场景INDEXFILEORGANIZATION索引文件的组织方式与查找策略索引文件通过建立关键字到物理地址的映射表来加速查找，稠密索引与稀疏索引在索引表大小和查找精度之间做出不同权衡，是外存数据组织的核心技术。索引表的基本原理01映射关系索引表存储关键字与记录物理地址的映射关系，查找时先在索引表中定位再直接访问目标记录02稠密索引为每个记录建立索引项，查找精度高但索引表体积大，可能无法全部装入内存03稀疏索引为一组记录建立一个索引项，索引表较小但定位后还需块内顺序搜索索引文件的操作特性04查找效率通过索引可将O(n)顺序查找降为O(logn)级别，大幅减少外存I/O次数05维护开销插入和删除需同时维护数据文件和索引表的一致性，增加更新操作复杂度06多级索引索引本身存储在外存按页块组织，多级索引结构中查找索引也需多次I/O操作HASHFILEORGANIZATION散列文件的组织方式与冲突处理散列文件通过散列函数将关键字直接映射到存储地址实现O(1)级别查找，但冲突处理和动态扩展是其核心挑战，适合精确查找频繁而范围查询较少的场景。01O(1)定位：散列函数将关键字映射到存储地址，理想情况下直接定位记录，是查找速度最快的文件组织方式02冲突处理：开放定址法（线性探测、二次探测、双重散列）和链地址法（同义词链表），各有适用场景03装载因子α：α=记录数/桶数，α越大冲突概率越高，通常需控制在0.7以下以保持查找效率04局限性：不支持范围查询和顺序扫描，文件动态增长时可能需要重新散列（rehash），维护成本较高装载因子与平均查找长度关系α超过0.7后查找长度急剧增加CHAPTER03多级索引结构B树与B+树——数据库索引系统的核心数据结构CHAPTER10·外部搜索B树的定义与基本性质B树是平衡多叉搜索树，每个节点对应一个磁盘页块，通过约束节点关键字数量范围（⌈m/2⌉-1到m-1）保证树的平衡性，使得查找、插入、删除操作的外存I/O次数保持在O(logn)级别。数据库服务器机房·B树节点映射磁盘页块的物理载体01m阶B树定义：每个节点至多m棵子树（m-1个关键字），除根节点外至少⌈m/2⌉棵子树，所有叶子在同一层。02节点结构：每个节点包含n个关键字K1<K2<...<Kn和n+1个子树指针P0,P1,...,Pn，Pi-1指向的子树关键字均小于Ki。03平衡性保证：所有叶子节点到根的路径长度相同，树的高度h≤log⌈m/2⌉((N+1)/2)+1，查找最多h次磁盘I/O。04与二叉搜索树对比：B树每个节点有多个关键字，一次I/O读取整个页块获得多个分支信息，大幅降低树高和I/O次数。B-TREEOPERATIONSB树的查找与插入操作B树查找沿根到叶路径逐层搜索，每层一次磁盘I/O；插入操作在叶子节点执行，节点满时通过分裂维持平衡，分裂可能向上传递直至根节点。查找操作01从根节点开始，在每个节点内用折半查找确定目标关键字位置或应进入的子树分支方向02每经过一层需要一次磁盘I/O读取子节点，查找效率取决于树高h，最多h次I/O即可完成查找03查找失败时到达叶子节点下方，整个过程与二叉搜索树查找类似但每步获得更多信息插入操作与节点分裂01插入一定发生在叶子节点，先查找确定位置，若节点关键字数<m-1则直接插入并写回磁盘02节点已满时需分裂：取中间关键字上移至父节点，剩余关键字分为两个新节点03分裂可能向上传递：父节点接收上移关键字后若也满则继续分裂，最坏情况根节点分裂使树高+1B-TREE·DELETIONB树的删除操作与节点合并B树删除操作需维持每个节点关键字数量的下限约束，不足时通过向兄弟节点借关键字或与兄弟节点合并来恢复平衡，合并可能引发向上传递的连锁反应。01非叶子节点删除转化—用其左子树最大值或右子树最小值替换待删关键字，将非叶子节点删除转化为叶子节点的删除问题02叶子节点下限检查—删除后若关键字数≥⌈m/2⌉−1则直接完成；否则需要调整以维持B树的下限约束03向兄弟借关键字—若相邻兄弟节点关键字数>⌈m/2⌉−1，通过父节点旋转一个关键字到当前节点，恢复平衡04与兄弟合并—若兄弟节点也处于最低限度，将两个节点与父节点中的分隔关键字合并为一个节点05合并的连锁反应—合并使父节点减少一个关键字，可能导致父节点也不足，向上传递直至根节点DATASTRUCTUREB+树的结构特点与应用优势B+树将所有数据记录存储在叶子节点并通过链表相连，非叶子节点仅起索引作用，使树更矮且天然支持高效范围查询B+树结构示意图30501020354060701510203035404550556070⇄索引节点叶子节点（数据）⇄双向链表01所有数据记录存储在叶子节点，非叶子节点仅含索引关键字和子树指针，同样页块可容纳更多索引项02所有叶子节点通过双向链表相连，支持高效顺序扫描和范围查询，无需回溯到父节点03非叶子节点的关键字也出现在其子树中（仅作分隔符），查找总是到达叶子节点，性能更稳定04树高更低：非叶子节点不存数据可容纳更多关键字，相同数据量下B+树比B树矮1-2层，减少I/O次数05范围查询高效：定位范围起点后沿叶子链表顺序读取，避免B树范围查询时反复回溯父节点的问题06MySQLInnoDB聚簇索引采用B+树结构，主键索引的叶子节点直接存储完整数据行CHAPTER04外部排序算法在有限内存条件下高效完成大规模数据排序的核心方法与优化策略ExternalSorting外部排序的基本方法与两阶段流程外部排序采用归并排序法，分为生成初始归并段和多路归并两个阶段，通过在有限内存与外存之间高效调度数据块来完成超大规模数据的排序任务。PHASE1第一阶段：生成初始归并段01将含n个记录的大文件按内存容量分成若干长度为L的子文件（归并段），每个子文件可一次性装入内存02分别将各子文件调入内存，采用高效内排序方法（如快速排序、堆排序）排序后写回外存形成有序归并段03初始归并段数量k=⌈n/L⌉，归并段长度L取决于可用内存大小，内存越大则归并段越少、后续归并越快k=⌈n/L⌉PHASE2第二阶段：多路归并01对初始归并段进行多遍归并，每遍将多个有序段合并为更大的有序段，直到形成整个文件的单一有序段02归并路数m取决于可用内存缓冲区数量，m路归并需要m个输入缓冲区和1个输出缓冲区03归并趟数s=⌈logm(k)⌉，减少归并趟数是优化外排序效率的关键，可通过增大m或减少初始归并段数k实现s=⌈logm(k)⌉ExternalSorting·CaseStudy磁盘排序过程实例分析以4500记录文件、750记录内存容量为例，磁盘排序第一阶段生成6个有序归并段，第二阶段通过多路归并形成最终有序文件，整个过程以外存页块为I/O单位进行数据调度。输入条件：文件含4500个记录，内存容量750个记录，磁盘页块长250个记录，每次I/O读写一个页块4500记录第一阶段：每次读入3个页块到内存排序后写回，共生成F1–F6六个长度为750的有序文件6个归并段第二阶段（3路归并）：F1+F2+F3→F7，F4+F5+F6→F8，F7+F8→最终有序文件，共需2趟归并2趟归并I/O开销分析：第一阶段读写各6次，第二阶段每趟归并读写全部数据，总I/O与归并趟数成正比∝归并趟数磁盘排序各阶段I/O次数分布外排序的I/O开销主要集中在归并阶段，减少归并趟数是优化总I/O次数的关键EXTERNALSORTING败者树在多路归并中的应用败者树是一种完全二叉选择树，通过记录比较中的"败者"而非"胜者"，使得每次输出最小值后仅需O(logm)次比较即可找到下一个最小值，大幅提升m路归并的效率。结构与原理01败者树是完全二叉树，m个叶子节点对应m个归并段的当前元素，内部节点记录比较中的败者（较大值）02根节点上方的额外节点记录最终胜者（全局最小值），每次输出胜者后从对应叶子开始向上调整03新元素替换叶子后沿路径向上与父节点中的败者比较，败者留在节点、胜者继续上升效率优势04每次选择最小值仅需⌈log₂m⌉次比较，远优于直接比较法的m-1次，当m较大时优势显著05败者树与胜者树功能等价但调整更简单：败者树只需与父节点比较，胜者树需与兄弟节点比较06初始化O(m)时间，后续每次调整O(logm)，m路归并n个元素的总比较次数为O(n·logm)EXTERNALSORTING置换-选择排序：生成更长的初始归并段置换-选择排序通过堆结构动态管理内存中的元素，使大于当前输出值的元素继续参与当前归并段，生成的初始归并段平均长度可达2L（内存容量的两倍），显著减少归并段数量和后续归并趟数。01核心思想：内存维护大小为L的最小堆，输出堆顶后读入新元素，若新元素≥输出值则入堆继续当前段，否则冻结等待下一段02归并段平均长度可达2L：在输入数据随机分布的假设下，置换-选择排序生成的归并段平均长度为内存容量的两倍2L03效率提升：归并段数量从n/L降为约n/2L，归并趟数减少，总I/O次数显著降低，尤其对大规模文件效果明显n/2L04实现要点：使用最小堆管理活跃元素，冻结元素存入另一个堆，当前段结束时将冻结元素激活开始新段的生成归并段长度对比置换-选择排序将平均归并段长度从L提升到2L，归并段数量减半ExternalSortingOptimization多路归并的优化策略通过最佳归并树优化归并顺序和双缓冲技术实现I/O与计算并行，从减少总I/O量和隐藏I/O延迟两个维度显著提升外排序效率。最佳归并树01初始归并段长度不等时，归并顺序直接影响总I/O量。核心原则是短段优先归并、长段晚参与，可使总I/O达到最小。这种策略避免了长段被反复读写，显著降低磁盘访问开销。02构造方法类似哈夫曼树的贪心策略：每次选取最短的m个归并段进行合并，生成的新段重新参与后续合并，迭代进行直至形成单一有序段。带权路径长度最小保证I/O最优。03当实际归并段数不满足(m-1)的整数倍加1这一结构要求时，需补充长度为0的虚段，使归并树成为严格的m叉树，确保算法正确执行。双缓冲与I/O并行技术01单缓冲模式下，I/O操作与CPU计算串行执行：CPU处理数据时I/O设备空闲等待，而进行I/O时CPU又处于阻塞状态，系统资源利用率低下，整体吞吐受限。02双缓冲机制引入两组交替工作的缓冲区：CPU处理一组缓冲区内数据的同时，另一组缓冲区并行执行I/O操作，实现计算与I/O的流水线并行，消除等待时间。03实际系统通常配置m个输入双缓冲加1个输出双缓冲，形成完整的缓冲池架构，确保m路归并过程中I/O延迟被完全隐藏，CPU持续满载运行。PerformanceAnalysis外部排序的性能分析与优化总结外排序总时间由I/O时间和CPU比较时间组成，增大归并路数m可减少归并趟数但增加内存需求，置换-选择排序和最佳归并树分别从减少初始段数和优化归并顺序两个维度降低总I/O量。01I/O瓶颈：归并趟数s=⌈log_m(k)⌉，每趟读写全部n个记录，总I/O量为2n·s，I/O时间是外排序的主要瓶颈02败者树优化：每次选择最小值需⌈log₂m⌉次比较，总CPU比较次数为n·s·⌈log₂m⌉，增大m对CPU影响可控03置换-选择排序：使初始归并段平均长度从L增至2L，k减半使s减少约1趟，总I/O量降低显著04综合优化路径：增大内存→增大归并段长度和归并路数→配合置换-选择排序→使用败者树→双缓冲并行I/O归并路数m对归并趟数和总I/O量的影响从2路增至6路可将归并趟数减半、总I/O量降低50%，但继续增加路数边际收益递减CHAPTER05外部搜索技术面向外存特性的搜索算法设计，平衡查找效率与存储开销EXTERNALSEARCHING外部搜索的基本方法与效率衡量外部搜索以磁盘I/O次数为主要效率指标，不同文件组织方式（顺序、索引、B树、散列）对应不同的搜索策略，I/O次数从O(n)到O(1)跨度极大，选择合适的文件组织方式是优化搜索效率的根本。效率指标核心指标是磁盘I/O次数而非关键字比较次数，因为一次I/O（毫秒级）远慢于一次内存比较（纳秒级）每次I/O读取一个完整页块（通常包含数十到数百个记录），应充分利用页块内所有数据减少后续I/O搜索效率取决于文件组织方式：顺序文件O(n/B)次、索引文件2-3次、B树O(logmn)次、散列O(1)次适用场景顺序搜索：适合小型文件或批量扫描场景，实现简单但随机查找效率低，不适合频繁查询的大型文件索引搜索：适合查询频繁但数据更新较少的场景，索引表需要额外存储空间且更新时需同步维护B树/B+树：适合同时支持精确查找和范围查询的场景，是数据库系统最常用的索引结构散列搜索：适合精确查找为主、不需要范围查询的场景，查找最快但不支持顺序扫描和范围检索EXTENDIBLEHASHING可扩充散列：动态适应数据增长的外部搜索可扩充散列通过目录数组和桶分裂机制实现散列表的动态扩展，桶满时仅分裂目标桶而非重建整个表，查找通常仅需2次I/O，是外存散列搜索的高效动态方案。目录数组→桶结构示意DIRECTORYd[0]d[1]d[2]d[3]d[4]BUCKETPage0Page1Page2Page3Page4全局深度d=3，目录大小=2d=8基本结构：目录数组（directory）存储指向桶（bucket）的指针，每个桶对应一个磁盘页块，目录大小由全局深度d控制2d查找过程：对关键字取散列值的前d位作为目录索引，找到对应桶后在桶内顺序搜索，通常仅需2次磁盘I/O2×I/O桶分裂：桶满时检查局部深度，若局部深度<d则仅分裂该桶并更新目录指针；若局部深度=d则先翻倍目录再分裂局深=d优势与局限：扩展代价小（仅分裂目标桶）、查找快速，但目录可能膨胀且不支持范围查询和顺序扫描代价小FILEORGANIZATION·COMPARISON外部搜索方法综合对比各种外部搜索方法在查找效率、更新代价、范围查询支持和空间开销等方面各有优劣，实际系统设计中需根据查询模式、更新频率和数据规模选择最适合的文件组织方式。外部搜索方法效率与特性对比搜索方法查找I/O次数范围查询更新代价最佳适用场景顺序文件O(n/B)支持高（移动数据）批量处理、日志归档索引文件2-3次支持中（维护索引）查询频繁、更新较少B+树O(logmn)支持中（节点分裂/合并）数据库主索引散列文件O(1)不支持低（直接定位）精确查找为主可扩充散列2次不支持低（桶分裂）动态增长的精确查找B+树在综合性能上最优，是数据库系统的首选索引结构；散列方法在精确查找场景下效率最高Chapter10·Application外排序与外搜索在实际系统中的应用外排序和外搜索技术广泛应用于数据库系统、分布式计算框架和操作系统中，从SQL排序到B+树索引再到MapReduce的Shuffle阶段，本章所学内容是现代计算机系统的核心基石。数据库系统应用SQL·QueryORDERBYSQL的ORDERBY和GROUPBY操作在数据量超过内存时自动触发外部排序，使用多路归并算法完成IndexB+TreeMySQLInnoDB引擎采用B+树聚簇索引，Oracle使用B*树索引，PostgreSQL支持B+树和Hash索引OptimizerHashJoin数据库查询优化器根据统计信息自动选择索引扫描、全表扫描或散列连接等执行策略分布式系统与操作系统MapReduceShuffleMapReduce框架的Shuffle阶段本质是分布式外部排序：Map端生成有序分区，Reduce端多路归并VirtualMemoryPageTable操作系统虚拟内存管理使用页表（多级索引结构）和页面置换算法，与外存数据管理思想一脉相承ext4·NTFSFileIndex文件系统（如ext4、NTFS）使用B+树或Hash索引管理文件元数据，支持高效的文件定位和目录遍历Chapter10·Review本章核心知识点回顾本章从外存特性出发，系统构建了文件组织、多级索引、外部排序和外部搜索四大知识模块，核心思想是通过优化数据在外存上的组织方式和减少I/O次数来提升大规模数据处理的效率。01外存访问特性外存访问比内存慢5–6个数量级，所有外存算法的核心目标是减少I/O次数02文件组织方式顺序文件（批量处理）、索引文件（快速查找）、散列文件（O(1)定位）三种方式03逻辑与物理记