1️⃣ INDEX

B-Tree

B-tree는 모든 리프 노드(leaf node, 단말 노드)가 동일한 깊이(depth)를 유지하도록 설계된 트리.

즉, 한쪽으로 치우치는 편향(skewed) 트리가 되는 것을 방지하며, 삽입 및 삭제 작업이 이루어져도 트리의 높이가 일정 수준 이하로 유지된다.

B-tree에서 균형 유지하는 방식

• 하나의 노드에 여러 개의 키(key)와 자식 노드를 가질 수 있음 (즉, 다진 트리)
• 특정 조건을 만족하면 노드 분할(Split) 또는 노드 병합(Merge) 수행
• 항상 모든 리프 노드가 같은 레벨에 위치하도록 자동으로 구조 조정

이러한 특징 덕분에 트리의 높이가 낮게 유지되며, 검색, 삽입, 삭제 연산의 최악의 경우에도 O(log N)의 시간 복잡도를 보장한다.

🔍 사용사례: 일부 데이터베이스 인덱스, 파일 시스템, 캐시 등

B+Tree

B+Tree는 B-Tree와 마찬가지로 균형 트리(Balanced Tree)이지만, 몇 가지 차이점이 있다.

B+Tree의 특징

• 내부 노드(Internal Node): B-tree와 달리 키만 저장, 데이터를 저장하지 않음 → 트리의 높이가 더 낮아짐
• 리프 노드(Leaf Node): 모든 데이터를 저장하고 연결 리스트(Linked List) 형태로 구성 → 빠른 범위 검색 가능
• 트리의 균형 유지: 삽입, 삭제 시 자동으로 재구성하여 높이 균형(Balanced)을 유지

🔍 사용사례: 대부분의 데이터베이스 인덱스 (MySQL InnoDB, PostgreSQL), 파일 시스템 (NTFS, HFS+), 키-값 저장소 (RocksDB, LevelDB)