B + Tree CPU 검색 시간

Question

클러스터되지 않은 클러스터 된 B + 트리의 최악의 시간을 어떻게 계산할 수 있을지 궁금한가요?

예를 들어, 1,000,000 레코드 (1 행 = 100 바이트), 디스크 페이지가 4000 바이트, 키가 20 바이트, 페이지 액세스 시간이 40ms라고 가정 해보십시오. 이러한 변수를 사용하여 클러스터되지 않은 클러스터 된 B + 트리의 최악의 경우 시간을 계산하는 방법은 무엇입니까?

내가 그 다음을 사용 A B의 + 트리의 높이/레벨을 계산하는 알고 (내가 생각하는) :

logF(keys) 

경우 F = praches 가지의 번호입니다.

높이를 사용하면 최종 최악의 경우 시간을 계산할 수 있지만 그 방법은 모르겠다 ... 나는 주변을 검색해 보았지만 괜찮은 경우는 평균적인 경우이거나 매우 명확하지 않은 사례들.

도움을 주시면 감사하겠습니다.

Answer 1

, 느릅 나무

logF (키)을 의미하는 나는 페이지를 찾는 그 최악의 경우를 logF (키) 말을하지만, 그 이후 최악의 경우는 모든 RID를 다른 페이지를 가리키는과 unclustured 인덱스 것 + N은 인덱스 노드의 껍질 수입니다.

그래서 결국 그것이있을 것이다

H = 트리 느릅 나무의 높이가 3 또는 4

H + N 같을 것이다 = 4 + (20분의 4,000) = (204) I/O를

메모리에 있고 CPU 시간을보고 싶다고 가정하면

CPU = 204 * 0.04 = 8.16 초가됩니다. 메모리에서 한 페이지를 이동하는 데 40 밀리미터 정도의 시간이 필요하다고 생각합니다. (디스크 읽기는 의미가 있습니다.)하지만 계산이 훌륭하다고 생각합니다.