In a CS exam on database systems, a question was asked what the maximum number of block access are to find a record in a given system using a B-tree for indexing. The order of the B-tree was 4, and maximum number of entries is when all internal nodes are half full (because if they are less than half full they will merge with neighbor). Thus the tree is at its highest depth when each node has 2 subtree pointers (and max number of accesses is equal to the depth of the tree). But this would effectively give the tree the same structure as a binary tree as each node simply holds one piece of data and two pointers.
So the question is this:
With the policies for insertion and deletion, is it physically possible to insert and delete nodes in a sequence that allows the tree to take this form, or will it always merge and reduce the depth of the tree?
Sure this is possible.
It is not possible to achieve such a binary tree with only insertions, but once you have inserted a bunch of keys (data elements) in a 4-degree b-tree, you can delete keys from the leaves so to target the binary tree shape.
You would target a certain tree height for the binary tree, so first make enough insertions to get a B-tree having that height. Then eliminate keys such to reduce the degree of the nodes that are not binary, starting at the top layers of the tree, working your way down.
Let's say you want to create such a tree with height 3. For that we will insert value 1 to 13 into an empty tree. This will lead to this tree:
[9]
[3, 6] [12]
[1, 2] [4, 5] [7, 8] [10, 11] [13]
Now in order to get only one key where we currently have [3, 6], we need to get rid of one of its children. So let's delete 7 and 8:
After deleting 8, a standard algorithm will "rotate" the value 5 from [4, 5] to its parent, and inject the parent key (6) into the child where we deleted 8:
[9]
[3, 5] [12]
[1, 2] [4] [6] [10, 11] [13]
We still have too many children at the same node, so we continue to delete 6. Now there is a merge of leaves, which will reduce the node we initially wanted to reduce:
[9]
[3] [12]
[1, 2] [4, 5] [10, 11] [13]
And now all non-binary nodes are at the bottom level. We can now delete keys 2, 5, and 11 to get the binary tree:
[9]
[3] [12]
[1] [4] [10] [13]
The same principle can be applied to trees with higher heights. Just start deleting keys from the subtree of internal nodes that are non-binary until they are. At some point there will be merges happening that will reduce the degree of the nodes that are non-binary, eventually making them binary.
If you do this from top to bottom, you will make layer after layer binary, and finally the bottom layer will be binary too.