B木とは
B木（ビーき）は、主にデータベースやファイルシステムにおいて、大量のデータの中から特定のデータを効率的かつ高速に検索、挿入、および削除するために設計された、自己平衡型の多分岐探索木構造のことです。
B木の概要とデータ構造における役割
B木（B-tree）は、1972年にRudolf BayerとEdward M. McCreightによって考案されました。
従来の二分探索木（Binary Search Tree）が、データの偏りによって性能が大きく変動する可能性があるのに対し、B木は、常に木の高さ（深さ）が最小限に保たれるように設計された平衡木（Balanced Tree）です。
B木の最も重要な特徴は、ノードが多数の子ノードを持つ（多分岐）ことができる点です。この多分岐の特性は、ディスクやSSDといった二次記憶装置（補助記憶装置）のアクセス効率を最大化するために最適化されています。
二次記憶装置へのアクセスは、主記憶（メインメモリ）へのアクセスと比較して非常に遅いため、検索に必要なアクセス回数を減らすことが性能向上に直結します。
B木は、ノード内に多くのキーとポインタを保持することで、木の高さ（深さ）を極端に低く保ちます。
これにより、大規模なデータセットであっても、ディスクI/O（読み書き操作）の回数を最小限に抑え、高速なデータ処理を実現します。
主な目的は、二次記憶装置に格納された大規模データに対する探索、挿入、削除の操作を、最悪の場合でも対数時間（O(logn)）で実行できるように保証することです。
B木の基本構造と特性
B木の構造は、その効率的な動作を保証するために、いくつかの厳格なルールによって定義されています。
1. ノードの構造
各ノードは、以下の要素で構成されます。
- キー（Key）: データを分類・探索するための値です。ノード内では昇順にソートされています。
- ポインタ（Pointer）: 子ノードを指すポインタです。キーの数より1つ多く存在します。キーによって定義された区間のデータを持つ子ノードを指します。
2. B木の厳格な規則（次数 m に基づく）
B木の構造は、その次数（Order）m（または最小次数 t=⌈m/2⌉）によって定義され、以下の規則を満たす必要があります。
- ノード内のキーの数: 根ノード（ルート）以外のノードは、最低限、⌈m/2⌉−1 個のキーを保持する必要があります。根ノードは例外的に1個以上のキーを持ちます。
- ノード内のポインタの数: 各ノードは、最低限、⌈m/2⌉ 個の子ポインタを保持する必要があります（根ノードを除く）。
- 木の平衡性: すべての葉ノード（リーフ）は、必ず同じ深さ（レベル）に存在する必要があります。この規則が、B木が自己平衡型であることの根拠となります。
- ノードの上限: 各ノードは、最大で m−1 個のキーと m 個の子ポインタを保持します。
3. データの探索
データ探索は、二分探索木と同様に根ノードから開始します。キーを検索し、適切な範囲の子ポインタをたどって下層へ進みます。キーの数が多いにもかかわらず探索が高速なのは、ノード内のキーがソートされているため、ノード内での検索には二分探索を適用できるからです。
B木の操作：挿入と削除（自己平衡の維持）
B木が平衡性を維持できるのは、データが挿入または削除された際に、規則に違反しないようにノードを分割または結合するメカニズムを備えているためです。
1. 挿入（Insertion）
- 葉ノードに新しいキーを挿入します。
- もしノードのキー数が上限（m−1）を超えた場合、そのノードは中央のキーを親ノードに昇格させ、残りのキーを新しい2つのノードに分割します（スプリット）。この分割操作が再帰的に上位のノードに伝播することで、木の深さを低く保ちます。
2. 削除（Deletion）
- キーを削除した後、ノードのキー数が最小キー数（⌈m/2⌉−1）を下回った場合、B木の規則を維持するために以下の操作を行います。
- 隣接ノードからの借用: 隣接する兄弟ノードに十分なキーがあれば、親ノードのキーを経由してキーを移動させます。
- ノードの結合: 隣接する兄弟ノードにも余裕がない場合、その兄弟ノードと結合し、親ノードのキーを1つ降格させます（マージ）。この結合も、再帰的に上位のノードに伝播する可能性があります。
B木とB+木
B木は多くのデータベースシステムで利用されていますが、特に商用データベースではB木の派生であるB+木がより広く使用されています。
| 特徴 | B木 | B+木 |
| データ（値）の格納 | すべてのノード（内部ノードと葉ノード）に格納可能。 | 葉ノードのみに格納される。内部ノードは探索用のキーとポインタのみを保持する。 |
| 葉ノードの結合 | 連結されていない。 | すべての葉ノードが順序付きリストとして連結されている。 |
| メリット | 単一キーの検索は速い可能性がある。 | 範囲検索（Range Query）が非常に高速であり、ディスクI/Oの効率も高い。 |
+木は、すべてのデータを連続した葉ノードに保持し、それらを連結することで、データセット全体や特定の範囲を効率的にスキャンできるため、現代のデータベースのインデックス構造として最適とされています。
関連用語
お問い合わせ
システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。
APPSWINGBYの
ソリューション
APPSWINGBYのセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
既存事業のDXによる新規開発、既存業務システムの引継ぎ・機能追加、表計算ソフトによる管理からの卒業等々、様々なWebシステムの開発を行っています。
iOS/Androidアプリ開発
既存事業のDXによるアプリの新規開発から既存アプリの改修・機能追加まで様々なアプリ開発における様々な課題・問題を解決しています。
リファクタリング
他のベンダーが開発したウェブサービスやアプリの不具合改修やソースコードの最適化、また、クラウド移行によってランニングコストが大幅にあがってしまったシステムのリアーキテクチャなどの行っています。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。
