それが僕には楽しかったんです。

僕と MySQL と時々 MariaDB

CMU Database Systems をひたすら追っていく ~06 Hash Tables~

この記事は「 けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 5日目の記事です。

はじめに

どうも、最近ダーク・タワーという映画がめちゃくちゃ刺さりまくって何周も見ているけんつです。
今回はハッシュテーブルに入っていく。徐々にレイヤー(ヒエラルキー)が上がってきてそれなりにわかりやすい部分が多くなってきているので少しスピードアップしていきたい。

今日の動画

www.youtube.com

Hash Table

ハッシュテーブルはキーがハッシュ値にマッピングされている連想配列を抽象化したデータ構造のこと。
これらは大きく２つの部分から成る。

  • ハッシュ関数: これは大きなキースペースを小さなドメインにマッピングするために使う。配列へのインデックスを計算するために使用されるがスループットと衝突率のトレードオフを考慮する必要がある。
  • ハッシュスキーマ: ハッシュの衝突を処理するためのもの。衝突回避のために大きなハッシュテーブルを割り当てる必要性とキーを検索・追加するために追加の命令を実行することのトレードオフを考慮する必要がある。

これら全てを考慮すると非常に規模が大きく複雑なものが出来上がってしまうので、ここではシンプルなエレメント毎にひとつのスロットを持つ巨大な配列をハッシュテーブルを想定する。

この章ではこれらを順をおってみていく。

Data Structures

その前にハッシュテーブル以外にも DBMS は内部的に様々な種類のデータ構造を使用している。例えば以下のようなもの。

  • Internal Meta-Data: データベースとシステム状態に関する情報を保持する
  • Core Data Storage: データベース内のタプルを保存する基礎となるストレージ
  • Temporary Data Structures: クエリ実行中に一時的なデータ領域を作成し、実行を高速化する(Join など)
  • Table Indexes: 特定のタプルに対する検索を高速化するための補助的なデータ構造。

またこれらのデータ構造を設計するためには以下の観点が重要になる。

  • Data Organization: メモリ上のレイアウトとデータ構造にどのようにデータを保存するかということ
  • Concurrency: 複数のスレッドが単一のデータ構造にアクセスする方法を確立すること

Hash Function

Open Addressing Hashing
  • スロットが単一の巨大なテーブルを作成する。
  • テーブル内の次の空きスロットを線形に探索して衝突を回避する
  • 値が存在するかどうかを確認するにはハッシュを用いてオフセットに移動してキーをスキャンする。
  • 無駄な評価の回数を減らすため、ハッシュキーの衝突を避けることが重要
Cuckoo Hashing
  • 異なるハッシュ関数によるテーブルを複数管理する
  • 要素の追加時に全てのテーブルを確認して空きスロットがある領域を選択する
  • 空きスロットを保持するテーブルが無い場合、いずれかのテーブルから要素を削除して新しい領域を確保する
Chained Hashing
  • ハッシュテーブルの各スロットのバケットに対するリンクリストを保持する
  • 同じハッシュキーを持つ要素を同じバケットに配置することにより衝突を避ける
  • バケットにキーを追加出来ない場合リストに別のバケットを作成し格納するという手段をとり続けるためハッシュテーブルは巨大になっていく
Extendible Hashing
  • Chained Hashing のようにバケットを使用したアプローチを取る。
  • バケットのリンクリストを無制限に増やすのではなく、増分的に分割する。
  • バケットがいっぱいになるとバケットを分割し要素を入れ替える
Linear Hashing

おわりに

今回はそこまで量があるわけではないが検索などを高速化するためのハッシュテーブルの構築に関わる内容となった。
これで不思議に思うが最悪存在しなくてもいいハッシュテーブルを作成する理由とは何なのか。
それは次の章にあるインデックスを構築するためらしい。というわけで次はインデックスの話となる。