article20201122
大数据 | 大数据基础--算法之外村模型算法：外存模型
亲爱的读者朋友大家晚上好，前几次我们简单介绍了并行模型算法，这次我们来介绍外村模型以及相应的一些算法。
外存模型
到目前为止，按照存储模型，我们学过的算法模型应该分为两种：一种是\(RAM\)模型，也就是我们常用的算法的设计模型，另一种是\(I/O\)模型，内存比数据量小，外存是无限的。
外存访问与内存访问有一些差异：
- 与外存相比，内存的速度更快
- 外存的连续访问比随机访问代价小，也就是说：以块\((block)\)为单位访问，而不是\(elemen\ wise\)
在\(I/O\)模型中，内存的大小为\(M\)，页面大小为\(B\)，外存大小无限，页面大小为\(B\)。
基于外存模型的基本问题
在\(I/O\)模型中，内存的大小为\(M\)，页面大小为\(B\)，外存大小无限，页面大小为\(B\)。
连续读取外存上的\(N\)个数据，需要多少次\(I/O\)？
\(O(N/B)\)
如何计算矩阵乘法？
输入两个大小为\(N\times N\)的矩阵\(X\)和\(Y\)
将矩阵分为大小为\(\sqrt{M}/2\times\sqrt{M}/2\)的块
考虑\(X\times Y\)矩阵中的每个块，显然共有\(O((\frac{N}{\sqrt{M} })^2)\)个块需要输出
每个块需要扫描\(\frac{N}{\sqrt{M} }\)对输入块
每次内存计算需要\(O(M/B)\)次\(I/O\)
共计\(O((\frac{N}{\sqrt{M} })^3\cdot M/B)\)次\(I/O\)
链表
进行三种操作：\(insert(x,p),remove(p),traverse(p,k)\)
内存模型下各个操作的时间复杂度：\(update O(1),traverse O(k)\)
在外存模型下，将一个链表中连续的元素放在一个大小为\(B\)的块中。同时，令每个块大小至少为\(B/2\)：
- \(remove:\)删除后如果小于\(B/2\)，与邻接的块合并，合并后如果大于\(B\)，则平均划分
- \(insert:\)插入后如果大于\(B\)，则平均划分
- \(traverse:O(2k/B)\)
搜索结构
进行三种操作：\(insert(x),remove(x),query(x)\)
\((a,b)-tree:2\leq a \leq (b+1)/2\)
类似二分查找树\(\Rightarrow (p_0,k_1,...,k_c,p_c)\)
\(root\)节点有0个或者\(\geq 2\)个孩子；除了\(root\)，每个非叶子节点的孩子数目\(\in [a,b]\)：
- \(remove:\)找到对应叶子节点，删除后如果小于\(a\)，与邻接的块合并，合并后如果大于\(b\)，平均划分，进而在上一层递归删除节点或者调整键值
- \(insert:\)找到对应叶子节点，插入后如果大于\(b\)，平均划分，递归向上一层插入
- \(query:O(log_a(N/a))\)
总结
以上就是关于外存模型的简单介绍以及一些基本的基于外村模型的数据结构和简单问题解决方案。下次我们会对外存排序问题进行分析，敬请期待~