In a B-tree of order m, where order means the maximum number of children a node may have, what is the maximum number of keys a node can hold?
Correct answer A. m − 1
Explanation
A node with k keys has k + 1 child pointers, because the keys split the range into k + 1 intervals. If a node can have at most m children, it can hold at most m − 1 keys; inserting one more triggers a split. Non-root nodes must also have at least ⌈m/2⌉ children, which keeps B-trees shallow and well suited to disk storage.
Answer checked How we write and check questions
Discussion