> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/17.-b-trees/17.6-summary.md).

# 17.6 Summary

* BSTs have best-case height $$\Theta(\log N)$$, and worst-case height $$\Theta(N)$$.
* Big O is *not* the same as worst-case!
* B-Trees are a modification of the BST that maintain $$\Theta(\log N)$$ runtime for `add` and `contains` in the worst case. They maintain perfect balance during insertion.
* A B-Tree has a limit $$L$$ on the number of values a node can hold, instead of having one item per node like a BST.
* Upon `add` in a B-Tree, we simply append the value to an existing leaf node in the correct location instead of creating a new leaf node. If the node is too full, it splits and pushes a value up.