Storing Data: Disks and Files

Disk Structure

Disks consist of platters, tracks, sectors, and blocks (pages)

Disk Page

Smallest unit of data transfer between disk and memory (typically 4–8 KB)

Seek Time

Time to move the disk arm to the correct track

Rotational Delay

Time for the disk to rotate desired sector under the read/write head

Transfer Time

Time to transfer data from disk to memory once positioned

Access Time =

Seek Time + Rotational Delay + Transfer Time

File

Sequence of pages, used to store records

Page

File I/O unit; a fixed-size block of data

Record

Logical unit of data stored in a page

Fixed-Length Record

Each field has a set size; simple layout

Variable-Length Record

Fields differ in size; uses a directory of field offsets

Slotted Page Structure

Supports variable-length records and record deletion

Page Header (Slotted Page)

Stores number of records, free space pointer, and slot directory

RID (Record ID)

Identifier that uniquely points to a record (Page ID + Slot ID)

Heap File

Unordered collection of records; easy inserts

Sorted File

Records kept sorted by a key; good for range queries

Hashed File

Hash function determines record placement; fast equality lookup

Free Space Management

Tracks pages with free space for new inserts

File Header

Stores metadata about the file (e.g., record format, page info)

Insertion in Heap File

Add record to first page with space or append to end

Deletion in Heap File

Mark slot as free and possibly track free space

Updating Variable-Length Records

May require moving record if size grows

Directory-Based File System

File system maintains metadata and pointers to pages

Buffer Manager

Manages in-memory page caching for performance

Page Replacement Policies

LRU, Clock, MRU used to choose which page to evict

Pinning a Page

Prevents buffer manager from evicting page currently in use

Force Page

Write dirty page from buffer to disk immediately

Steal Policy

Allows buffer manager to overwrite uncommitted page (used with logging)

Checkpoints

Periodically flush all dirty pages and write log info for recovery