Question:
In a relational database, a B+ Tree Index is to be constructed for a relation on a key field. In a B+ Tree, a Node Pointer points to a sub-tree and a Data Record Pointer points to a block of database records.
Let, Node size = 4096 bytes, Node Pointer size = 10 bytes, Search Key Field size = 11 bytes and Data Record Pointer size = 12 bytes.
The maximum number of Node Pointers that can be present in a non-leaf node of the B+ Tree is __________. (Answer in integer)
In a relational database, a B+ Tree Index is to be constructed for a relation on a key field. In a B+ Tree, a Node Pointer points to a sub-tree and a Data Record Pointer points to a block of database records.
Let, Node size = 4096 bytes, Node Pointer size = 10 bytes, Search Key Field size = 11 bytes and Data Record Pointer size = 12 bytes.
The maximum number of Node Pointers that can be present in a non-leaf node of the B+ Tree is __________. (Answer in integer)
Let, Node size = 4096 bytes, Node Pointer size = 10 bytes, Search Key Field size = 11 bytes and Data Record Pointer size = 12 bytes.
The maximum number of Node Pointers that can be present in a non-leaf node of the B+ Tree is __________. (Answer in integer)
Show Hint
A non-leaf node with n pointers holds n-1 keys between them; set up the space inequality and solve for the largest integer n.
Updated On: Jul 22, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 195
Solution and Explanation
Step 1: Recall the structure of a non-leaf B+ Tree node.
A non-leaf node with \(n\) Node Pointers holds \(n\) pointers and \((n-1)\) search key values arranged between them (the keys are used to decide which pointer to follow). It does not store Data Record Pointers, those only appear in leaf nodes.
Step 2: Write the space constraint.
Total space used by \(n\) node pointers and \((n-1)\) keys must fit inside the node size:
\[ n \times (\text{Node Pointer size}) + (n-1) \times (\text{Search Key size}) \leq \text{Node size} \]
\[ n \times 10 + (n-1) \times 11 \leq 4096 \]
Step 3: Simplify the inequality.
\[ 10n + 11n - 11 \leq 4096 \]
\[ 21n \leq 4107 \]
\[ n \leq 195.57 \]
Step 4: Take the largest integer satisfying the constraint.
Since \(n\) must be a whole number, \(n = 195\).
Step 5: Verify by substitution.
For \(n = 195\): \(195 \times 10 + 194 \times 11 = 1950 + 2134 = 4084\) bytes, which fits within 4096 bytes.
For \(n = 196\): \(196 \times 10 + 195 \times 11 = 1960 + 2145 = 4105\) bytes, which exceeds 4096 bytes, so 196 pointers do not fit.
Final Answer:
The maximum number of Node Pointers in a non-leaf node is 195. \[ \boxed{195} \]
A non-leaf node with \(n\) Node Pointers holds \(n\) pointers and \((n-1)\) search key values arranged between them (the keys are used to decide which pointer to follow). It does not store Data Record Pointers, those only appear in leaf nodes.
Step 2: Write the space constraint.
Total space used by \(n\) node pointers and \((n-1)\) keys must fit inside the node size:
\[ n \times (\text{Node Pointer size}) + (n-1) \times (\text{Search Key size}) \leq \text{Node size} \]
\[ n \times 10 + (n-1) \times 11 \leq 4096 \]
Step 3: Simplify the inequality.
\[ 10n + 11n - 11 \leq 4096 \]
\[ 21n \leq 4107 \]
\[ n \leq 195.57 \]
Step 4: Take the largest integer satisfying the constraint.
Since \(n\) must be a whole number, \(n = 195\).
Step 5: Verify by substitution.
For \(n = 195\): \(195 \times 10 + 194 \times 11 = 1950 + 2134 = 4084\) bytes, which fits within 4096 bytes.
For \(n = 196\): \(196 \times 10 + 195 \times 11 = 1960 + 2145 = 4105\) bytes, which exceeds 4096 bytes, so 196 pointers do not fit.
Final Answer:
The maximum number of Node Pointers in a non-leaf node is 195. \[ \boxed{195} \]
Was this answer helpful?
0
0
Top GATE DA Data Science and Artificial Intelligence Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions
Top GATE DA Database Management Systems Questions
- Let \(R(A,B,C,D,E)\) be a relational schema with functional dependency set \(F = \{A \rightarrow BC,\ CD \rightarrow E,\ E \rightarrow A\}\).
Which of the following statements is correct? - Consider two relations \(r\) and \(s\) defined on the relational schemas \(R(A,B)\) and \(S(E,C)\), respectively. \(A\) is the primary key of \(R\) and \(E\) is a foreign key of \(S\) referencing \(A\) in \(R\).
Which of the following operations will NEVER violate the foreign key constraint? - Consider a B+ Tree where the maximum number of key values in each leaf node is 2 and the maximum number of pointers in each non-leaf node is 3. Let the content of the B+ Tree be as shown in the figure.
Which of the following options denotes the key value(s) stored in the root node after inserting a key value 3 in the given B+ Tree? - Consider the given relations \(X\), \(Y\) and \(Z\). The relation \(X\) has three columns P, Q and R. The relation \(Y\) has three columns P, Q and S. The relation \(Z\) has two columns P and T.
Relation X:P Q R P1 Q1 R1 P2 Q2 R2 P3 Q3 R2
Relation Y:P Q S P1 Q1 2 P1 Q2 5 P2 Q1 6 P3 Q3 1
Relation Z:P T P1 T1 P3 T2 P4 T3 P4 NULL
Consider the relational algebra expression
\[ \Pi_{P,R,S}\Big[\big(\sigma_{(Q=Q3 \vee R=R2)}[X \Join Y]\big) \Join \big(\sigma_{(S>1)}[Y \Join Z]\big)\Big] \]
where \(\Join\) denotes natural join operation.
Which of the following options is the correct output for the given expression? - Consider a table Employee(EmpID, TeamID), where the column EmpID (ID of an employee) is the primary key. The column TeamID denotes the team ID of the team of which the employee is a member. TeamID is a NOT NULL column.
We want to display the size of the team (denoted as TeamSize) in which each employee is a member by using SQL. As an example, the desired output for the given Employee table is also shown in tabular form.
Which of the following is/are correct?
Employee table:
EmpID TeamID 1 8 2 8 3 8 4 7 5 7 6 9
Output table:
EmpID TeamSize 1 3 2 3 3 3 4 2 5 2 6 1
View More Questions
Top GATE DA Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions