[Index-3][Optimization] 심화 이론 (1) - B-Tree와 B+Tree

1. 들어가며

 앞서 인덱스를 '데이터를 미리 정렬해 둔 사본'이라고 설명했다. 그렇다면 데이터베이스는 이 정렬된 데이터를 단순히 선형 리스트(Linear List) 형태로 보관할까?

 

 만약 수천만 건의 데이터를 단순히 일렬로 정렬해 둔다면, 데이터를 하나 추가할 때마다 뒤에 있는 수천만 건의 데이터를 한 칸씩 밀어내야 하는 성능 재앙이 발생한다. 정렬된 리스트에서 특정 값을 찾는 이진 탐색 자체는 O(log N)으로 효율적이다. 그러나 데이터베이스 환경에서는 데이터의 삽입·삭제가 빈번하게 발생하며, 이 경우 정렬된 리스트 구조는 대규모 데이터 이동을 유발해 치명적인 성능 저하를 일으킨다.

 

 MySQL에서는 이를 해결하기 위해 B+Tree라는 자료구조를 이용한 InnoDB 엔진을 사용한다. 인덱스의 깊은 원리를 이해하기 위해, 그 기반이 되는 트리(Tree) 알고리즘의 기초 지식을 살펴보자.

---

2. 트리(Tree)

2.1. 트리 자료구조의 기초

 

트리는 이름 그대로 나무를 거꾸로 세워놓은 듯한 계층형 비선형 구조이다. 우리가 흔히 사용하는 '폴더 구조'가 대표적인 트리의 예시이다.

• 노드(Node): 데이터를 저장하는 기본 단위이다.
• 루트(Root): 트리의 맨 꼭대기에 있는 노드이다.
• 리프(Leaf): 자식이 없는 최하단의 노드이다.
• 높이(Height): 루트에서 리프까지 이르는 가장 긴 경로의 길이다.

2.2.이진 트리(Binary Tree)와 탐색 효율

 수많은 트리 종류 중 인덱스와 가장 밀접한 것은 이진 트리(Binary Tree)이다. 각 노드가 최대 2개의 자식만을 가지는 구조이다.

특히, 데이터가 왼쪽부터 차례대로 채워지는 완전 이진 트리(Complete Binary Tree)는 배열로도 효율적으로 표현이 가능하다. 우리가 트리의 '높이'에 주목해야 하는 이유는 바로 시간 복잡도 때문이다.

 

 데이터베이스에서 인덱스를 탄다는 것은, 루트 노드부터 시작해 리프 노드까지 트리의 높이만큼 내려가며 탐색한다는 의미이다.

만약 데이터의 총 개수(N)에 대해, 완전 이진 트리의 높이(h)는 대략 다음과 같다.

 

이 수식이 의미하는 바는 매우 크다. 데이터가 511개일 때 트리의 높이는 8에 불과하며, 데이터가 100만 개로 늘어나도 탐색 횟수는 단 20번 내외로 수렴한다. 이것이 인덱스가 수천만 건의 데이터 속에서도 수 밀리초(ms) 만에 결과를 반환할 수 있는 수학적 근거이다.

---

3. B-Tree: 다중 키를 통한 높이의 최소화

완전 이진 트리의 높이가 O(log N)임을 확인하였다. 이는 탐색의 안정성을 보장하지만, 실제 대규모 데이터를 다루는 데이터베이스 환경에서는 이보다 더 효율적인 자료구조가 필요하다. 이번에는 Binary Tree의 발전형 알고리즘인 Balanced Tree를 알아보자.

 

 B-Tree는 이진 탐색 트리를 확장하여 하나의 노드가 여러 개의 키를 가질 수 있도록 설계된 균형 트리이다. 모든 리프 노드가 동일한 레벨에 존재하며 다음과 같은 특징을 가진다.

• 다중 키 저장: 각 노드는 여러 개의 키를 오름차순으로 정렬하여 저장한다.
• 자식 노드 분할: 부모 노드에 저장된 키의 개수가 N개라면, 자식 노드는 최대 N+1개까지 가질 수 있다. 예를 들어, 부모 노드에 '55'와 '65'가 저장되어 있다면 자식 노드는 '55 미만', '55~65 사이', '65 초과'의 세 영역으로 나뉘어 데이터를 저장한다.
• 탐색 효율의 극대화: B-Tree의 탐색 비용은 O(log_m N)이다(m은 자식 노드의 개수인 Branching Factor). 자식이 2개뿐인 이진 트리에 비해 m의 값을 100 이상으로 크게 설정할 수 있는 B-Tree는 트리의 높이를 획기적으로 낮출 수 있다. 이는 디스크 I/O를 최소화해야 하는 시스템 환경에서 압도적인 성능 우위를 제공한다.

---

4. B+Tree: MySQL이 선택한 범위 검색의 최강자(★)

 

 

 MySQL의 InnoDB 엔진은 B-Tree를 한 단계 더 개선한 B+ Tree를 채택하여 인덱스를 관리한다. B+ Tree는 B-Tree와 유사하지만 몇 가지 결정적인 차이점이 존재한다.

• 리프 노드의 연결성: B+ Tree는 모든 리프 노드가 연결 리스트(Linked List) 형태로 서로 연결되어 있다. 이는 범위 검색 시 매우 강력한 이점을 제공한다. B-Tree는 범위 검색 시 매번 루트 노드부터 탐색을 반복해야 하지만, B+ Tree는 시작점의 리프 노드만 찾으면 이후부터는 연결된 경로를 따라 순차적으로 탐색할 수 있다.
• 데이터 저장 방식: B-Tree는 모든 노드에 실제 데이터의 주소값을 저장하는 반면, B+ Tree는 오직 리프 노드에만 실제 데이터를 저장한다. 이로 인해 중간 노드(Internal Node)의 메모리 효율이 높아져 하나의 페이지에 더 많은 인덱스 키를 담을 수 있고, 결과적으로 트리의 높이를 더 낮게 유지할 수 있다.

💡 왜 해시(Hash) 인덱스가 아닌 트리를 사용하는가?
해시 테이블은 O(1)의 시간 복잡도로 데이터를 조회할 수 있는 매우 빠른 자료구조이다. 그러나 데이터베이스에서 해시를 주력 인덱스로 사용하지 않는 이유는 범위 검색이 불가능하기 때문이다. 해시 함수는 값이 조금만 달라져도 완전히 다른 해시값을 생성하므로, "특정 기간 내의 주문 목록 조회"와 같은 범위 쿼리가 빈번한 실제 서비스 환경의 요구를 충족하지 못한다.