btree

btree自体はtree構造の一つ。

で、なんでこいつとこいつの派生(だいたいB+)がインデックスに利用されているのかについて

文章化する。

ハードディスクに適したデータ構造

ハードディスクはシークと呼ばれる針で円を読み取るみたいなのはよく説明ででてきている。

要は欲しいデータの場所にまで移動するまでにめちゃくちゃ時間がかかる。

それもランダムな読み取りとなるとひどいことになる。

だから欲しいデータはある程度まとまっていて欲しい、シーケンシャルであってほしい。

btreeの節のキーサイズをブロックサイズで調整すると、一回のブロック読み取りですむことになる。

これに関してはSSDでもブロック単位の読み取りでまとまることにより多少は速度的には早くなるはず。

SSD

こちらは特にシーケンシャルでなくとも、ランダムアクセスでもそれなりの速さをだしてくるが、

ランダム、不均一な書き込みに関してはかなり速度が落ちる。

これはガーベジコレクション機能が影響している。

わからんかったこと

  • マージのときの動き、再編成

参考

B木 - naoyaのはてなダイアリー

知らないと怖い、フラッシュストレージに対する誤解と落とし穴 (3/3):EnterpriseZine(エンタープライズジン)