File and Index Structures

Physical database design

The phase where the logical data model is translated into an actual physical structure for a specific DBMS; focuses on HOW data is stored, accessed, and optimized for performance.

Three main phases of database design

1) Conceptual design, 2) Logical design, 3) Physical design.

Conceptual/logical design vs. physical design

Conceptual and logical design focus on WHAT data is stored and how it is logically organized; physical design focuses on HOW it is stored, accessed, and optimized.

SQL query evaluation

The process by which a DBMS interprets a SQL query, determines the most efficient execution plan (optimization), and carries it out (execution).

Relational operators

Basic operations used to process queries: selection, projection, join, union, and intersection. The DBMS combines them to execute complex SQL queries.

Access methods

Techniques for efficiently retrieving data from storage. Examples: sequential scan, index scan, hash lookup, B+ tree traversal.

Buffer management

Manages in-memory storage of disk pages during query execution; reduces disk I/O by keeping frequently accessed data in RAM.

Disk/file management

Organizes how data is stored on physical media; includes file structures, page allocation, and strategies to minimize seek time and maximize throughput.

Storage device hierarchy (fastest to slowest)

Cache memory, main memory, flash memory, magnetic disk, optical drives, magnetic tapes. Arranged by speed, cost, and capacity.

Why not store everything in main memory?

Cost (RAM is expensive compared to disk) and volatility (data in RAM is lost when power is off).

Typical storage hierarchy in a DBMS

Main memory (RAM) = data currently in use; Disk (secondary storage) = persistent main database; Tape (tertiary storage) = archive of older or less frequently accessed data.

Disks vs. tapes

Disks allow random access at a fixed cost per page (consecutive pages are much cheaper than random ones). Tapes are sequential-only, cheaper, and mainly used for archival storage.

Why is disk access the primary bottleneck in a DBMS?

Disk access is thousands of times slower than memory access.

Disk block (page)

The unit in which data is stored on and transferred between disk and main memory.

Disk organization

The disk surface is divided into tracks, which are subdivided into sectors; each track is divided into equal-sized disk blocks (pages).

Three components of disk block access time

1) Seek time (move head to the correct track), 2) Rotational delay (wait for block to rotate under head), 3) Transfer time (move data to/from disk surface).

Which access-time components dominate?

Seek time and rotational delay.

Best practice to reduce disk I/O cost

Store the blocks of a file sequentially on disk to minimize seek and rotational delays.

Record ID (rid)

Identifies a record's physical location on external storage.

Index

A data structure that allows efficient retrieval of record IDs based on a search key.

Buffer manager

Loads pages from physical storage into main memory (the buffer cache/pool) as needed. File and index layers go through it to access data.

Buffer pool bookkeeping

A table of pairs tracks which pages are in memory; each frame also has a pin count and a dirty bit.

Steps when a requested page is not in the buffer pool

1) Choose a frame for replacement, 2) If the frame is dirty, write it back to disk, 3) Read the requested page into that frame, 4) Pin the page and return its memory address.

Pin count

The number of active requestors using a page. If it is zero, the page is a candidate for replacement.

Dirty bit

Indicates whether a page has been modified in memory (so it must be written back to disk before its frame is replaced).

Prefetching

Reading multiple pages at once when page requests are predictable (e.g., during sequential scans) to improve performance.

Write-Ahead Log (WAL)

Concurrency control and recovery mechanisms may require extra I/O, such as writing to a WAL, when a frame is selected for replacement.

Buffer replacement policies

Least-Recently-Used (LRU), Clock, and Most-Recently-Used (MRU). The best choice depends on the access pattern.

Sequential flooding

A problem with LRU during repeated sequential scans: if buffer frames < pages in the file, every page request causes an I/O. MRU performs much better here (workload-dependent).

Why a DBMS doesn't just rely on the OS for buffer/disk management

OS-based management has limited support for database-specific features and potential portability problems. A DBMS needs to pin pages, force pages to disk, customize replacement policy, and prefetch based on access patterns.

Blocking factor (bfr) formula

bfr = floor(B / R), where B = block size and R = record size.

Unused space per block formula

B - (bfr x R)

System catalogs

Store metadata about the database schema (relations, attributes and types, indexes, integrity constraints, views, statistics, authorization info, buffer pool size, etc.). Catalogs are themselves stored as relations.

What the catalog stores for each index

Its structure (e.g., B+ tree) and its search key fields (columns).

What the catalog stores for each relation

Relation name, file name and file structure (e.g., heap file), attribute names and types, names of associated indexes, and integrity constraints.

What the catalog stores for each view

The view name and definition.

Basic fixed-format record layout

Fields stored consecutively in a fixed order. Simple, but reaching the i'th field may require scanning preceding fields, and NULLs waste space because every field has reserved storage.

Directory-based record layout

A small directory at the start of the record stores offsets to each field. Gives direct access to the i'th field, handles NULLs efficiently by skipping unused fields, with minimal overhead.

Variable-length record: basic layout

Field count at the start, with fields delimited by special symbols (e.g., $).

Variable-length record: directory-based layout

An array of field offsets at the start of the record pointing to each field.

File (in DBMS terms)

A collection of pages (blocks), where each page contains a collection of records.

Operations a file must support

Insert, delete, or modify a record; read a specific record by rid; scan all records (optionally with conditions to retrieve a subset).

Heap (unordered) file

Simplest file structure; records are stored in no particular order. Best when most operations scan the entire file. Pages are allocated and de-allocated dynamically.

What a heap file must track

The pages belonging to the file, free space on each page, and the records stored within each page.

Heap file implemented as a list

A header page points to two linked lists of data pages: full pages and pages with free space. Each page has two pointers (previous and next) in addition to record data.

Heap file using a page directory

A header page leads to a directory (a collection of pages, e.g., a linked list) whose entries point to data pages; an entry can include the number of free bytes on that page.

Sorted file

Records are kept in order on a search key. Ideal when records must be retrieved in a specific order or when only a range is needed.

File organizations: heap vs. sorted vs. index

Heap: scan all records. Sorted: ordered or range retrieval. Index: tree or hash structure on search key fields; speeds up searches for subsets like a sorted file, but updates are generally much faster than in sorted files.

Primary index

An index on a set of fields that includes the primary key, so it has no duplicate search key values.

Secondary index

Any index that is not a primary index; may contain duplicate search key values.

Unique index

An index whose search key corresponds to a candidate key, so each search key value is unique.

Clustered index

An index where the physical order of data records on disk is the same as (or closely follows) the order of the index's search key values.

Unclustered index

An index where data records are stored in an order independent of the index's search key order.

Clustering constraint

A data file can be clustered on at most one search key, so at most one clustered index can exist per data file (multiple unclustered indexes are allowed).

Why clustered indexes matter for performance

They generally give significantly lower I/O cost for range queries than unclustered indexes.

Building a clustered index

First sort the heap file on the search key, typically leaving some free space on each page for future insertions.

Hash-based index

Organized as a collection of buckets; well suited for equality selections (not range queries).

Bucket (in hashing)

A primary page plus zero or more overflow pages.

Hash function h(r)

Maps a record r to its bucket by applying h to r's search key fields. Example: h(x) = x mod 4.

Modulo operation

Returns the remainder of a division; used here to define hash functions.

Two hashing techniques covered

Extendible hashing and linear hashing (both are dynamic).

Extendible hashing

A dynamic hashing technique that uses a directory of bucket pointers plus buckets. Characterized by a global depth and a local depth per bucket.

Global depth (d) in extendible hashing

Determines how directory entries map to buckets. The directory has 2^d entries, each storing a bucket address.

Local depth (d') in extendible hashing

The number of hash bits used to identify records in a bucket. Always d' <= d.

When is local depth equal to global depth for every bucket?

When each directory entry points to a distinct bucket.

Extendible hashing: bucket overflows and d' < d

Allocate a new bucket (split) and update the directory entries; the directory does not need to double.

Extendible hashing: bucket overflows and d' = d

The directory must be doubled and the global depth increased by one; the bucket is split and its local depth increases by one.

Extendible hashing example: insert 20 into d=2 (mod 4) with bucket 0 full (4, 12, 16, 32)

Local depth = global depth, so the directory doubles to d=3 (mod 8). Bucket 0 splits into 16, 32 (000) and 4, 12, 20 (100); both get local depth 3.

Extendible hashing example: insert 9 into d=3 where bucket 001 is full (1, 5, 21, 13, local depth 2)

Local depth < global depth, so just split without doubling: 1, 9 go to bucket 001 and 5, 13, 21 go to bucket 101; both get local depth 3.

Linear hashing

A dynamically updatable, disk-based hash index that grows or shrinks one bucket at a time. Mainly supports exact-match queries. Uses overflow pages.

Linear hashing: which bucket is split?

Buckets are split in round-robin order (bucket 0, then 1, 2, …), NOT necessarily the one that overflowed. A split is triggered whenever any bucket overflows.

Linear hashing: Next pointer

Marks the next bucket to split. Buckets 0 to Next-1 have already been split in the current round.

Linear hashing: family of hash functions

h0 = x mod 2^2, h1 = x mod 2^3, h2 = x mod 2^4, … (h_level, h_level+1, …). Used to determine the bucket for a key.

Linear hashing example: insert 43 (43 mod 4 = 3) when bucket 11 is full

Create an overflow page for bucket 11 and place 43 there; then split the bucket at Next (bucket 00) using h1 (mod 8), moving 36 and 44 to new bucket 100 and leaving 32.

Linear hashing weakness

Skewed data distributions can create long overflow chains, hurting performance.

Extendible vs. linear hashing (key difference)

Extendible uses a directory and doubles it when needed, with no overflow chains in the basic scheme. Linear uses no directory, splits buckets round-robin, and relies on overflow pages.