Physical Database Storage Architecture: Indexing Structures, B-Trees, B+ Trees, and Static/Dynamic Hashing

1. The Physical Storage Bottleneck & Block I/O Mechanics

In database systems engineering, disk access (I/O) is roughly 100,000 times slower than main memory RAM access. Consequently, relational database performance is governed almost entirely by minimizing physical disk block reads. Data between non-volatile disk storage and the DBMS memory buffer is transferred in fixed-size units called Blocks (Pages), typically ranging from 4 KB to 8 KB in size.

Without an index, finding a specific tuple requires a Full Table Scan (reading every data block from disk sequentially), requiring (O(N)) block transfers. An Index is an auxiliary physical access structure that maps search key values directly to disk block addresses, reducing retrieval cost to (O(log N)) or (O(1)).

2. Index Architecture: Primary, Clustering & Secondary Indices

Physical database indexes are classified based on the ordering of the underlying data file:

• Primary Index: Built on an ordered data file where the search key is a candidate/primary key (each key value is unique).
• Clustering Index: Built on an ordered data file where the search key is a non-key field (multiple records share the identical search key value, grouped physically together on disk).
• Secondary Index: Built on an unordered or differently ordered data file. Provides an alternative, secondary access path (e.g., searching by LastName on a table physically sorted by EmpId). A table can possess only ONE primary/clustering index, but dozens of secondary indexes.

3. Dense vs Sparse Indexing Tradeoffs

Indexes differ in the granularity of their index entries:

4. B-Trees vs B+ Trees: Architectural Deep-Dive

Multi-level indexing using static files incurs high re-indexing overhead during frequent insertions and deletions. B-Trees and B+ Trees solve this by maintaining self-balancing tree structures: