9. なぜ 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
![Cache-Oblivious データ構造入門 @DSIRNLP#5](https://cdn-ak-scissors.b.st-hatena.com/image/square/22bd43f57a3dfca0ceb88ff8d44ab2e0975725ca/height=288;version=1;width=512/https%3A%2F%2Fcdn.slidesharecdn.com%2Fss_thumbnails%2Fcache-oblivious-140111065928-phpapp01-thumbnail.jpg%3Fwidth%3D640%26height%3D640%26fit%3Dbounds)