2025-08-29 23:52

• B-트리는 대용량 데이터를 디스크에서 효율적으로 관리하기 위해 탄생한 균형 트리 자료구조입니다.

• 하나의 노드에 많은 데이터를 저장하여 트리의 높이를 낮추고, 디스크 접근 횟수를 획기적으로 줄입니다.

• 데이터베이스 인덱스와 파일 시스템의 핵심 기술로, 현대 데이터 관리의 기반이 됩니다.

B-트리 완벽 가이드: 데이터베이스와 파일 시스템의 비밀

우리가 매일 사용하는 구글 검색, SNS, 은행 시스템 뒤에는 방대한 데이터를 빠르고 안정적으로 처리하는 기술이 숨어있습니다. 그 기술의 심장부에는 바로 B-트리(B-Tree) 라는 자료구조가 있습니다. B-트리는 단순히 컴퓨터 과학 이론에 머무는 개념이 아닙니다. 오늘날 디지털 세상의 근간을 이루는 실용적인 해결책이자, 수십 년간 데이터 관리 분야의 왕좌를 지켜온 핵심 기술입니다.

이 핸드북에서는 B-트리가 왜 만들어졌는지, 어떤 구조로 이루어져 있으며 어떻게 작동하는지, 그리고 실제 세상에서 어떻게 활용되는지 깊이 있게 탐험해 보겠습니다.

1. B-트리의 탄생: 왜 새로운 자료구조가 필요했을까?

B-트리를 이해하려면 먼저 컴퓨터의 저장 장치 특성을 알아야 합니다. 컴퓨터에는 크게 두 종류의 저장 공간이 있습니다. 바로 **RAM(주기억장치)**과 **하드 디스크 또는 SSD(보조기억장치)**입니다.

• RAM: 속도가 매우 빠르지만, 가격이 비싸고 전원이 꺼지면 데이터가 사라집니다.

• 디스크: 속도는 느리지만, 가격이 저렴하고 대용량의 데이터를 영구적으로 저장할 수 있습니다.

대부분의 데이터는 디스크에 저장됩니다. 문제는 디스크에서 데이터를 읽고 쓰는 속도가 RAM에 비해 현저히 느리다는 점입니다. 특히 데이터를 한 번에 하나씩 읽는 것이 아니라, ‘블록(Block)’ 또는 ‘페이지(Page)’ 라는 정해진 크기의 덩어리 단위로 읽어온다는 특징이 있습니다. 디스크에 한 번 접근하는 것(Disk I/O)은 매우 비싼 작업입니다.

기존의 이진 탐색 트리(Binary Search Tree)나 AVL 트리 같은 자료구조는 RAM 안에서 작동할 때는 매우 효율적입니다. 하지만 수억, 수십억 건의 데이터가 디스크에 저장된 상황에서는 심각한 성능 저하를 일으킵니다. 데이터를 하나 찾기 위해 트리의 여러 노드를 방문해야 하고, 각 노드 방문이 곧 한 번의 디스크 접근을 의미하기 때문입니다. 트리의 높이가 50이라면, 최악의 경우 50번의 디스크 I/O가 발생할 수 있습니다.

이 문제를 해결하기 위해 1971년, 루돌프 바이어와 에드워드 맥크레이트는 B-트리를 세상에 내놓았습니다. B-트리의 핵심 아이디어는 다음과 같습니다.

“디스크 I/O 횟수 자체를 줄이자. 그러려면 트리의 높이를 최대한 낮춰야 한다. 트리의 높이를 낮추려면, 나무를 옆으로 넓게 퍼뜨리면 된다!”

B-트리는 하나의 노드에 2개의 자식만 두는 대신, 수백 개 이상의 자식을 가질 수 있도록 설계되었습니다. 노드 하나의 크기를 디스크의 블록 크기(예: 4KB)에 맞춤으로써, 한 번의 디스크 I/O로 수많은 데이터를 메모리에 가져올 수 있게 된 것입니다. 이로 인해 트리의 높이는 극단적으로 낮아지고, 디스크 접근 횟수는 획기적으로 줄어듭니다.

2. B-트리의 핵심 구조: 어떻게 균형을 유지하는가?

B-트리는 ‘스스로 균형을 맞추는 트리(Self-Balancing Tree)‘입니다. 데이터가 삽입되거나 삭제될 때 특정 규칙에 따라 구조를 변경하여, 트리가 한쪽으로 치우치지 않고 항상 낮은 높이를 유지합니다.

B-트리는 차수(Order) 라는 개념을 가지며, 이를 m이라고 표기합니다. m차 B-트리는 다음과 같은 규칙을 따릅니다.

• 규칙 1: 모든 리프 노드는 같은 높이에 있다.

  • 이 규칙 덕분에 어떤 데이터를 검색하더라도 항상 비슷한 시간이 소요됨을 보장합니다.

• 규칙 2: 각 노드는 m/2 이상 m 이하의 자식을 가질 수 있다. (단, 루트 노드는 예외)

  • m/2를 최소 차수(Minimum Degree) 라고도 하며, 보통 t로 표기합니다. 이 경우 노드는 t-1개에서 2t-1개의 키를 가집니다.

  • 이 규칙은 노드가 항상 절반 이상 채워져 있도록 하여 공간 효율성을 높이고 트리의 균형을 유지합니다.

• 규칙 3: 노드에는 k개의 키가 있다면, k+1개의 자식 포인터를 가진다.

  • 노드의 키들은 정렬된 상태로 저장됩니다.

  • 자식 포인터는 키와 키 사이의 범위를 가리킵니다. 예를 들어, [10, 30] 이라는 키가 있는 노드는 3개의 자식 포인터를 가집니다: (<10), (10~30), (>30)

이러한 구조 덕분에 B-트리는 키가 수억 개에 달하더라도 높이가 3~5 정도로 매우 낮게 유지될 수 있습니다.

3. B-트리의 작동 원리: 삽입과 삭제

B-트리의 핵심은 **분할(Split)**과 병합(Merge) 연산을 통해 스스로 균형을 맞추는 과정에 있습니다.

탐색 (Search)

탐색은 간단합니다. 루트 노드부터 시작하여 찾고자 하는 값이 노드의 키 범위 중 어디에 속하는지 확인하고, 해당하는 자식 포인터를 따라 내려갑니다. 이 과정을 리프 노드에 도달할 때까지 반복합니다.

삽입 (Insertion)

1. 탐색과 동일한 방식으로 새로운 키가 삽입될 리프 노드를 찾습니다.

2. 해당 리프 노드에 여유 공간이 있다면, 키를 정렬된 위치에 삽입하고 연산을 종료합니다.

3. 만약 리프 노드가 꽉 차 있다면, ‘노드 분할’이 발생합니다.

   • 기존 키들과 새로운 키를 모두 정렬합니다.

   • 중간값(median)을 선택하여 부모 노드로 올려보냅니다.

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

   • 만약 부모 노드도 꽉 차 있다면, 이 분할 과정이 루트까지 연쇄적으로 일어날 수 있습니다. 만약 루트 노드가 분할되면, 새로운 루트가 생성되고 트리의 높이가 1 증가합니다.

이 ‘분할’ 메커니즘이 바로 B-트리가 스스로 성장하며 균형을 유지하는 비결입니다.

삭제 (Deletion)

삭제는 삽입보다 조금 더 복잡하며, ‘최소 키 개수’ 규칙을 지키기 위한 과정이 추가됩니다.

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

2. 키를 삭제한 후, 해당 노드의 키 개수가 최소 개수(t-1)보다 적어지는지 확인합니다.

3. 만약 최소 개수보다 적어진다면 (언더플로우, Underflow), 다음 두 가지 방법으로 해결합니다.

   • 재분배 (Redistribution): 형제 노드가 여유 키를 가지고 있다면, 부모 노드를 통해 키를 하나 빌려옵니다. 마치 옆집에서 음식을 빌리는 것과 같습니다. 이는 가장 효율적인 방법입니다.

   • 병합 (Merge): 형제 노드도 여유가 없다면, 해당 노드를 형제 노드와 합칩니다. 이 과정에서 부모 노드로부터 키를 하나 내려받아 합쳐진 노드를 구성합니다. 이 병합으로 인해 부모 노드에서 언더플로우가 발생할 수 있으며, 이 경우 삭제 연산이 루트까지 연쇄적으로 영향을 미칠 수 있습니다.

4. B-트리 vs B+ 트리: 무엇이 다른가?

실제 데이터베이스 시스템에서는 B-트리보다 B+ 트리가 더 널리 사용됩니다. B+ 트리는 B-트리의 기본 구조를 유지하면서 몇 가지 중요한 개선을 이룬 변형입니다.

특징	B-트리	B+ 트리
데이터 저장 위치	모든 노드(내부, 리프)에 (키, 데이터) 쌍을 저장	오직 리프 노드에만 (키, 데이터) 쌍을 저장
내부 노드의 역할	키와 데이터, 자식 포인터 저장	경로 탐색을 위한 **키(인덱스)**와 자식 포인터만 저장
리프 노드 구조	독립적으로 존재	모든 리프 노드가 **연결 리스트(Linked List)**로 서로 연결됨
주요 사용 사례	특정 키 하나를 찾는 **점 질의(Point Query)**에 유리	특정 범위의 데이터를 모두 찾는 **범위 질의(Range Query)**에 압도적으로 유리

대부분의 데이터베이스 작업은 WHERE age > 30 과 같이 특정 범위를 조회하는 경우가 많습니다. B+ 트리는 리프 노드들이 연결 리스트로 이어져 있어, 시작점만 찾으면 그 다음부터는 리프 노드를 따라 순차적으로 스캔하면 되므로 매우 효율적입니다. 반면 B-트리는 범위 조회를 하려면 트리의 여러 노드를 반복적으로 오르내려야 합니다.

또한, B+ 트리는 내부 노드에 데이터 대신 키만 저장하므로 더 많은 키를 담을 수 있습니다. 이는 트리의 팬아웃(fanout, 자식 수)을 높여 전체적인 트리 높이를 더욱 낮추는 효과를 가져옵니다.

B-트리와 B+트리는 둘 다 대용량 데이터 관리에 탁월하지만, 데이터 저장 방식과 구조에서 중요한 차이가 있어 실제 사용처가 갈립니다. 현재 열려있는 핸드북 4장의 내용을 조금 더 자세히 풀어 설명해 드릴게요.

핵심적인 차이점은 다음 세 가지입니다.

1. 데이터는 어디에 저장되는가?

   • B-트리: 책의 각 목차 항목에 내용 일부가 함께 적혀있는 것과 같습니다. 즉, 루트 노드나 중간 노드(내부 노드)에도 실제 데이터(또는 데이터 포인터)가 저장됩니다.

   • B+트리: 책의 맨 뒤에 있는 ‘찾아보기(인덱스)‘와 같습니다. 중간 노드에는 오직 경로를 찾아가기 위한 ‘키(key)’ 값만 있고, 모든 실제 데이터는 책의 본문 페이지에 해당하는 가장 마지막 레벨의 노드(리프 노드)에만 모여 있습니다.

2. 범위 탐색(Range Scan)의 효율성

   • B-트리: 30~50 사이의 모든 데이터를 찾으려면, 트리의 여러 레벨을 오르락내리락하며 관련된 노드를 모두 방문해야 해서 비효율적입니다.

   • B+트리: 모든 데이터가 저장된 리프 노드들이 서로 연결된 리스트(Linked List) 형태로 이어져 있습니다. 따라서 30이 있는 리프 노드를 찾으면, 그 다음부터는 연결된 노드를 따라 순서대로 쭉 읽기만 하면 되므로 범위 탐색에 압도적으로 빠르고 효율적입니다. 데이터베이스에서 WHERE 나이 > 30과 같은 쿼리가 빠른 이유입니다.

3. 트리의 높이 (성능)

   • B+트리는 중간 노드에 데이터 없이 키만 저장하므로, 같은 크기의 노드에 더 많은 키를 담을 수 있습니다. 이는 곧 **더 많은 자식 노드를 가질 수 있음(더 높은 차수)**을 의미하며, 결과적으로 전체 트리의 높이를 B-트리보다 더 낮게 유지할 수 있습니다. 트리의 높이가 낮다는 것은 디스크 접근 횟수가 줄어든다는 뜻이므로 검색 성능이 더 향상됩니다.

이러한 장점 때문에 오늘날 MySQL, PostgreSQL, Oracle 등 대부분의 데이터베이스 시스템은 인덱스 구현에 B-트리가 아닌 B+트리를 사용합니다.

5. B-트리의 실제 활용 사례

• 데이터베이스 인덱스:

  • MySQL(InnoDB), PostgreSQL, Oracle 등 거의 모든 관계형 데이터베이스는 B+ 트리를 사용하여 인덱스를 구현합니다. SELECT 문의 WHERE 절을 실행할 때, B+ 트리 인덱스 덕분에 전체 테이블을 스캔하지 않고 원하는 데이터를 수 밀리초 안에 찾아낼 수 있습니다.

• 파일 시스템:

  • Windows의 NTFS, macOS의 HFS+ 및 APFS, Linux의 ext4 등 현대적인 파일 시스템들은 파일의 메타데이터나 디렉토리 구조를 관리하기 위해 B-트리 계열의 자료구조를 사용합니다. 수십만 개의 파일이 들어있는 폴더의 내용을 빠르게 보여줄 수 있는 이유가 바로 이 때문입니다.

결론: 시대를 초월한 데이터 관리의 지혜

B-트리는 ‘느린 디스크’라는 물리적 제약을 극복하기 위한 천재적인 아이디어에서 출발했습니다. 트리의 높이를 극단적으로 낮춰 디스크 접근 횟수를 최소화한다는 단순하지만 강력한 원칙은 오늘날까지도 대용량 데이터 관리 시스템의 근간을 이루고 있습니다.

SSD의 등장으로 디스크 접근 속도가 빨라졌지만, 여전히 RAM보다는 훨씬 느립니다. B-트리의 원리는 여전히 유효하며, 데이터가 폭발적으로 증가하는 빅데이터 시대에 그 중요성은 더욱 커지고 있습니다. B-트리를 이해하는 것은 단순히 하나의 자료구조를 배우는 것을 넘어, 현대 소프트웨어 시스템이 어떻게 데이터를 효율적으로 다루는지에 대한 깊은 통찰을 얻는 과정입니다.

레퍼런스(References)

B 트리