再バランシング 
用途
以下の場合には、データベースシステムによって B* の構造が変更されます。
● データレコードが変更または挿入されるときに、リーフページに利用可能なスペースが十分にない場合
データベースシステムによって新しいリーフページが追加され、データレコードが再配分されます。
したがって、テーブルのサイズは、データ領域内で利用可能な記憶域の合計量によってのみ制限されます。
● データレコードの削除後に、リーフページが十分に一杯にならなくなった場合
データベースシステムによってこのリーフページが削除され、データレコードは別のリーフページに移されます。
● データレコードが変更または挿入されたために、次に上位にある区切記号が一意でなくなった場合
データベースシステムによって区切記号が再配分されます。
これにより、B* ツリーの一部の分岐で、他の分岐よりもページ数が多くなる可能性があります。ページがこのように不規則に配分されると、データベースシステムのパフォーマンスが低下します。これは、ページ数の多い分岐のデータを検索する場合は、ページ数が少ない分岐よりも多くアクセスする必要があるためです。
データベースシステムは、このような不規則な配分を認識し、負荷を自動的にバランシングします (再編成の原則はありません)。
以下のグラフは、INSERT 文が実行されたとき、データベースシステムによって B* ツリー構造がどのように変更されるかを示しています。
リーフレベルでのページ配分の例
ADDRESS テーブルで、CITY 列が一次キーとして定義されています。ユーザは INSERT 文を使用して、CITY 列に値 Albas の新しいデータレコードを挿入します。ただし、このデータレコードは、大きすぎて B* ツリーの対応するリーフページに挿入することができません。その結果、データベースシステムによって以下のアクションが実行されます。
...
1. 新しいリーフページが登録され、新しいデータレコードはこの新しいリーフページに挿入されます。新しいリーフページのエントリが、新しいデータレコードから始まる順序でソートされます。
2. 必要に応じて、新しいリーフページのソート領域に属するすべてのデータレコードが、古いリーフページから新しいリーフページにコピーされ、その後、古いリーフページから削除されます。この手順はページ分割と呼ばれます。続いて、ポジション一覧およびそれぞれのポインタが、リーフレベル内の後続ページに更新されます。
3. 新しいリーフページのアドレスおよび区分記号情報が、1 段階上位レベルにある対応するルートページまたは B* ツリー索引ページに挿入されます。
○ B* ツリー索引ページが小さすぎる場合は、新しい B* ツリー索引ページがこの索引レベルに挿入されます。
○ 最上位レベルのルートページが小さすぎる場合は、新しい B* ツリー索引レベルが登録されます。
参照: