No, the final B tree is not correct. The intermediate one is though. The last one should be like this
[K]
/ \
/ \
/ \
[D][G] [N][R][V]
/ / / / / \ \
/ / / / / \ \
/ / / / / \ \
AC EF HIJ LM OPQ ST WX
You missed something very important. In a B-tree, insertions are only done in the leaf node and every full node on the way is split. You inserted Q
in a level 2 node in your final tree.
Edit: I think you are confused about the insertion algorithm. Insertions only take place in the leaf node. In the downward path from root to leaf, if any full node is encountered it is split first. If the leaf node is full, it will be split first and then the key will be inserted. In your case the leaf node OPRST
will be split when it is encountered because it has 5 nodes and is full. Thus R
will be moved up and and a new leaf node containing keys ST
will be created. The older leaf node now will only have OP
keys. Q
is then compared with R
and search moves leftward to OP
node where Q
finally gets inserted.