Cache-Oblivious データ構造入門 @DSIRNLP#59. なぜ B-Tree の方が良いか？ 大事な前提（若干雑） 1. ディスクの読み込み時間 >> 計算時間 2. ディスクである箇所を読み込むと周辺も含 めてそこそこ大きく読まれる 前提より • ディスクを読み込む回数だけを考える – 普段の議論：「O(ほげ) 時間」 – 今回の議論：「ディスクI/O 𝑂(ほげ) 回」 • 一度に読み込まれるサイズを 𝐵 とおく Cache-Oblivious データ構造入門 (@iwiwi) 10 10. データの探索にかかる I/O 回数 二分探索木 • 𝑂 log 𝑛 回 一回の I/O で 2 分岐 B-Tree • 𝑂 log 𝐵 𝑛 回 一回の I/O で Θ(𝐵) 分岐！ ↑ノードのサイズをブロックサイズ 𝐵に合わせる B-Tree のほうが log 𝐵 倍ぐらい早い これは平気で 10 倍とかになるので大違い！ Cac
