今更B-Treeに関して勉強
きっかけ
おーいつのまにかsqlite4なるものが。
だが記事を読んでいていつもalgorithm周りはすっ飛ばしてるなーということに気づいてたまには調べることにする。
個人としてはalgorithmの勉強とか単独でやるのは面倒くさい、とprogrammerにあるまじきことを思っているので、使う段にならないと結局調べても身につかないだろうけど。
勉強の始まり
おあつらえ向きのtextが。
indexが何かくらいはさすがに知ってる。indexをB-Treeで実装しているというのもわかる。んでB-Treeってどういう話かと。
B-tree構造に基づくインデックスは、ルートノードと子ノード (ブランチノード)、そしてリーフノードで構成されています。
ルートノードと子ノードの各ページは、キー値と子ノードへのポインタを持つ リーフノードの各ページは、キー値とデータへのポインタを持つ (B+ treeの場合、データを持つのはリーフノードだけ)
さてそろそろ用語がわからなくなってきたぞ。いや技術系のtextってどうしても最初に一番いろんな用語が出るんだけど。
ええっと、自分なりに書き下して、nodeは以下の三種類。
- root node
- child node
- leaf node
そのうちleaf node = key, value(pointer)を持つというのはまあわかりやすい。keyが何に働くのかまだわからないけど。
root nodeとchild nodeはkeyとchild nodeへのpointer。 まあつまりroot nodeから下はchild nodeの構造で出来ている、と。で、どこにleaf nodeが出てくるのか。 んー。ぱらぱらと読むけど果てにはあるっぽい。
こう読んでいると混乱してきたのでまずわかってる範囲だけで言うと、rootを起点としてchild nodeが連なっていく普通の木構造で、終点にはleaf nodeがそれぞれぶら下がっているという感じ。 childとしてつながっているのがさらなる探索用のnodeへのpointerなのか、valueにつながるpointerなのか、の差。
rootを起点として、nodeがたくさんあって、探索用nodeへのpointerか、valueへのpointerがpageとしてnodeに紐付けられている。
最終的にやりたいのはvalueにたどり着くことなので……うんだめだまだ組み立てられない。ちゃんと読もう。
検索
検索する際、ルートノードから出発し、子ノードへのポインタに沿ってリーフノードを探します。
まずルートノードへ行き、検索値よりも大きな値のポインタが見つかったら、その左側の子ノードへ移動する。検索値よりも大きな値が見つからない時は、キーの最大値の右側の子ノードへ移動する 子ノードでも同様のことを繰り返し、最終的に、目的の値が存在しないと判断するか、リーフページにたどり着く
もう検索値よりも大きな値のpointerが見つかったら、というのがふわっとしていてよくわからない。pointerの位置で比較してるの？ いやそんなわきゃあるまい。skbでheadずらしてるのとは違うんだぞ。
検索以前にもう少し構造がよくわからないとなんともならない気がしてきた。
インデックスの生成
テーブルに既にデータが入っている状態でインデックスが生成される時、内部でどのようなツリー構造が生成されるのかを見ていきます。
はじめに、テーブルにアクセスし、CREATE TABLE文のインデックスに指定された列の順序に従って、値をソートする ソートされた結果をリーフノードに記録していく もしリーフノードがPCTFREE (Percent free: 空き領域率) に到達し、新しいリーフノードを要求したら、子ノードを生成する。その際、新しく割り当てられたリーフノードの開始値とそのノードのアドレス情報で構成された行を、子ノードに挿入する。この子ノードは最上位レベルであるため、ルートノードとなる 子ノードに行が積み上げられ、子ノードがPCTFREEに到達したら、新しい子ノードを割り当てる 新しく生成された子ノードの情報を保存するために、上位レベルの子ノードが生成される。この子ノードは最上位レベルであるためルートノードとなる。2〜5が繰り返される
うん？ これだとroot nodeが複数できる？ rootなのに？ また謎になってきた。
まずDBとB-Treeの紐付けから
idカラムにIndexを張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時)
あー。DBでいうindexがそのままここでいうindexのことをさして説明していたのか。でindexの探索にあたってどういう探索algorithmを採用するかと言えば、という話でB-Treeが出てきたわけで（そこまで巻き戻すのかよ……）。
うん、なんか疑問が氷解した。結局DBのindexとして付与された値のsortか。
あらためてB-Treeについて
ここまで来るとDBとかどうでもいいから探索手法としてのB-Treeを理解できればいい。きっかけをぶん投げている気がするけどまあ気にしない。
でもさっきのpageのBTreeの項目で大体わかった。
その上で、DBの場合一番単純な流れで考えればindexが1, 2, 3, …と増えていくわけだから、
インデックスの生成
テーブルに既にデータが入っている状態でインデックスが生成される時、内部でどのようなツリー構造が生成されるのかを見ていきます。
はじめに、テーブルにアクセスし、CREATE TABLE文のインデックスに指定された列の順序に従って、値をソートする ソートされた結果をリーフノードに記録していく もしリーフノードがPCTFREE (Percent free: 空き領域率) に到達し、新しいリーフノードを要求したら、子ノードを生成する。その際、新しく割り当てられたリーフノードの開始値とそのノードのアドレス情報で構成された行を、子ノードに挿入する。この子ノードは最上位レベルであるため、ルートノードとなる 子ノードに行が積み上げられ、子ノードがPCTFREEに到達したら、新しい子ノードを割り当てる 新しく生成された子ノードの情報を保存するために、上位レベルの子ノードが生成される。この子ノードは最上位レベルであるためルートノードとなる。2〜5が繰り返される
こうなると。新しいroot nodeが作られるのもtreeの規模が一定より大きくならないようにするためだろうし。
まあ大体わかった。どちらかというとあとは1からB-Treeが作られていく工程をどこかで見られたらもやもやもすっきりしそうなんだけど、ないかなあ。
B Treeが作られていく工程
あった。 ここのB木の成長を見ればわかった。
今日はこれで終わり
