RandomAccessFile(String name, String mode)
close()
read(byte[] b)
write(byte[] b)
seek(long pos)
Primary storage: Main memory (RAM)
An organization for data on disk is often called a file structure.
Disk-based space/time tradeoff: Compress information to save processing time by reducing disk accesses.
// ADT for buffer pools using the message-passing style
public interface BufferPoolADT {
// Copy "sz" bytes from "space" to position "pos" in the buffered storage
public void insert(byte[] space, int sz, int pos);
// Copy "sz" bytes from position "pos" of the buffered storage to "space"
public void getbytes(byte[] space, int sz, int pos);
}
// ADT for buffer pools using the buffer-passing style
public interface BufferPoolADT {
// Return pointer to the requested block
public byte[] getblock(int block);
// Set the dirty bit for the buffer holding "block"
public void dirtyblock(int block);
// Tell the size of a buffer
public int blocksize();
};
// Improved ADT for buffer pools using the buffer-passing style.
// Most user functionality is in the buffer class, not the buffer pool itself.
// A single buffer in the buffer pool
public interface BufferADT {
// Read the associated block from disk (if necessary) and return a
// pointer to the data
public byte[] readBlock();
// Return a pointer to the buffer's data array (without reading from disk)
public byte[] getDataPointer();
// Flag buffer's contents as having changed, so that flushing the
// block will write it back to disk
public void markDirty();
// Release the block's access to this buffer. Further accesses to
// this buffer are illegal
public void releaseBuffer();
}
public interface BufferPoolADT {
// Relate a block to a buffer, returning a pointer to a buffer object
Buffer acquireBuffer(int block);
}
To sort, portions of the data must be brought into main memory, processed, and returned to disk.
An external sort should minimize disk accesses.
Approach 1: Read in entire records, sort them, then write them out again.
Approach 2: Read only the key values, store with each key the location on disk of its associated record.
After keys are sorted the records can be read and rewritten in sorted order.
Quicksort requires random access to the entire set of records.
A group of sorted records is called a run.
Is each pass through input and output files sequential?
What happens if all work is done on a single disk drive?
How can we reduce the number of Mergesort passes?
If the next key in the file is greater than the last value output, then
- Replace the root with this key
else
- Replace the root with the last key in the array
Add the next record in the file to a new heap (actually, stick it at the end of the array).
Is there benefit from sequential reading?
Is working memory well used?
Need a way to reduce the number of passes.