DBMS: B-Tree Indexing

# Without Index: Full Table Scan
SELECT * FROM users WHERE email = 'vaibhav@example.com';
? 1 million rows scan karega — SLOW! (O(n))

# With Index on email:
? B-Tree mein email sorted hai
? Binary search lagao — O(log n)
? Seedha row pe pahuncho — FAST!

# Index Types:
1. Primary Index: Primary Key pe automatically
2. Secondary Index: Manually created on columns
3. Clustered Index: Physical order of data = index order
4. Non-Clustered Index: Separate index structure + pointer to data

# B-Tree: Balanced Tree for disk-based storage

# Properties:
1. Har node mein multiple keys (not binary)
2. All leaf nodes at same level (balanced)
3. Keys sorted in each node
4. Order m = maximum children per node

# B-Tree of order 3:
 [10 | 20]
 / | \
 [5|8] [12|15] [25|30]
 / | \ / | \ / | \
 [1-4][6-7][9][11][13-14][16-19][21-24][26-29][31+]

# Search: O(log m n)
? Root se start, key dhundho, child pe jao
? Har level pe kuch comparisons
? Height bahut chhoti hoti hai (3-4 levels for millions of rows)

# Insert: 
? Key add karo, agar node full hai toh split karo
? Balance maintain hota hai automatically

# Delete:
? Key remove karo, agar node underflow hai toh merge karo
? Balance maintain hota hai

# B+ Tree = B-Tree ka improved version

# Key Differences:
1. Data sirf leaf nodes mein hota hai
2. Internal nodes sirf keys rakhte hain (routing)
3. Leaf nodes linked hain (range queries easy)
4. Search always leaf tak jaata hai

# Structure:
 [10 | 20] — Internal (routing only)
 / | \
 [5|8] [12|15] [25|30] — Internal
 / | \ / | \ / | \
 [1-4]?[6-7]?[9]?[11]?[13-14]?[16-19]?[21-24]?[26-29]? Leaf (data + links)

# Why B+ Tree over B-Tree?
? More keys per internal node (no data) — shorter tree
? Range queries easy (linked leaf nodes)
? Consistent search time (always leaf)
? Better cache performance

# Most databases use B+ Tree:
- MySQL InnoDB
- PostgreSQL
- Oracle

# 1. Clustered Index
? Physical order of data = index order
? Table mein sirf EK clustered index ho sakta hai
? Usually Primary Key
? Data rows stored in index order

# 2. Non-Clustered Index
? Separate structure with pointer to data
? Table mein multiple non-clustered indexes ho sakte hain
? Index leaf node mein row pointer hota hai
? Extra step: Index — Pointer — Actual Data

# 3. Covering Index
? Index mein saare columns hain jo query chahiye
? Table access ki zaroorat nahi (index se data milega)
? "SELECT email FROM users WHERE email = 'x'"
? email index = covering index

# 4. Composite Index
? Multiple columns pe combined index
? CREATE INDEX idx ON users(name, email)
? Leftmost prefix rule: name pe pehle, phir name+email

# Indexing Best Practices:
? WHERE clause ke columns pe index
? JOIN columns pe index
? ORDER BY columns pe index
? Small tables pe index mat lagao (overhead zyada)
? Har column pe index mat lagao (write slow)