バランス木

どの葉までの深さもほぼ等しくなるように保たれた木。木が一方に偏ると探索が遅くなるため、挿入・削除のたびに形を整え直す。AVL木やB木が代表例で、探索時間をO(log n)に保てる。

キーの大小関係に従って節点を配置し、根から比較しながらたどることで目的のキーを効率よく探せるようにした木。各節点で左の部分木に小さいキー、右に大きいキーを置く2分探索木が基本で、平均O(log n)で探索・挿入・削除ができる。偏った順にデータを入れると高さが増してO(n)に悪化するので、AVL木や赤黒木、B木のように高さを自動的に保つ平衡木が使われる。

B木を改良したデータ構造で、データ（またはその所在）は葉にだけ格納し、内部の節は探索のためのキーだけを持つ。葉どうしがポインタで順につながっているため、範囲を指定した検索や順次の読出しが速く、データベースの索引に広く使われる。

要素（節、ノード）を親子関係で階層的につないだデータ構造。最上位の節を根、子を持たない節を葉という。2分木、2分探索木、B木などの種類があり、データの探索や、ディレクトリのような階層データの表現に使う。

キーを整列した状態で保持する平衡木（B木やB+木）で構成した索引で、根から葉までの深さがどのキーでも同じなので、データ量がnのとき探索・挿入・削除をO(log n)で行える。一致検索のほか範囲検索や並び替えにも使えるため、多くのDBMSで標準の索引方式になっている。値の種類が多い（カーディナリティが高い）列に向く。

1つの節点が3つ以上の子を持てる木で、m個までの子を持つものをm分木という。1つの節点に多くのキーと子を持たせると木の高さが低くなり、根から葉までにたどる節点が少なくて済む。この性質を使ったB木やB+木は、ディスクの1回の読込みで多くのキーを比較できるので、データベースの索引に使われる。