백엔드 개발자 면접에서 "데이터베이스 인덱스(Index)는 어떤 자료구조로 이루어져 있나요?"라는 질문에 단순히 "트리 구조입니다"라고 대답한다면 십중팔구 탈락의 고배를 마시게 됩니다. 관계형 데이터베이스(RDBMS)가 수억 건의 레코드 속에서도 0.01초 만에 원하는 데이터를 찾아내는 마법의 이면에는, 일반적인 이진 탐색 트리(BST)가 아닌 B-Tree와 그 진화형인 B+Tree라는 매우 정교하고 복잡한 자료구조가 숨어 있기 때문입니다. 오늘은 하드 디스크의 물리적 한계를 극복하고 DB 검색 속도를 극대화하기 위해 탄생한 이 두 가지 자료구조의 동작 원리와 결정적인 차이점을 완벽하게 해부해 보겠습니다.
1. 일반 이진 탐색 트리(BST)를 DB에 쓰지 않는 이유
B-Tree를 이해하기 위해서는 먼저 "왜 일반 트리를 쓰지 못할까?"라는 근본적인 의문을 해결해야 합니다.
1-1. 디스크 I/O의 치명적인 병목 현상
컴퓨터의 메모리(RAM)는 속도가 무척 빠르지만, 데이터베이스의 거대한 데이터는 전원이 꺼져도 유지되어야 하므로 속도가 훨씬 느린 하드 디스크(HDD)나 SSD에 저장됩니다. 디스크에서 데이터를 읽어올 때는 효율성을 위해 1바이트씩 읽지 않고 '블록(Block)' 또는 '페이지(Page)' 단위(보통 4KB~8KB)로 뭉텅이로 읽어옵니다.
일반 이진 탐색 트리는 자식 노드가 2개뿐이라 데이터가 많아질수록 트리의 높이(Depth)가 기하급수적으로 깊어집니다. 트리가 깊어지면 노드를 방문할 때마다 디스크 블록을 새로 읽어와야 하는 디스크 I/O(입출력)가 빈번하게 발생하여 검색 속도가 끔찍하게 느려집니다. 이를 해결하기 위해 "하나의 노드에 여러 개의 데이터를 꽉꽉 채워 넣고, 자식도 여러 명 거느리게 만들자"는 발상에서 탄생한 것이 다위 탐색 트리(Multi-way Search Tree)인 B-Tree입니다.
2. B-Tree: 뚱뚱하고 넓은 트리의 탄생
B-Tree의 'B'는 Balanced(균형)를 의미합니다. 어떤 데이터가 추가되거나 삭제되더라도, 루트 노드에서 모든 리프 노드(단말 노드)까지의 거리가 항상 동일하게 유지되도록 스스로 균형을 맞추는 영리한 자료구조입니다.
2-1. B-Tree의 핵심 구조
- 하나의 노드 안에 여러 개의 Key와 Data가 존재: 이진 트리는 노드 하나에 값이 1개지만, B-Tree는 블록 크기에 맞춰 노드 하나에 수십~수백 개의 데이터(Key-Value)를 배열처럼 오름차순으로 저장합니다.
- 자식 포인터의 확장: 노드에 Key가 $K$개 있다면, 그 노드는 자식으로 뻗어 나가는 포인터를 $K+1$개 가질 수 있습니다.
- 탐색 과정: 노드 안에서는 데이터가 정렬되어 있으므로 이진 탐색을 통해 빠르게 다음 자식 노드로 찾아 내려갑니다.
이처럼 노드를 옆으로 뚱뚱하게 늘린 덕분에, 수천만 건의 데이터도 트리의 높이가 고작 3~4층밖에 되지 않아 디스크 I/O 횟수를 획기적으로 줄일 수 있습니다.
3. B+Tree: 데이터베이스 인덱스의 실질적 표준
B-Tree도 훌륭하지만, RDBMS(MySQL, Oracle 등)에서는 거의 대부분 이를 한 번 더 개조한 B+Tree를 표준으로 사용합니다. 무엇이 아쉬워서 개조를 한 것일까요?
3-1. 범위 검색(Range Scan)의 한계 극복
데이터베이스에서는 특정 값 하나만 찾는 경우(`SELECT * FROM users WHERE age = 20`)도 있지만, 특정 범위의 데이터를 훑어야 하는 경우(`WHERE age BETWEEN 20 AND 30`)가 훨씬 많습니다. B-Tree는 데이터가 모든 노드에 흩어져 있어 범위 검색을 하려면 트리를 오르락내리락(In-order 탐색) 해야 하는 치명적인 비효율이 발생합니다.
3-2. B+Tree의 혁신적인 변화
B+Tree는 이 범위 검색 문제를 완벽하게 해결했습니다.
- 모든 실제 데이터는 리프 노드(맨 밑바닥)에만 저장: 가지 역할을 하는 내부 노드(Internal Node)에는 길잡이 역할을 하는 'Key(키)'만 저장하고 실제 데이터는 없습니다. 오직 맨 끝 리프 노드에만 실제 데이터 포인터가 존재합니다.
- 내부 노드의 용량 극대화: 데이터를 빼버린 덕분에 한 노드에 훨씬 더 많은 Key를 담을 수 있게 되어, 트리의 높이가 B-Tree보다 더욱 얕아집니다.
- 리프 노드 간의 연결 리스트(Linked List): 가장 중요한 차이점입니다. 맨 밑바닥 리프 노드끼리는 옆으로 이동할 수 있도록 포인터로 연결되어 있습니다. 따라서 범위 검색을 할 때, 루트에서 시작해 원하는 시작점의 리프 노드만 찾으면, 그다음부터는 연결 리스트를 타고 옆으로 쭉 훑기만 하면 끝납니다. (초고속 순차 탐색)
1. B-Tree는 하나의 노드에 여러 개의 데이터를 담아 트리의 높이를 낮추고 디스크 I/O를 최소화한 균형 트리입니다.
2. B+Tree는 B-Tree를 개조하여 모든 실제 데이터를 리프 노드에만 몰아넣은 DB 인덱스의 표준 구조입니다.
3. B+Tree는 리프 노드끼리 연결 리스트로 이어져 있어, 데이터베이스의 필수 기능인 범위 검색(Range Scan)에 압도적인 성능을 냅니다.