Question:
What is the maximum number of keys that a B-tree of order \(m\) and height \(h\) (where root is at height 0) can store?
क्रम \(m\) और ऊंचाई \(h\) (जहां रूट ऊंचाई 0 पर है) का एक B-ट्री अधिकतम कितनी कुंजियों (keys) को संग्रहीत कर सकता है?
Options:
- \(m^{h+1} – 1\)
- \(m^h – 1\)
- \(2m^h\)
- \((m-1)^{h+1}\)
- \(m^{h+1} – 1\)
- \(m^h – 1\)
- \(2m^h\)
- \((m-1)^{h+1}\)
Correct Answer: a)
Explanation:
At height \(i\), the maximum number of nodes is \(m^i\), and each node can contain at most \(m – 1\) keys. Summing from \(i = 0\) to \(h\): \(\sum_{i=0}^h m^i (m – 1) = (m – 1) \frac{m^{h+1} – 1}{m – 1} = m^{h+1} – 1\).
प्रत्येक स्तर पर अधिकतम नोड्स और प्रत्येक नोड में अधिकतम \(m-1\) कुंजियों का योग गुणोत्तर श्रेणी के सूत्र से \(m^{h+1} – 1\) आता है।