インデックスの階層数によるパフォーマンスの差

質問

Bツリーのインデックスで、階層数が増えるとパフォーマンスが悪化するとありますが、なぜでしょうか。
データ量が膨大な場合は、むしろパフォーマンスが上がるような気がしてならないのですが・・・
例えば階層が3から4に増えた場合、検索時に単にIOが1回増えるだけのように思えますが、その1回のコストを問題にしているということなのでしょうか？

基本的な質問ですみませんが、よろしくお願いします。
（削除リーフ数はゼロという前提で）

回答No.2

entree

No.1の方も回答されている通り、「その1回のコストを問題」にしています。

とは言え、最近はB-TreeはRebuildしない方がよいとも言われています。

第一に、Range Scanの場合、一般的に、索引で検索するときのコストよりも、索引で検索した後テーブルをScanしなければなりませんが、そのコストの方がはるかに大きいです。Unique Scanの場合は、ループで繰り返し実行しない限り、「1回のコスト」の影響はほとんどありません。例えループで繰り返し実行する場合でも、3が4なら1.33倍遅くなるくらいです。結局、索引断片化の影響が大きく出るのは、Index Fast Full Scan くらいです。

第二に、一般的に索引は無限に断片化し続けるのではなく、ある程度断片化すると平衡状態になります。Rebuild してもどうせまた断片化して変更状態になるわけだし、Rebuild にかかる CPU や I/O のコストや Redo 増大の影響の方が大きくなるかもしれません。

お礼

お礼が遅くなりすみません。
実践的なご回答ありがとうございました。
なるほど、最終的にはどのようなSQLが多いかとか、運用スケジュールに拠る感じですね。
自動で締め切られてたのでベストアンサー指定できませんでしたが、回答いただいたお二方には感謝です。

回答No.1

muyoshid

こんにちわ。

> 例えば階層が3から4に増えた場合、検索時に単にIOが1回増えるだけのように
> 思えますが、その1回のコストを問題にしているということなのでしょうか？
そう言う事です。
階層が3から4に増えると、目的にデータに辿り着くまでに
索引(3回) + テーブル(1回) = 4回で済んでいたものが
5回のI/O が必要になるのでI/O が25% 増える事になります。
1SQL 当りではそれ程大きな差にならなくても、数万回とか実行
されると大きな違いになってきます。

お礼

さっそく回答いただいていたのにお礼が遅くなりすみません。
なるほど、必ず1回増加というのは全体として問題ですね。
ありがとうございました。