海量数据处理专题(九)——外排序

【引言】

在数据结构的课程上,我们学习了不少的排序算法,冒泡,堆,快排,归并等。但是这些排序方法有着共同的特点,那就是所有的操作都是在内存中完成的,算法过程中不需要IO,这就使得这样的算法总体上速度比较快,但是也随之出现了一个问题:当需要排序的数据量异常的大的时候,以上的算法就显得力不从心了。这时候,你需要一种另外的排序算法,它的名字叫“外排序”。

通常的,设备的内存读取速度要比外存读取速度快得多(RAM的访问速度大约是磁盘的25万倍),但是内存的容量却要比外存小很多,当所有的数据不能在内存中完全放下的时候,就需要使用到外排序。这是外排序的一个显著特征。 继续阅读