B+ Trees

Jab database me laakhon-karodon records ho jaate hain, to unhe dhoondhna (search karna) bahut slow ho jaata hai. B+ Tree ek special tree-based data structure hai jo database me indexing ke liye use hota hai. Yeh searching, insertion, aur deletion ko bahut fast bana deta hai, khaas kar jab data hard disk par store ho.

Why B+ Trees?

Normal Binary Search Trees (BST) disk-based databases ke liye inefficient hote hain. B+ Tree 'mota' aur 'chota' (fat and short) hota hai, jiska matlab hai:

• Low Height: Iski height kam hoti hai.
• High Fanout: Har node me bahut saari keys aur child pointers hote hain.

In do cheezon ki vajah se, data ko dhoondhne ke liye kam se kam disk I/O operations lagte hain, jisse performance dramatically improve hoti hai.

Structure of a B+ Tree

• Internal Nodes: Inka kaam sirf raasta dikhana (navigation) hai. Inme sirf keys aur pointers (child nodes ke address) hote hain.
• Leaf Nodes: Asli data (ya data ke records ka pointer) sirf leaf nodes me hota hai. Saare leaf nodes ek hi level par hote hain.
• Linked Leaves: Saare leaf nodes aapas me ek doubly linked list ki tarah jude hote hain. Isse range queries (e.g., saare employees dhoondho jinki salary 50k se 80k ke beech hai) bahut fast ho jaati hain.

Rules for Order 'p'

• Har node me (except root) kam se kam `ceil(p/2)` pointers hone chahiye.
• Har node me zyada se zyada `p` pointers ho sakte hain.
• Har node me (except root) kam se kam `ceil(p/2) - 1` keys honi chahiye.
• Har node me zyada se zyada `p-1` keys ho sakti hain.

Exam me numericals aate hain jisme keys dekar B+ Tree construct karna hota hai. Usme node overflow (jab node bhar jaaye) hone par node split karna sabse important step hai.