4.1外存存储结构与外存算法：

分层存储：

做法：

可扩展性问题：若程序分散地访问磁盘上的数据，即使是好的操作系统也无法利用数据块存取优势

基本界限：

、

队列和堆栈：

4.2外存算法示例：外存排序算法

算法的分析1：(多路归并)

M/B路

以块为单位进行调度

1.首先从磁盘里把磁盘块放进内存，在内存中进行排序，每次放M/B块，一共放N/B块。做完后，外存中已经是在大小为M/B的区域里、分别排好序的数据。再分别取M/B-1个这些区域的第一个元素，放入内存中。

2.在内存中，将M/B-1块用于磁盘块的归并，剩余的一块用作缓存

do{

　　step1.[取出]M/B-1块中最小的数据，放于缓存中

　　step2.(用于缓存的磁盘块未满，step1)||(缓存满后，写出到外存，清空缓存)||(前M/B-1个磁盘块中的数据被取完，加载相应区域的下一个磁盘块)

}while(将所有的磁盘块中的数据都进行了排序)

疑问：如果step1中，排序磁盘块的次数大于M/B-1，那么归并排序时应该怎么做？

(演示的例子里，在内存中排序磁盘块的次数=M/B-1=3)

 

循环停止条件：(k-1代表第k轮)

算法分析2：(快排)

根号(M/B)路

 

M=8，N=24，B=2

(8,16是选择的分点，buffer磁盘块的大小为B，buffer满了以后，将里面的数据写到外存)

此时，写出到外存的三个区域的元素还没进行排序，但是大小已经可以放进内存，接下来将数据放进内存进行排序。若大小仍不能放进内存，则继续上述做法，直到数据块的大小可以放进内存。

复杂度分析：

划分停止条件：

计算分割元素：

存在的问题：

解决方法：

改进的算法的步骤：

从而得到每一路归并的元素上限。

 

算法复杂性分析：

其中，步骤二经过根号(M/B)次抽取分割元素，在4N/根号(M/B)的数据(第一次的抽样的结果)内抽取

总结：

它们都是最优的。

 

4.3外存数据结构示例：外存查找树

内存查找树：

外存查找树：

外部搜索树：

存在的问题：使用红黑树维护BFS块

5.1B树：

B树上的查询：

为符合需求，B树应该满足的性质：

(a,b)树：

“所有的叶子在同一层并且包括a到b个元素”：叶子节点的磁盘块的数量为[a,b]

对(a,b)树进行分析：

(a,b)树中的操作：

　　插入：

　　

 

　　删除：

注：若最后合并影响了根节点，使根节点的儿子小于a，此时根节点是不变的(参考上文对根节点数量的定义)。然而，若根节点只有一个儿子，则把根节点给删了

B树的结论：

5.2KD树

 

查询：

kdB-树：

kdB-树的构建：

改进：

复杂度：

动态地改进：

　　插入：

　　

　　删除：

　　

kdB-树总结：

6.1 表排序及其应用

表排序(List Ranking)

表排序的困难之处：

一种高效的表排序算法：

分析：

目标：对给定的树T，以表L表示，进而让对T的每一种计算可用对L的一种rank来完成

 欧拉回路技术：

 

 应用场景：

1.父子关系判定：

2.计算前序计数：

3.计算子树大小：

 

6.2时间前向处理方法：

将图问题表示为有向无环图的估值问题

 

 

处理过程：

 

......

测试：

求最大独立集MIS(贪心法，不一定求得最优解)：

(1的入度为0，在I中，选取后面的节点时，若其父亲节点在I中，则该节点不能加入I中)：

 

6.3缩图法：

即把大的图缩到内存中

求连通性->半外存算法：结点在内存中，边在外存中

算法分析：

M(memory)

若|V|>M：　　

　　

　　

 

　　

　　算法复杂度分析：

　　

应用：最小生成树

时间复杂度分析：

 

 另一种图算法技术：