B-Tree란?

B-Tree는 데이터베이스나 파일시스템 등에서 디스크 접근 횟수를 최소화하고, 검색·삽입·삭제 연산을 효율적으로 처리하기 위해 고안된 균형 트리(Balanced Tree) 구조입니다. 노드 한 개가 다수의 **키(key)**와 자식 포인터를 보유할 수 있어, 이진 탐색 트리(Binary Search Tree)보다 더 넓은 폭(branching factor)을 가집니다.

 

 

- 쉽게 말해, 디스크 블록 크기에 맞춰 한 노드 안에 여러 키를 묶어 저장하고, 이를 통해 트리 높이를 낮추어 디스크 I/O 횟수를 줄이는 것이 핵심 아이디어입니다.

 

1. B-Tree의 기본 개념

1. Self-Balancing(균형 유지)
   • B-Tree는 삽입·삭제 연산 후에도 노드 분할(split) 또는 병합(merge)을 통해 트리 높이가 일정 수준으로 유지되도록 설계되었습니다.
   • 삽입 시 한 노드가 용량(키 개수)을 초과하면 분할하여 균형을 맞추고, 삭제 시 노드 내 키 개수가 지나치게 줄어들면 병합 또는 재분배를 수행해 균형을 유지합니다.
2. 노드 내 다중 키
   • 각 노드에는 여러 개의 키가 정렬된 상태로 저장되어 있으며, 키들 사이에는 자식 노드를 가리키는 포인터가 위치합니다.
   • 키와 자식 포인터 개수에는 최소·최대 허용치가 존재하여, 어느 정도 이하(최소 분기수)로 떨어지지 않도록 보장합니다.
3. 낮은 트리 높이(Depth)
   • 한 노드에 여러 키를 저장함으로써, 전체 트리의 높이를 최대한 낮게 유지합니다.
   • 예를 들어, 1만10만 건 이상의 레코드를 담아도 트리 높이가 34 레벨 정도밖에 되지 않는 식입니다.
   • 이는 디스크 접근(랜덤 I/O) 횟수를 줄이는 중요한 장점이 됩니다.
4. 디스크 블록 최적화
   • B-Tree는 보통 **디스크 블록(또는 페이지)**에 맞춰 노드 크기를 설계합니다(예: 4KB, 8KB 등).
   • 이렇게 하면 한 번의 디스크 읽기(블록 단위)로 노드 전체 키를 모두 가져올 수 있으므로 추가적인 랜덤 I/O를 줄일 수 있습니다.

 

2. B-Tree vs. B+Tree

• B+Tree는 B-Tree를 파일시스템/데이터베이스 인덱스 용도에 더 맞도록 개선한 변형입니다.
  • 차이점
    1. 모든 실제 데이터(레코드)는 리프 노드에만 저장하고, 상위 노드는 오직 인덱스(키, 포인터) 정보만 저장합니다.
    2. 리프 노드들이 링크드 리스트로 연결되어 있어, **범위 쿼리(range scan)**가 매우 빠릅니다.
  • 사용 사례
    • MySQL(InnoDB), PostgreSQL, Oracle, MS SQL Server 등 대부분의 RDBMS에서 B+Tree를 인덱스 구조로 활용합니다.
    • 파일시스템(FAT, NTFS, EXT 등)도 유사한 구조의 B+Tree 변형을 인덱싱에 사용합니다.

 

 

 

3. B-Tree(또는 B+Tree)의 주요 연산

1. 검색(Search)
   • 루트 노드부터 시작하여, 노드 안의 키 목록을 이진 탐색하거나 순차 탐색한 뒤,
   • 범위에 따라 적절한 자식 포인터를 따라 내려가는 과정을 트리의 리프까지 반복합니다.
   • 트리 높이가 낮으므로 디스크 접근 횟수가 많지 않음(보통 2~4회 정도).
2. 삽입(Insert)
   • 검색 과정으로 들어갈 리프 노드를 찾습니다.
   • 노드가 가득 차지 않았다면 그대로 삽입하고 정렬을 유지합니다.
   • 노드가 꽉 차 있으면, 노드를 **분할(split)**하여 상위 노드에 새 키를 삽입해 균형을 맞춥니다.
3. 삭제(Delete)
   • 검색 과정을 통해 해당 키가 있는 노드를 찾고, 삭제 후 키 개수가 최소 한도 이하로 감소하면,
   • 형제 노드와 **재분배(redistribution)**를 하거나, 노드 **병합(merge)**을 수행합니다.
   • 마찬가지로 트리 전체 높이가 균형을 유지하도록 조정합니다.
4. 범위 검색(Range Query) – 주로 B+Tree에서 효율적
   • 리프 노드들이 연결 리스트로 연결되어 있으면, 시작 키를 찾은 뒤 링크드 리스트를 따라가면서 빠르게 데이터를 순회할 수 있어,
   • 범위 조회(where clause에 range가 있는 SQL)나 정렬된 순서로 데이터 접근이 용이합니다.

 

 

4. B-Tree의 장단점

장점

1. 디스크 I/O 최적화
   • 한 노드가 여러 키를 담으므로, 검색·삽입·삭제 시 트리 높이가 낮아 디스크 블록 접근 횟수가 적습니다.
2. 범용성(OLTP 인덱스 구조)
   • 전통적인 RDBMS의 인덱스 구조로 널리 채택되어 왔으며,
   • 읽기-쓰기 균형이 좋고, 특정 키를 빠르게 찾거나, 범위 검색에도 효율적입니다.
3. 랜덤 접근에 대한 적절한 성능
   • 순차 쓰기만 최적화하는 LSM Tree와 달리, 읽기-쓰기가 섞인 전통적 OLTP 환경에서 자주 사용됩니다.

단점

1. 랜덤 쓰기 비용
   • 노드 분할/병합 시 랜덤 디스크 쓰기가 발생할 수 있습니다.
   • 단일 대용량 순차 쓰기에 특화된 환경(로그성 데이터 등)에서는 성능이 떨어집니다.
2. 메모리 부족 시 성능 저하
   • B-Tree 노드를 캐시하지 못하고 매번 디스크에서 읽어야 한다면, 검색 성능이 급격히 떨어질 수 있습니다.
3. 아주 잦은 삽입·삭제 환경에서 오버헤드
   • 노드 스플릿(분할)이나 병합 작업이 자주 일어나면 추가 비용이 발생합니다.
   • 이런 케이스에는 LSM Tree가 더 적합할 수도 있습니다.