B-Tree: Properties, Structure, and Insertion

B-Tree ek self-balancing, m-way search tree data structure hai jo specifically large blocks of data ko secondary storage (Hard Disks, SSDs, Database indexing systems) par manage karne ke liye optimize kiya gaya hai. Binary search trees me har node sirf 1 key aur 2 children rakhta hai jisse tree height badi ho jaati hai aur disk I/O operations costly hote hain. B-Tree node multi-key aur multi-child architecture follow karta hai.

Properties of B-Tree of Order m

• Har node me at most m children ho sakte hain.
• Root node ke paas kam se kam 2 children hote hain (agar root leaf na ho).
• Root ke alawa har internal node ke paas kam se kam ceil(m / 2) children hone compulsory hain.
• Agar kisi node ke paas k children hain, toh usme exactly k - 1 keys hongi.
• Har non-root node me minimum keys = ceil(m / 2) - 1, aur maximum keys = m - 1.
• All leaves are at the exact same level! (B-Tree strictly perfectly balanced hota hai).

B-Tree of Order 4 (Max 3 keys, Max 4 children):

                 [ 20 | 50 ]
               /      |      \
     [ 10 | 15 ]   [ 30 | 40 ]  [ 60 | 70 | 80 ]

Node Splitting on Insertion

Jab kisi leaf node me insertion ke baad keys m - 1 se exceed (overflow) ho jaati hain, toh node Split hota hai: Median key parent node me promote (push up) ho jaati hai, aur bache hue keys do naye sibling nodes me split ho jaate hain.

Agli post me hum cover karenge B+ Tree: Structure and Comparison with B-Tree.