Lock in $30 Savings on PRO—Offer Ends Soon! ⏳

データベース14: B+木 & ハッシュ索引

データベース14: B+木 & ハッシュ索引

1. 関係データの物理的な格納方式
2. 索引
3. B+木
4. ハッシュ索引
5. 索引づけのためのSQL

講義ノートURL
https://dbnote.hontolab.org/content/indexing/01.html

Y. Yamamoto

May 31, 2024
Tweet

More Decks by Y. Yamamoto

Other Decks in Technology

Transcript

  1. 関係データはどこに保存されている?(1/2) 商品ID 商品 単価 登録日 PA001 はーいお茶 130 2018/10/25 PA002

    きのこの里 230 2018/11/17 PB050 タケノコの山 170 2019/12/25 PC008 タケノコの山 200 2019/12/28 … … PZ015 滝子の里山 360 2023/07/07 関係「商品」 データベース DBS
  2. 関係データはどこに保存されている?(2/2) 商品ID 商品 単価 登録日 PA001 はーいお茶 130 2018/10/25 PA002

    きのこの里 230 2018/11/17 PB050 タケノコの山 170 2019/12/25 PC008 タケノコの山 200 2019/12/28 … … PZ015 滝子の里山 360 2023/07/07 関係「商品」 HDDやSSDのような 記憶装置
  3. 関係データの物理的な格納イメージ(1/2) 商品ID PA001 商品名 はーいお茶 単価 130 登録⽇ 2018/10/25 商品ID

    PA002 商品名 きのこの⾥ 単価 230 登録⽇ 2018/11/17 商品ID PZ015 商品名 滝⼦の⾥⼭ 単価 360 登録⽇ 2023/07/07 … 商品ID 商品 単価 登録日 PA001 はーいお茶 130 2018/10/25 PA002 きのこの里 230 2018/11/17 … … PZ015 滝子の里山 360 2023/07/07 関係「商品」 テーブルは レコード単位に 分割され…
  4. 関係データの物理的な格納イメージ(2/2) HDDのような 記憶装置 記憶装置の特定の 場所に格納される 商品ID PA001 商品名 はーいお茶 単価

    130 登録⽇ 2018/10/25 アドレス1 商品ID PA002 商品名 きのこの⾥ 単価 230 登録⽇ 2018/11/17 アドレス2 商品ID PZ015 商品名 滝⼦の⾥⼭ 単価 360 登録⽇ 2023/07/07 アドレス10000 … 問合せ時は、DBが該当レコードの格納位置を調べデータ取得
  5. 該当レコードの探索⽅法 (1/2) 商品ID 商品 単価 登録日 PA001 はーいお茶 130 2018/10/25

    PA002 きのこの里 230 2018/11/17 PB050 タケノコの山 170 2019/12/25 PC008 午前の紅茶 150 2019/12/28 … … PZ015 たきのこの里山 360 2023/07/07 「商品」列の値を上からチェック 概念的には SELECT * FROM 商品 WHERE 商品名 = ‘ブリッツ’;
  6. 該当レコードの探索⽅法 (2/2) HDDのような 記憶装置 商品ID PA001 商品名 はーいお茶 単価 130

    登録⽇ 2018/10/25 アドレス1 商品ID PS715 商品名 ブリッツ 単価 150 登録⽇ 2018/11/17 アドレス50000 商品ID PZ935 商品名 たきのこの⾥⼭ 単価 360 登録⽇ 2023/07/07 アドレス1000000 … … SELECT * FROM 商品 WHERE 商品名 = ‘ブリッツ’; 全部の場所にアクセスしてチェックするのは⼤変 記憶装置の各場所を順にアクセスしてチェック
  7. 本における索引 索引 [ア⾏] ⼀貫性制約 47, 100 異状 220 インスタンス 11,

    22, 33 … [カ⾏] 外部キー 50 外部結合 100 関係 22, 44, 63 … 100ページ 索引で見たいキーワードが載っているページ番号を探せば 全ページを調べる手間は省ける
  8. データベースにおける索引 属性「単価」の索引 単価 130 記憶装置の場所 1 150 3, 10, 54

    170 50 200 8, 6 230 2 … 商品ID PA001 商品名 はーいお茶 単価 130 登録⽇ 2018/10/25 アドレス1 商品ID PA002 商品名 きのこの⾥ 単価 230 登録⽇ 2018/11/17 商品ID PZ 商品名 滝 単価 36 登録⽇ 20 アドレス10 … HDDのような記憶装置 属性値に対応するレコードの場所を記した特殊なデータを 余分に構築しデータ探索を高速化 アドレス2
  9. 索引と探索コスト 商品ID 商品 単価 PA001 はーいお茶 130 PA002 きのこの里 230

    PB050 タケノコの山 170 PC008 午前の紅茶 150 … … PZ015 たきのこの里山 360 単価 130 記憶装置の場所 1 150 3, 10, 54 170 50 200 8, 6 230 2 … 25000 19820925 1億件のレコード 1万件の索引キー 索引づけ 探したい値を ⾒ていく… サイズが⼤きいと索引と⾔えども探すのは⼤変…
  10. 素朴な⾼速化⼿法 - 2分探索(2/3) ソート済み配列から欲しい値を高速に見つける手法 130 150 170 230 270 300

    1 2 3 6 4 5 360 7 索引キー 配列番号 (例: 単価) 欲しい値 = 170 130 150 170 1 2 3 170 3 230より⼩ 150より⼤ 2回の配列アクセスで欲しい値にたどり着く
  11. 素朴な⾼速化⼿法 - 2分探索(3/3) ソート済み配列から欲しい値を高速に見つける手法 130 150 170 230 270 300

    1 2 3 6 4 5 360 7 130 150 170 1 2 3 270 300 6 5 360 7 130 1 170 3 270 5 360 7 230より⼩ 230より⼤ 150より⼩ 150より⼤ 300より⼩ 300より⼤ 最悪でもLog2 N回の配列アクセスで探索完了
  12. B+⽊ 属性値に1をもつ レコードのリスト … B+⽊によって 構築された索引 64 25 100 9

    196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト 更新コストが比較的小さく、探索効率もよい 索引用の木形式のデータ構造
  13. B+⽊ 属性値に1をもつ レコードのリスト … B+⽊によって 構築された索引 64 25 100 9

    196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト 更新コストが比較的小さく、探索効率もよい 索引用の木形式のデータ構造 レコードに対する索引
  14. B+⽊ 属性値に1をもつ レコードのリスト … B+⽊によって 構築された索引 64 25 100 9

    196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト 更新コストが比較的小さく、探索効率もよい 索引用の木形式のデータ構造 索引に対する索引
  15. B+⽊ 属性値に1をもつ レコードのリスト … B+⽊によって 構築された索引 64 25 100 9

    196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト 更新コストが比較的小さく、探索効率もよい 索引用の木形式のデータ構造 索引の索引に対する索引 索引に対する索引を木構造で保持
  16. B+⽊の特徴 – 葉ノード 属性値に1をもつ レコードのリスト … B+⽊による索引 64 25 100

    9 196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト § 葉ノードは隣接した葉ノードと接続 § 最低 e/2 個、最大e個の索引キーで埋める 下のケースは e = 3
  17. B+⽊の特徴 – 中間ノード (1/2) 属性値に1をもつ レコードのリスト … B+⽊による索引 64 25

    100 9 196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト § 最低d個、最大2d個の索引キーで埋める 下のケースは d = 1
  18. B+⽊の特徴 – 中間ノード (2/2) 属性値に1をもつ レコードのリスト … B+⽊による索引 64 25

    100 9 196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト § 索引キーkの左にはk未満のキーを含む子ノードへのポインタを持つ 下のケースは d = 1 § 右にはk以上のキーを含む子ノードへのポインタを持つ 64未満 64以上
  19. B+⽊の特徴 – 根ノード 属性値に1をもつ レコードのリスト … B+⽊による索引 64 25 100

    9 196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト § 中間ノードと同様のルールでポインタを張る § 最低1個、最大2d個の索引キーで埋める 25以上100未満 100以上
  20. B+⽊の最⼤の特徴 属性値に1をもつ レコードのリスト … B+⽊によって 構築された索引 64 25 100 9

    196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に4をもつ レコードのリスト どの葉ノードも根からの距離が同じ B+⽊のBは“balanced”のB
  21. B+⽊を使った完全⼀致検索(例: 81の値をもつレコードを探したい) 属性値に1をもつ レコードのリスト … B+⽊によって 構築された索引 64 25 100

    9 196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に4をもつ レコードのリスト 属性値に81をもつ レコードのリスト ターゲットは64以上 ターゲットは25以上100未満 … 1. 根から葉ノードまでたどる 2. 葉ノード内を右にたどり探索値を探す 3. 値が⾒つかればそれに紐付くレコードを取得
  22. B+⽊を使った範囲検索(例: 16以上40未満の値をもつレコードの検索) 属性値に1をもつ レコードのリスト … B+⽊ 64 25 100 9

    196 1 4 9 16 25 36 49 64 81 100 121 144 169 144 属性値に16をもつ レコードのリスト 属性値に36をもつ レコードのリスト ③ターゲット上限の40まで右にたどる ①ターゲット下限25未満 ②ターゲット下限9以上 属性値に25をもつ レコードのリスト … 1. 下限の値に着⽬して根から葉ノードまでたどる 2. 下限値が⾒つかるまで葉ノード内を右にたどる 3. 上限値が⾒つかるまで葉ノード右にたどりレコードを取得
  23. ハッシュ索引 検索値からレコード格納場所を直接求める索引 学籍番号 cxxxx001 cxxxx002 cxxx5000 ハッシュ関数 1 100 4999

    ハッシュ値 記憶装置 学籍番号cxxx5000 のレコード 場所1 学籍番号cxxxx002 のレコード 場所100 学籍番号cxxxx001 のレコード 場所 4999 ハッシュ関数の計算時間はO(1)で超⾼速 f 計算時間O(1) ハッシュ関数を用いて 範囲検索はできない…
  24. ハッシュ索引の⻑所と短所 長所 § 値の探索時間はO(1) で超⾼速 § 索引のサイズがB+⽊より⼩さい 短所 § 範囲検索ができない

    § 適切なハッシュ関数を選ぶ必要あり § 複数の異なるキーが同じハッシュ値になる「衝突」 が起きると,計算時間が悪化する ハッシュ索引は完全⼀致検索を⾼速に⾏い時に使う
  25. 索引づけのためのSQL CREATE INDEX 索引名 ON テーブル名(索引の対象属性) USING 索引の種類; CREATE INDEX

    product_price_idx ON product (price) USING btree; 構⽂ 例 Productテーブルのprice属性が対象 B+⽊を使う 索引は検索の⾼速化に⾮常に効果的 記憶領域を使うのでむやみに索引を作るのは避ける
  26. 回 実施日 トピック 1 04/15 ガイダンス:データベースを使わない世界 2 04/22 データベースの概念 3

    04/29(祝) 関係データモデル 4 05/13 SQL (1/3) 5 05/20 SQL (2/3) 6 05/27 SQL (3/3) 7 06/03 SQL演習 – レポート課題1 8 06/10 実体関連モデル (1/3) 9 06/17 実体関連モデル (2/3) 10 06/24 実体関連モデル (3/3) 11 07/01 正規化 (1/2) 12 07/08 正規化 (2/2) 13 07/15(祝) データベース設計演習 – レポート課題2 14 07/22 索引付け 15 07/29 NoSQL 16 08/05 期末試験 今後の予定 41