データベース探索方法

参考

「webエンジニアのためのデータベース技術実践入門」　（松信嘉範）

検索手法

• 線形探索
  　　　O(N)の計算量
  　　　初めから終わりまで順番に検索してデータを探す手法
  　　　検索にかかる時間は文書のサイズに依存する

• インデックス探索
  　　　O(１)の計算量
  　　　キーとペアで索引を作る
  　　　しかし、索引の桁数が違うため固定長フォーマットにできない
  　　　　→値をハッシュ関数にかけてハッシュ値で保存しておく
  　　　ハッシュ値が同じになる可能性があるので検知する仕組みは必要になる

ids	bite
1	1バイト目
2	5バイト目
3	8バイト目

• B+Treeインデックス
  　　　O(log mN)の計算量
  　　　ワーストケースでのアクセス回数が減らせる
  　　　RDBMSにおける事実上の標準
  root

ids	branch
<20000	ブランチ１
<40000	ブランチ2
<60000	ブランチ3

ブランチ１

ids	leaf
<5000	リーフ１
<10000	リーフ2
<15000	リーフ3
<20000	リーフ4

更新コストのための最適化

• 一時的にメモリに保存しておき一気に更新する（MYSQL）
  　　　問題点：インデックス更新ではデータ更新のコストは増える
  　　　ランダムライトよりはるかに効率がいい
• 並列更新性能を高める
  　　　問題点：整合性を取るためにインデックスの組み替え処理が終わるまで一切の更新を許さない
  　　　パーティション表を作る
  　　　ロックフリーなアルゴリズムが提案されている