B-treeを理解していく

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

B-treeの前に

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

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

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

可視化してみる

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

B-Tree Visualization

実装で見てみる

ちょうど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)))

GitHub - google/btree: BTree provides a simple, ordered, in-memory data structure for Go programs.

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

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

なぜBTreeがIndexに使われているのか - maru source

ブロックアクセス

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

ブロックアクセスとファイルアクセス

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