2-3木
子供を2つもつノード。aより小さいノードが p、大きいノードが qになる。
子供を3つもつノード。aより小さいノードが p、aより大きく bより小さいノードが q、bより大きいノードが r になる。
2-3木は後述する様に要素の持ち方に関して文献によって違いがあるが、共通する定義として、
すべての内部ノードは 2か3の子供を持つ(1つ、または4つ以上の子供を持つ親は存在しない)
全ての葉は根からの距離が等しい(平衡木)
内部ノードは1つか2つのキーを持つ。
1つのキーを持つノードは2分探索木と同様に、そのキーより小さい子供を左に大きい子供を右に格納している。
2つのキー(a, bで a < b とする)を持つノードは、a より小さい子供を左に、a より大きく b より小さい子供を真ん中に、b より大きい子供を右に配置する。
という木構造である。