Bangladesh Satellite Company Limitedপ্রশ্ন ও সমাধান

Definition: A database index is an auxiliary data structure (commonly a B+ Tree, or a hash table for equality lookups) built on one or more columns that lets the database engine locate rows without scanning the entire table.

Why it speeds up queries

• Without an index: the engine must perform a full table scan — reading every row (O(n)) — to find matches for a WHERE condition.
• With a B+ Tree index: the engine navigates the tree from the root, following ordered keys, reaching the target row(s) in O(log n) comparisons, then follows leaf-level pointers directly to the matching rows.

graph TD
    Root["Root: 50"] --> N1["<=30"]
    Root --> N2[">30 & <=70"]
    Root --> N3[">70"]
    N1 --> L1["Leaf: 10,20,30 -> row ptrs"]
    N2 --> L2["Leaf: 40,50,60,70 -> row ptrs"]
    N3 --> L3["Leaf: 80,90 -> row ptrs"]
    L1 --> L2
    L2 --> L3

Concrete benefits

• Faster WHERE/equality/range lookups: e.g., WHERE employee_id = 5001 uses the index to jump directly to the row instead of scanning the whole table.
• Faster JOINs: indexes on foreign-key columns let the optimizer perform efficient index-nested-loop joins.
• Faster ORDER BY/GROUP BY: an index already stores keys in sorted order, avoiding a separate sort step.
• Efficient MIN/MAX: answered directly from the first/last leaf of the index, without scanning data.

Costs to weigh

• Extra storage space for the index structure.
• Slower INSERT/UPDATE/DELETE, since every index on the table must also be updated.
• Diminishing returns on low-cardinality columns (e.g., a boolean "gender" column) where the index barely narrows the search.

Exam takeaway: Indexes trade write-time overhead and storage for large read-time speedups (O(n) scan → O(log n) lookup); index columns that are frequently filtered, joined, or sorted on — not every column.