Dbms-indexing
DBMS-インデックス作成
データはレコードの形式で保存されます。 すべてのレコードにはキーフィールドがあり、一意に認識されるのに役立ちます。
インデックス作成は、インデックス作成が行われた属性に基づいてデータベースファイルからレコードを効率的に取得するためのデータ構造技術です。 データベースシステムでのインデックス作成は、書籍で見られるものと似ています。
索引付けは、その索引付け属性に基づいて定義されます。 インデックスは、次のタイプにすることができます-
- プライマリインデックス-プライマリインデックスは、順序付けられたデータファイルで定義されます。 データファイルは*キーフィールド*で並べられます。 通常、キーフィールドはリレーションのプライマリキーです。
- セカンダリインデックス-セカンダリインデックスは、候補キーであり、すべてのレコードに一意の値を持つフィールド、または重複する値を持つ非キーから生成される場合があります。
- クラスタリングインデックス-クラスタリングインデックスは、順序付けられたデータファイルで定義されます。 データファイルは、非キーフィールドで並べられます。
順序付けされたインデックスは2種類あります-
- 密なインデックス
- スパースインデックス
密なインデックス
密索引では、データベース内の検索キー値ごとに索引レコードがあります。 これにより検索が高速になりますが、インデックスレコード自体を保存するためにより多くのスペースが必要です。 インデックスレコードには、検索キーの値とディスク上の実際のレコードへのポインタが含まれます。
スパースインデックス
疎インデックスでは、すべての検索キーに対してインデックスレコードが作成されるわけではありません。 ここのインデックスレコードには、検索キーとディスク上のデータへの実際のポインタが含まれています。 レコードを検索するには、最初にインデックスレコードに進み、データの実際の場所に到達します。 探しているデータがインデックスをたどって直接到達する場所ではない場合、システムは目的のデータが見つかるまで順次検索を開始します。
マルチレベルインデックス
インデックスレコードは、検索キー値とデータポインターで構成されます。 マルチレベルインデックスは、実際のデータベースファイルとともにディスクに保存されます。 データベースのサイズが大きくなると、インデックスのサイズも大きくなります。 検索操作を高速化するために、メインメモリにインデックスレコードを保持する必要性は計り知れません。 単一レベルのインデックスを使用すると、大きなサイズのインデックスをメモリに保持できなくなり、複数のディスクアクセスが発生します。
マルチレベルインデックスは、インデックスをいくつかの小さなインデックスに分割し、最も外側のレベルを非常に小さくして、メインメモリのどこにでも簡単に収容できる単一のディスクブロックに保存できるようにします。
B ^ [。small]＃+＃^ツリー
B ^ [。small]＃＃^ツリーは、マルチレベルインデックス形式に従うバランスの取れたバイナリ検索ツリーです。 B ^ [。small]＃＃^ツリーのリーフノードは、実際のデータポインターを示します。 B ^ [。small]＃＃^ツリーは、すべてのリーフノードが同じ高さにとどまり、バランスが取れていることを保証します。 さらに、リーフノードはリンクリストを使用してリンクされます。したがって、B ^ [。small]＃＃^ツリーは、ランダムアクセスとシーケンシャルアクセスをサポートできます。
B ^ [。small]＃+＃^ツリーの構造
すべてのリーフノードは、ルートノードから等距離にあります。 B ^ [。small]＃＃^ツリーの順序は *n* で、 *n* はすべてのB ^ [。small]＃＃^ツリーに対して固定されています。
内部ノード-
- 内部（リーフではない）ノードには、ルートノードを除く少なくとも⌈n/2⌉のポインターが含まれます。
- 最大で、内部ノードには n ポインターを含めることができます。
リーフノード-
- リーフノードには、少なくとも⌈n/2⌉レコードポインターと⌈n/2⌉キー値が含まれます。
- 最大で、リーフノードには n レコードポインターと n キー値を含めることができます。
- すべてのリーフノードには、次のリーフノードを指す1つのブロックポインター P が含まれ、リンクリストを形成します。
B ^ [。small]＃+＃^ツリーの挿入
- B ^ [。small]＃+＃^ツリーは下から埋められ、各エントリはリーフノードで行われます。
- 葉ノードがオーバーフローした場合-
- ノードを2つの部分に分割します。
- * i =⌊（m + 1）〜[.small]＃/2＃〜⌋。*のパーティション
- 最初の i エントリは1つのノードに保存されます。
- 残りのエントリ（i + 1以降）は新しいノードに移動されます。
- i ^ [。small] #_ th _＃^ キーは、リーフの親で複製されます。
- 非葉ノードがオーバーフローした場合-
- ノードを2つの部分に分割します。
- * i =⌈（m + 1）〜[.small]＃/2＃〜⌉*でノードを分割します。
- i までのエントリは1つのノードに保持されます。
- 残りのエントリは新しいノードに移動します。
B ^ [。small]＃+＃^ツリーの削除
- B ^ [。small]＃+＃^ツリーエントリは、リーフノードで削除されます。
- ターゲットエントリが検索され、削除されます。
- 内部ノードの場合は、削除して、左の位置からのエントリに置き換えます。
- 削除後、アンダーフローがテストされ、
- アンダーフローが発生した場合は、残りのノードからエントリを配布します。
- 左から配布できない場合、
- ノードから直接それに配布します。
- 左または右から配布できない場合、
- 左右にノードをマージします。
