B-Trees, hash indexes, and composite indexes. Visualize how indexes speed up reads and the trade-offs with write performance.
Index Types
🌳
B-Tree Index
A self-balancing tree where all leaves are at the same depth. Supports equality, range, ORDER BY, and prefix queries efficiently.
Range QueriesO(log n)Default Index
Example:Default index type in PostgreSQL, MySQL/InnoDB. Ideal for most workloads.
#️⃣
Hash Index
Stores a hash of each indexed value with a pointer to the row. Ultra-fast for exact equality (=), but useless for ranges.
O(1) LookupExact MatchNo Range Scan
Example:Used in Redis, PostgreSQL hash indexes, and memory engine in MySQL.
🔗
Composite Index
An index over multiple columns. The left-prefix rule means the ORDER of columns in the index definition determines which queries benefit.
Left-Prefix RuleMulti-ColumnColumn Order Matters
Example:INDEX(user_id, status) helps queries on user_id or (user_id, status), not status alone.
🛡️
Covering Index
When all columns in a query (SELECT + WHERE + ORDER BY) exist in the index, the heap is never accessed — an index-only scan.
Zero Heap I/OIndex-Only ScanHigh Read Speed
Example:PostgreSQL INCLUDE columns make any index a covering index for specific queries.
How the Query Planner Decides
The planner chooses between an index scan and a sequential scan based on statistics
flowchart TD
Q(["🔎 SELECT * FROM users WHERE id = 42"])
Opt{Query Planner}
Q --> Opt
Opt -->|Index available| IdxScan["B-Tree Index Scan
O(log n)"]
Opt -->|No index| SeqScan["Sequential Table Scan
O(n)"]
IdxScan --> Leaf[("Leaf Node
id=42 -> row ptr")]
Leaf --> HeapFetch["Heap Fetch
Fetch actual row"]
SeqScan --> AllRows["Read every row
until match found"]
HeapFetch --> Result(["✅ Result Returned"])
AllRows --> Result
style Q fill:#1a1f2b,stroke:#00e5ff,color:#fff
style Opt fill:#1a1f2b,stroke:#00e5ff,color:#fff
style IdxScan fill:#12161f,stroke:#00e5ff,color:#fff
style SeqScan fill:#12161f,stroke:#ff5252,color:#fff
style Leaf fill:#12161f,stroke:#3effab,color:#fff
style HeapFetch fill:#0d1117,stroke:#3effab,color:#aaa
style AllRows fill:#0d1117,stroke:#ff5252,color:#aaa
style Result fill:#1a1f2b,stroke:#3effab,color:#fff
Interactive Index Flow
Step through each index type to see how a query is resolved
Waiting...
B-Tree Index Lookup
Traverse a balanced tree to reach the leaf — O(log n) reads
1
Query: SELECT * FROM users WHERE id = 42
2
Start at root node — compare 42 with root key (50). 42 < 50, go left.
3
Reach internal node (25). 42 > 25, traverse right child.
4
Reach leaf node — id = 42 found! Follow row pointer to heap.
5
✓ Only 3 I/O reads needed — O(log n) regardless of table size. Supports range scans too.
Match Found
Scanning
Not Used
Pruned Path
Key Concepts
What every engineer must understand about database indexes
Why Indexes Speed Up Reads
Without an index, the database must read every row in the table (full table scan) — O(n). An index creates a sorted, navigable auxiliary structure so the DB can jump directly to matching rows — O(log n) for B-Tree.
Rule of thumb: add an index on every column used in WHERE, JOIN ON, or ORDER BY clauses in hot queries.
The Write Penalty
Every INSERT, UPDATE, or DELETE must also update all relevant indexes. Too many indexes slow down write throughput and bloat storage. Always profile before adding — unused indexes are pure overhead.
Strategy: use EXPLAIN to verify index usage; drop indexes not appearing in execution plans.
Index Selectivity
Selectivity = distinct values / total rows. A high-selectivity index (e.g. email) is very effective. A low-selectivity index (e.g. boolean status) is often ignored by the optimizer — a full scan is cheaper.
Rule: index columns with at least 10–20% cardinality ratio for significant speedup.
Real-World Implementations
How popular databases implement indexing under the hood
🐘PostgreSQLB-Tree / GiST / BRIN
Default B-Tree for most cases. GiST for geospatial & full-text. BRIN for append-only time-series data with minimal overhead.
🐬MySQL InnoDBClustered B-Tree
Primary key index IS the table (clustered). Secondary indexes store the PK value as a row pointer — choose PK wisely.
🍃MongoDBB-Tree
Compound indexes follow the same left-prefix rule. Sparse and partial indexes let you index only a subset of documents.
⚡RedisHash + Skip List
Hash table for O(1) key lookups. Sorted Sets use a skip list for range queries by score (similar to B-Tree scan).
🔍ElasticsearchInverted Index
An inverted index maps each unique term to the list of documents containing it — the foundation of full-text search.
🪶SQLiteB-Tree
Both tables and indexes are B-Trees. Covering indexes in SQLite dramatically reduce I/O for read-heavy embedded apps.