本 : 詳説データベース

[kawasin73]

https://www.amazon.co.jp/dp/4873119545

[kawasin73]

第１部 ストレージエンジン

• データベース管理システム DBMS

  • モジュールシステムで複数の部分から構成される。
    • リクエストを扱う転送レイヤー
    • クエリプロセッサ
    • 実行エンジン
    • ストレージエンジン データベースの比較 目標を明確に定義する。想定した状況をシミュレートして動かして比較するのも大切。

      1章 基本事項の紹介と概要

• OLTP データベース : Online transaction processing

  • 短時間で大量のクエリをさばいて返す。

• OLAP データベース : Online analytical processing

  • 複雑な集計処理

• HTAP : Hybrid transaction analytical processing

  1.1 : DBMS アーキテクチャ

• クライアント・サーバーモデル

  • ノードがサーバーで、アプリケーションがクライアント

• 転送サブシステム

  • クラスタ通信
  • クライアント通信

• クエリプロセッサ

  • クエリパーサ
  • クエリオプティマイザ

• 実行エンジン

  • リモート実行・ローカル実行

• ストレージエンジン

  • トランザクションマネージャ
  • ロックマネージャ
  • アクセスメソッド
  • バッファマネージャ
  • リカバリマネージャ

    1.2 : メモリベースの DBMS とディスクベースの DBMS

    1.2.1 : メモリベースのストアの永続性

    write ahead log とバックアップデータ。

    1.3 : 列指向 DBMS と行指向 DBMS

    1.3.1 : 行指向のデータレイアウト

    空間的局所性の向上

    1.3.2 : 列指向のデータレイアウト

    列ごとにファイルやファイルセグメントをわける。 １つの種類の値を集計するときに余分な読み込みを防げる。集計処理に向いている。 各値は、キーと一緒に保存

    1.3.3 : 相違点と最適化

    1.3.4 : ワイドカラムストア

    データが多次元のマップとして表される

    1.4 : データファイルとインデックスファイル

• ストレージの効率性

• アクセスの効率性

• 更新の効率性

  • ディスクの更新を減らす

    1.4.1 : データファイル

• インデックス構成表 : IOT

  • インデックス自体にデータが保存される
  • ディスクのシークを1回は減らすことができる

• ヒープ構成表

  • どんどん書き込んでいく

• ハッシュ構成表

  • バケットがある。キーのハッシュ値によってバケットが決まる
  • バケット内は書き込み順だったり、ソートされてたり

    1.4.2 : インデックスファイル

    プライマリインデックスとセカンダリインデックス クラスタ化 : キーの順序に並んでいるか プライマリインデックスはクラスタ化 セカンダリインデックスは非クラスタ化

    1.4.3 間接参照としてのプライマリインデックス

    ファイルオフセットで直接指定するか、プライマリキーインデックスで指定するか

    1.5 : バッファリングとイミュータビリティおよびオーダリング

    この3つが対立軸となる

不変性は、追記のみまたはコピーオンライトで達成できる

1.6 : まとめ

[kawasin73]

2章 B ツリーの基本

2.1 : 二分探索木

BST

2.1.1 : ツリーのバランシング

ひとつの操作が終わるたびに回転してバランシングを行う。

2.1.2 : ディスクベースのストレージ用のツリー

• ファンアウト (ノードごとに許容される子の個数) が小さいので頻繁にバランシングの操作を行う。そのためディスクベースには不向き

以下が必要

• 大きなファンアウトで隣接するキーとの局所性を改善
• ツリーの高さを低く保ち、ノードを辿るときのシークを減らす

  2.2 : ディスクベースの構造

  データセットが大きすぎてメモリ上に全てを保持するのが難しいときにディスク上のデータ構造が利用される。 その一部がメモリ上にキャッシュされる形になる。

  2.2.1 : ハードディスクドライブ

  回転式のディスク

  2.2.2 : ソリッドステートドライブ

  SSD

• メモリセル
• ストリング (32 ~ 64 個のセル)
• アレイ
• ページ (2KB ~ 16KB)
• ブロック (64 ~ 512 個のページ)
• プレーン
• ダイ

読み取りの最小単位はページ。 変更を加えられるのは削除された後のメモリセル。 最小の削除単位はブロック。 空白のブロックに含まれる複数のページにはシーケンシャルに書き込みが行われる フラッシュメモリコントローラは

• 空白のページ
• 書き込み済みのページ
• 破棄済みのページ を追跡する機能を持ち、FTL (フラッシュトランスレーションレイヤ)と呼ばれる。 ブロックを削除する前に有効なページを別の場所に移し、ページ ID をマッピングし直す ブロックデバイス抽象化のために、IO はバッファリングされ、ブロック全体が読み込まれる。 ガーベージコレクションのために、ランダムで不均一な書き込みは書き込みパフォーマンスが悪くなる データで完全に埋まったブロックを書き込み、それに続く書き込みは追記のみになると必要な IO の数が減る

  2.2.3 : ディスク上の構造

  ディスク操作の最小単位がブロックであることを考慮 ディスク上のポインタ計算が簡単になることが推奨されている

  2.3 : ユビキタス B ツリー

  B ツリーのノード内のキーはソートされている。

  2.3.1 : B ツリーの階層

• ルートノード
• リーフノード
• 中間ノード Bツリーではページとノードはほぼ同じ。 ここでは B+ ツリーのことと B ツリーと呼んでいる。

  2.3.2 : セパレータキー

  ノードには予備領域があるのでストレージ使用率は 100% ではない。パフォーマンスに影響はない

  2.3.3 : B ツリーの検索の計算量

• ブロック転送の回数
  • log スケール。グラフの高さ
  • 底は N (ノードごとの子の数)
• 比較の回数
  • それぞれのノード内は二分探索
  • log スケールで底は 2

    2.3.4 : B ツリーの検索アルゴリズム

    検索では対象のキーまたは直前のキーを検出する。 ノード内では二分探索

    2.3.5 : キーのカウント

    2.3.6 : B ツリーノードの分割

    ノードのオーバーフローでスプリットする。 半分を新しいノードにコピーして、境界のキーを親に追加する。（キーの昇格） ルートも同じ。分割されて新しい親にキーが追加される。 中間とリーフの分割では水平に増える。 ルートの分割では高さが増える。

    2.3.7 : B ツリーノードのマージ

    ノードの値の数が閾値を下回る（アンダーフロー）

• 2つのノードを合わせて1つのノードに収まる場合
  • マージして1つにする
• 1つのノードに収まらない場合
  • リバランシング 一般的には右側の要素を左側の兄弟ノードに移動する

    2.4 : まとめ