B-tree and B+ tree — motivation (disk storage), properties

3.4.9 · Coding › Trees

B-trees exist kyun karte hain? (motivation: disk storage)

Disk humhe kya free mein deta hai. Disks (aur SSDs) ek byte nahi padhte; woh ek poora block / page padhte hain (jaise 4 KB ya 16 KB) ek hi I/O mein. Ek hi block se 1 key ya 200 keys padhne ka cost same hota hai — sirf ek read.

Node size kaise choose karte hain. Keys ki sankhya itni raho ki ek node = ek disk block. Disk block size hi tree ka branching factor dictate karti hai.

B-tree: definition aur properties

Height bound derive karna (scratch se)

Formula B-tree ki Height

KYUN: hum prove karna chahte hain ki tree chota hai. KAISE: har level pe nodes ki minimum possible sankhya count karo — woh $N$ keys ke liye maximum possible height deta hai.

Root mein $\geq 1$ key hai → $\geq 2$ children. Depth $\geq 1$ pe har node mein $\geq t$ children hain. Toh nodes ki sankhya har level pe $t$ factor se badhti hai:

depth	min nodes
0	1
1	2
2	$2 t$
3	$2 t^{2}$
$h$	$2 t^{h - 1}$

Har non-root node mein $\geq t - 1$ keys hain. Total keys: $N \geq 1 + (t - 1) \sum_{i = 1}^{h} 2 t^{i - 1} = 1 + 2 (t - 1) \frac{t ^{h} - 1}{t - 1} = 2 t^{h} - 1$ $h$ ke liye solve karte hain: $h \leq lo g_{t} (\frac{N + 1}{2})$ Toh height base $t$ mein logarithmic hai — aur $t$ bahut bada hai → bahut choti height.

Figure — B-tree and B+ tree — motivation (disk storage), properties

B+ tree: definition aur yeh database ka favourite kyun hai

	B-tree	B+ tree
Data stored in	saare nodes mein	sirf leaves mein
Internal node fanout	kam (data carry karta hai)	zyada (sirf keys)
Range/sequential scan	awkward (in-order traversal)	fast (linked leaves)
Search rok sakta hai	internal node pe	hamesha leaf pe

Worked examples

Common mistakes (steel-manned)

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho tumhari books ek badi warehouse mein hain aur har baar jab tum ek shelf fetch karte ho toh ek lamba walk lagta hai. Tum 30 baar walk nahi karna chahte. Toh ek shelf-card pe ek book rakhne ki jagah, tum ek poori row of book titles ek card pe rakhte ho. Ab ek walk tumhe saikdon books ke baare mein bata deta hai, aur tum sirf 3–4 baar walk karte ho ek billion mein se koi bhi book dhundhne ke liye. Woh mota, chota cards ka directory hi B-tree hai. B+ tree same hai, lekin woh saari real books sirf niche wali shelves pe rakhta hai, aur un niche wali shelves ko ek rope se baandhta hai taaki tum bina upar wapas gaye ek range of books ek baar mein le sako.

Flashcards

B-trees kya optimize karte hain — comparisons ya disk accesses?

Disk/block accesses (random reads HDD pe ms cost karti hain, SSD pe ~0.1 ms, dono ≫ RAM); CPU comparisons almost free hain.

Node size disk block size ke barabar kyun hoti hai?

Ek disk read same cost pe ek poora block fetch karta hai, toh fanout maximize karne aur reads minimize karne ke liye har node mein ek full block of keys pack karo.

Min degree

t

(non-root) ke B-tree node mein max aur min keys ki sankhya?

Max

2 t - 1

, min

t - 1

k

keys wale B-tree node mein kitne children hote hain?

k + 1

N

keys aur min degree

t

wale B-tree ki height bound?

h \leq lo g_{t} \frac{N + 1}{2}

Kaun sa node minimum-keys rule se exempt hai?

Root (usme sirf 1 key bhi ho sakti hai).

Key structural difference: B-tree vs B+ tree mein data kahan rehta hai?

B-tree: saare nodes mein. B+ tree: sirf leaves mein; internal nodes routers hain.

Databases ke liye B+ trees kyun preferred hain?

Zyada fanout (internal nodes sirf keys rakhte hain) + linked leaves fast range/sequential scans dete hain.

Saare B-tree leaves same depth pe kyun hone chahiye?

B-trees root ko upar split karke badhte hain, kisi ek branch ko extend nahi karte, toh tree perfectly balanced rehta hai — worst case

lo g_{t} N

guarantee hoti hai.

B+ tree mein kya search ek internal node pe key match hone par ruk sakti hai?

Nahi — internal keys exact separators hain lekin koi record nahi rakhte; actual data padhne ke liye leaf tak descend karna zaroori hai.

Nodes ko "at least half full" force karna kyun important hai?

Yeh branching factor high rakhta hai taaki height

lo g_{t} N

rahe; merges/splits is invariant ko enforce karte hain.

Connections

Binary Search Tree — woh $lo g_{2}$ baseline jise B-trees disk ke liye improve karte hain.
AVL Tree / Red-Black Tree — in-RAM balanced trees (binary, low fanout).
Disk and Memory Hierarchy — block/page reads, seek time motivation.
Database Indexing — B+ trees default index structure ke roop mein (InnoDB, PostgreSQL).
File Systems — NTFS, ext4, HFS+ directories ke liye B-tree variants use karte hain.
Big-O Notation — I/O complexity vs CPU complexity count karna.