B 트리(B-tree) - 알고리즘

B 트리 (B-tree)

B트리의 정의

 

★ 각 노드의 최대 키의 수는 m - 1

     최소 키의 수 → (m/2) - 1

     각 노드에 포함된 키 순서가 항상 정렬 상태

     좌측 서브트리 < 부모 < 우측 서브트리

     삽입은 항상 단말 노드에서 발생

     삽입되는 키로 인해 최대 키수가 초과되면 노드가 분할되며 중간키가 부모 노드로 이동

     트리 구축은 밑에서 위로 진행

 

트리의 형태

→ m-ary 트리 (m개 이하 아들. 각 node의 data수는 m-1)

root → 최소 2개의 아들

leaf → 모든 leaf의 레벨은 동일

       → 모든 leaf 노드는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.

→ 한노드 안에 있는 키 값은 오름차순을 유지한다.

→ 탐색, 추가, 삭제는 루트로부터 시작한다.

 

node상의 데이터

각 node상의 데이터는 정렬 상태

binary search tree의 성질과 동일 (좌우측간 데이터 대소 관계)

 

B트리의 장단점

 

장점

→ 노드의 삽입과 삭제 후에도 균형트리 유지

→ 균등한 응답속도 보장

→ Time complexity : O(log n)

 

단점

→ 순차탐색 지원하지 않음 (매번 root에서부터 검색 시작)

→ 노드의 낮은 공간 활용성