Please enable JavaScript.
Coggle requires JavaScript to display documents.
External Sorting - Coggle Diagram
External Sorting
-
-
External Merge-Sort
Problem: Sort N pages with B available buffer pages (N>=B) => same relation sorted on a given attribute
Solution
- Split into small chunks to sort in memory (runs)
- Merge groups of runs using external merge algorithm
- Keep merging (each time = pass) until a single sorted file
run: each sorted sub-file, size = # buffer frames
2-way merge algorithm: 3 buffers, I/O = 2N(ceil(log2(N))+1)
-
-
External Merge
-
Merge B lists with B+1 buffer pages, with same I/O