B 트리(B tree)

m차 검색 트리

B 트리(B tree)

m차 검색 트리(m-way search tree)

차수가 [eqn: m]인 검색 트리는 각 노드가 최대 [eqn: m]개의 부트리를 가질 수 있도록 이진 검색 트리를 확장한 것이다. 각 노드는 분지수보다 하나 작은 개수의 값을 정렬된 상태로 가지고 있다. 아래에 [eqn: 3]-way 검색 트리의 예가 있다.

이진 검색 트리에서의 검색, 삽입 및 삭제 연산을 확장하여 [eqn: m]차 검색 트리에 적용할 수 있다.

m차 B 트리(m-way B tree)

[eqn: m]차 B 트리는 다음과 같은 성질을 갖는 [eqn: m]차 검색 트리이다.

a. 루트는 최소한 [eqn: 2]개의 자식 노드를 갖는다.

b. 루트를 제외한 다른 모든 노드는 [eqn: lfloor m/2 rfloor]개 이상의 자식 노드를 갖는다.

c. 모든 리프 노드의 레벨은 같다.

B 트리에서 검색은 각 노드내에서는 [eqn: O(log m)] 시간에 어느 부트리로 내려갈 것인지를 결정할 수 있고, B 트리의 높이는 [eqn: O(log_m n)]이므로 [eqn: O(log m log_m n)] = [eqn: O(log n)] 시간에 실행할 수 있다. 삽입과 삭제는 [eqn: O(m log_m n)] = [eqn: O((m / log m ) log n)] 시간에 수행할 수 있다. 삽입 및 삭제 알고리즘은 여기서 생략하기로 한다.

검색 시간은 [eqn: m] 값에 무관하지만, 삽입과 삭제 연산은 [eqn: m]값이 커질수록 시간이 많이 걸리게 된다. 주기억장치 내에서는 B 트리의 차수가 작은 경우가 유리하다고 할 수 있다.

실제적으로 B 트리는 하드디스크에 저장되어 있는 데이터베이스 시스템에서 많이 쓰인다. 차수 [eqn: m]인 B 트리가 사용될 경우 디스크 접근 회수는 [eqn: O(log_m n)]에 비례하게 된다. 각 디스크 접근은 부트리로의 방향을 결정하기 위하여 [eqn: O(log m)]의 부가적인 연산을 하지만 사실 이 시간은 디스크의 블록을 읽어오는 시간에 비해 매우 작으므로 [eqn: m]값이 매우 크지 않은 이상 무시할 수 있다. 따라서 일반적으로 [eqn: m]값은 각 노드가 디스크의 한 블록정도의 크기로 정하는데 대략 [eqn: 32 le m le 256] 정도의 값을 갖도록 한다.