Core Principles & Data Structures:
- Purpose: An index is an auxiliary data structure that trades storage and write overhead for accelerated read query performance, avoiding full table scans.
1. B-Tree / B+Tree Indexes:
- Structure: Self-balancing multi-way search trees. In B+Trees, all data pointers live exclusively in leaf nodes linked sequentially as a doubly linked list; internal nodes store only routing keys.
- Performance: O(log N) search, insert, and delete complexity.
- Capabilities: Supports point lookups (WHERE id = 5), range queries (WHERE age BETWEEN 20 AND 30), inequality checks (>, <), and ordered sorting (ORDER BY).
- Default Choice: Standard default in relational databases (PostgreSQL, MySQL InnoDB).
2. Hash Indexes:
- Structure: Bucketed hash tables mapping hashed keys to row pointers.
- Performance: O(1) average lookup time.
- Limitations: Cannot support range queries or sorting because hashing scrambles key order. Only supports strict equality lookups (WHERE email = 'user@example.com').
- Default Choice: Ideal for memory-resident key-value caches or specific equality-only tables.