I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each node you pass maximum $4$ time. The upper limit is $O(n)$. So in B+ tree it's limit by $2*B$ times. Is it right?

  • $\begingroup$ In a B+ tree, to do an in-order traversal, one need only traverse the leaves as they link to each other. And by design, at least a certain fraction of each leaf is full. So it is $O(n)$. $\endgroup$ – Reinstate Monica Mar 8 '18 at 1:05
  • $\begingroup$ Thank you @Solomonoff'sSecret . I didn't mention it but I mean the implementation without links between the leaves. $\endgroup$ – ChaosPredictor Mar 8 '18 at 10:30
  • $\begingroup$ Note that the number of nodes in a B+ tree is $\theta(n)$ because the number of nodes is twice the number of leaves less one, and the number of edges is one less than the number of nodes, which is also $\theta(n)$. So traversal is still $\theta(n) \subset O(n)$. $\endgroup$ – Reinstate Monica Mar 8 '18 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.