External Sorting
Sorting a collection of records on some (search) key is a very useful
operation.
When the data to be sorted is too large to fit into available main memory, we need to
use an external sorting algorithm. Such algorithms seek to minimize the
number of disk accesses.
Minibase supports external merge sort
(see the
text for a full
description)
:
Suppose we have M buffer pages available in memory, and we need to sort a large
file with, say, N pages. There are two passes for the external sort.
- In Pass 0, read in M pages at a time and sort internally to produce ceil(N/M) runs
of M pages each (except the last run, which may contain fewer pages).
Runs are held in temporary heap files.
- In Passes i = 1, 2, ..., use M - 1 buffer pages for input, and use the remaining
page for output; thus you do a M - 1 way merge in each pass.
The public interface for the external sorting utility is available
here.
Back to the List of Components
Back to the Minibase Home Page
|
