Storage, Indexing & File Structures

In the architecture of a DBMS, Storage, Indexing, and File Structures sit at the physical and logical data organisation levels. This layer bridges the logical schema (relations, attributes) and the physical hardware (HDDs, SSDs). Understanding it is a prerequisite for query processing, optimisation, and scalable system design.

The efficiency of a database is critically dependent on these choices. Poorly chosen file organisations or missing indexes can cause catastrophic performance bottlenecks under heavy load. The central trade-off is always between storage space, access time, and update cost.

Essential terms for understanding storage, indexing, and file structures at the university level.

Disk Access Time Components

Traditional Hard Disk Drives (HDDs) are mechanical devices. Their access time has three components:

Total Access Time = Seek Time + Rotational Latency + Transfer Time

Random I/O  = 1 x (SeekTime + RotLatency + TransferTime)  -- expensive
Sequential  = 1 x SeekTime + 1 x RotLatency + N x TransferTime  -- efficient

RAID Levels

Buffer Pool Management

Since disk I/O is expensive, the DBMS maintains a buffer pool -- a designated area of main memory that caches frequently accessed disk pages. The buffer manager controls fetching, pinning, and eviction of pages.

A file organisation dictates how records are physically stored and managed on disk. The choice significantly impacts the efficiency of insert, delete, search, and range scan operations.

Clustered vs Unclustered

The B+Tree is the de facto standard for database indexing. It is a self-balancing tree structure where all data pointers reside in leaf nodes (which are linked), and internal nodes serve purely as a navigation directory.

Key Properties

Operations & I/O Cost

Hash-based indexes provide very fast O(1) average-case equality lookups. A hash function maps a search key to a bucket, which holds the matching records. They are completely unsuitable for range queries.

B+Tree vs Hash Index Comparison

A bitmap index creates a separate bit vector for each distinct value of a low-cardinality attribute. Each bit corresponds to one record: 1 if the record has that value, 0 otherwise.

-- Example: Gender column with 10 records
-- Bitmap for 'M': 1 0 1 0 0 1 0 1 0 1  (records 1,3,6,8,10 are Male)
-- Bitmap for 'F': 0 1 0 1 1 0 1 0 1 0  (records 2,4,5,7,9 are Female)

-- Query: Gender='M' AND Department='Sales'
-- Result = BITWISE_AND(Bitmap_M, Bitmap_Sales)
-- This is a single CPU instruction per 64 records!

Composite Indexes & Column Ordering

A composite index is built on multiple columns. The column order critically determines which queries can use the index.

-- Index on (department_id, employee_id)
WHERE department_id = 10                     -- uses index (leading column)
WHERE department_id = 10 AND employee_id > 5 -- uses index (both columns)
WHERE employee_id = 101                      -- cannot use index (skips leading)

Covering Indexes

A covering index includes all columns referenced by a query (WHERE + SELECT), enabling an index-only scan that never touches the data file.

-- Query requires: department_id (filter), employee_id, salary (output)
CREATE INDEX idx_covering
  ON Employees (department_id, employee_id, salary);

-- Now this query needs zero data-page I/Os:
SELECT employee_id, salary FROM Employees WHERE department_id = 20;

Partial (Filtered) Indexes

A partial index indexes only a subset of rows satisfying a WHERE clause. Smaller size, lower maintenance overhead.

-- Only index active employees -- much smaller than a full index
CREATE INDEX idx_active_emp
  ON Employees (employee_id)
  WHERE status = 'Active';

Clustered vs Non-Clustered Comparison

Multi-Dimensional Indexes (R-Trees, Quad-Trees)

Spatial data requires indexes that handle multi-dimensional queries. R-Trees use minimum bounding rectangles (MBRs) to partition space hierarchically -- used by PostGIS for geospatial queries. Quad-Trees subdivide 2D space into quadrants recursively. Both dramatically outperform B+Trees for "find all points within this region" queries.

What is the main difference between a B-Tree and a B+Tree, and why is B+Tree preferred in databases?

In a B-Tree, data pointers can exist in both internal and leaf nodes. In a B+Tree, all data pointers reside only in leaf nodes -- internal nodes serve purely as a directory. B+Trees are preferred for three reasons: (1) leaf nodes are linked, enabling efficient range query traversal without returning to the root; (2) internal nodes hold only keys, giving a higher fan-out and shorter tree height; (3) all searches end uniformly at the leaf level, simplifying the implementation.

When should I choose a hash index over a B+Tree index?

Choose a hash index when your primary access pattern involves exact match equality queries (e.g., WHERE employee_id = 123). Hash indexes offer O(1) average-case lookup, which is faster than a B+Tree's O(log_f N). However, hash indexes provide no inherent ordering, making range queries (BETWEEN, >, <) require a full table scan. For any query involving order, ranges, or ORDER BY, a B+Tree is the correct choice.

What is a "covering index" and how does it improve query performance?

A covering index is a non-clustered index that includes all columns required by a query -- both in the WHERE clause and the SELECT list. It improves performance by allowing the database to satisfy the query entirely by reading only the index, without accessing the actual data pages. This eliminates potentially many random I/Os, which is especially significant for unclustered indexes where each data fetch involves a separate disk read.

What are the trade-offs of using a clustered index versus a non-clustered index?

A clustered index physically orders data records on disk in index key order, making range queries and sequential scans extremely fast since related records are co-located. Only one clustered index is allowed per table. Updates to the clustering key are expensive as they may require physically relocating records. A non-clustered index is a separate structure pointing to data via RIDs -- multiple can exist per table, supporting fast lookups on many attributes. However, each record retrieval may involve a separate random I/O to fetch the actual data page, unless the index is a covering index.

How does the buffer pool interact with disk I/O, and what is the role of a replacement policy?

The buffer pool is a cache in main memory holding copies of disk pages. When the DBMS needs a page, it first checks the buffer pool (a buffer hit avoids disk I/O). On a buffer miss, the page is fetched from disk and placed in a free frame. A replacement policy (LRU, CLOCK, MRU) determines which page to evict when the pool is full. The goal is to evict the page least likely to be needed again, maximising the buffer hit rate and minimising slow disk I/Os.

Why is I/O cost the dominant performance metric in disk-based databases?

Disk I/O is orders of magnitude slower than CPU operations or RAM access. An HDD seek takes 5-20ms while a CPU instruction takes nanoseconds -- a difference of over a million times. Even SSDs are 10-100x slower than RAM for random access. Because a single query can require thousands of page reads, minimising the number of disk I/O operations (especially random ones) is far more impactful than any CPU optimisation. This is why file organisations, indexes, and buffer management all focus on reducing I/O count.