ablog

不器用で落着きのない技術者のメモ

T-Treeインデックス

B+TreeはディスクI/Oを軽減するためのデータ構造で、T-Treeはメモリ領域とCPUサイクルの利用を低減するためのデータ構造。B+Treeはノード(ブロック)へのアクセス回数を少なくしてディスクI/Oを軽減するが、T-Treeはノードへ(全てメモリ上にある)のアクセス回数は気にせず、比較回数を少なくしている。圧倒的に遅いディスクI/Oがなくなると、如何に少ないCPUサイクルで処理するかということになるB+Treeの場合、ノードにぶら下がっている子が多いので比較回数が多くなるが、T-Treeの場合はノードに子が2つしかなく比較回数が少なくなる。

B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ b の記憶装置があるとき、b の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い(2分探索木はブロック型でない記憶装置に適している)。

Oracle の B*Tree インデックスの内部構造についてお勉強中(その1) - drk7jp