| Version current |
Version 5 |
|
A \emph{B-tree of \PMlinkescapetext{order} $m$} is a \PMlinkname{balanced}{BalancedTree} search tree in
|
A \emph{B-tree of \PMlinkescapetext{order} $m$}is a \PMlinkname{balanced}{BalancedTree} search tree in
|
| which |
which |
| \begin{itemize} |
\begin{itemize} |
| \item |
\item |
| every node has at most $m$ children, |
every node has at most $m$ children, |
| \item |
\item |
| every node, other than a root or leaf, has at least $m/2$ children, |
every node, other than a root or leaf, has at least $m/2$ children, |
| \item |
\item |
| the root has at least 2 children if it is not a leaf, |
the root has at least 2 children if it is not a leaf, |
| \item |
\item |
| all leaf nodes appear on the same level |
all leaf nodes appear on the same level |
| \item |
\item |
| a nonleaf node with $k$ children has $k-1$ keys. |
a nonleaf node with $k$ children has $k-1$ keys. |
| \end{itemize} |
\end{itemize} |
|
|
|
|
| If the tree has $n$ nodes its height is $O(log_2(n))$. |
If the tree has $n$ nodes its height is $O(log_2(n))$. |
