Question:
A node size is 4096B. Node pointer size is 10B. Search key is 11B. Record pointer is 12B. What is the Max node pointers that can be stored in a non-leaf node of a B+ tree?
A node size is 4096B. Node pointer size is 10B. Search key is 11B. Record pointer is 12B. What is the Max node pointers that can be stored in a non-leaf node of a B+ tree?
Show Hint
Remember the structure of B+ tree nodes. Non-leaf nodes store keys and child pointers, while leaf nodes store keys and data/record pointers. For non-leaf node calculations, ignore the record pointer size. The relationship is always `m` pointers and `m-1` keys.
Updated On: Feb 23, 2026
Hide Solution
Verified By Collegedunia
Correct Answer: 195
Solution and Explanation
Step 1: Understanding the Question:
We need to determine the maximum order (maximum number of child pointers) of a non-leaf node in a B+ tree given the size of the node and the sizes of the keys and pointers. The record pointer size is only relevant for leaf nodes, not non-leaf nodes.
Step 2: Key Formula or Approach:
A non-leaf node in a B+ tree with an order of 'm' contains 'm' child pointers and 'm-1' search keys. The total size occupied by these pointers and keys must be less than or equal to the total node size.
Total Size = (m $\times$ size of a node pointer) + ((m-1) $\times$ size of a search key) $\le$ Node Size
Step 3: Detailed Explanation:
Let 'm' be the maximum number of node pointers (the order of the node).
Given:
- Node Size = 4096 Bytes
- Node pointer size = 10 Bytes
- Search key size = 11 Bytes
We set up the inequality based on the structure of a non-leaf node: \[ (m \times 10) + ((m-1) \times 11) \le 4096 \] Now, we solve for m: \[ 10m + 11m - 11 \le 4096 \] \[ 21m - 11 \le 4096 \] \[ 21m \le 4096 + 11 \] \[ 21m \le 4107 \] \[ m \le \frac{4107}{21} \] \[ m \le 195.571... \] Step 4: Final Answer:
Since the number of pointers 'm' must be an integer, we take the floor of the result. The maximum integer value for m is 195. Therefore, the maximum number of node pointers is 195.
We need to determine the maximum order (maximum number of child pointers) of a non-leaf node in a B+ tree given the size of the node and the sizes of the keys and pointers. The record pointer size is only relevant for leaf nodes, not non-leaf nodes.
Step 2: Key Formula or Approach:
A non-leaf node in a B+ tree with an order of 'm' contains 'm' child pointers and 'm-1' search keys. The total size occupied by these pointers and keys must be less than or equal to the total node size.
Total Size = (m $\times$ size of a node pointer) + ((m-1) $\times$ size of a search key) $\le$ Node Size
Step 3: Detailed Explanation:
Let 'm' be the maximum number of node pointers (the order of the node).
Given:
- Node Size = 4096 Bytes
- Node pointer size = 10 Bytes
- Search key size = 11 Bytes
We set up the inequality based on the structure of a non-leaf node: \[ (m \times 10) + ((m-1) \times 11) \le 4096 \] Now, we solve for m: \[ 10m + 11m - 11 \le 4096 \] \[ 21m - 11 \le 4096 \] \[ 21m \le 4096 + 11 \] \[ 21m \le 4107 \] \[ m \le \frac{4107}{21} \] \[ m \le 195.571... \] Step 4: Final Answer:
Since the number of pointers 'm' must be an integer, we take the floor of the result. The maximum integer value for m is 195. Therefore, the maximum number of node pointers is 195.
Was this answer helpful?
0
0
Top Questions on Data Structures and Algorithms
- In a Binary Search Tree, which traversal method produces the elements in non-decreasing order?
- CUET (PG) - 2026
- Data Science
- Data Structures and Algorithms
- Which data structure is used by the system to implement recursion?
- CUET (PG) - 2026
- Data Science
- Data Structures and Algorithms
- What is the time complexity of building a heap from an unsorted array of size \(n\)?
- CUET (PG) - 2026
- Data Science
- Data Structures and Algorithms
- P = [1, 2, 3, 5, 4]
Two sorting algo Binary sort (BS), Insertion sort (IS) apply. Let N$_1$ be the total number of comparisons done by BS on the element of P and N$_2$ be the total number of comparisons done by IS on the elements of P. Which of the following option is/are correct?- GATE DA - 2026
- Data Science and Artificial Intelligence
- Data Structures and Algorithms
- Consider the directed graph G = (V, E) where V is the finite set of vertices and E is the set of directed edges between the vertices. G may contain cycle but there is no self-loop, further G may not be strongly connected. Let G$^R$ be the graph obtained by reversing direction of all edges without changing set of vertices. Assume that BFS or DFS for any given vertex V of a graph will visit only the reachable vertices from V in that graph. Which of the following statement must always be true regardless of the structure of G?
- GATE DA - 2026
- Data Science and Artificial Intelligence
- Data Structures and Algorithms
View More Questions
Questions Asked in GATE DA exam
- Rishi and Swathi are students of Class 5. Pavan and Tanvi are students of Class 4. Rishi and Pavan are boys. Swathi and Tanvi are girls. These four students played a total of three games of chess. The games were played one after another. A player who lost a game did not participate in any more games. It was observed that:
1. The first game was the only game where two students of the same class played against each other.
2. The students of Class 5 won more games than the students of Class 4.
3. The boys won 2 games and the girl won 1 game.
The student who did not lose any game is:- GATE DA - 2026
- Logical Reasoning
Consider two distinct positive numbers \( m, n \) with \( m > n \). Let \[ x = n^{\log_n m}, \quad y = m^{\log_m n}. \] The relation between \( x \) and \( y \) is -
- GATE DA - 2026
- Logarithms
- Consider the supervised learning task. The objective function being minimized is \( f(w) = w \cdot x \), where \( w \in \mathbb{R} \) is the parameter. Stochastic Gradient Descent with learning rate of 0.10. Let \( w = 10.00 \) be the \( i^{\text{th}} \) iteration (\( w_i \)). The value of \( w \) at the end of iteration \( (i+1) \) is if \( x = 10 \) ________. Round off 2 decimal.
- GATE DA - 2026
- Machine Learning
- The value of \[ \sum_{j=0}^{\infty} \sum_{i=1}^{\infty} 2^{-j} 3^{-i} \] is ________.
- GATE DA - 2026
- Sequences and Series
- Consider the Ridge LRR is being used to learn prediction function \( y_{\text{pred}} = w^T x \) where \( w, x \in \mathbb{R}^2 \) & mean absolute error (MAE) is used to measure the prediction error. A weight of 0.20 is associated with the regularizer. At an intermediate step of training process assume that the parameter \( w = [-3.00, 4.00]^T \). In the next step for the I/P \( x = [1.00, 2.00]^T \), the predicted value of \( y \) is noted. Let the relation b/w \( x = [x_1, x_2]^T \) & the true value of \( y \) be \( y_{\text{true}} = x_1 + x_2 \). The value of the overall regularized loss for instance is __________ (upto 2 decimal).
- GATE DA - 2026
- Machine Learning
View More Questions