B-tree questions become confusing when order, maximum keys, children, leaf entries and block pointers are treated as interchangeable. In insertion questions, another common error is counting the leaf split but missing a split that propagates to the root.
These 12 questions move from occupancy invariants through node-capacity arithmetic to insertion and cascading root splits. Choose an option first, then write the governing inequality or tree state before reading the explanation. KnowledgeGate has over 90 more practice questions on B-tree and B+ tree structure and insertion, alongside the rest of CS Fundamentals.
B-tree and B+ tree rules to write before solving
Node | Space budget |
|---|---|
B+ internal node of order |
|
B-tree node of order |
|
B+ leaf of capacity |
|
All leaves stay at one depth. Only the root gets the occupancy exception. B+ record pointers live in leaves, not internal nodes.
For a 512-byte internal block with a 6-byte child pointer and 14-byte key, 6p + 14(p - 1) <= 512, so 20p <= 526 and p = 26. For a 1024-byte leaf with a 9-byte value, 7-byte record pointer and 6-byte next-leaf pointer, 16q + 6 <= 1024, so q = 63.
Insert into a leaf, split overflow, promote or copy the separator under the stated convention, and continue upward. A root split adds both a new sibling and a new root.
Structure and occupancy MCQs 1-4
Question 1
In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
A. Only the root node
B. All leaf nodes
C. All internal nodes
D. Only the leftmost leaf node
Answer: A.
The root alone may be the sole leaf or have fewer children. Every non-root node must meet minimum occupancy, so B, C and D invent exceptions.
Question 2
Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?
A. B+ Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data records
C. Key values in each node are kept in sorted order
D. Each leaf node has a pointer to the next leaf node
Answer: B.
A, C and D are properties. B is false because internal nodes hold search keys and child pointers, not record pointers. NOT reverses the selection.
Question 3
B+ Trees are considered BALANCED because
A. the lengths of the paths from the root to all leaf nodes are all equal.
B. the lengths of the paths from the root to all leaf nodes differ from each other by at most 1.
C. the number of children of any two non-leaf sibling nodes differ by at most 1.
D. the number of records in any two leaf nodes differ by at most 1.
Answer: A.
Balance means equal root-to-leaf path lengths, not the AVL-style wording in B or occupancy comparisons in C and D. Differently occupied leaves can share one level.
Question 4
Consider a B+ -tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
A. 1
B. 2
C. 3
D. 4
Answer: B.
Five keys permit 6 children. Half occupancy gives ceil(6/2) = 3 children, hence 3 - 1 = 2 keys in a non-root internal node. A non-root leaf needs ceil(5/2) = 3 keys, so 2 is the smallest legal count anywhere below the root.
Node-capacity MCQs 5-7: turn bytes into one inequality
Question 5
The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?
A. 24
B. 25
C. 26
D. 27
Answer: C.
For order p, 6p + 14(p - 1) <= 512, or 20p <= 526, so p = 26. Check: 26 x 6 + 25 x 14 = 506 bytes fits; 27 needs 27 x 6 + 26 x 14 = 526 and overflows.
Question 6
Consider a table T in a relational database with a key field K. A B-tree of order p is used as an access structure on K, where p denotes the maximum number of tree pointers in a B-tree index node. Assume that K is 10 bytes long; disk block size is 512 bytes; each data pointer PD is 8 bytes long and each block pointer PB is 5 bytes long. In order for each B-tree node to fit in a single disk block, the maximum value of p is
A. 20
B. 22
C. 23
D. 32
Answer: C.
Budget p block pointers and p - 1 key/data-pointer pairs: 5p + (p - 1)(10 + 8) <= 512. Thus 23p - 18 <= 512, so p <= 530/23 = 23.04; the greatest integer is 23. Unlike Question 5, each key carries a data pointer.
Question 7
The order of a leaf node in a tree B+ is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
A. 63
B. 64
C. 67
D. 68
Answer: A.
Use 1K = 1024. Each pair costs 16 bytes and the next-leaf pointer costs 6, so 16q + 6 <= 1024. Thus q <= 63.625, giving 63. A 64-entry leaf needs 1030 bytes.
Disk indexing and range-query MCQs 8-10
Question 8
Which one of the following is a key factor for preferring B+ -trees to binary search trees for indexing database relations?
A. Database relations have a large number of records
B. Database relations are sorted on the primary key
C. B+ -trees require less memory than binary search trees
D. Data transfer from disks is in blocks
Answer: D.
A B+ node matches the disk block transfer unit, so one read returns a whole node. High fan-out means each read eliminates a large slice of the key range, where a binary search tree spends one disk read per single comparison. Record count, sorting and memory use do not explain the choice.
Question 9
Which of the following is correct?
A. B-trees are for storing data on disk and B+ trees are for main memory.
B. Range queries are faster on B+ trees.
C. B-trees are for primary indexes and B++ trees are for secondary indexes.
D. The height of a B+ tree is independent of the number of records.
Answer: B.
Find the first key through the internal index, then follow linked leaves through the range. A and C invent restrictions; D fails because height depends on entry count and fan-out.
Question 10
B+ -trees are preferred to binary trees in databases because
A. Disk capacities are greater than memory capacities
B. Disk access is much slower than memory access
C. Disk data transfer rates are much less than memory data transfer rates
D. Disks are more reliable than memory
Answer: B.
High fan-out keeps the tree shallow, reducing block accesses. C is tempting, but access latency and the number of I/O operations drive index design, not a blanket transfer-rate claim.
Insertion and split MCQs 11-12
Question 11
A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are:
A. 5
B. 4
C. 3
D. 2
Answer: A.
The leaf and two internal splits create one sibling each. The root split creates a sibling plus a new root. Thus 1 + 1 + 1 + 2 = 5 new nodes.
Question 12
A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?
A. 3
B. 4
C. 5
D. 6
Answer: C.
Order 4 means at most 3 keys. With split-before-descending, insert 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. The five splits are:
Inserted key | Split node | Promoted key | Cumulative splits |
|---|---|---|---|
4 | Old root | 2 | 1 |
6 | Right leaf | 4 | 2 |
8 | Right leaf | 6 | 3 |
9 | Full root | 4 | 4 |
10 | Right leaf | 8 | 5 |
The final root is [4], with internal children [2] and [6,8]. Leaves [1], [3], [5], [7] and [9,10] account for every key.
The five traps these B-tree MCQs are checking
Trap | Exact correction |
|---|---|
Order | Order |
Child pointers versus separators |
|
B+ internal versus B+ leaf layout | Internal nodes route; leaves hold record pointers and the next-leaf link. |
1000 bytes versus 1K | Question 7 uses |
One split versus a cascade | Question 11 can create five nodes when splitting reaches the root. |
Use a 60-second check: label the node type, write its byte budget, keep the inequality until the final floor, state the root exception, then trace every split upward. Continue with the DBMS MCQ hub, or contrast these database trees with the BST, AVL and heap questions in Binary Tree MCQs.
Short version and the next practice step
B+ internal nodes route searches. B+ leaves hold record pointers and form the range-scan chain. Node order comes from a byte inequality, all leaves stay at one depth, and insertion can split every level before creating a new root.
Redo Questions 5, 7, 11 and 12 without the options. Those four reveal whether the formulas and split mechanics are secure. Write each intermediate tree state on paper. For a GATE-focused sequence, use GATE Guidance by Sanchit Sir. For broader semester-level CS revision, use the Zero to Hero Complete CS Course.
