-
B 트리 작업 성능 분석
이진 검색 트리는 균형이 잘 맞을 경우 높이가 log_2-n 에 근접할 수 있다. 마찬가지로 d진 검색 트리가 균형이 잘 맞으면 높이가 log_d-n에 근접할 수 있다. 또한 B 트리는 루트를 제외한 노드는 최소 └d/2┘개의 자식을 가져야 하므로 B 트리의 깊이는 최악의 경우에도 대략 log_d/2-n 보다 깊을 수 없다.
B 트리의 깊이는 다음의 범위에서 결정된다.
[log_d-n, log_d/2-n]
B 트리의 작업 수행시간은 디스크 접근 횟수를 기준으로 하며 B 트리의 모든 작업의 시간 복잡도는 점근적으로 Ο(logn)이 된다.
※ 노드를 메모리에 올린 이후 작업 시간이 디스크 접근 시간에 비하면 무시할 수 있을 정도로 작기 때문에 디스크 접근 횟수를 기준으로 한다.