B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules Notes in Hindi & English : B-ट्री: मल्टी-वे सर्च ट्री, ऑर्डर M, डिस्क आधारित डेटाबेस इंडेक्सिंग और 20 महत्वपूर्ण MCQ प्रश्न (Rajasthan IT Exam)

Post a Comment

PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules (B-ट्री: मल्टी-वे सर्च ट्री, ऑर्डर M, डिस्क आधारित डेटाबेस इंडेक्सिंग) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।

Overview: A B-Tree (Bayer & McCreight, 1972) is a self-balancing multi-way search tree designed for disk-based databases and filesystems where each node matches one disk block. In an Order M B-Tree, internal nodes hold ceil(M/2) to M children and keep all leaves at identical depth, holding worst-case height to O(log_M n) disk reads.

अध्याय सार: B-ट्री (Bayer और McCreight, 1972) डिस्क-आधारित डेटाबेस और फाइल सिस्टम के लिए बना एक स्व-संतुलित मल्टी-वे सर्च ट्री है, जहाँ प्रत्येक नोड एक डिस्क ब्लॉक के बराबर होता है। ऑर्डर M के B-ट्री में आंतरिक नोड्स के पास ceil(M/2) से M चाइल्ड होते हैं और सभी लीव्स एक ही गहराई पर रहकर O(log_M n) डिस्क रीड में सर्च पूरा करते हैं।

B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules: Detailed Notes & Architecture (B-ट्री: मल्टी-वे सर्च ट्री, ऑर्डर M, डिस्क आधारित डेटाबेस इंडेक्सिंग)

1. Why Disk-Based Databases Need Multi-Way B-Trees (डिस्क डेटाबेस में B-ट्री की आवश्यकता)

[EN] Reading a block from HDD/SSD takes milliseconds or microseconds—orders of magnitude slower than RAM/CPU comparisons. A binary tree (order 2) storing 10 million records needs ~24-30 separate random disk reads. By packing hundreds of keys into one 4 KB or 8 KB node (Order M = 200 to 500), a B-Tree flattens tree height to just 3 or 4 levels, fetching billions of rows in 3-4 disk I/Os.

[HI] हार्ड डिस्क या SSD से एक ब्लॉक पढ़ना RAM की तुलना में हजारों गुना धीमा होता है। 1 करोड़ रिकॉर्ड के लिए बाइनरी ट्री ~25 डिस्क रीड लेगा, जबकि B-ट्री एक 4 KB/8 KB नोड में सैकड़ों कुंजियाँ (Order M = 200-500) रखकर ट्री की ऊंचाई केवल 3-4 स्तरों तक सीमित कर देता है।

2. Formal Rules of a B-Tree of Order M (ऑर्डर M वाले B-ट्री के सख्त नियम)

[EN] Under the standard Knuth definition where Order M denotes the maximum number of children per node: (1) Every node has at most M children and at most M - 1 keys; (2) Every non-root internal node has at least ceil(M/2) children and at least ceil(M/2) - 1 keys; (3) The root has at least 2 children if it is not a leaf (minimum 1 key when non-empty); (4) All leaf nodes exist at the exact same level; (5) In a standard B-Tree, BOTH internal nodes and leaves store record/data pointers alongside keys.

[HI] मानक Knuth परिभाषा (Order M = अधिकतम चाइल्ड संख्या) के अनुसार: (1) हर नोड में अधिकतम M चाइल्ड व M-1 कुंजियाँ होंगी; (2) रूट को छोड़कर हर नोड में न्यूनतम ceil(M/2) चाइल्ड व ceil(M/2)-1 कुंजियाँ अनिवार्य हैं; (3) रूट यदि लीफ न हो तो कम से कम 2 चाइल्ड होंगे; (4) सभी लीफ नोड्स बिल्कुल समान गहराई पर होते हैं; (5) B-ट्री में आंतरिक व लीफ दोनों नोड्स डेटा/रिकॉर्ड पॉइंटर रखते हैं।

3. Node Splitting (Bottom-Up Growth) & Deletion Merging (नोड स्प्लिटिंग (ऊपर की ओर वृद्धि) और मर्जिंग)

[EN] Every insertion targets an appropriate leaf node. When inserting causes a node to overflow with M keys (exceeding M - 1), the node splits into two nodes and its median key is promoted UPWARD into the parent—splitting recursively up to the root if needed. Thus, unlike BSTs that grow downward at leaves, a B-Tree grows upward only when the root splits. Deletion removes keys and fixes underflow (< ceil(M/2) - 1 keys) by borrowing from a sibling or merging siblings together with a separator key pulled down from the parent.

[HI] नई कुंजी हमेशा लीफ नोड में डाली जाती है; यदि नोड में M कुंजियाँ (ओवरफ्लो) हो जाएं, तो बीच की (Median) कुंजी ऊपर पैरेंट में भेजकर नोड को दो हिस्सों में तोड़ दिया जाता है। इस प्रकार B-ट्री नीचे के बजाय रूट के टूटने पर ऊपर की ओर बढ़ता है। डिलीशन में अंडरफ्लो होने पर पड़ोसी नोड से कुंजी उधार ली जाती है या दोनों को मर्ज किया जाता है।

4. CLRS Minimum Degree 't' vs Knuth Order 'M' & Height Bound (CLRS डिग्री 't' बनाम Order 'M' तथा ऊंचाई सूत्र)

[EN] Exam papers use two common notations: Knuth's Order M (max children M, min children ceil(M/2)) and Cormen/CLRS's minimum degree t (min children t, max children 2t, so M = 2t for even orders). For n keys in a B-Tree with minimum branching factor d = ceil(M/2) >= 2, worst-case tree height satisfies h <= log_d((n + 1) / 2). All Search, Insert, and Delete operations require O(log_M n) disk block accesses.

[HI] परीक्षाओं में Knuth का Order M (अधिकतम चाइल्ड M, न्यूनतम ceil(M/2)) और CLRS की न्यूनतम डिग्री t (जहाँ M = 2t) दोनों संकेतन पूछे जाते हैं। यदि न्यूनतम चाइल्ड d = ceil(M/2) हों, तो n कुंजियों के लिए अधिकतम ऊंचाई h <= log_d((n + 1)/2) होती है।

Syntax, Formula & Technical Example (B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules)

# B-Tree Order M = 5 Node Rules:
# Max children = 5 | Min internal children = ceil(5/2) = 3
# Max keys     = 4 | Min non-root keys     = 3 - 1 = 2
# Root min keys = 1 (min 2 children if non-leaf)

# Overflow Split Example (Order M = 5, inserting 35 into [10, 20, 30, 40]):
# Sorted 5 keys: [10, 20, 30, 35, 40] -> Median key 30 moves UP to parent
# Left child: [10, 20]  |  Right child: [35, 40]

B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules Quick Reference & Comparison Table

B-Tree Order M ParameterExact Mathematical RuleOrder M = 5 Value
Max Children per NodeM (Order of the B-Tree)At most 5 child pointers
Min Children (Non-Root Internal)ceil(M / 2)At least 3 child pointers
Max Keys per NodeM - 1At most 4 keys per node
Min Keys (Non-Root Node)ceil(M / 2) - 1At least 2 keys per non-root node

B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules Top 20 Bilingual MCQs with Answers

Q1. In a B-Tree of Order M = 5 (Knuth definition), what are the minimum and maximum number of keys allowed in a non-root leaf node?

(ऑर्डर M = 5 वाले B-ट्री (Knuth परिभाषा) के किसी गैर-रूट लीफ नोड में न्यूनतम और अधिकतम कितनी कुंजियाँ हो सकती हैं?)

(A) Minimum 2 keys, Maximum 4 keys

(B) Minimum 3 keys, Maximum 5 keys

(C) Minimum 1 key, Maximum 5 keys

(D) Minimum 2 keys, Maximum 5 keys

Correct Answer: (A)

[EN] Max keys = M - 1 = 4. Min keys in non-root nodes = ceil(M/2) - 1 = ceil(2.5) - 1 = 3 - 1 = 2.

[HI] अधिकतम कुंजियाँ M - 1 = 4 और गैर-रूट नोड में न्यूनतम कुंजियाँ ceil(5/2) - 1 = 3 - 1 = 2 होती हैं।

Q2. In a B-Tree of Order M = 6, how many minimum and maximum children can a non-root internal node possess?

(ऑर्डर M = 6 के B-ट्री में एक गैर-रूट आंतरिक नोड के न्यूनतम और अधिकतम कितने चाइल्ड हो सकते हैं?)

(A) Minimum 3 children, Maximum 5 children

(B) Minimum 2 children, Maximum 5 children

(C) Minimum 4 children, Maximum 6 children

(D) Minimum 3 children, Maximum 6 children

Correct Answer: (D)

[EN] Max children = M = 6; min children for non-root internal nodes = ceil(6/2) = 3.

[HI] ऑर्डर M = 6 में अधिकतम चाइल्ड M = 6 और न्यूनतम चाइल्ड ceil(6/2) = 3 होते हैं।

Q3. Who invented the B-Tree in 1972 while working at Boeing Research Labs?

(1972 में Boeing Research Labs में कार्य करते हुए B-ट्री का आविष्कार किसने किया था?)

(A) Donald Knuth and Robert Sedgewick

(B) Adelson-Velsky and Landis

(C) Edgar F. Codd and Raymond Boyce

(D) Rudolf Bayer and Edward M. McCreight

Correct Answer: (D)

[EN] Bayer and McCreight introduced the B-Tree in 1972 specifically for maintaining large ordered indexes on random-access disk drives.

[HI] 1972 में Rudolf Bayer और Edward McCreight ने डिस्क-आधारित बड़े इंडेक्स बनाने हेतु B-ट्री प्रस्तुत किया था।

Q4. What is the MINIMUM number of children that a non-leaf ROOT node of a B-Tree of Order M = 10 must have?

(ऑर्डर M = 10 वाले B-ट्री का गैर-लीफ रूट नोड कम से कम कितने चाइल्ड रख सकता है?)

(A) 1 child

(B) 2 children (and minimum 1 key)

(C) 9 children

(D) 5 children (ceil(M/2))

Correct Answer: (B)

[EN] Regardless of Order M, the root only needs >= 1 key and >= 2 children whenever the tree has more than one node.

[HI] ऑर्डर M कुछ भी हो, यदि रूट लीफ नहीं है तो उसमें कम से कम 1 कुंजी और 2 चाइल्ड होना पर्याप्त है।

Q5. How does a B-Tree grow in height when insertions trigger node splits?

(इन्सर्शन के कारण नोड्स के टूटने (Splitting) पर B-ट्री की ऊंचाई किस दिशा में बढ़ती है?)

(A) Unevenly on the left spine only

(B) Downward at random leaf branches only

(C) Upward at the root (when the root itself splits)

(D) Height never increases once root has 1 key

Correct Answer: (C)

[EN] Splitting promotes keys upward; height only increments by 1 when the root splits into two halves and spawns a brand-new root above them.

[HI] स्प्लिटिंग से कुंजी ऊपर जाती है; जब रूट स्वयं टूटता है तो ऊपर एक नया रूट बनता है, जिससे सभी लीव्स समान गहराई पर रहते हैं।

Q6. What condition is ALWAYS guaranteed about the depths of all leaf nodes in any valid B-Tree?

(किसी भी मान्य B-ट्री के सभी लीफ नोड्स (Leaf Nodes) की गहराई के बारे में कौन सा नियम सदैव सत्य होता है?)

(A) Leaves contain zero keys

(B) Leaf depths may differ by at most 1 (like AVL)

(C) All leaf nodes lie at the exact same depth (level)

(D) Leaves only appear on the rightmost branch

Correct Answer: (C)

[EN] Unlike AVL trees where leaf depths may vary slightly, B-Trees are strictly balanced so every leaf sits at identical distance from the root.

[HI] AVL के विपरीत, B-ट्री के सभी लीफ नोड्स रूट से बिल्कुल समान दूरी (एक ही लेवल) पर स्थित होते हैं।

Q7. When a node overflows during insertion in a B-Tree (reaching M keys), which key is promoted to the parent?

(B-ट्री में इन्सर्शन के दौरान नोड ओवरफ्लो (M कुंजियाँ) होने पर कौन सी कुंजी ऊपर पैरेंट नोड में भेजी जाती है?)

(A) The largest key moves up

(B) The smallest key moves up

(C) A copy of the median stays in the child like B+ Tree

(D) The median (middle) key moves up and leaves the split children

Correct Answer: (D)

[EN] In a standard B-Tree, the median key physically moves upward into the parent, leaving the remaining M - 1 keys split across left and right halves.

[HI] सामान्य B-ट्री में बीच की (Median) कुंजी टूटने वाले चाइल्ड से हटकर सीधे ऊपर पैरेंट नोड में चली जाती है।

Q8. If a B-Tree uses CLRS minimum degree t = 4, what is its equivalent Knuth Order M and maximum keys per node?

(यदि किसी B-ट्री की CLRS न्यूनतम डिग्री t = 4 है, तो इसका समतुल्य Order M और प्रति नोड अधिकतम कुंजियाँ कितनी होंगी?)

(A) Order M = 8, Max keys = 7

(B) Order M = 16, Max keys = 15

(C) Order M = 4, Max keys = 3

(D) Order M = 9, Max keys = 8

Correct Answer: (A)

[EN] CLRS defines min children = t and max children = 2t (= M), so max keys = 2t - 1 = 7 (and min keys for non-root = t - 1 = 3).

[HI] CLRS परिभाषा में अधिकतम चाइल्ड 2t = 8 (Order M) और अधिकतम कुंजियाँ 2t - 1 = 7 होती हैं।

Q9. What is the MAXIMUM total number of keys possible in an entire B-Tree of Order M = 5 with height 2 (root at level 0, leaves at level 2)?

(ऑर्डर M = 5 और ऊंचाई 2 (लेवल 0, 1, 2) वाले पूरे B-ट्री में कुल अधिकतम कितनी कुंजियाँ आ सकती हैं?)

(A) 24 keys

(B) 124 keys

(C) 624 keys

(D) 100 keys

Correct Answer: (B)

[EN] Level 0 (root): 4 keys, 5 children. Level 1: 5*4 = 20 keys, 25 children. Level 2: 25*4 = 100 keys. Total = 4 + 20 + 100 = 124 (i.e., 5^3 - 1).

[HI] लेवल 0 में 4, लेवल 1 में 5*4=20 और लेवल 2 में 25*4=100 कुंजियाँ होंगी—कुल 4 + 20 + 100 = 124 कुंजियाँ।

Q10. Consider a disk block size of 4096 bytes, block pointer = 8 bytes, key = 12 bytes, and record pointer = 10 bytes. What is the maximum Order M of a B-Tree node?

(यदि डिस्क ब्लॉक 4096 बाइट, ब्लॉक पॉइंटर 8 बाइट, कुंजी 12 बाइट और रिकॉर्ड पॉइंटर 10 बाइट का है, तो B-ट्री का अधिकतम ऑर्डर M क्या होगा?)

(A) M = 204

(B) M = 512

(C) M = 100

(D) M = 137

Correct Answer: (D)

[EN] Solve M*8 + (M - 1)*(12 + 10) <= 4096 => 30*M - 22 <= 4096 => 30*M <= 4118 => M = floor(4118 / 30) = 137 (137*8 + 136*22 = 4088 <= 4096).

[HI] समीकरण M*8 + (M-1)*(12+10) <= 4096 से 30M <= 4118 प्राप्त होता है, जिससे अधिकतम ऑर्डर M = 137 मिलता है।

Q11. If a B-Tree node of block size 2048 bytes has block pointer = 8 bytes, key = 16 bytes, and record pointer = 8 bytes, what is the maximum Order M?

(यदि ब्लॉक साइज 2048 बाइट, ब्लॉक पॉइंटर 8 बाइट, कुंजी 16 बाइट और रिकॉर्ड पॉइंटर 8 बाइट का हो, तो B-ट्री नोड का अधिकतम ऑर्डर M क्या होगा?)

(A) M = 85

(B) M = 128

(C) M = 64

(D) M = 32

Correct Answer: (C)

[EN] Solve M*8 + (M - 1)*(16 + 8) <= 2048 => 32*M - 24 <= 2048 => 32*M <= 2072 => M = floor(2072 / 32) = 64 (64*8 + 63*24 = 2024 <= 2048).

[HI] समीकरण M*8 + (M-1)*(16+8) <= 2048 से 32M <= 2072 प्राप्त होता है, जिससे अधिकतम ऑर्डर M = 64 मिलता है।

Q12. What is the MINIMUM total number of keys in a B-Tree of Order M = 5 with height 2 (root at level 0, leaves at level 2)?

(ऑर्डर M = 5 और ऊंचाई 2 (रूट लेवल 0, लीव्स लेवल 2) वाले B-ट्री में कुल न्यूनतम कितनी कुंजियाँ हो सकती हैं?)

(A) 25 keys

(B) 124 keys

(C) 17 keys

(D) 7 keys

Correct Answer: (C)

[EN] Level 0 (root): min 1 key, 2 children. Level 1: 2 nodes * 2 keys = 4 keys, total 6 children. Level 2: 6 leaves * 2 keys = 12 keys. Total = 1 + 4 + 12 = 17.

[HI] रूट में कम से कम 1 कुंजी (2 चाइल्ड), लेवल 1 में 2*2=4 कुंजियाँ (6 चाइल्ड) और लेवल 2 में 6*2=12 कुंजियाँ होंगी—कुल 1 + 4 + 12 = 17।

Q13. Why are Order 3 (2-3 tree) and Order 4 (2-3-4 tree) the smallest practical multi-way B-Trees rather than Order 2?

(ऑर्डर 2 की तुलना में ऑर्डर 3 (2-3 ट्री) और ऑर्डर 4 (2-3-4 ट्री) को सबसे छोटे व्यावहारिक B-ट्री क्यों माना जाता है?)

(A) Because Order 2 B-Tree allows infinite keys per node

(B) Because Order 2 B-Tree stores keys only in root

(C) Because AVL trees always maintain equal leaf depths

(D) Because M = 2 allows at most 1 key and min ceil(2/2)-1 = 0 non-root keys, failing flexible balanced splitting across equal-depth leaves

Correct Answer: (D)

[EN] Since M = 2 restricts nodes to 1 key without spare split room, M = 3 (1-2 keys, 2-3 children) is the smallest practical B-Tree order.

[HI] ऑर्डर 2 में नोड केवल 1 कुंजी रख सकता है जिससे लचीली स्प्लिटिंग संभव नहीं होती; इसलिए 2-3 ट्री (ऑर्डर 3) या 2-3-4 ट्री (ऑर्डर 4) उपयोग होते हैं।

Q14. In a B-Tree, if an internal node currently holds k keys (where k <= M - 1), how many child pointers does it have?

(B-ट्री के एक आंतरिक नोड में यदि k कुंजियाँ हों, तो उसमें कितने चाइल्ड पॉइंटर्स होंगे?)

(A) k + 1 child pointers

(B) k child pointers

(C) k - 1 child pointers

(D) 2k child pointers

Correct Answer: (A)

[EN] Each of the k keys acts as a delimiter separating k + 1 subtrees (< K1, between K1..K2, ..., > Kk).

[HI] k कुंजियाँ मानों को k + 1 अंतरालों में विभाजित करती हैं, इसलिए चाइल्ड पॉइंटर्स की संख्या सदैव k + 1 होती है।

Q15. Which classic balanced tree structures correspond directly to B-Trees of Order M = 3 and Order M = 4?

(ऑर्डर M = 3 और ऑर्डर M = 4 वाले B-ट्री को क्रमशः किन विशेष नामों से जाना जाता है?)

(A) Min-Heap and Fibonacci Heap

(B) 2-3 Tree (M = 3) and 2-3-4 Tree (M = 4)

(C) Trie and Suffix Tree

(D) AVL Tree and Splay Tree

Correct Answer: (B)

[EN] An Order 3 B-Tree allows 2 or 3 children per internal node (2-3 Tree), while Order 4 allows 2, 3, or 4 children (2-3-4 Tree, isomorphic to Red-Black Tree).

[HI] ऑर्डर 3 में 2 या 3 चाइल्ड (2-3 ट्री) और ऑर्डर 4 में 2, 3 या 4 चाइल्ड (2-3-4 ट्री) होते हैं।

Q16. Which statement about standard B-Trees is FALSE?

(मानक B-ट्री के बारे में निम्नलिखित में से कौन सा कथन असत्य (FALSE) है?)

(A) In a standard B-Tree, record/data pointers are stored exclusively inside leaf nodes and never in internal nodes

(B) A search in a B-Tree can terminate successfully at an internal node

(C) All leaf nodes of a B-Tree appear at the exact same level

(D) Every node in a B-Tree stores keys in sorted ascending order

Correct Answer: (A)

[EN] Storing data pointers ONLY in leaves is the defining trait of a B+ Tree; a standard B-Tree stores data pointers in BOTH internal and leaf nodes.

[HI] डेटा पॉइंटर केवल लीफ नोड्स में रखना B+ ट्री की विशेषता है; मानक B-ट्री में डेटा पॉइंटर आंतरिक और लीफ दोनों नोड्स में रहते हैं।

Q17. Within B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules, which b-tree order m parameter directly maps to: "M (Order of the B-Tree)"?

(B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules में कौन सा B-Tree Order M Parameter सीधे "M (Order of the B-Tree)" से संबंधित है?)

(A) Max Keys per Node

(B) Min Children (Non-Root Internal)

(C) Max Children per Node

(D) Min Keys (Non-Root Node)

Correct Answer: (C)

[EN] In B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules, 'Max Children per Node' handles 'M (Order of the B-Tree)' (At most 5 child pointers).

[HI] B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules में 'Max Children per Node' का कार्य/विवरण 'M (Order of the B-Tree)' (At most 5 child pointers) है।

Q18. Which option accurately describes 'Min Children (Non-Root Internal)' in B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules?

(B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules के संदर्भ में 'Min Children (Non-Root Internal)' की सही विशेषता कौन सी है?)

(A) M (Order of the B-Tree)

(B) ceil(M / 2) - 1

(C) ceil(M / 2)

(D) M - 1

Correct Answer: (C)

[EN] 'Min Children (Non-Root Internal)' provides 'ceil(M / 2)' — key point: At least 3 child pointers.

[HI] 'Min Children (Non-Root Internal)' का मुख्य विवरण 'ceil(M / 2)' है (At least 3 child pointers)।

Q19. In B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules, identify the correct parameter for the specification: "M - 1".

(B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules में "M - 1" विवरण किस विकल्प के लिए सही है?)

(A) Max Keys per Node

(B) Max Children per Node

(C) Min Keys (Non-Root Node)

(D) Min Children (Non-Root Internal)

Correct Answer: (A)

[EN] 'Max Keys per Node' corresponds to 'M - 1' (At most 4 keys per node).

[HI] 'Max Keys per Node' का संबंध 'M - 1' (At most 4 keys per node) से है।

Q20. Considering B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules, what key behavior defines 'Min Keys (Non-Root Node)'?

(B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules में 'Min Keys (Non-Root Node)' की मुख्य भूमिका या मान क्या है?)

(A) ceil(M / 2) - 1

(B) M - 1

(C) M (Order of the B-Tree)

(D) ceil(M / 2)

Correct Answer: (A)

[EN] 'Min Keys (Non-Root Node)' represents 'ceil(M / 2) - 1' (At least 2 keys per non-root node).

[HI] 'Min Keys (Non-Root Node)' का अर्थ/मान 'ceil(M / 2) - 1' है (At least 2 keys per non-root node)।

B-Tree Fundamentals: Multi-Way Search Tree, Order M Rules — Exam FAQs

Q1: Why do some textbooks say minimum keys is ceil(M/2) - 1 while others say t - 1?

कुछ किताबों में न्यूनतम कुंजियाँ ceil(M/2) - 1 और कुछ में t - 1 क्यों लिखी होती हैं?

[EN] Knuth defines Order M as max children (so min children = ceil(M/2) and min keys = ceil(M/2) - 1). CLRS defines minimum degree t as min children (so min keys = t - 1 and max children = 2t).

[HI] Knuth अधिकतम चाइल्ड को Order M कहते हैं (न्यूनतम कुंजियाँ ceil(M/2)-1), जबकि CLRS न्यूनतम चाइल्ड को डिग्री t कहते हैं (न्यूनतम कुंजियाँ t-1, अधिकतम चाइल्ड 2t)।

Q2: Can a B-Tree search finish without reaching a leaf node?

क्या B-ट्री में सर्चिंग बिना लीफ नोड तक पहुँचे भी समाप्त हो सकती है?

[EN] Yes! Because internal nodes store both search keys and their corresponding record/data pointers, finding the target key at the root or any internal node stops the search immediately.

[HI] हाँ! चूँकि B-ट्री के आंतरिक नोड्स में कुंजी के साथ डेटा पॉइंटर भी मौजूद होता है, इसलिए कुंजी ऊपर ही मिल जाने पर सर्च वहीं सफल हो जाता है।

Q3: What is a 2-3-4 Tree's connection to Red-Black Trees?

2-3-4 ट्री (Order 4 B-Tree) का Red-Black ट्री से क्या संबंध है?

[EN] Every 2-3-4 Tree maps isomorphically to a Red-Black Tree by splitting 3-nodes and 4-nodes into binary black roots with red children.

[HI] प्रत्येक ऑर्डर 4 B-ट्री (2-3-4 ट्री) को 3-नोड और 4-नोड को लाल (Red) चाइल्ड के रूप में दिखाकर ठीक एक Red-Black ट्री में बदला जा सकता है।

Related Posts

  • Loading related posts...

Post a Comment

Search Topic Notes & 20 MCQs (Hindi / English)