| External heaps combined with effective buffering | |
| Authors: | Ramzi Fadel, Kim Vagn Jakobsen, Jyrki Katajainen, and Jukka Teuhola |
| Publication: | Report 96/40, Department of Computer Science, University of Copenhagen (1996), 7 app.pp. |
| Abstract: | An external heap structure is suggested that tries to make the best use of the available buffer space in main memory. The heap is a multi-way balanced tree, with blocks of records as nodes, satisfying a generalized heap property. The root is buffered, whereas other nodes are kept on secondary storage. A special property of the tree is that the nodes may be partially filled, as with B-trees. The structure is complemented with priority queue operations insert and delete-max. When handling a sequence of these operations, the amortized number of page accesses per operation is shown to be O((1 / P) log(M / P) (N / P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N the largest number of records in the heap (4 P < M < N). This results in optimal external heapsort that performs O((N / P) log(M / P) (N / P)) page accesses in the worst case, when sorting N records. |
| Related: |  HTML (Conference version) |
| BibLATEX: | @report{FJKT1996R,
author = {Ramzi Fadel and Kim Vagn Jakobsen and Jyrki Katajainen and Jukka
Teuhola},
title = {External heaps combined with effective buffering},
type = {Report},
number = {96/40},
institution = {Department of Computer Science, University of Copenhagen},
year = {1996},
pagetotal = {7},
}
|