基于蛇型磁带的海量数据排序算法

A Massive Data Sort Algorithm Based on Serpentine Tape

在数字图书馆和数据仓库中,需要解决海量数据的排序问题.利用蛇型磁带自身的物理特点,实现了一种高效的磁带排序算法STESort(serpentine tape external sort).与传统的2路归并磁带排序算法相比,STESort算法减少了磁带总定位时间.STESort算法具有更优的效率.STESort算法在提高排序效率的同时,通过减少磁头在磁带表面的移动次数延长了磁带的使用寿命.理论分析和实验结果表明,STESort算法优于传统的磁带排序算法,适合于海量数据排序.

In order to solve massive data sort in digital library and dataware house, a new highly efficient algorithm based on serpentine tape, named STESort (serpentine tape external sort), is provided in this paper. Taking full advantage of the characteristics of serpentine tape, the STESort algorithm reduces the whole seek time on tapes compared with traditional 2-way merge tape sort algorithm. Besides increasing the efficiency of tape sort, the STESort algorithm prolongs the duration of tapes by reducing the times of tape header moving on tape surface. The theoretical analysis and the experimental results show that the STESort algorithm is more efficient than the traditional tape sort algorithms. The STESort is suitable for massive data sort.