System DesignIndex là data structure (thường là B-Tree) cho phép database tìm kiếm records nhanh mà không cần full table scan – giảm query time từ O(n) xuống O(log n).
- B-Tree Index: phổ biến nhất, hỗ trợ equality và range queries (=, <, >, BETWEEN, LIKE 'prefix%'), tốt cho high-cardinality columns.
- Hash Index: cực nhanh cho equality lookups (=) nhưng không hỗ trợ range queries, dùng trong memory-optimized tables.
- Composite Index: index trên nhiều columns – thứ tự columns quan trọng (leftmost prefix rule); index (a,b,c) hỗ trợ queries trên (a), (a,b), (a,b,c) nhưng không hỗ trợ chỉ (b) hoặc (c).
- Partial Index: chỉ index một subset của rows (ví dụ
WHERE status='active') – nhỏ hơn và hiệu quả hơn. - Full-Text Index: cho text search.
- GIN/GiST Index (PostgreSQL): cho array, JSONB, geometric data.
- Covering Index: index chứa tất cả columns cần cho query – không cần đọc thêm table rows.
Trade-off: mỗi index tốn storage và làm chậm write (phải cập nhật index); không phải nhiều index là tốt hơn. Dùng EXPLAIN ANALYZE để hiểu query plan trước khi thêm index.
Database indexes enable sub-millisecond lookups by maintaining sorted auxiliary structures; common types include B-Tree, Hash, Composite, and Covering indexes — reducing query time from O(n) to O(log n).
- B-Tree Index: the most common type; supports equality and range queries (=, <, >, BETWEEN, LIKE 'prefix%'); good for high-cardinality columns.
- Hash Index: extremely fast for equality lookups (=) but does not support range queries; used in memory-optimized tables.
- Composite Index: an index on multiple columns — column order matters (leftmost prefix rule); an index on (a, b, c) supports queries on (a), (a, b), and (a, b, c) but not queries on only (b) or (c).
- Partial Index: indexes only a subset of rows (e.g., WHERE status='active') — smaller and more efficient.
- Full-Text Index: for text search queries.
- GIN/GiST Index (PostgreSQL): for arrays, JSONB, and geometric data.
- Covering Index: includes all columns needed for a query, eliminating the need to read the actual table rows.
Trade-offs: each index consumes storage and slows writes (the index must be updated); more indexes is not always better. Use EXPLAIN ANALYZE to understand the query plan before adding an index.