B +ツリーCPUの検索時間

Question

クラスタ化されていないクラスタ化されたB +ツリーの最悪の時間をどのように計算するのだろうか？

たとえば、1,000,000レコード（1行= 100バイト）、ディスクページは4000バイト、キーは20バイト、ページのアクセス時間は40msです。これらの変数を使用して、クラスター化されていないクラスター化されたB +ツリーの最悪ケース時間はどのように計算されますか？

が、私はそれはあなたが以下を使用したB +ツリーの高さ/レベルを計算するために知っている（私は思う）：

logF(keys) 

ここで、F = praches分岐の数。

高さを使って最終的な最悪の時間を計算することができますが、その方法はわかりません...私は周りを探索しようとしましたが、平均的な場合や、例はあまり明確ではありませんでした。

ご協力いただきましてありがとうございます。

Answer 1

、ウィッヒ

LOGF（キー）を意味私はページを見つけることにその最悪の場合をLOGF（キー）と言うだろうが、その後、最悪の場合には、すべてのあなたのRIDは、別のページを指しているとunclustured指標になります+ NはNであり、インデックスノード内のridの数である。

そう端では、ツリーWICHの

H =高さが3または4

H + N = 4 +（20分の4000）= 204のI/O

ようになるであろう

メモリに入っていてCPU時間を見たい場合は、

CPU = 204 * 0.04 = 8.16秒です。メモリのページを移動するのに40ミリ秒かかりますが、ディスクの読み込みには意味があると思いますが、計算がうまくいくと思います。