Unit 5 — Storage & Indexing

Unit Overview

This unit addresses one of the most critical aspects of database management — how data is physically stored on disk and how it can be retrieved efficiently. While SQL and relational algebra describe what data you want, the storage and indexing layer determines how fast you can actually get it. This is where theoretical database knowledge meets practical performance engineering.

Every time you execute a query, the database engine must decide how to locate the relevant records among potentially millions of rows stored across thousands of disk blocks. Without proper file organization and indexing, even simple queries could require scanning entire tables — an operation that might take minutes or hours on large databases. Indexing structures like B-trees and hashing techniques reduce this to milliseconds.

Topics Covered in This Unit

The Disk Access Problem

Understanding storage requires understanding why disk access is expensive. Reading data from a hard disk involves mechanical movement — the disk arm must seek to the correct track and wait for the platter to rotate to the correct sector. Even with modern SSDs, reading from persistent storage is orders of magnitude slower than reading from RAM.

This enormous speed gap means that database performance is dominated by the number of disk block accesses. Every indexing technique in this unit aims to minimize disk I/O — the fewer blocks you read, the faster your query completes.

How Topics Build on Each Other

File organization establishes how records are physically laid out — this determines baseline performance for sequential scans. Single-level indexing adds a first layer of organization on top of the data files. Multi-level indexing addresses the problem of large single-level indexes by building indexes on indexes, naturally leading to B-trees and B+ trees as the standard index structures used in virtually every commercial database system.

Hashing provides an alternative to tree-based indexing — instead of traversing a tree structure, a hash function computes the exact location of a record in one step. Static and dynamic hashing explore fixed versus adaptive approaches to this technique.

Finally, query processing and optimization tie everything together — given a SQL query, the optimizer uses knowledge of available indexes, file organization, and cost estimation to choose the fastest execution plan.

Learning Objectives

After completing this unit, you should be able to:

1. Compare different file organization methods and identify appropriate use cases for each
2. Explain when to use primary versus secondary indexes, and dense versus sparse indexes
3. Trace insertion and deletion operations in B-trees and B+ trees
4. Apply hash functions and handle collisions in both static and dynamic hashing schemes
5. Describe the steps in query processing from SQL parsing through execution
6. Estimate query costs using block transfer and seek calculations
7. Apply equivalence rules for algebraic query optimization

These skills are directly applicable in database administration, performance tuning, and systems programming roles.