Aritalab:Lecture/Database/Storage

ディスク管理

データベースのレコードを管理する際に重要なのは、I/Oアクセス数を減らすことです。計算機のメモリはページ毎にアクセスされます。大雑把に以下のモデルを考えましょう。

• データページの総数 N
• 1ページを読み書きするのにかかる時間 T (15ミリ秒程度)
• レコードに対するインデクスのサイズ 1/10, ハッシュ関数の適用にかかる時間 c (100ナノ秒程度）

データ中の特定レコードを検索するコスト、全レコードをスキャンするコスト、レコードの挿入または削除に要するコストという観点から考えてみます。 整列させたリストからレコードを削除した際、空いた部分を詰めていく戦略や、ツリーのバランス、ハッシュ値の衝突など細かい点をすべて忘れて大まかに考えると以下のような表ができます。

データ構造	1レコード検索	整列順に全スキャン	挿入と削除
レコードを整列させて格納	T (log2N + 1) レコードの検索に要するステップは log2N	TN 全ページを順にアクセス	T (log2N + 1) + 0.5TN 検索後、該当ページの特定後、挿入により後ろのレコードをずらして格納
レコードのインデクスを作成し、B+ツリーで管理	T (log20.1N + 1) インデクスのページ数は log20.1N	TN ツリーの葉に対応するページだけを順にアクセス	T (log20.1N + 2) 検索後、該当ページを読んで書き戻し
レコードをハッシュ表で管理	c + T ハッシュ表が1ページに収まっていると仮定	TN log2N 全ページをスキャンしてからソート*	c + 2T ページを特定してから修正。用意したバケツに格納スペースがあると仮定

* ... 整列にかかる時間はそのアルゴリズムにも依存して見積もりが難しいので、単純に log N をかけています。

整列レコードの問題点は挿入・削除する場合に挿入箇所より後ろにあるレコードを全てずらして格納しなくてはならない点です。（配列の途中で挿入・削除するのと同じ。期待値としては全体サイズNの半分にあたるレコードをずらさなくてはなりません。）また、データーベースでは単一レコードの検索よりも複数レコードをスキャンする場合が多いため、スキャンに膨大な時間がかかるハッシュ構造も不利になります。あらかじめデータを整列させて格納するツリー構造が得策になります。

B+ 木

1972年、R Bayer と E McCreight (Boeing Scientific Research Labs) はB木というデータ構造を発表しました。B木の構造はここで説明するB+木とほぼ同じですが、葉の頂点だけでなく根から降りる途中の頂点もレコードを置く点だけが異なります。 B+木とはB木の改良版にあたり、途中の頂点にはインデクスのみを置くことにしました。両方とも以下の特徴を持ちます。

• 挿入や削除といった操作のコストがほぼ一定
• 各頂点は常に d+1 以上 2d+1 以下の子供（リンク）を持つ。つまり常に最大リンク数の半分以上をもつ
• 根にあたる頂点だけは 1 以上 2d+1 以下の子供（リンク）を持つ

B+木はさらに葉頂点の間を相互にリンクさせることで、レコードを整列順に取り出す操作を簡単にしました。（途中の頂点にもレコードを置く場合、次のレコードを求める操作に log_d n ステップを要します。）ここでいう数値 d は木のオーダー (order) と呼ばれるパラメータで通常は100程度に設定されます。木の深さは通常 3 から 4 で、数百から数千万レコードを扱えるサイズです。

探索

木の根からラベルを見てノードを下っていくだけです。

function node find(record k)
  return tree_search(root, k)
end

function node tree_search(node n, record k)
  if (isLeaf(n)) return n;
  else 
    find i such that K_i < k < K_{i+1} // i は子ノードの添え字
    return tree_search( getChild(n,i), k);
end

挿入

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

function void insert(record k)
  tree_insert(root, k)
end

function node tree_insert(node n, record k)
  if (isLeaf(n)) 
    if (hasSpace(n))
      addEntry(n, k)
      return null
    else
      m = splitNode(n, k)     // 2d レコードを d 個ずつに分ける
      setSiblingPointers(m,n) // 葉ノード間を二重リンクリスト化
      return m
  else // 中間ノード
    find i such that K_i < k < K_{i+1} // i は子ノードの添え字
    node m = tree_insert(getChild(n,i), k)
    if (m == null) return
    else if (hasSpace(m))
      addNode(n, m)
      return null
    else
      node o = splitNode(n, k)
      if (n == root)
        root = newNode()
        addNode(root, n)
        addNode(root, o)
        return null
      else
        return o
end

削除

削除は挿入の逆操作で、葉頂点からレコードを削除することで隣と結合できる場合に合併処理をおこないます。実際にはデータ量は増え続ける場合が多いので、削除の際に合併処理をおこなわない選択肢もあります。

function void delete(record k)
  tree_delete(null, root, k)
end

function node tree_delete(node p, node n, record k)
  if (isLeaf(n))
    if (isUnderfull(n))
      node s = getSibling(n)
      if (hasExtraEntry(s))
        Move entry from s to n evenly.
        Replace the index for n in the parent node p.
        return null
      else              // n will be deleted
        Merge n into s.
        Adjust sibling pointers.
        return n
    else                // usual case
      removeEntry(n, k)
      return null
  else  // internal node
    find i such that K_i < k < K_{i+1} // i は子ノードの添え字
    node d = tree_delete(n, getChild(n,i), k)
    if (d == null) return // usual case
    else
      removeNode(n, d)
      if (isUnderfull(n))
        node s = getSibling(p, n)
        if (hasExtraEntry(s))
          Move entry from s to n evenly.
          Replace the index for n in the parent node p.
          return null
        else
          Pull splitting key from parent p into s.
          Merge n into s.
          return s
      else
        return null
end

実用上の工夫

重複インデクスの扱い

B+木で管理するキー値に重複を許す場合、同じキー値を持つレコードが複数ページにまたがる可能性があります。このとき、上に示した挿入アルゴリズムでは検索されたキーを持つレコード全てを探すことができません。（検索結果としてたどり着いたページの左右にも同じキー値が格納されているかもしれない。）検索結果のレコードから左右に葉ノード間のリンクをたどり、同一キーを持つレコードを列挙する必要があります。また、あるキーを削除した際に、複数のページを削除して縮約する必要性も出てきます。

重複インデクスの対処法として、オーバーフロー用のページを用意することも可能です。同一キーが多く入ってきた場合は葉にあたる頂点からオーバーフローページを新規につなげていきます。

キー短縮化

キー値のサイズ小さくすればページ内により多くのインデクスを格納できます。特にインデクスに文字列を利用する際は、オーダーを上げるために最初の n 文字を使う等の短縮化をおこないます。これは重複インデクスと同じ効果をもたらすため、検索結果のレコードから左右にリンクをたどる必要性が生じます。

一括作成

最初にB+木を作成するときは、全レコードをソートしてからヒープを作成する要領で一括作成できます。

参考文献

ハッシュ関数

ハッシングは高速で実用上便利ですが、ハッシュ値の衝突によりバケツが溢れる際の処理が面倒です。通常、同一のハッシュ値に対して固定サイズのバケツを用意し、同一ページ上に格納します。 バケツが溢れたときの基本対策は、オーバーフローページの用意です。 しかしいずれはハッシュ表全体がいっぱいになるので、表サイズ（バケツの個数）を増やさねばなりません。表サイズの拡張法としてExtendible HashとLinear Hashがあります。

Extendible Hash

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

ここに図を入れる

インデクス層はハッシュ表サイズと共に倍々に拡張しますが、中身が溢れたバケツ以外はインデクスを更新しません。バケツが溢れる毎に、複数のインデクスが用意されているか確認し、インデクスが空いているときはそれを利用、空いていないときは表全体を2倍に拡大する処理をおこないます。

Linear Hash

Extendible Hashはバケツが一つでも溢れたら表全体が2倍に膨れる処理を繰り返しますが、多くのバケツは使われないままです。またインデクス層を使うため、レコードにアクセスするのに2ページ見なくてはなりません。Linear Hashはこの問題を、バケツ個数を1個ずつ増やすという手法で解決します。

Linear Hashはハッシュ関数を h₀, h₁, h₂, ... と複数用意し、関数 h_i は h_i-1の 2 倍の範囲を指すようにします。現在どの関数を用いているかを、level 変数で管理しておきます。

バケツが溢れたときは、基本的にオーバーフローページを用います。ただし、オーバーフローが起きるたびに1個ずつバケツの数を増やしていき、増やしたバケツには一段上の level 変数を用いてレコードを分割します。

ここに図を入れる

Linear Hashの利点は、ハッシュ値を計算後は1ページのアクセスでレコードにたどり着けることです。ただしオーバーフローページを用いるので、ハッシュ値が偏った場合は、極端に効率が落ちてしまいます。