Indexing — B-tree index, hash index, full-text

4.4.13 · Coding › Databases

WHY indexes exist

Cost jo hum trade karte hain fast reads ke liye:

Extra storage (index indexed column ki copy + row pointer hota hai).
Slower writes: har INSERT/UPDATE/DELETE ko har index bhi update karna padta hai.

Yahi trade-off database tuning ka 80/20 hai: jinhe filter/join/sort karo unhe index karo, sab kuch index mat karo.

1. B-tree index (default, ~90% of all indexes)

Structure kaise kaam karta hai

Ek node mein $m$ children tak hote hain ( $m$ = branching factor, aksar hundreds kyunki ek node = ek disk page of ~8 KB).
Internal nodes separator keys store karte hain jo search route karte hain ("keys < 30 left jaao").
Leaves actual key → row-pointer pairs sorted order mein store karti hain.

B-trees kisme GREAT hain

Equality: WHERE id = 42 → neeche walk karo, $O (lo g N)$ .
Range: WHERE age BETWEEN 20 AND 30 → 20 dhundho, phir linked leaf list walk karo — yahi reason hai ki leaves sorted+linked hoti hain.
Sorting / ORDER BY: data pehle se order mein hai, extra sort nahi chahiye.
Prefix matching: LIKE 'app%' kaam karta hai; LIKE '%pp' nahi karta (koi known prefix nahi jahan se start karein).

Figure — Indexing — B-tree index, hash index, full-text

2. Hash index

Operation	B-tree	Hash
`=` equality	$O (lo g N)$	$O (1)$
range / `<`, `>`, `BETWEEN`	✅ $O (lo g N + k)$	❌ full scan
`ORDER BY`	✅ free	❌
`LIKE 'pre%'`	✅	❌

3. Full-text index

Worked example Inverted index build aur query karna

Docs: D1="the cat sat", D2="the dog sat". Stop-word removal + stemming ke baad:

cat -> {D1}
sat -> {D1, D2}
dog -> {D2}

Query sat AND dog → intersect {D1,D2} ∩ {D2} = {D2}. Yeh step kyun? Boolean text search = postings lists par set operations, jo fast hai kyunki lists pre-sorted document IDs hain.

Common mistakes (steeled)

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho ek giant book hai jisme ek billion pages hain. Har page padh ke "dragon" word dhundhna forever le lega. Toh peeche hum ek index rakhte hain: words ABC order mein page numbers ke saath. Ek B-tree wahi alphabetical index hai — sorted, isliye "cat" se "dog" tak ke saare words bhi aasani se grab ho sakte hain. Ek hash index ek magic coat-check ki tarah hai: tum exact ticket number do aur turant apni cheez milti hai, lekin tum "10 se 20 ke beech ke saare tickets" nahi maang sakte. Ek full-text index ek aisi list hai jo kehti hai "word dragon pages 4, 17, 88 par hai" — sentences ke andar words dhundhne ke liye perfect.

Flashcards

B-tree lookup ko

O (lo g_{m} N)

disk reads kyun kaha jaata hai — kaunsi data-structure property iske liye zimmedaar hai?

Yeh balanced hai (saari leaves same depth par) aur har node = ek disk page with high branching factor

m

, toh

h = ⌈ lo g_{m} N ⌉

B+tree leaf nodes ek sorted list mein linked kyun hain?

Fast range scans / ORDER BY support karne ke liye — start dhundho, phir leaves sequentially walk karo.

Hash index ORDER BY aur range queries ke liye kyun fail hota hai?

Hashing keys ko order destroy karne ke liye scatter karta hai, isliye adjacent values unrelated buckets mein jaati hain; walk karne ke liye koi order nahi.

~1 billion rows ke liye branching factor 100 ke saath B-tree mein kitne levels honge?

~5, kyunki

lo g_{100} 1 0^{9} = 4.5

Normal B-tree index LIKE '%word%' kyun serve nahi kar sakta?

Leading wildcard koi known prefix nahi deta jahan se descent start ho, isliye full scan hoti hai; full-text/inverted index use karo.

Inverted index kya hota hai?

Har word/token → us word wale documents (postings) ki list ka map, full-text search ke liye use hota hai.

Full-text index banane ke liye teen text preprocessing steps kaunse hain?

Tokenization, stemming, stop-word removal.

Composite B-tree indexes ka leftmost-prefix rule batao.

(a,b) par index a ya (a,b) queries help karta hai lekin sirf b nahi, kyunki pehle a se sort hota hai.

Index add karne ka main cost/trade-off kya hai?

Extra storage + slower writes (har insert/update/delete ko index maintain karna padta hai).

B-tree ke upar hash index kab sahi choice hai?

Jab queries sirf pure equality lookups hain, koi ranges/sorting nahi (jaise session_id cache).

Connections

Query Optimization — planner decide karta hai index use karna hai ya nahi, cost estimates se.
B+ Tree Data Structure — underlying balanced tree.
Hashing — hash functions, collisions, load factor jo hash indexes ke peeche hain.
Disk vs Memory I/O — kyun hum page reads count karte hain, comparisons nahi.
Clustered vs Non-clustered Index — actual row kahan rehti hai.
Big-O Notation — $O (lo g N)$ vs $O (1)$ vs $O (N)$ .