BTree 2007-07-04 15:22:11 2007-07-05 21:06:14 Definition order % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here A \emph{B-tree of \PMlinkescapetext{order} $m$} is a \PMlinkname{balanced}{BalancedTree} search tree in which \begin{itemize} \item every node has at most $m$ children, \item every node, other than a root or leaf, has at least $m/2$ children, \item the root has at least 2 children if it is not a leaf, \item all leaf nodes appear on the same level \item a nonleaf node with $k$ children has $k-1$ keys. \end{itemize} If the tree has $n$ nodes its height is $O(log_2(n))$.