9.1 Indexing in DBMS: Primary, Secondary, Clustered vs Non-Clustered
An Index is an auxiliary data structure (typically a B+ tree) that enables the DBMS to locate target records in a fraction of a millisecond without scanning every block of the physical table on disk (Full Table Scan).
Clustered vs Non-Clustered Index
| Feature | Clustered Index | Non-Clustered (Secondary) Index |
|---|---|---|
| Physical Row Order | Rows are physically sorted on disk by key | Separate structure; pointers reference table rows |
| Max Count Per Table | Exactly ONE (Table can only have 1 physical order) | Multiple (Typically up to hundreds) |
| Leaf Node Contents | The actual complete data row (table itself) | Index key value + Row pointer (or Clustered PK) |
| Lookup Performance | Fastest (Direct page hit; no second lookup) | Requires double lookup if non-covering query |
Dense vs Sparse Index
- Dense Index: An index entry appears for every single search-key value in the database file. Faster search, but occupies more memory.
- Sparse Index: An index entry appears only for some of the search-key values (typically one entry per disk block). Consumes significantly less space.
9.2 B-Trees and B+ Trees: Storage Engine Architecture
Almost all production relational storage engines (InnoDB, Postgres heap, Oracle) employ B+ Trees as their default indexing data structure due to their massive fan-out, self-balancing depth, and superior disk block utilization.
Figure 9.1: B+ Tree architecture: Internal nodes store only router keys to maximize fan-out, while all data pointers reside in leaf nodes linked horizontally.
Why B+ Trees Beat Standard B-Trees in DBMS
- Higher Fan-Out: Because internal nodes do not store bulky data pointers or payload records, each disk page (e.g. 16 KB) can hold hundreds of routing keys. A tree with fan-out 100 can index 1,000,000 rows in just 3 levels ($100^3$).
- Constant Search Cost: Every search path from root to leaf has the exact same depth ($O(log N)$).
- Blazing Range Queries: In a regular B-tree, range queries require expensive in-order tree traversals across parent and child nodes. In a B+ tree, the engine navigates to the start key at the leaf level, then sequentially traverses the linked leaf nodes directly on disk!
9.3 Query Optimization & EXPLAIN Execution Plans
When a client submits a declarative SQL query, the DBMS does not execute it blindly. Instead, the Query Optimizer analyzes hundreds of possible evaluation strategies and selects the one with the lowest estimated CPU and disk I/O cost.
Figure 9.2: Stages of query optimization: Parsing → Logical Relational Algebra → Heuristics → Cost Estimation → Physical Plan Execution.
Using EXPLAIN to Diagnose Slow Queries
-- Inspect execution plan for an employee query:
EXPLAIN SELECT emp_name, salary
FROM Employees
WHERE department_id = 42;
-- Key attributes to check in the plan output:
-- 1. type: 'ALL' (bad: full table scan) vs 'ref' / 'range' / 'const' (good: index hit)
-- 2. possible_keys: indices evaluated by the optimizer
-- 3. key: the exact index chosen for execution
-- 4. rows: estimated rows scanned (lower is better!)
-- 5. Extra: 'Using filesort' or 'Using temporary' indicates heavy memory/disk overhead
