[Algorithm] B Tree, B+ Tree

개념

B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

모든 키는 정렬돼 있고, 탐색·순차접근·삽입·삭제가 모두 O(log n)에 가능하도록 높이(h)를 매우 낮게 유지한다.

이 구조는 디스크/페이지 I/O를 최소화하려고 고안됐고, DB와 파일시스템 인덱스의 표준이다.

최대 M개 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다.

[ DB 인덱스로 B(+)-트리를 채택하는 이유 ]

메모리는 랜덤 접근이 빠르지만, 디스크/SSD는 페이지 단위 접근 비용이 크다.

B-트리는 한 노드(=한 페이지)에 많은 키를 담아 팬아웃(fan-out)을 크게 만들고, 높이 h를 2~4 정도로 작게 유지함으로써,

탐색 시 읽는 페이지 수(I/O)를 극적으로 줄인다.

삽입 과정

리프까지 내려가 삽입 위치 결정
여유가 있으면 키 삽입 후 종료
오버플로우(키가 m−1 초과) 시 분할(split):
- 중앙 키를 위로 승격, 좌/우 노드로 분할
- 필요 시 분할이 상위로 전파(루트까지 가면 높이 +1)
  복잡도: O(h)

삭제 과정

개념

B-Tree에서 확장된 개념으로, 리프 노드를 제외하고는 값을 담지 않는 트리이다.

리프 노드에만 데이터를 저장하기때문에, 메모리를 더 많이 확보한다. 따라서 더 많은 key를 담을 수 있어 팬아웃이 커지고, 트리의 높이를 낮출 수 있다. 트리의 높이가 낮을수록 cache hit을 높일 수 있으므로 데이터 탐색이 빠르다.

현대 DBMS의 순서 보존 인덱스 대부분이 이 구조(또는 변형)를 쓴다.

B+트리는 리프 노드를 순차적으로 연결하는 포인터 집합을 가지고 있다. 인덱스된 순차 파일 처리시, 포인터를 이용하여 키, 값을 일일이 비교하지 않고 다음 데이터에 접근해서 빠르게 처리할 수 있다.

풀 스캔(Full scan)시, B+Tree는 리프노드에 데이터가 있기 때문에 선형탐색을 할 수 있어서, B+트리보다 빠르다.

삽입 과정

대상 리프에 삽입 → 오버플로우 시 분할(split), 부모로 분할 전파 가능(루트 분할 시 높이+1)

삭제 과정

리프에서 제거 → 언더플로우 시 재분배/병합, 필요 시 상위로 전파(루트 축소 가능)

모두 O(h)=O(logₘ n), 여기서 m은 분기수(팬아웃)

구분	B-Tree	B+Tree
데이터 저장 위치	내부/리프 모두 데이터(또는 레코드 포인터) 보관 가능	리프만 실제 데이터, 내부는 키+자식 포인터만
탐색 종료 위치	내부에서 바로 찾을 수도 있음(리프로 안 내려갈 수 있음)	항상 리프에서 결과 획득(포인트 조회도 리프 도달)
팬아웃/높이	내부에 데이터가 섞이면 팬아웃이 상대적으로 작아질 수 있음	내부가 가벼워 팬아웃↑, 높이↓ 경향(페이지 I/O 절감)
범위 질의	가능하나 리프 연결이 없으면 추가 구조가 필요할 수 있음	리프들이 연결 리스트로 이어져 순차/범위 스캔 최적화
키 중복	구현체마다 상이(대개 내부/리프 혼재로 중복 덜함)	리프에 모든 키 보유라 필요한 범위에서 키 복제가 자연스러움
삽입/삭제 비용	분할/재분배/병합으로 O(log n)	로직 유사, 내부는 경로 라우팅만 변경하므로 업데이트가 비교적 단순. O(log n)

[ 왜 B+Tree가 실전에서 유리한가 ]

낮은 높이(h): 내부가 가벼워 같은 페이지 크기에서 더 많은 키를 담아 디스크 접근 횟수 감소
범위 질의/정렬 스캔: 리프 연결로 순차 접근이 빨라 ORDER BY/BETWEEN, 인덱스 스캔에 강함
DB 구현 친화성: PostgreSQL 등은 내부/리프 페이지 구조와 메타페이지를 갖춘 다층 인덱스로 B-트리류를 구현하며, 리프에 튜플 포인터(TID)를 저장한다

cod