B 트리

[DB/자료구조] B-Tree(B트리), B+ 트리

B-Tree Visualization

B+ Tree Visualization

T = 올림 연산

Degree가 5인 경우, T = 5/2 ⇒ 3

특징

• 삽입 및 삭제 후, 자동적으로 정렬된다.
• 모든 리프 노드들은 같은 Level에 있다.
• 루프 노드와 리프노드를 제외한 모든 노드는 최소 M/2, 최대 M 개의 서브 트리를 가진다.
• 저장 공간에서 비효율적 (파편화)
• 같은 레벨의 노드는 서로 연결되어 있다. (정렬)

장점:

노드 삽입, 삭제에도 동등한 속도

시간복잡도 O(logN)

단점:

트리 균형 유지를 위해 복잡한 계산이 필요함