B+木は多分平衡探索木（バランス木）であり、各ノードに複数のキーと子ノードへのポインタを保持します。データ総件数を $X$、ノードあたりの分岐数（ファンアウト）を $m$ とすると、木の高さ（中間ノードから葉ノードまでの深さ）は $O(\log_m X)$ となります。したがって、候補キーによる1件検索においてアクセスするノード数のオーダーは底によらず $O(\log X)$ となります。