CMU Databases Systems 2019 Fall Course 6-8 講義メモ

元動画


6 - Hash Table

概要

与えられたキーから値へのマッピングを保持する連想配列. ハッシュ関数を用いてキーをもとに配列のindexを特定する.

(1) ハッシュ関数 パフォーマンスと衝突レートのトレードオフで選択する. 例:

(2) ハッシュアルゴリズム

key:valueが一対他を認めたい場合どうするか?

リサイズ

上で見たように, hash tableは事前に格納するキーの値を知っていることが必要でそれを超過した場合はリサイズが必要. 必要に応じたリサイズには以下のような方法がある.

ハッシュテーブルはDBのページインデックスとして用いるのには適していない.

7 - Table indexes (1)

概要

テーブルインデックスとはアクセス効率のために保持されるテーブルのサブセットのレプリカ(一部値はソートしたり何らかの変換処理することも). DBMSがテーブルとテーブルインデックスの値の同期を保証する. DBごとに作るインデックスの数はストレージサイズ, インデックス更新コストとのトレードオフになる. クエリごとのインデックス戦略もDBMSの仕事.

B+Tree

平衡木の一つでデータはソートされている状態を保つため検索, 挿入, 削除, シーケンシャルアクセスがO(logN)で実行可能. Binary search treeのノードが2つ以上子ノードを持てる拡張版で, 大きなデータブロックの読み書き用に最適化されている. 以下の性質を満たす M-way search treeとも言える. [Example]

BTreeとの違い

Nodes

すべてのB+ tree上のnodeは key/value ペアの配列で構成されている. keyはindexの構成要素となるattribute, valueはinner nodeでは子ノードへのポインタ, leaf nodeではtupleへのポインタあるいはtupleそのものといった実データに関連する値. 基本的にはペアはkey値でソートされている. [Example]

Leaf nodes

leaf node同士はsiblingへのポインタを保持している [Example]

sort keysはkey map + indirectionで保持されることが多い.[Example]

valuesはtupleそのものあるいはtupleへのポインタ(record ID), DBによって異なる. tupleそのものが格納されている場合 secondary indexsはポインタを格納する必要がある.

Insert

挿入すべきLeft node L1を探す. L1にエントリーをソート順に挿入, スペースが空いていれば終了. 空きがなければL1のキーをL1と新しいノードL2とに分割して格納する. middle keyは再帰的にparentにpushされる.

Delete

エントリーの存在するleft Lを見つけてエントリーを削除する. Lがまだhalf-fullであれば終了. そうでない場合はsiblingからエントリーをもらって再配置する. それができない場合はsiblingをマージする. 実際にはマージはexpensiveなためbackgroundタスクで再構築したりしてマージ処理を遅らせることが多い.

B+Tree in practive

Cluster indexes

テーブルはprimary key順に保持される. MySQLなど一部DBMSはprimary keyがなくてもrow idを自動的に設定してprimary keyとして用いる.

Optimization

8 - Table indexes (2)

重複キーの対処

その他のコンセプト

Implicit indexes

多くのDBMSは明示的に指定されなくとも自動的にインデックスを作成する.

Partial indexes

テーブルデータのサブセットに対してインデックスを作成する. DATEの範囲でインデックスを張るのが一例. [Postgresの例]

Covering indexes

クエリで必要な列が全てインデックスでカバーされている場合, DBMSはタプルの実データを取り出す必要がない.

Index include columns

上記のようなindex-only queryを実現するためインデックスに追加でカラムを格納する. 追加のカラムはleaf nodeにのみ追加されインデックスの検索キーとして使われることはない. PostgresはCREATE INDEX INCLUDE句で対応.

Functional / Expression indexes

キーがテーブルに格納されているものとは別の表現で格納されているインデックス.

CREATE INDEX idx ON users (EXTRACT(dow FROM login));

どのインデックスを用いるかはDBMSのクエリプランによる.

Trie index

B+Treeのinnder nodesはキーが存在するかどうかを判定できないので, 検索時はつねにleaf nodeまでたどる必要がある. そのため存在しないキーに対してはB+Treeの各レベルごとに最低でも1度はbuffer poolのページミスが起こることになる. この問題を回避するためにTreeの各レベルにprefixを配置していくTrie構造を取る.

Trieの形状はキーの文字列スペース, 長さに依存しB+Treeのように挿入順や既に存在するキーの影響を受けない. かつリバランスも必要ない. 全てのオペレーションはキーの長さkに比例する = O(k). キーは検索pathから復元できる.

Radix tree (a.k.a Patricia Tree)

Trieから, 子が一人しかいないノードを省略したもの. False positiveがありうるのでDBMSが実tupleが存在するかチェックをする.

Inverted index

ここまで紹介したインデックスは全て"point"または"range"クエリに有効であるがキーワード検索には向いていない. そのためにキーワードからレコードへのマッピングを保持したものをinverted indexと呼び, 多くのDBMSでサポートされている.

これらのインデックスが

に応じたデザインで使われている. B+Treeが木構造インデックスにおいてはデファクトスタンダード.