B+木
定義
用語
Internal node (内部ノード) Leaf node 以外のノード
Leaf node (葉ノード) 末端のノード
$ b分木、高さ $ h の B+木の定義
バランス木である (Root node から Leaf node へのパスは、全て同じになる)
Internal node は、次数が $ b のとき$ \frac{2}{b} から $ b の子をもつ ($ b 分木なので、最大 $ b の子をもてる)
Leaf node は、次の Leaf node へのポインタを持つ
メリット
データ構造は、特定の問題を解決するためにあるが、B+木 の解決する課題は以下。 バランスを保持することが簡単 B+木 の操作後に、改めて B+木 のバランスが保たれているかを確かめる必要はない 他の木構造よりも探索が高速 要求されたデータにアクセスする際の読み込み回数の最大長がツリーの深さに基づいて決まるため、スケールする
例えば、検索対象のデータがメモリ上に収まらずディスク上に格納する必要がある場合に非常に効果的。
特徴
$ b分木、高さ $ h の B+木の場合
格納できる最大レコード数は $ n=b^h
レコードの挿入に要する走査回数は最悪で$ O(log_b n)
レコードの探索に要する走査回数は最悪で$ O(log_b n)