という大小関係になっています。また、ページを指していないbranchは、NULL値になっています。 厳密に言うとページは、次のようなキビしい条件を満たします。ページ1つについてのキーの個数が最大2M個だとすると、 ページ当たりのキーの個数n は M ≦ n ≦ 2M を満たす。つまり、各ページは少なくとも半分埋まっていなければいけない。ただし、根(一つだけある)については 0 ≦ n ≦ 2 Mでよい。 各ページ上のキーは昇順にならべる( key[0] < key[1] <…< key[n-1] ) ポインタ branch[k] ( k > 0 )の指すページが含むすべてのキーは key[k-1] より大きい ポインタ branch[k] ( k < n )の指すページが含むすべてのキーは key[k] より小さい 木の高さはいたるところ一定。つまり、根から末端のページ(葉)に至るポインタ