B और B+ trees: capacity, updates और range search
लक्ष्य और पहले conventions
Bytes से node capacity निकालें, B tree और B+ tree अलग करें, height/occupancy समझें और split, borrowing तथा merging trace करें। “Order” शब्द standard नहीं: कहीं maximum children, कहीं minimum degree, कहीं maximum keys होता है। इस पाठ में m internal node के maximum children और L, B+ leaf के maximum data entries हैं। Formula लगाने से पहले प्रश्न की convention पढ़ें। Examples में unique search keys मानें।
1. B tree और B+ tree
दोनों balanced multiway search trees हैं: सभी leaves की depth समान होती है। B tree में searchable data entries या record references internal nodes तथा leaves दोनों में हो सकते हैं। इसलिए successful search internal node पर रुक सकता है। B+ tree में internal keys routing करते हैं और सभी data entries/references leaves में होते हैं। Internal separator, leaf key value को दोहरा सकता है। Leaves सामान्यतः linked होते हैं; range query एक बार descend करके leaf links follow करती है।
B+ internal node में children P0,...,Pk तथा sorted separators K1,...,Kk हों। यहाँ Ki, child Pi के subtree की smallest key है। पहले child में K1 से कम values, middle child में [Ki,K(i+1)) और आखिरी में Kk या अधिक values हैं। Equality separator के right side जाती है। अन्य conventions valid हैं, लेकिन trace में conventions mix न करें।
Maximum children m हों तो nonroot internal node में ceil(m/2) से m children और ceil(m/2)−1 से m−1 separators होते हैं। Nonleaf root के कम-से-कम दो children और अधिकतम m हैं। Root अकेला leaf भी हो सकता है और usual minimum से कम entries रख सकता है। बाकी B+ leaves में ceil(L/2) से L entries हैं। Internal तथा leaf capacity बराबर होना जरूरी नहीं।
2. Byte budget से capacity
Page B bytes, internal header H bytes, child pointer P bytes और separator key K bytes लें। p children के साथ p−1 keys होंगी, इसलिए pP+(p−1)K+H≤B। Maximum fanout floor((B−H+K)/(P+K)) है। p pointers के साथ p keys न गिनें; एक extra child महत्वपूर्ण है।
Leaf entry में K-byte key और R-byte record identifier हों, header H_l तथा एक next-leaf pointer P bytes हो तो L=floor((B−H_l−P)/(K+R))। दो sibling pointers, extra metadata, variable keys या full records हों तो budget बदलें। Formulas fixed sizes, no compression और कोई extra hidden overhead न होने पर हैं।
उदाहरण: B=512,H=16,K=8,P=8। Internal inequality 8p+8(p−1)+16≤512 अर्थात 16p+8≤512 है; m=31। Leaf में H_l=16, एक 8-byte sibling pointer और R=8 लें। L=floor((512−16−8)/16)=30। 31 entries को 520 bytes चाहिए, इसलिए नहीं fit होंगी। Minimum nonroot internal fanout ceil(31/2)=16 और minimum nonroot leaf entries ceil(30/2)=15 हैं।
3. Height तथा I/O assumptions
Height h को root से leaf तक edges की संख्या मानें। Root-leaf tree का h=0 और एक node level है। सभी pages uncached हों तो equality search h+1 index pages पढ़ता है। अलग heap record fetch करने में data-page I/O जुड़ता है। Root cached हो तो उसका physical I/O घटाएँ। Query की सारी required values index में हों तो covering index अलग data fetch बचा सकता है।
h≥1 के लिए d=ceil(m/2), ell=ceil(L/2) लें। Minimum-occupancy tree में कम-से-कम 2d^(h−1) leaves और 2d^(h−1)ell entries हैं। Full tree में अधिकतम m^h leaves और m^hL entries हैं। Root का minimum दो special case है; root पर d लगाने से minimum जरूरत बढ़ाकर गलत आँकेंगे।
m=4,L=3 में d=2,ell=2। Height 1 की maximum capacity 43=12 है। Height 2 की maximum 4²3=48 और minimum 222=8 है। इसलिए 40 entries को कम-से-कम height 2 चाहिए। फिर भी entry count से actual height unique नहीं: sparse taller tree में भी 40 fit हो सकते हैं। Exact height/page count के लिए fullness assumption बताएँ।
Range example: h=2 और range चार consecutive leaf pages में है। Uncached index cost (h+1)+(4−1)=6 reads है। पहली leaf descent में पहले ही गिनी गई। अलग data fetches clustering, cache और qualifying records की distinct table pages पर निर्भर हैं। चार leaf pages का अर्थ चार table pages जरूरी नहीं।
4. B+ insertion: leaf पर copy, internal पर promote
Target leaf खोजकर key क्रम में insert करें। Fit हो तो रुकें। Overflow पर valid occupancy वाली दो leaves बनाएँ, sibling links ठीक करें और नई right leaf की smallest key parent में copy करें। Data key leaf में रहती है। Parent overflow हो तो child-pointer sequence split करके separator ऊपर promote करें। Promoted separator उस internal level से हटता है, लेकिन उसका data entry leaves में रहता है। Root split से नया root और height में एक की वृद्धि होती है।
m=4,L=3, बिना preemptive split के 10,20,30 डालें। Root leaf भरती है। 40 डालने पर [10,20] तथा [30,40] leaves और root [30] बनता है। 50 से right leaf [30,40,50]। 60 डालने पर उसे [30,40] और [50,60] बाँटकर 50 root में copy करें। Root [30,50], leaf chain [10,20]→[30,40]→[50,60] है। सभी leaves की depth समान है।
अब 70,80,90,100 डालें। 80 पर split से root [30,50,70] होता है। 100 पर पाँच leaves [10,20],[30,40],[50,60],[70,80],[90,100] और temporary separators [30,50,70,90] हैं। पाँच children, m=4 से अधिक हैं। Internal node को दो-child left और तीन-child right में बाँटकर 50 promote करें। नया root [50], left internal [30], right internal [70,90] है। 50 सहित सारे data entries leaves में हैं। Convention अनुमति दे तो दूसरा valid distribution भी संभव है; यहाँ यह distribution चुना है।
5. Deletion: redistribution और merge
Leaf से entry हटाएँ। Minimum occupancy बनी हो तो बदले हुए subtree minimum के separators ठीक करें। Underflow पर minimum से अधिक entries वाला sibling entry lend कर सकता है; फिर parent separator बदलें। अन्यथा suitable sibling से merge करें, parent का extra pointer/separator हटाएँ और leaf links ठीक करें। Parent underflow ऊपर propagate हो सकता है। Nonleaf root में केवल एक child बचे तो child को root बनाएँ, height एक घटती है। Leaves की equal depth बनी रहती है।
Borrow example: m=4,L=3, root [30], leaves [10,20] तथा [30,40,50]। 10 हटाएँ तो [20], minimum 2 से कम है। Right से 30 borrow करें। Leaves [20,30] तथा [40,50], root [40] बनेगा। Separator update भूलने से future search गलत route हो सकती है।
Merge example: root [30], leaves [10,20] तथा [30,40]। 10 हटाएँ; right sibling minimum पर है, lend नहीं कर सकता। [20] और [30,40] merge करके [20,30,40] बनाएँ। पुराने root का separator हटने पर केवल एक child बचता है, इसलिए वही leaf root बनेगी। Height 1 से 0 होगी। B tree deletion में target data key internal भी हो सकती है; predecessor/successor replacement और rebalancing को उसके occupancy rules बनाए रखने होंगे।
6. B-tree का छोटा update trace
तुलना के लिए minimum degree t=2 का B tree लें: nonroot nodes में 1–3 keys और internal nodes में 2–4 children होते हैं। Top-down insertion में full root [10,20,30] को 40 डालने से पहले split करें। Median 20 promote होकर root [20] और children [10],[30] बनाता है। Right child में 40 डालकर [30,40] बनाएँ। B+ leaf split के विपरीत data entry 20 अब केवल internal root में है, leaf में duplicate नहीं।
Internal 20 delete करने में right child के पास कम-से-कम t keys हैं, इसलिए 20 को successor 30 से replace करें और right child से 30 हटाएँ। Result root [30], leaves [10],[40] है। अब root key 30 हटानी हो तो दोनों children minimum t−1 keys पर हैं। [10], parent की separator/data key 30 और [40] को [10,30,40] में merge करें, फिर 30 हटाएँ। Root leaf [10,40] बन जाता है। General B-tree deletion descending से पहले child में पर्याप्त keys सुनिश्चित करती है: parent के रास्ते borrowing या merging करती है। Parent data key को छोड़ देने वाला B+ leaf merge rule यहाँ न लगाएँ।
सावधानियाँ
- B+ internal match routing separator है, final data entry नहीं।
- Internal key count और pointer count में एक का अंतर है।
- Root exceptions तथा leaf/internal capacities स्पष्ट रखें।
- Leaf split separator copy करता है; internal split उस level से promote करके हटाता है।
- Edges में height और node levels में एक का अंतर है।
- Logarithmic complexity, cache तथा data-fetch assumptions की जगह नहीं लेती।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. बताई convention में internal B+ node के p children हों तो separators कितने हैं?
A. p−1 B. p C. p+1 D. 2p
उत्तर: A
A: Separators p child ranges को बाँटते हैं।
B: यह एक अधिक गिनता है।
C: यह दो अधिक गिनता है।
D: दो keys प्रति child का rule नहीं।
P02. Internal node में B=512,H=16,K=P=8। Maximum children?
A. 30 B. 31 C. 32 D. 63
उत्तर: B
A: 30 fit है, लेकिन 31 भी fit है।
B: 16p+8≤512 से p≤31.5, इसलिए 31।
C: 32 को 520 bytes चाहिए।
D: यह keys की storage भूलता है।
P03. B+ tree height 2 edges है; uncached range scan 4 leaves छूता है। Table data छोड़कर index reads?
A. 4 B. 5 C. 6 D. 7
उत्तर: C
A: यह internal descent pages भूलता है।
B: दो internal pages तथा चार leaves हैं।
C: तीन-page descent और तीन अतिरिक्त leaves, कुल छह।
D: यह पहली leaf दो बार गिनता है।
P04. B+ leaf split में नई right leaf की minimum key का क्या होता है?
A. सभी leaves से delete B. Leaf में रखकर parent में copy C. हमेशा leaf से बाहर promote D. Leaves की depths unequal बनाने में उपयोग
उत्तर: B
A: Data entry leaves में searchable रहनी चाहिए।
B: Leaf split routing value ऊपर copy करता है।
C: Internal promotion और leaf copying अलग हैं।
D: Balance में leaf depth समान रहती है।
P05. m=4,L=3। Root [30], leaves [10,20] और [30,40]। Minimum occupancy 2 में 10 delete करें। सही परिणाम?
A. 30 borrow, right leaf [40] रखें B. Root leaf [20,30,40] में merge C. Underfull [20] permanently रखें D. पुराने root के ऊपर नया root
उत्तर: B
A: Right sibling underfull हो जाएगी।
B: Sibling lend नहीं कर सकता; merge और root contraction होगा।
C: Nonroot leaf minimum occupancy तोड़ती है।
D: यहाँ deletion height घटाता है, बढ़ाता नहीं।
P06. कौन-सा अंतर सही है?
A. B+ data entries leaves में; B tree में internal भी B. B trees हमेशा binary C. B+ internal match पर lookup हमेशा पूरा D. B+ leaves की arbitrary depths
उत्तर: A
A: यही बताया structural distinction है।
B: B trees multiway हैं।
C: Internal B+ keys search को leaves तक guide करती हैं।
D: सभी leaves की depth समान है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन