B+Tree란 무엇인가
B+Tree는 정렬된 데이터를 트리 형태로 저장하는 자료구조로, 대부분의 관계형 데이터베이스(MySQL의 InnoDB, PostgreSQL 등)가 인덱스 구조로 채택하고 있습니다. 이름은 ‘B-Tree’에서 파생되었지만 몇 가지 중요한 차이가 있습니다. B-Tree는 모든 노드에 데이터를 저장하지만, B+Tree는 실제 데이터(혹은 데이터 위치 정보)를 오직 리프 노드(leaf node)에만 저장합니다. 중간 노드는 검색 경로를 안내하는 ‘이정표’ 역할만 합니다. 또한 리프 노드끼리는 연결 리스트(linked list)로 서로 연결되어 있어, 범위 검색 시 옆으로만 이동하면 되므로 매우 효율적입니다.
동작 원리를 비유로 이해하기
도서관에서 책을 찾는 상황을 떠올려보세요. 책 제목이 무작위로 꽂혀 있다면 처음부터 끝까지 다 뒤져야 합니다. 하지만 도서관에는 ‘분류 안내판’이 있고, 그 아래에는 세부 구역 안내판이 있고, 마지막에 실제 책이 꽂힌 서가가 있습니다. B+Tree도 이와 같습니다.
- 루트 노드: 가장 큰 범위의 안내판 (예: A~M, N~Z)
- 중간 노드: 더 좁은 범위 안내 (예: A~D, E~H)
- 리프 노드: 실제 데이터가 있는 서가
예를 들어 WHERE id = 500 같은 쿼리가 들어오면, 루트에서 시작해 중간 노드를 몇 단계 거쳐 리프 노드까지 도달합니다. 데이터가 100만 건이어도 트리의 높이는 3~4단계 정도로 유지되기 때문에, 탐색 시간이 거의 일정하게 유지됩니다. 이를 시간 복잡도로 표현하면 O(log n)입니다.
실무에서 왜 B+Tree를 쓰는가
B+Tree가 데이터베이스 인덱스의 표준이 된 이유는 크게 세 가지입니다. 첫째, 디스크 I/O에 최적화되어 있습니다. 데이터베이스는 디스크에서 데이터를 ‘페이지’ 단위로 읽는데, B+Tree는 하나의 노드가 여러 개의 자식을 가질 수 있도록 설계되어 트리의 높이를 낮게 유지합니다. 높이가 낮을수록 디스크 접근 횟수가 줄어듭니다. 둘째, 리프 노드가 연결 리스트로 이어져 있어 BETWEEN이나 ORDER BY 같은 범위 검색과 정렬 작업이 빠릅니다. 셋째, 삽입과 삭제가 발생해도 트리의 균형이 자동으로 재조정되어 성능이 급격히 나빠지지 않습니다.
결국 B+Tree는 ‘많은 데이터 중에서 원하는 값을 빠르게 찾고, 순서대로 훑어보기도 쉬운 구조’라는 두 가지 목표를 동시에 만족시키기 때문에 인덱스 구현체로 널리 사용되는 것입니다.