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)