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?
Why is b-tree search O(log n)?
algorithm analysis;data structures;search trees;balanced search trees
You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$.There 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 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 the $m << N$ and what is more important 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$).