What's the insert complexity of btree?

It seems when new node is inserted(whose complexity is O(logN)), the whole tree needs to be r开发者_如何学Pythone-balanced.

What's the complexity of re-balancing?

---

It's the height of the tree. It's not rebalanced in the sense of a binary tree. When you add a node, if that causes a split you insert a key into the node above. If that causes as split, then you do the same thing one level up, etc., until you get to the root. So the complexity is O(logN).