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

※この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル CREATE TABLE user ( id INT UNSIGNED NOT NULL, name VARCHAR(255) NOT NULL, UNIQUE INDEX (id) ); idカラムにIndexを張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしています

[mrkn]

つまりオンメモリDBだったりデータが SSD 上にある場合は BTree じゃなくても良い。／←これは間違いで、SSDはブロックサイズが大きいからBTreeの重要性がより高くなっているそうです。

[fumiya23808]

面白いです

[msykt]

“ブロックの読み取り回数は木の深さ(探索回数t)になります。 BTreeの場合log N / log m、二分探索木の場合log Nになります。これはmが大きくなればなるほど、差が出てきます。”

[d_animal141]

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

[super_wakame]

b-tree

[kuenishi]

別にSSDでもRAMでも同じだし単にアラインメントが違ってたりレイテンシが小さすぎて見えないってだけだと思うけど測ってない＞ハードディスクからデータを読み取る場合、あるサイズ単位の塊でデータを読み取ります

[efcl]

二分探索、二分探索木、BTreeについて。 計算量の考え方やBTreeはHDDとの相性が良いとされるため使われてる話等分かりやすい

[chezou]

わかりやすい

[a_bicky]

二分探索や計算量の説明から入ってて図もあってわかりやすい