wqwq

インデックス周りを掘る機会があったので、いろいろほっていきたいと思います。

B-treeの前に

まずどんなアルゴリズムが良いかと言うと、バランスが取れている木構造の高さ、つまりlog2Nの計算量になるアルゴリズムが欲しいというモチベーションが存在すると理解しています。これを実現するために色々アルゴリズムが存在します。

よくB-treeの説明の際に目にするのは、二分探索木です。小さい数字を左下へ、大きい数値を右下へ分岐させていく木構造になります。ただし、木構造が偏っていた場合に、O(n)の計算量になってしまうという欠点があります。他にもAVL木とかB+ treeというアルゴリズムも存在しますが、今回は割愛できればと思います。

資料だとこのスライドが非常にわかりやすかったので、非常におすすめです。

可視化してみる

先ほど書いたB-treeの特徴を理解するために、B-tree Visualizationというサービスを使ってみます。このサービスを使うと、B-treeのノードの分岐をUI上で確認することができます。0から9まで順番にインサートしていった結果が下記図になります。

実装で見てみる

ちょうどgo のパッケージでB-treeで実装されているものもあったので、一応記載しておきます。

 tr := btree.New(10)
for i := btree.Int(0); i < 10; i++ {
tr.ReplaceOrInsert(i)
}
fmt.Println("len: ", tr.Len())
fmt.Println("get3: ", tr.Get(btree.Int(3)))
fmt.Println("get100: ", tr.Get(btree.Int(100)))

なぜB-treeがDatabaseで使用されるのか

理由は、ブロックの読み取り回数は木構造の高さになるからです。
詳細は、下記記事が非常にわかりやすく解説されているので、一読をおすすめします。

ブロックアクセス

ストレージは、ハードディスクの物理的構造を隠蔽し、ブロックやファイルの論理単位でアクセスしていきます。ブロックは、ディスク→論理ボリュームに分割→論理ボリューム→ブロックに分割してようやくブロックという単位になります。
このブロックの読み取り回数が多いと、ハードディスクへのアクセス回数も増えてしまい、その分処理が遅くなってしまうという理解でいます。

B-treeのMITの講義もありました。
この動画でも、B-treeだと毎回ディスクにアクセスしなくなるし、ブロックを効率的に使用することができると説明されています。(たぶん)

--

--

インデックス周りを掘る機会があったので、その学びのアウトプットをしていければと思います。

PostgreSQLは、対象テーブルに対する同時挿入、更新、削除を防止するようなロックを獲得せずにインデックスを作成します

B-treeのインデックスだと、Shareでロックをかけてインデックスを貼っていきます。CONCURRENTLYをつけるとそのロックを取らずにインデックスをはることが可能になります。

SQLでの書き方

作り方は「CONCURRENTLY」を付けるだけです。

CREATE INDEX CONCURRENTLY sales_quantity_index ON sales_table (quantity);

sql-migrateでの書き方

「notransaction」を付ける必要があります。
文字通りトランザクションはらなくなるので、ご注意を。

-- +migrate Up notransaction
CREATE INDEX CONCURRENTLY sample_idx ON samples using btree (updated_at);
-- +migrate Down
DROP INDEX sample_idx;

--

--

OAuth2.0の目的

OAuth2.0の目的は、IDとパスワードを渡すことなく、APIにアクセスできるようになることになります。

背景として、アプリ開発においてユーザーの認証情報を共有せず、ユーザーの代わりにAPI(リソース)にアクセスすることを許可することが求められたことがあります。

OAuth2.0の仕様

大まかな処理の流れ

  1. クライアントは必要なパラメータを使用し、認可エンドポイントに認可リクエストを送信する
  2. クライアントは、認可画面において承認・非承認を行う
  3. 認可サーバーは、あらかじめ受け取ったリダイレクトURI先にリダイレクトさせる。そのときに認可コードが含まれている
  4. クライアントは、認可コードを用いてトークン発行のリクエストを送信する
  5. 認可サーバーは、アクセストークンを発行する

http://openid-foundation-japan.github.io/rfc6749.ja.html#code-authz-req より引用

実装するときに気をつけること

  • 基本的に認可エンドポイント、トークンを発行するエンドポイントの2つを実装する
  • 認可画面を作る(このときユーザーは承認か否認を行うことができる)
  • 認可レスポンスには、302を使用しリダイレクトさせる

--

--