2-3木
2-3木の検索は以下のように行われる。
根を対象ノードとして検索を開始する
検索対象のノードが葉であり、検索値と一致するなら検索成功として終了、検索値と一致しないなら木に登録されていないものとして終了する
検索対象の内部ノードのキーが一つの場合、検索値がキーより小さいなら左へ大きいなら右のノードを次の対象とする。
検索対象の内部ノードのキーが二つの場合、検索値2つのキーどちらよりも小さいなら左へ、片方のキーより大きくもう片方のキーより小さいなら真ん中へ、どちらよりも大きい場合は右のノードを次の対象とする
2.以下を繰り返す。
BB木の場合はこれに、内部ノードのキーに一致した場合に検索成功として返す処理が加わる。2-3木は根から葉までの距離が全て等しいため、要素数を N とすると検索に要する実行時間 2-3木、BB木共に O (log N) に比例する。2分探索木と異なりこの時間は、データの順序によって劣化することはない。