B-tree의 깊이를 계산하는 방법은 무엇입니까?

Question

B-Tree에 저장되는 키의 수와 B-Tree의 순서 (즉, 비 루트 노드의 최대 자식 포인터 수)를 알고있는 경우 간단한 대수 방정식을 사용하여 나무의 높이는 얼마나 될까요?

Answer 1

체크 아웃 wikipedia :

하자 m 노드 당 자녀 수있을 완전히 채워의 모든 노드가 높이 h의 B-나무는 N = MH-1 항목이 있습니다.

A B 트리의 최상의 경우 높이입니다

ceil(log_m(n+1)) 

하자 내부 루트가 아닌 노드가 가질 수있는 아이의 최소 수있을 거라고. 일반 B- 트리의 경우, d = ⌈m/2⌉.

A B 트리의 최악의 높이입니다

floor(log_d((n+1)/2) + 1)