시스매

데이터베이스의 심장을 파헤치다 B-Tree 핸드북 완벽 가이드

20 min read

2025-08-24 13:47

데이터베이스의 심장을 파헤치다 B-Tree 핸드북 완벽 가이드

컴퓨터 과학을 공부하거나 데이터베이스를 다루다 보면 ‘B-Tree’라는 용어를 반드시 마주치게 됩니다. B-Tree는 단순히 데이터를 정렬하는 여러 방법 중 하나가 아닙니다. 오늘날 우리가 사용하는 거의 모든 데이터베이스 시스템과 파일 시스템의 성능을 좌우하는 핵심적인 자료구조입니다. 왜 B-Tree가 이렇게 중요할까요? 이 질문에 답하기 위해, 우리는 잠시 컴퓨터의 기억 장치 구조를 이해해야 합니다.

컴퓨터의 CPU와 메인 메모리(RAM)는 눈 깜짝할 사이에 데이터를 처리하지만, 하드 디스크(HDD)나 SSD 같은 보조 기억 장치는 그에 비해 매우 느립니다. 마치 빛의 속도로 달리는 슈퍼맨(CPU)이 일반 우편으로 편지(데이터)를 주고받는 것과 같습니다. 데이터가 아무리 많아져도 슈퍼맨이 직접 우체국을 방문하는 횟수만 줄일 수 있다면, 전체 작업 시간은 획기적으로 단축될 것입니다.

B-Tree는 바로 이 ‘우체국 방문 횟수’, 즉 디스크 접근(I/O) 횟수를 최소화하기 위해 탄생한 자료구조입니다. 이 핸드북을 통해 B-Tree가 어떤 원리로 이 문제를 해결했는지, 그리고 어떻게 현대 기술의 근간이 되었는지 쉽고 깊이 있게 알아보겠습니다.

1. B-Tree는 왜 만들어졌을까? 속도의 차이에서 시작된 고민

B-Tree의 탄생 배경을 이해하기 위해 거대한 도서관을 상상해 봅시다. 수백만 권의 책(데이터)이 보관된 서고(디스크)가 있고, 우리는 특정 책을 찾아야 합니다.

  • 방법 1: 무작정 찾기 (Full Scan) 첫 번째 서가부터 마지막 서가까지 모든 책을 하나씩 확인하는 방법입니다. 가장 원시적이고, 책이 많아질수록 시간이 기하급수적으로 늘어납니다. 데이터베이스에서 이는 ‘풀 테이블 스캔’에 해당하며, 최후의 수단으로 사용됩니다.

  • 방법 2: 이진 탐색 트리 (Binary Search Tree) 활용 책을 가나다순으로 정리하고, 중간 지점의 책과 비교하여 찾으려는 책이 앞쪽에 있는지 뒤쪽에 있는지 판단해 나가는 방식입니다. 훨씬 효율적이지만, 최악의 경우 트리가 한쪽으로 길게 늘어진 편향 트리(Skewed Tree)가 될 수 있습니다. 또한, 데이터가 많아지면 트리의 깊이가 깊어져 여러 번의 비교, 즉 여러 번의 디스크 접근이 필요합니다. 디스크의 특정 위치로 탐색해 가는 시간(Seek Time)이 매우 느리기 때문에, 비교 횟수가 늘어나는 것은 치명적입니다.

여기서 핵심 문제가 드러납니다. “어떻게 하면 디스크에 접근하는 횟수 자체를 줄일 수 있을까?”

B-Tree의 창시자들(Rudolf Bayer, Edward M. McCreight)은 이 문제를 해결하기 위해 발상을 전환했습니다. “한 번 디스크에 접근할 때, 최대한 많은 정보를 읽어오면 어떨까?”

이 아이디어가 B-Tree의 핵심입니다. 이진 트리가 한 노드에 하나의 데이터만 가지는 것과 달리, B-Tree는 하나의 노드(Node)에 여러 개의 데이터(Key)를 저장합니다. 마치 도서관의 색인 카드를 한 장씩 넘기는 게 아니라, 한 페이지에 수십 개의 책 위치 정보가 담긴 ‘색인 목록’을 보는 것과 같습니다.

이렇게 하나의 노드에 많은 데이터를 담으면, 트리의 분기(branch)가 많아집니다. 이를 팬아웃(Fan-out)이 높다고 표현합니다. 팬아웃이 높으면 같은 양의 데이터를 저장하더라도 트리의 전체 높이가 매우 낮아집니다. 예를 들어 1,000만 개의 데이터를 저장할 때, 이진 트리의 높이는 약 24가 되지만, 하나의 노드에 100개의 데이터를 담는 B-Tree의 높이는 3~4 수준으로 급격히 줄어듭니다.

트리의 높이가 곧 디스크 접근 횟수이므로, B-Tree는 데이터베이스 검색 성능을 극적으로 향상시킬 수 있었던 것입니다.

2. B-Tree의 구조 파헤치기

B-Tree는 ‘균형 잡힌(Balanced)’ 트리입니다. 즉, 루트(Root) 노드에서부터 모든 리프(Leaf) 노드까지의 경로 길이가 같아, 데이터가 어디에 있든 비슷한 속도로 접근할 수 있음을 보장합니다.

B-Tree의 핵심 규칙

B-Tree를 이해하기 위해서는 몇 가지 규칙을 알아야 합니다. 최대 M개의 자식을 가질 수 있는 B-Tree를 ‘M차 B-Tree’라고 부르며, 모든 규칙은 이 M값을 기준으로 합니다.

  1. 노드의 구조: 각 노드는 [P₁, K₁, P₂, K₂, ..., Pₙ, Kₙ, Pₙ₊₁] 형태로 구성됩니다.

    • Kᵢ: 노드에 저장된 키(Key)로, 오름차순으로 정렬되어 있습니다.

    • Pᵢ: 자식 노드를 가리키는 포인터(Pointer)입니다. Kᵢ의 왼쪽에 있는 Pᵢ는 Kᵢ보다 작은 값들을 가진 서브트리를, 오른쪽에 있는 Pᵢ₊₁는 Kᵢ보다 큰 값들을 가진 서브트리를 가리킵니다.

  2. 키와 자식의 수:

    • 한 노드는 최대 M-1개의 키를 가질 수 있습니다.

    • 루트 노드를 제외한 모든 노드는 최소 ⌈M/2⌉ - 1개의 키를 가져야 합니다.

    • 한 노드에 n개의 키가 있다면, n+1개의 자식 노드를 가집니다.

  3. 균형: 모든 리프 노드는 같은 레벨(높이)에 존재해야 합니다.

  4. 정렬: 노드 내의 키는 항상 오름차순으로 정렬되어 있습니다.

예를 들어, 5차 B-Tree가 있다고 가정해 봅시다.

  • 한 노드는 최대 4개(5-1)의 키를 가질 수 있습니다.

  • 루트를 제외한 노드는 최소 2개(⌈5/2⌉ - 1)의 키를 가져야 합니다.

  • 모든 리프 노드는 같은 높이에 있습니다.

이러한 규칙들 덕분에 B-Tree는 데이터가 삽입되거나 삭제될 때 스스로 구조를 변경하여 항상 균형을 유지하고, 검색 성능을 일정하게 보장합니다.

3. B-Tree는 어떻게 동작하는가? 탐색, 삽입, 삭제

B-Tree의 진가는 데이터가 동적으로 변할 때 나타납니다. 탐색, 삽입, 삭제 연산이 어떻게 이루어지는지 살펴보겠습니다.

탐색은 B-Tree의 가장 기본적이고 빠른 연산입니다.

  1. 루트 노드에서 시작합니다.

  2. 찾고자 하는 값과 노드 내 키들을 비교합니다.

    • 값이 노드 내에 존재하면 탐색을 성공적으로 마칩니다.

    • 값이 존재하지 않으면, 값이 속할 범위를 결정합니다. (예: K₁과 K₂ 사이)

  3. 해당 범위에 맞는 자식 포인터를 따라 다음 레벨의 노드로 이동합니다.

  4. 리프 노드에 도달할 때까지 2~3번 과정을 반복합니다. 리프 노드에도 값이 없으면, 해당 데이터는 트리에 존재하지 않는 것입니다.

트리의 높이가 매우 낮기 때문에, 이 과정은 단 몇 번의 디스크 접근만으로 완료됩니다.

나. 삽입 (Insertion)

삽입은 탐색보다 조금 더 복잡합니다. 노드가 꽉 찼을 때 ‘분열(Split)‘이라는 특별한 과정이 필요하기 때문입니다.

  1. 탐색: 먼저 새로운 키가 삽입될 적절한 리프 노드를 탐색 과정을 통해 찾습니다.

  2. 삽입: 찾은 리프 노드에 새로운 키를 오름차순에 맞게 삽입합니다.

  3. 오버플로우 및 분열 처리:

    • 만약 키를 삽입한 후 노드의 키 개수가 최대치(M-1)를 초과하면 **오버플로우(Overflow)**가 발생합니다.

    • 이때 **노드 분열(Node Split)**이 일어납니다.

    • 기존 노드의 키들 중 **중간값(Median)**을 선택합니다.

    • 중간값은 부모 노드로 올려보냅니다.

    • 중간값을 기준으로 나머지 키들은 두 개의 새로운 노드로 나뉩니다.

    • 만약 부모 노드로 올라간 키 때문에 부모 노드 역시 오버플로우가 발생하면, 이 분열 과정이 루트 노드에 도달할 때까지 재귀적으로 반복됩니다. 트리의 높이가 커지는 유일한 순간입니다.

이 ‘분열’ 메커니즘 덕분에 B-Tree는 항상 스스로 균형을 맞출 수 있습니다.

다. 삭제 (Deletion)

삭제는 B-Tree에서 가장 복잡한 연산입니다. 키를 삭제한 후 노드가 최소 키 개수 조건을 위반하는 **언더플로우(Underflow)**가 발생할 수 있기 때문입니다.

  1. 탐색: 삭제할 키를 탐색합니다.

  2. 삭제 및 재조정:

    • Case 1: 키가 리프 노드에 있는 경우

      • 키를 삭제한 후에도 노드가 최소 키 개수(⌈M/2⌉ - 1) 이상을 유지하면, 단순히 키만 삭제하고 연산을 종료합니다.

      • 삭제 후 언더플로우가 발생하면, 재조정이 필요합니다.

        • 재분배(Redistribution): 형제 노드에 여유 키가 있다면, 부모 노드의 키를 하나 빌려오고, 형제 노드의 키를 부모 노드로 올려서 균형을 맞춥니다.

        • 병합(Merging): 형제 노드도 최소한의 키만 가지고 있다면, 현재 노드를 형제 노드 및 부모로부터 내려온 키와 합쳐 하나의 노드로 만듭니다. 이 과정에서 부모 노드에 언더플로우가 발생하면, 재조정 과정이 위로 전파될 수 있습니다.

    • Case 2: 키가 내부 노드(Internal Node)에 있는 경우

      • 해당 키의 바로 다음 순서(in-order successor)나 이전 순서(in-order predecessor) 키를 리프 노드에서 찾아옵니다. (이들은 항상 리프 노드에 존재합니다.)

      • 찾아온 키와 삭제할 키의 위치를 바꿉니다.

      • 이제 삭제할 키는 리프 노드에 있으므로, 위의 Case 1과 동일한 방법으로 처리합니다.

이러한 복잡한 과정을 통해 B-Tree는 어떤 상황에서도 균형을 잃지 않고 안정적인 성능을 제공합니다.

4. B-Tree의 진화: B+ Tree

실제 데이터베이스 시스템에서는 B-Tree를 그대로 사용하기보다, 이를 개선한 B+ Tree를 훨씬 더 많이 사용합니다. B+ Tree는 B-Tree의 장점은 유지하면서, 특정 시나리오에 더욱 최적화된 구조입니다.

구분B-TreeB+ Tree
데이터 저장 위치모든 노드(내부, 리프)에 키와 데이터 모두 저장내부 노드에는 키만 저장, 데이터는 오직 리프 노드에만 저장
노드 구조내부 노드와 리프 노드의 구조가 동일내부 노드는 자식 노드를 찾는 인덱스 역할만 수행
리프 노드 연결연결되어 있지 않음모든 리프 노드가 연결 리스트(Linked List) 형태로 서로 연결됨

B+ Tree는 왜 더 좋을까?

  1. 더 높은 팬아웃(Fan-out): 내부 노드에 데이터 포인터를 저장하지 않으므로, 같은 노드 크기에 더 많은 키를 저장할 수 있습니다. 이는 트리의 높이를 더욱 낮추어 검색 성능을 향상시킵니다.

  2. 효율적인 범위 탐색(Range Scan): WHERE age > 30 과 같이 특정 범위의 데이터를 모두 조회해야 할 때, B+ Tree는 압도적인 성능을 보입니다. 한번 특정 리프 노드를 찾으면, 그 다음부터는 연결 리스트를 따라 순차적으로 디스크를 읽기만 하면 됩니다. B-Tree처럼 트리를 오르내릴 필요가 없습니다. 이를 풀 테이블 스캔(Full Table Scan)보다 훨씬 효율적인 트리 스캔이라고 합니다.

  3. 단순한 구조: 모든 데이터가 리프 노드에 모여있어 삽입, 삭제 연산이 B-Tree보다 비교적 간단합니다.

이러한 장점 때문에 MySQL의 InnoDB, PostgreSQL 등 대부분의 현대 관계형 데이터베이스는 인덱스 구조로 B+ Tree를 채택하고 있습니다.

5. B-Tree는 어디에 사용될까?

B-Tree와 B+ Tree는 우리 디지털 세상의 보이지 않는 곳에서 묵묵히 제 역할을 수행하고 있습니다.

  • 데이터베이스 인덱스 (Database Indexes): 가장 대표적인 사용처입니다. 테이블의 특정 컬럼에 인덱스를 생성하면, 데이터베이스는 내부적으로 B+ Tree를 만들어 해당 컬럼의 값을 빠르게 찾을 수 있도록 돕습니다.

  • 파일 시스템 (File Systems): NTFS(Windows), HFS+(macOS), Ext4(Linux) 등 우리가 사용하는 대부분의 파일 시스템은 파일의 메타데이터(이름, 크기, 디스크 위치 등)를 관리하기 위해 B-Tree 계열의 자료구조를 사용합니다. 덕분에 우리는 수많은 파일 속에서 원하는 파일을 빠르게 찾을 수 있습니다.

  • Key-Value 저장소: 일부 NoSQL 데이터베이스나 Key-Value 저장소에서도 내부적으로 데이터를 정렬하고 빠르게 접근하기 위해 B-Tree 구조를 활용합니다.

결론: 느린 세상을 빠르게 만드는 조용한 혁명가

B-Tree는 화려한 기술은 아닐지 모릅니다. 하지만 CPU와 디스크 사이의 거대한 속도 차이라는 근본적인 제약을 극복하고, 대용량 데이터를 효율적으로 다룰 수 있는 길을 열어준 조용한 혁명가와 같습니다.

하나의 노드에 여러 키를 담아 트리의 높이를 낮춘다는 단순하지만 강력한 아이디어는 오늘날 우리가 당연하게 여기는 빠른 데이터 검색과 안정적인 시스템의 기반이 되었습니다. 다음에 데이터베이스 쿼리가 순식간에 결과를 반환하거나, 수만 개의 파일 중에서 원하는 파일을 즉시 찾을 때, 그 뒤에서 묵묵히 작동하고 있는 B-Tree의 지혜를 한번쯤 떠올려보는 것은 어떨까요? 이 핸드북이 B-Tree의 세계를 이해하는 데 훌륭한 안내서가 되었기를 바랍니다.

레퍼런스(References)

B 트리

그래프 뷰

백링크