Why is b-tree search O(log n)?

B-tree is a data structure, which looks like this:

If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need to go through several elements in the child-node to find its right child-node etc.

The point is, when I have $n$ elements in every node, then I have to go through all of them in the worst case. So, we have $O(n)$ complexity for searching in one node.

Then, we must go through all the levels of the structure, and they're $log_m N$ of them, $m$ being the order of B-tree and $N$ the number of all elements in the tree. So here, we have $O(log N)$ complexity in the worst case.

Putting these information together, we should have $O(n) O(log n) = O(n log n)$ complexity.

But the complexity is just $O(log n)$ - why? What am I doing wrong?

You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$.

Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(N)\rceil$ but there is also a saturation factor $d$, that you have not mentioned.

The height will be $O(log N)$, please notice that $m$ disappeared, because it effectively is multiplication by a constant.

Now at every node you have at most $m$ sorted elements, so you can perform binary search giving $log_2(m)$, so the proper complexity is $O(log(N) * log(m))$.

Since $m << N$, and what is more important, is that it does not depend on $N$, so it should not be mixed, or it might be given explicitly (with $m$ not $N$ or appearing $n$).

StackExchange Computer Science Q#59453, answer score: 12