B-Tree와 B+Tree 인덱스의 구조적 차이

데이터베이스 성능을 결정하는 인덱스의 핵심 B Tree와 B Plus Tree 이해하기

데이터베이스를 사용하는 애플리케이션을 개발하거나 운영하다 보면 성능 저하라는 벽에 부딪히곤 합니다. 이때 가장 먼저 살펴보는 것이 바로 인덱스입니다. 인덱스는 책의 맨 뒤에 있는 찾아보기와 같아서, 방대한 데이터 중에서 원하는 정보를 빠르게 찾을 수 있도록 돕는 일종의 이정표입니다. 하지만 인덱스라고 해서 다 같은 방식은 아닙니다. 데이터베이스 관리 시스템은 효율을 극대화하기 위해 B-Tree와 B+Tree라는 독특한 자료구조를 사용합니다. 이 두 구조가 무엇인지, 왜 중요한지, 그리고 실무에서는 어떤 차이를 만드는지 자세히 알아보겠습니다.

B Tree가 무엇인지 살펴보기

B-Tree는 데이터베이스와 파일 시스템에서 널리 사용되는 균형 잡힌 이진 탐색 트리의 확장판입니다. 이진 탐색 트리는 자식 노드를 최대 2개만 가질 수 있지만, B-Tree는 한 노드에 여러 개의 키를 저장할 수 있고 자식 노드도 여러 개를 가질 수 있습니다. 이를 통해 트리의 높이를 낮게 유지할 수 있습니다.

B-Tree의 가장 큰 특징은 모든 노드가 실제 데이터 레코드의 주소값을 가지고 있다는 점입니다. 즉, 어떤 노드에 접근하느냐에 따라 데이터를 바로 찾을 수도 있고, 하위 노드로 내려가야 할 수도 있습니다. 데이터가 노드 곳곳에 분산되어 저장되어 있는 구조라고 이해하면 쉽습니다.

B Tree의 구조적 특징

• 노드 내부에 키와 데이터가 함께 저장됩니다.

• 자식 노드들의 키 값은 부모 노드의 키 값을 기준으로 정렬되어 있습니다.
• 모든 리프 노드는 같은 레벨에 위치하여 탐색 속도가 일정합니다.
• 데이터가 중간 노드에 위치할 수 있어 탐색이 빠를 때도 있지만, 데이터 분포가 일정하지 않으면 효율이 떨어질 수 있습니다.

B Plus Tree가 현대 데이터베이스의 표준인 이유

대부분의 관계형 데이터베이스(MySQL, Oracle 등)가 기본 인덱스 구조로 채택하고 있는 것은 B+Tree입니다. B+Tree는 B-Tree를 개선한 버전으로, 실무 환경에서의 데이터 접근 패턴을 고려하여 설계되었습니다. B-Tree와의 결정적인 차이는 데이터 저장 방식과 노드 간의 연결에 있습니다.

B Plus Tree의 핵심적인 차이

• 데이터는 오직 리프 노드에만 저장됩니다. 중간 노드(인덱스 노드)는 오직 길을 찾기 위한 키 값만 저장합니다.

• 모든 리프 노드는 연결 리스트로 서로 연결되어 있습니다.
• 중간 노드에 데이터를 저장하지 않기 때문에 하나의 노드에 더 많은 인덱스 키를 담을 수 있습니다.
• 트리의 높이가 B-Tree보다 낮아질 가능성이 크며, 이는 디스크 I/O 횟수를 줄여줍니다.

데이터베이스 성능을 좌우하는 구조적 차이 비교

B-Tree와 B+Tree의 차이를 이해하는 것은 인덱스 설계의 첫걸음입니다. 다음 표를 통해 두 방식이 어떤 차이를 만드는지 비교해 보겠습니다.

구분	B Tree	B Plus Tree
데이터 저장 위치	모든 노드	리프 노드에만 저장
범위 탐색 효율	낮음 (트리 순회 필요)	매우 높음 (리프 노드 간 연결)
중간 노드 용량	데이터 포함으로 작음	키만 포함하여 큼
탐색 성능	최적의 경우 빠름	모든 경우 균일하게 빠름

왜 B Plus Tree가 실무에서 더 유리한가

실무에서 데이터베이스를 운영할 때 가장 중요한 요소 중 하나는 범위 검색입니다. 예를 들어 ‘지난달 1일부터 30일까지의 주문 내역을 모두 조회’하는 쿼리를 실행한다고 가정해 봅시다. B-Tree 구조에서는 특정 범위를 찾기 위해 트리를 계속해서 오르내리며 데이터를 수집해야 합니다. 이는 디스크 I/O를 빈번하게 발생시켜 성능을 저하시킵니다.

반면 B+Tree는 리프 노드들이 연결 리스트로 이어져 있습니다. 시작 지점만 찾으면 그 뒤로는 리프 노드를 따라 옆으로 쭉 읽기만 하면 됩니다. 이 방식은 순차적인 데이터 접근이 빈번한 데이터베이스 환경에서 압도적인 성능 우위를 보여줍니다. 또한 중간 노드에 데이터를 저장하지 않아 인덱스 페이지에 더 많은 키를 넣을 수 있으므로, 메모리에 더 많은 인덱스 정보를 올려두어 디스크 접근을 최소화할 수 있습니다.

흔히 접하는 오해와 사실 관계

인덱스에 대해 많은 개발자가 오해하는 부분들이 있습니다. 이를 바로잡는 것이 효율적인 데이터베이스 설계의 시작입니다.

인덱스가 많을수록 좋다?

흔한 오해 중 하나는 인덱스를 많이 만들면 조회 속도가 빨라지니 무조건 많이 만드는 것이 좋다는 생각입니다. 하지만 인덱스는 데이터를 삽입(Insert), 수정(Update), 삭제(Delete)할 때마다 함께 갱신되어야 합니다. 인덱스가 많으면 데이터 변경 작업 시 성능이 급격히 떨어지며, 인덱스 자체가 차지하는 저장 공간도 무시할 수 없습니다. 필요한 컬럼에만 전략적으로 인덱스를 생성하는 것이 현명합니다.

데이터가 적으면 인덱스는 필요 없다?

데이터 양이 적을 때는 인덱스를 사용하는 것보다 테이블 전체를 스캔(Full Table Scan)하는 것이 더 빠를 수 있습니다. 인덱스를 탐색하는 비용보다 그냥 처음부터 끝까지 읽는 비용이 적기 때문입니다. 따라서 데이터 양이 충분히 많아지고, 특정 조건으로 검색하는 빈도가 높을 때 인덱스를 도입하는 것이 비용 효율적입니다.

전문가가 제안하는 인덱스 활용 팁

데이터베이스의 성능을 최적화하기 위해서는 구조를 이해하는 것만큼이나 실전적인 활용 능력이 중요합니다. 전문가들이 권장하는 몇 가지 실무 팁을 정리해 드립니다.

카디널리티를 확인하세요

카디널리티는 특정 컬럼에 들어있는 값의 중복도가 낮은 정도를 의미합니다. 예를 들어 성별(남/여)은 카디널리티가 낮고, 주민등록번호는 카디널리티가 높습니다. 카디널리티가 높은 컬럼에 인덱스를 걸어야 인덱스를 통해 데이터를 걸러내는 효과가 극대화됩니다.

복합 인덱스 순서를 고려하세요

여러 컬럼을 조합하여 하나의 인덱스를 만드는 복합 인덱스를 사용할 때는 순서가 매우 중요합니다. B+Tree는 왼쪽 컬럼을 기준으로 정렬된 상태에서 다음 컬럼을 정렬합니다. 따라서 쿼리에서 자주 사용되는 조건 순서대로 인덱스 컬럼을 배치해야 인덱스를 효율적으로 사용할 수 있습니다.

커버링 인덱스를 활용하세요

커버링 인덱스는 쿼리에 필요한 모든 데이터를 인덱스 자체에서 찾을 수 있는 경우를 말합니다. 리프 노드에 데이터가 존재하는 B+Tree의 특성을 이용해, 별도의 테이블 데이터 접근 없이 인덱스 페이지만 읽어서 결과를 반환하면 성능을 획기적으로 높일 수 있습니다.

자주 묻는 질문과 답변

Q: B+Tree를 사용하면 데이터 삽입 시 성능 저하가 발생하지 않나요?

A: 물론 발생합니다. 리프 노드에 데이터를 순차적으로 삽입할 때 노드가 꽉 차면 분할(Split) 과정이 일어나는데, 이 과정에서 성능 비용이 발생합니다. 하지만 B-Tree와 비교했을 때 리프 노드 간의 연결성 덕분에 전체적인 데이터 관리 효율이 훨씬 높습니다.

Q: 인덱스를 생성하면 무조건 조회 속도가 빨라지나요?

A: 그렇지 않습니다. 인덱스도 결국은 자료구조입니다. 인덱스를 타지 않는 쿼리(예를 들어 인덱스 컬럼에 함수를 적용하거나, 와일드카드를 앞에 붙여 검색하는 경우)라면 인덱스는 무용지물이 됩니다. 쿼리 실행 계획(Explain)을 확인하여 인덱스를 제대로 사용하는지 검증하는 과정이 필수적입니다.

Q: B+Tree 외에 다른 인덱스 구조도 있나요?

A: 네, 해시 인덱스(Hash Index)나 R-Tree 등이 있습니다. 해시 인덱스는 등가 비교에는 매우 빠르지만 범위 검색이 불가능하다는 단점이 있고, R-Tree는 공간 정보를 다룰 때 주로 사용됩니다. 하지만 범용적인 데이터베이스 환경에서는 여전히 B+Tree가 가장 안정적이고 다재다능한 선택지입니다.

효율적인 운영을 위한 인덱스 관리 전략

데이터베이스는 살아있는 생물과 같습니다. 데이터가 쌓임에 따라 인덱스도 노후화되거나 파편화(Fragmentation)될 수 있습니다. 정기적으로 인덱스를 재구성(Rebuild)하거나 사용하지 않는 인덱스를 삭제하는 과정은 데이터베이스 관리자에게 매우 중요한 업무입니다. 인덱스는 ‘공짜 점심’이 아닙니다. 저장 공간을 소비하고 데이터 변경 시 비용을 발생시키므로, 항상 ‘이 인덱스가 실제 쿼리 성능을 향상시키고 있는가?’라는 질문을 던져야 합니다.

실제 서비스를 운영할 때는 슬로우 쿼리 로그를 주기적으로 분석하여, 인덱스가 없어서 느려지는 쿼리를 찾아내고 그 부분에 적절한 인덱스를 추가하는 방식으로 운영하는 것이 가장 비용 효율적입니다. 무작정 모든 컬럼에 인덱스를 걸기보다는, 서비스의 핵심 비즈니스 로직에서 가장 빈번하게 조회되는 조건들을 파악하고 그 우선순위에 따라 인덱스를 최적화하는 습관을 들이는 것이 좋습니다.