이번 글에서는 데이터 구조 중 하나인 B-트리(B-Tree)에 대해 자세히 알아보겠습니다. B-트리는 특수한 형태의 m-way 탐색 트리(m-way search tree)로, 주로 디스크 접근(disk access)에 최적화되어 있어 데이터베이스와 파일 시스템에서 널리 활용됩니다.
B-트리란 무엇인가?
B-트리는 차수(order)가 m인 경우, 한 노드가 최대 m-1개의 키(key)와 m개의 자식 노드를 가질 수 있습니다. 하나의 노드에 많은 수의 요소를 저장할 수 있기 때문에 트리 전체의 높이가 상대적으로 낮아지며, 이것이 B-트리의 가장 큰 장점입니다.
트리의 높이가 낮다는 것은 데이터를 찾기 위해 거쳐야 하는 노드의 수가 줄어든다는 의미이고, 디스크 접근 횟수가 감소한다는 뜻입니다. 디스크 I/O는 메모리 접근보다 훨씬 느리기 때문에, 이러한 특성 덕분에 B-트리는 대용량 데이터 처리에 매우 효율적입니다.
B-트리의 주요 성질
B-트리는 m-way 트리의 모든 성질을 가지며, 그 외에 다음과 같은 추가적인 조건을 만족해야 합니다.
- B-트리의 모든 노드는 최대 m개의 자식 노드를 가질 수 있습니다.
- 루트 노드와 리프(leaf) 노드를 제외한 모든 노드는 최소 ⌈m/2⌉개의 자식 노드를 가져야 합니다.
- 루트 노드는 반드시 최소 2개 이상의 자식 노드를 가져야 합니다.
- 모든 리프 노드는 반드시 같은 레벨(깊이)에 위치해야 합니다.
B-트리 예시
B-트리의 기본 연산
B-트리는 탐색(search), 삽입(insertion), 삭제(deletion)와 같은 기본 연산을 지원합니다. 각 노드 내부의 키들은 항상 정렬된 상태로 유지됩니다.
i번째 위치에 있는 키를 기준으로, 그 앞쪽(왼쪽)에 있는 자식 노드들은 해당 키보다 작은 값들을 담고, 뒤쪽(오른쪽)에 있는 자식 노드들은 해당 키보다 큰 값들을 담습니다. 이러한 정렬 규칙 덕분에 이진 탐색 트리와 유사한 방식으로 효율적인 탐색이 가능합니다.
정리
B-트리는 낮은 트리 높이를 통해 디스크 접근 횟수를 최소화하는 자료구조로, MySQL, Oracle 등의 데이터베이스 인덱스와 파일 시스템(예: NTFS, ext4)의 핵심 기술로 사용되고 있습니다. 대용량 데이터를 다루는 시스템을 설계할 때 반드시 이해해야 할 중요한 데이터 구조입니다.