Aritalab:Lecture/Database/Storage - Revision history

Adm: /* B+ 木 */

2011-09-16T07:20:06Z

‎B+ 木

Adm: /* Extendible Hash */

2011-09-16T06:42:41Z

‎Extendible Hash

Adm: /* ディスク管理 */

2011-09-16T06:41:45Z

‎ディスク管理

Adm: /* 重複インデクスの扱い */

2011-09-16T06:40:41Z

‎重複インデクスの扱い

Adm: /* 削除 */

2011-09-16T06:38:53Z

‎削除

Adm: /* 挿入 */

2011-09-16T06:36:30Z

‎挿入

Adm: /* 挿入 */

2011-09-16T06:35:28Z

‎挿入

Adm: /* B+ 木 */

2011-09-16T06:34:18Z

‎B+ 木

Adm: /* ディスク管理 */

2011-09-16T06:33:23Z

‎ディスク管理

Adm: /* ディスク管理 */

2011-09-16T06:32:34Z

‎ディスク管理

@@ Line 33: / Line 33: @@
 ==B+ 木==
-B+木とは、葉の部分にのみレコードを格納する木構造で、以下の特徴を持ちます。
+年、R Bayer と E McCreight (Boeing Scientific Research Labs) はB木というデータ構造を発表しました。<ref>R. Bayer and E. McCreight. "Organization and Maintenance of Large Ordered Indexes," Acta Informatica, 1, 1972</ref>B木の構造はここで説明するB+木とほぼ同じですが、葉の頂点だけでなく根から降りる途中の頂点もレコードを置く点だけが異なります。
 * 挿入や削除といった操作のコストがほぼ一定
-* 各頂点は常に d 以上 2d 以下の子供を持つ、半分以上のリンクがつねに埋まっている
+* 各頂点は常に d+1 以上 2d+1 以下の子供（リンク）を持つ。つまり常に最大リンク数の半分以上をもつ
-* 根にあたる頂点だけは 1 以上 2d 以下の子供を持つ
+* 根にあたる頂点だけは 1 以上 2d+1 以下の子供（リンク）を持つ
-数値 d は木のオーダー (order) と呼ばれるパラメータで通常は100程度に設定されます。木の深さは通常 3 から 4 で、数百から数千万レコードを扱えるサイズです。
+B+木はさらに葉頂点の間を相互にリンクさせることで、レコードを整列順に取り出す操作を簡単にしました。（途中の頂点にもレコードを置く場合、次のレコードを求める操作に log<sub>d</sub> n ステップを要します。）ここでいう数値 d は木のオーダー (order) と呼ばれるパラメータで通常は100程度に設定されます。木の深さは通常 3 から 4 で、数百から数千万レコードを扱えるサイズです。
 ===探索===
@@ Line 147: / Line 149: @@
 ====一括作成====
 最初にB+木を作成するときは、全レコードをソートしてからヒープを作成する要領で一括作成できます。
 ==ハッシュ関数==

@@ Line 154: / Line 154: @@
 ===Extendible Hash===
-いずれかのバケツが1箇所でも溢れたらハッシュ表全体のサイズを2倍に拡張する方式です。溢れたバケツの中身は半分に分割します。ここで残りのバケツも全て半分ずつに分けていては処理が遅くなるため、ハッシュ関数値からバケツまでの間に一段、インデクス層を設けます。
+いずれかのバケツが1箇所でも溢れたらハッシュ表全体のサイズを2倍に拡張する方式です。溢れたバケツの中身は半分に分割します。ここで残りのバケツも全て半分に分けていては処理が遅くなるため、ハッシュ関数値からバケツまでの間に一段、インデクス層を設けます。
 <br/>

@@ Line 26: / Line 26: @@
 |'''c + T'''<br/>ハッシュ表が1ページに収まっていると仮定
 |'''TN log<sub>2</sub>N'''<br/>全ページをスキャンしてからソート<sup>*</sup>
-|'''c + 2T'''<br/>ページを特定してから修正。用意したバケットに格納スペースがあると仮定
+|'''c + 2T'''<br/>ページを特定してから修正。用意したバケツに格納スペースがあると仮定
 |}
 <small>* ... 整列にかかる時間はそのアルゴリズムにも依存して見積もりが難しいので、単純に log N をかけています。</small>

@@ Line 138: / Line 138: @@
 ===実用上の工夫===
 ====重複インデクスの扱い====
-B+木で管理するキー値に重複を許す場合、同じキー値を持つレコードが複数ページにまたがる可能性があります。このとき、上に示した挿入アルゴリズムでは検索されたキーを持つレコード全てを探すことができません。検索結果のレコードから左右にリンクをたどり、同一キーを持つレコードを列挙する必要があります。また単一のキーを削除した際に、複数のページを削除して縮約する必要性も出てきます。
+B+木で管理するキー値に重複を許す場合、同じキー値を持つレコードが複数ページにまたがる可能性があります。このとき、上に示した挿入アルゴリズムでは検索されたキーを持つレコード全てを探すことができません。（検索結果としてたどり着いたページの左右にも同じキー値が格納されているかもしれない。）検索結果のレコードから左右に葉ノード間のリンクをたどり、同一キーを持つレコードを列挙する必要があります。また、あるキーを削除した際に、複数のページを削除して縮約する必要性も出てきます。
 重複インデクスの対処法として、オーバーフロー用のページを用意することも可能です。同一キーが多く入ってきた場合は葉にあたる頂点からオーバーフローページを新規につなげていきます。

@@ Line 96: / Line 96: @@
 <pre>
-function node delete(node p, node n, record k)
+function void delete(record k)
    if (isLeaf(n))
      if (isUnderfull(n))
@@ Line 113: / Line 117: @@
    else  // internal node
      find i such that K_i < k < K_{i+1} // i は子ノードの添え字
-     node d = delete(n, getChild(n,i), k)
+     node d = tree_delete(n, getChild(n,i), k)
      if (d == null) return // usual case
      else

@@ Line 57: / Line 57: @@
 ===挿入===
 最初は、根となる頂点とからっぽの葉頂点一つからスタートします。
-レコードを挿入するのは根となる頂点で、そこから再帰的に子頂点のいずれかにレコードを渡します。葉に到達したらレコードを格納しますが、ある時点で頂点に書き込めるレコード数の上限に達するので、頂点を分割します。分割した場合、中央にあたるレコード値を親頂点に渡します。（これが元で親頂点も分割され、根までさかのぼる場合もあります。）
+レコードを挿入するのは根となる頂点 root で、そこから再帰的に子頂点のいずれかにレコードを渡します。葉に到達したらレコードを格納しますが、ある時点で頂点に書き込めるレコード数の上限に達したら、頂点を分割します。分割した場合、中央にあたるレコード値を親頂点に渡します。（これが元で親頂点も分割され、根までさかのぼる場合もあります。）
 <pre>

@@ Line 60: / Line 60: @@
 <pre>
-function node insert(node n, record k)
+function void insert(record k)
    if (isLeaf(n))
      if (hasSpace(n))
@@ Line 71: / Line 75: @@
    else // 中間ノード
      find i such that K_i < k < K_{i+1} // i は子ノードの添え字
-     node m = insert(getChild(n,i), k)
+     node m = tree_insert(getChild(n,i), k)
      if (m == null) return
      else if (hasSpace(m))

@@ Line 11: / Line 11: @@
 {| class="wikitable"
-! データ構造 || レコード検索 || 整列順に全スキャン || 挿入と削除
+! データ構造 || 1レコード検索 || 整列順に全スキャン || 挿入と削除
 |-
 | レコードを整列させて格納
 |'''T (log<sub>2</sub>N + 1)'''<br/> レコードの検索に要するステップは log<sub>2</sub>N
 |'''TN'''<br/>全ページを順にアクセス
-|'''T (log<sub>2</sub>N + 1)'''<br/>検索後、該当ページを読んで書き戻し
+|'''T (log<sub>2</sub>N + 1) + 0.5TN'''<br/>検索後、該当ページの特定後、挿入により後ろのレコードをずらして格納
 |-
 | レコードのインデクスを作成し、B+ツリーで管理
 |'''T (log<sub>2</sub>0.1N + 1)'''<br/> インデクスのページ数は log<sub>2</sub>0.1N
 |'''TN'''<br/>ツリーの葉に対応するページだけを順にアクセス
-|'''t (log<sub>2</sub>0.1N + 2)'''<br/>検索後、該当ページを読んで書き戻し
+|'''T (log<sub>2</sub>0.1N + 2)'''<br/>検索後、該当ページを読んで書き戻し
 |-
 | レコードをハッシュ表で管理
 |'''c + T'''<br/>ハッシュ表が1ページに収まっていると仮定
-|'''&alpha; &times; TN log<sub>2</sub>N'''<br/>全ページをスキャンしてからソート<ref>整列にかかる時間はそのアルゴリズムにも依存して見積もりが難しいので、単純に log N をかけています。</ref>
+|'''TN log<sub>2</sub>N'''<br/>全ページをスキャンしてからソート<sup>*</sup>
 |'''c + 2T'''<br/>ページを特定してから修正
 |}
-ツリー構造で整列順にスキャンする手間の見積はデータ構造にも大きく依存するので上記が常に成り立つわけではありませんが、単一の検索ではなく複数のレコードを検索するシステムの場合は、全スキャンに膨大な時間をかけるハッシュ構造よりも、あらかじめ整列されたツリー構造で管理するのが得策になります。
+整列レコードの問題点は挿入・削除する場合に挿入箇所より後ろにあるレコードを全てずらして格納しなくてはならない点です。（配列の途中で挿入・削除するのと同じ。期待値としては全体サイズNの半分にあたるレコードをずらさなくてはなりません。）また、データーベースでは単一レコードの検索よりも複数レコードをスキャンする場合が多いため、スキャンに膨大な時間がかかるハッシュ構造も不利になります。あらかじめデータを整列させて格納するツリー構造が得策になります。
 ==B+ 木==