B-tree는 모든 리프 노드(leaf node, 단말 노드)가 동일한 깊이(depth)를 유지하도록 설계된 트리.
즉, 한쪽으로 치우치는 편향(skewed) 트리가 되는 것을 방지하며, 삽입 및 삭제 작업이 이루어져도 트리의 높이가 일정 수준 이하로 유지된다.
B-tree에서 균형 유지하는 방식
이러한 특징 덕분에 트리의 높이가 낮게 유지되며, 검색, 삽입, 삭제 연산의 최악의 경우에도 O(log N)의 시간 복잡도를 보장한다.
🔍 사용사례: 일부 데이터베이스 인덱스, 파일 시스템, 캐시 등
B+Tree는 B-Tree와 마찬가지로 균형 트리(Balanced Tree)이지만, 몇 가지 차이점이 있다.
B+Tree의 특징
🔍 사용사례: 대부분의 데이터베이스 인덱스 (MySQL InnoDB, PostgreSQL), 파일 시스템 (NTFS, HFS+), 키-값 저장소 (RocksDB, LevelDB)