Indexes are the foundation of database query performance. Without proper indexing, executing a query on a table with 10 million rows requires a sequential table scan, reading every disk block into memory. A well-designed index reduces disk I/O from millions of page reads to 3-4 block traversals.
This tutorial covers the internal mechanics of B-Tree, Hash, and GIN indexes, how the database query planner uses them, and practical indexing rules for production workloads.
1. B-Tree Indexes: The Universal Workhorse
B-Trees (Balanced Trees) are the default index type in PostgreSQL, MySQL, Oracle, and SQL Server. A B-Tree maintains sorted data in hierarchical tree nodes (Root, Branch, and Leaf nodes), keeping all leaf nodes at the exact same depth.
Because data is sorted, B-Trees efficiently support equality queries (=), range queries (<, <=, >, >=, BETWEEN), prefix matching (LIKE 'abc%'), and sorting operations (ORDER BY). Traversal time complexity is guaranteed at O(log N).
- Logarithmic search time guaranteed through self-balancing node splits
- Supports equality, range scans, and index-based sorting without filesorts
- Leaf nodes form a doubly linked list, enabling rapid forward and backward sequential scans
2. Composite Index Column Ordering & Leftmost Prefix Rule
A composite index covers multiple columns: CREATE INDEX idx_users_org_status ON users(org_id, status, created_at).
The database engine sorts data first by org_id, then by status, and finally by created_at. Therefore, the index can accelerate queries filtering on (org_id), (org_id, status), and (org_id, status, created_at). However, it CANNOT be used efficiently for queries filtering only on (status) or (created_at) without org_id. Always order composite index columns from highest equality selectivity to range filters.
3. GIN and Specialized Index Types in PostgreSQL
GIN (Generalized Inverted Index) is designed for composite and semi-structured data types like JSONB, Arrays, and Full-Text Search vectors. Instead of mapping a row to an indexed key, GIN splits an array or JSON document into individual keys and maps each key to the list of matching row pointers (Heap TIDs).
BRIN (Block Range Index): Optimized for massive append-only timeseries tables where values correlate with physical block storage. BRIN indexes occupy a fraction of the RAM of B-Trees by storing only min/max values per page range.
4. Diagnosing Query Plans with EXPLAIN ANALYZE
Never guess if an index is being used. Always execute EXPLAIN (ANALYZE, BUFFERS) in PostgreSQL or EXPLAIN in MySQL to inspect the execution plan.
Look for Index Scan (traversing index to fetch table rows), Index Only Scan (answering the query entirely from index memory without touching the heap table), versus Seq Scan (sequential table scan indicating missing or un-sargable indexes).
Frequently Asked Questions
Why shouldn't I index every single column in my database?
Every index imposes a write penalty. Whenever a row is inserted, updated, or deleted, all associated indexes must be updated and re-balanced synchronously. Excessive indexes consume memory buffer pool space and slow down write-heavy workloads.
What is an 'Index Only Scan' (Covering Index)?
An Index Only Scan occurs when all columns requested in the SELECT clause and WHERE clause exist within the index itself (including INCLUDE columns). The query engine returns results directly from the index without reading the underlying heap table blocks.
Written by Rajesh Nair
Technical contributor and subject matter specialist at PrimerPrep. Dedicated to breaking down complex systems into transparent, verified engineering principles.
Ready to test your knowledge?
Put these concepts into action with our independently reviewed practice questions and coding challenges.
Start practicing free