Intuition The one-sentence pictureAn index is a separate, sorted (or hashed) data structure that lets the database find rows without scanning the whole table — exactly like a book's index lets you jump to a page instead of reading every page.
A table is stored as a heap (or clustered file) of rows. To answer WHERE email = 'x' the database must do a full table scan : read every row, compare, discard. That is O ( N ) O(N) O ( N ) N N N
Intuition WHY this is catastrophic on diskThe bottleneck is not CPU, it is disk/SSD I/O . A spinning disk does ~100 random seeks/sec; SSD ~10k. Scanning a 100-million-row table touches thousands of disk pages . We want to turn O ( N ) O(N) O ( N ) O ( log N ) O(\log N) O ( log N ) O ( 1 ) O(1) O ( 1 )
The cost we trade for fast reads:
Extra storage (the index is a copy of the indexed column + a row pointer).
Slower writes : every INSERT/UPDATE/DELETE must also update each index.
That trade-off is the 80/20 of database tuning: index the columns you filter/join/sort on, do not index everything.
Definition B-tree / B+treeA balanced, sorted, multi-way search tree where every leaf is the same distance from the root. Each node holds many keys (one disk page worth), so the tree is wide and shallow . In a B+tree (what real databases use) all real data/pointers live in the leaves , and leaves are linked in a sorted list .
A node has up to m m m m m m branching factor , often hundreds because one node = one disk page of ~8 KB).
Internal nodes store separator keys that route the search ("keys < 30 go left").
Leaves store the actual key → row-pointer pairs in sorted order .
Worked example Why B-trees are SO shallow — plug in numbersN = 1,000,000,000 N = 1{,}000{,}000{,}000 N = 1 , 000 , 000 , 000 m = 100 m = 100 m = 100 h = log 100 ( 10 9 ) = 9 2 = 4.5 ≈ 5 h = \log_{100}(10^9) = \frac{9}{2} = 4.5 \approx 5 h = log 100 ( 1 0 9 ) = 2 9 = 4.5 ≈ 5 Why this step? log 100 x = log 10 x log 10 100 = 9 2 \log_{100} x = \frac{\log_{10} x}{\log_{10} 100} = \frac{9}{2} log 100 x = l o g 10 100 l o g 10 x = 2 9 billion rows are reached in ~5 disk reads . With the root + top levels cached in RAM, often just 1–2 actual disk hits . That is the magic.
Equality : WHERE id = 42 → walk down, O ( log N ) O(\log N) O ( log N ) Range : WHERE age BETWEEN 20 AND 30 → find 20, then walk the linked leaf list — this is why leaves are sorted+linked.Sorting / ORDER BY : data is already in order, no extra sort.Prefix matching : LIKE 'app%' works; LIKE '%pp' does not (no known prefix to start at).
Stores entries in a hash table : bucket = hash(key) mod num_buckets, each bucket holds the row pointer(s). Lookup is average O ( 1 ) O(1) O ( 1 ) — compute hash, jump to bucket.
Intuition WHY faster than B-tree for equality but useless for rangesHashing destroys order on purpose to spread keys evenly. hash(99) and hash(100) land in unrelated buckets, so there is no way to walk a range or sort. Great for WHERE x = ?, hopeless for WHERE x > ? or ORDER BY x.
Operation
B-tree
Hash
= equalityO ( log N ) O(\log N) O ( log N ) O ( 1 ) O(1) O ( 1 )
range / <, >, BETWEEN
✅ O ( log N + k ) O(\log N + k) O ( log N + k )
❌ full scan
ORDER BY✅ free
❌
LIKE 'pre%'✅
❌
Worked example When to choose hashA cache/session table queried only by exact session_id. No ranges, no sorting → hash index gives O ( 1 ) O(1) O ( 1 ) CREATE INDEX ... USING hash (session_id);
Definition Full-text index (inverted index)For searching words inside text (WHERE body CONTAINS 'database'). A B-tree on the whole column can't help (you'd need LIKE '%word%' = full scan). Instead build an inverted index : a map from each word → list of documents (postings) containing it .
A normal index maps document → its words . We invert it to word → documents , because the query gives us the word and asks for the documents . The text is first run through tokenization (split into words), stemming (running→run), and stop-word removal (the, is).
Worked example Building & querying an inverted indexDocs: D1="the cat sat", D2="the dog sat".
After stop-word removal + stemming:
cat -> {D1}
sat -> {D1, D2}
dog -> {D2}
Query sat AND dog → intersect {D1,D2} ∩ {D2} = {D2}.
Why this step? Boolean text search = set operations on postings lists , which is fast because lists are pre-sorted document IDs.
Common mistake "More indexes = always faster."Why it feels right: indexes speed reads, reads are most queries.
The fix: every index must be maintained on every write and costs storage. On write-heavy tables, too many indexes slow the system down . Index only what you query.
Common mistake "A hash index is always better than a B-tree becauseO ( 1 ) < O ( log N ) O(1) < O(\log N) O ( 1 ) < O ( log N ) Why it feels right: big-O says constant beats logarithmic.
The fix: log m N \log_m N log m N hash dies on ranges/sorting/LIKE , which are most real queries. B-tree is the safe default; hash only for pure equality.
LIKE '%term%' uses my B-tree index."
Why it feels right: there is an index on the column.
The fix: a leading wildcard has no known prefix , so the tree can't pick a start point → full scan. Use a full-text index for inside-word search.
Common mistake "Indexing column(a, b) helps queries on b alone."
Why it feels right: b is in the index.
The fix: a composite B-tree is sorted by a first, then b (like a phone book by last-then-first name). It helps a, or a AND b, but not b alone — this is the leftmost-prefix rule .
Recall Feynman: explain it to a 12-year-oldImagine a giant book with a billion pages. Finding the word "dragon" by reading every page would take forever. So at the back we keep an index : words in ABC order with page numbers. A B-tree is that alphabetical index — sorted, so you can also grab every word from "cat" to "dog" easily. A hash index is like a magic coat-check: you give the exact ticket number and instantly get your item, but you can't ask for "all tickets between 10 and 20." A full-text index is a list saying "the word dragon appears on pages 4, 17, 88" — perfect for finding words inside sentences.
"B for Between, H for Hit-exact, F for Find-words."
B-tree → B etween/ranges/order. Hash → exact H its only. Full-text → F ind words inside text.
What data-structure property makes a B-tree lookup O ( log m N ) O(\log_m N) O ( log m N ) It's balanced (all leaves same depth) and each node = one disk page with high branching factor
m m m , so
h = ⌈ log m N ⌉ h=\lceil\log_m N\rceil h = ⌈ log m N ⌉ .
Why are B+tree leaf nodes linked in a sorted list? To support fast range scans / ORDER BY — find the start, then walk the leaves sequentially.
Why does a hash index fail for ORDER BY and range queries? Hashing scatters keys to destroy order, so adjacent values land in unrelated buckets; no order to walk.
For ~1 billion rows with branching factor 100, how many levels does the B-tree have? ~5, since
log 100 10 9 = 4.5 \log_{100}10^9 = 4.5 log 100 1 0 9 = 4.5 .
Why can't a normal B-tree index serve LIKE '%word%'? A leading wildcard gives no known prefix to start the descent, forcing a full scan; use a full-text/inverted index.
What is an inverted index? A map from each word/token → list of documents (postings) containing it, used for full-text search.
What three text preprocessing steps build a full-text index? Tokenization, stemming, stop-word removal.
State the leftmost-prefix rule for composite B-tree indexes. An index on (a,b) helps queries on a or (a,b) but not b alone, because it's sorted by a first.
What is the main cost/trade-off of adding an index? Extra storage + slower writes (every insert/update/delete must maintain the index).
When is a hash index the right choice over B-tree? When queries are pure equality lookups with no ranges/sorting (e.g., session_id cache).
Query Optimization — the planner decides whether to use an index via cost estimates.B+ Tree Data Structure — the underlying balanced tree.Hashing — hash functions, collisions, load factor behind hash indexes.Disk vs Memory I/O — why we count page reads, not comparisons.Clustered vs Non-clustered Index — where the actual row lives.Big-O Notation — O ( log N ) O(\log N) O ( log N ) O ( 1 ) O(1) O ( 1 ) O ( N ) O(N) O ( N )
Index: sorted or hashed structure
Height h = log base m of N
Range and ORDER BY queries
Extra storage + slower writes
Intuition Hinglish mein samjhoSocho tumhare paas ek table hai jisme 1 crore rows hain. Agar tum WHERE email = 'x' chalao bina index ke, to database ko poori table scan karni padti hai — har row padho aur compare karo. Yeh slow hai kyunki asli bottleneck disk I/O hai, CPU nahi. Index ek alag sorted ya hashed structure hai jo seedha row tak le jaata hai, bilkul kitaab ke peeche wale index ki tarah.
B-tree sabse common index hai (~90% cases). Yeh ek balanced tree hai jahan har node ek disk page jitna bada hota hai, isliye branching factor bahut high hota hai (sau-sau children). Iska matlab tree bahut chhota aur chaurra hota hai — 1 billion rows sirf ~5 levels mein, yaani ~5 disk reads. Aur kyunki leaves sorted aur linked hote hain, range queries (BETWEEN) aur ORDER BY bhi free mein ho jaate hain.
Hash index key ko hash karke seedha bucket mein daal deta hai — exact match ke liye O(1) , sabse fast. Lekin hashing order ko jaan-bhoojh kar tod deti hai, isliye >, <, ya ORDER BY ke liye yeh bekaar hai. Sirf tab use karo jab queries pure equality hon (jaise session_id).
Full-text index tab kaam aata hai jab tumhe text ke andar word dhoondhna ho. LIKE '%word%' B-tree use nahi kar sakta. Iske liye inverted index banta hai: har word ke saamne uss word wale documents ki list. Query sat AND dog = sets ka intersection. Yaad rakho: B for Between, H for Hit-exact, F for Find-words — yahi 80/20 hai indexing ka.
