Source: Dev.to

B-Tree 인덱스가 SQL 데이터베이스에서 어떻게 동작하는지 – 직관적인 가이드

개요

데이터베이스에서 인덱스는 테이블에 저장된 데이터를 빠르게 찾을 수 있게 해 주는 데이터 구조입니다. 가장 널리 사용되는 인덱스 유형은 B-Tree(균형 트리)이며, 이는 거의 모든 관계형 데이터베이스 시스템(MySQL, PostgreSQL, SQL Server, Oracle 등)에서 기본 인덱스 구현으로 사용됩니다. 이 글에서는 B-Tree 인덱스가 어떻게 구성되고, 검색·삽입·삭제 연산을 수행하는지 직관적으로 설명합니다.

B-Tree 기본 개념

• 균형 트리: 모든 리프 노드가 같은 깊이에 위치해 있어, 최악의 경우에도 트리 높이가 일정합니다. 따라서 검색 시 O(log N)의 시간 복잡도를 보장합니다.
• 노드: 각 노드는 **키(key)**와 포인터(pointer)(또는 자식 노드에 대한 레퍼런스)를 포함합니다.
• 차수(order): 한 노드가 가질 수 있는 최대 자식 수를 의미합니다. 일반적으로 디스크 페이지 크기와 레코드 크기에 맞춰 자동으로 결정됩니다.

B-Tree 구조

[ 내부 노드 ] ──► [ 내부 노드 ] ──► … ──► [ 리프 노드 ]
   (키, 포인터)      (키, 포인터)                (키, 레코드 포인터)

• 루트(root): 트리의 최상위 노드. 트리 높이가 1이면 루트가 동시에 리프가 됩니다.
• 내부 노드(internal node): 검색 경로를 좁히는 역할을 하며, 키와 자식 노드에 대한 포인터를 가집니다.
• 리프 노드(leaf node): 실제 데이터 레코드(또는 레코드 위치)를 가리키는 포인터를 포함합니다. 대부분의 구현에서는 리프 노드가 링크드 리스트 형태로 연결돼 있어 순차 스캔이 가능합니다.

검색(Search) 과정

1. 루트에서 시작: 검색하고자 하는 값 v와 루트 노드의 키들을 비교합니다.
2. 범위 선택: v가 k1 ≤ v < k2 와 같은 구간에 속하면, 해당 구간에 연결된 자식 포인터를 따라갑니다.
3. 반복: 위 과정을 리프 노드에 도달할 때까지 반복합니다.
4. 리프에서 확인: 리프 노드에 도착하면, v와 정확히 일치하는 키가 있는지 확인하고, 있다면 해당 레코드 포인터를 반환합니다.

예시

SELECT * FROM users WHERE email = 'alice@example.com';

위 쿼리는 email 컬럼에 B-Tree 인덱스가 존재한다면, 루트 → 내부 노드 → 리프 노드 순으로 탐색해 해당 레코드 위치를 바로 찾습니다.

삽입(Insert) 과정

1. 검색: 삽입하려는 키 k가 들어갈 리프 노드를 찾습니다.
2. 삽입: 리프 노드에 k를 삽입합니다. 노드에 여유 공간이 있으면 바로 삽입됩니다.
3. 분할(Split): 리프 노드가 가득 차면, 노드를 두 개로 분할하고 중간 키를 부모 노드에 올립니다.
4. 재귀적 분할: 부모 노드도 가득 차면 같은 과정을 반복합니다. 최악의 경우 루트가 분할돼 트리 높이가 1 증가합니다.

삭제(Delete) 과정

1. 검색: 삭제하려는 키 k가 있는 리프 노드를 찾습니다.
2. 삭제: 리프 노드에서 k를 제거합니다.
3. 언밸런스 해결: 노드에 최소 개수 이하의 키가 남으면, **형제 노드와 병합(merge)**하거나 **키를 재분배(redistribute)**합니다.
4. 재귀적 조정: 병합이 발생하면 부모 노드에서도 키가 부족해질 수 있어, 위로 올라가면서 동일한 과정을 수행합니다.

장점

단점

실제 사용 팁

1. 선택도(Selectivity) 고려: 컬럼의 고유값 비율이 높을수록 인덱스 효율이 좋습니다. (email, uuid 등)
2. 복합 인덱스: 여러 컬럼을 조합한 인덱스는 앞쪽 컬럼이 가장 선택도가 높아야 효과적입니다.
3. 커버링 인덱스: 인덱스에 필요한 모든 컬럼을 포함시켜 SELECT 시 테이블에 접근하지 않게 하면 성능이 크게 향상됩니다.
4. 정기적인 재구성: 대량 삭제·삽입이 반복된 테이블은 인덱스 파편화가 발생할 수 있으니 REINDEX(PostgreSQL)·ALTER INDEX REBUILD(SQL Server) 등을 주기적으로 수행합니다.

결론

B-Tree 인덱스는 균형 잡힌 트리 구조 덕분에 대규모 데이터에서도 일관된 검색 성능을 제공하며, 대부분의 관계형 데이터베이스에서 기본 인덱스 구현으로 채택되고 있습니다. 삽입·삭제 시 발생하는 트리 재조정 비용을 이해하고, 컬럼 선택도와 쿼리 패턴을 고려해 적절히 설계한다면 데이터베이스 성능을 크게 향상시킬 수 있습니다.

---

이 가이드는 B-Tree 인덱스의 핵심 원리를 직관적으로 설명하기 위해 작성되었습니다. 보다 깊이 있는 구현 세부 사항은 각 DBMS의 공식 문서를 참고하세요.

왜 인덱스가 존재하는가 (실제 문제)

관계형 데이터베이스는 대량의 데이터를 신뢰성 있게 저장하도록 최적화되어 있지만, 기본적으로 그 데이터를 효율적으로 검색하도록 최적화되어 있지는 않습니다. 인덱스 없이 특정 행을 찾도록 데이터베이스에 요청하면 전체 테이블 스캔을 수행하게 되며, 이는 모든 행을 하나씩 살펴보는 방식입니다. 작은 규모에서는 작동하지만 데이터가 증가할수록 매우 느려집니다.

인덱스는 이러한 무차별 탐색을 피하기 위해 존재합니다. 모든 행을 검사하는 대신, 인덱스를 사용하면 데이터베이스가 일치하는 데이터가 어디에 있는지 빠르게 좁혀갈 수 있습니다.

B‑Tree 인덱스는 대부분의 SQL 데이터베이스(PostgreSQL, MySQL/InnoDB, SQL Server, Oracle)에서 기본 선택이며, 데이터를 정렬된 상태로 유지하면서 삽입 및 업데이트를 제어되고 예측 가능한 방식으로 지원합니다.

직관적으로 보면, 1천만 행이라도 B‑Tree 인덱스는 단일 값을 찾기 위해 보통 몇 번의 비교 단계만 필요합니다. 행을 찾는 과정은 수백만 개의 항목을 스캔하는 것이 아니라 몇 번의 목표된 점프에 불과합니다. 쓰기 작업에는 오버헤드가 따릅니다—각 삽입이 이 구조를 유지해야 하지만, 그 비용은 천천히 증가하므로 B‑Tree는 매우 뛰어난 확장성을 제공합니다.

B‑트리가 해결하는 문제

B‑트리는 다음과 같은 저장 시스템을 위해 특별히 설계되었습니다:

• 범위 쿼리와 정렬을 위해 데이터를 정렬된 상태로 유지
• 로그 시간 검색 제공 (O(log n))
• 얕고 넓게 설계하여 디스크 I/O 최소화
• 국부적인 노드 분할을 통한 효율적인 쓰기 지원

핵심 제약: 데이터베이스는 개별 행이 아니라 페이지 단위로 데이터를 읽습니다.

Source: …

페이지: 데이터베이스가 실제로 데이터를 저장하는 방식

B‑트리를 논하기 전에 한 가지 기본 개념을 이해하는 것이 도움이 됩니다: 데이터베이스는 페이지를 사용한다는 점입니다.

• 페이지는 고정 크기의 데이터 블록이며(보통 8 KB)
• 데이터베이스가 무언가(행, 인덱스 항목, 포인터 등)를 필요로 할 때는 해당 항목이 포함된 전체 페이지를 읽어들입니다.

이는 다음에 적용됩니다:

• 테이블 데이터(실제 행)
• 인덱스 데이터(B‑트리 노드)

성능 목표는 간단합니다: 페이지를 읽을 때 가능한 한 많은 유용한 작업을 수행하는 것. B‑트리 노드는 하나의 페이지 안에 깔끔하게 들어가도록 설계되어, 데이터베이스가 디스크에 접근할 때마다 큰 진전을 이룰 수 있습니다. 이 페이지 기반 모델 때문에 B‑트리는 교과서에 나오는 이진 트리와 매우 다르게 보입니다.

Source:

B‑Tree 구조 (고수준)

B‑Tree는 세 개의 계층으로 구성됩니다:

1. 루트 노드 – 모든 검색의 시작점
2. 내부 노드 – 탐색에 사용되는 표지판
3. 리프 노드 – 실제 데이터(또는 포인터)가 존재하는 최하위 계층

특성

• 정렬된 키 – 노드 내부의 키는 항상 순서대로 유지됩니다
• 높은 팬‑아웃 – 각 노드에 많은 키가 포함됩니다(종종 수백 개), 두 개만 있는 것이 아닙니다
• 균형 잡힌 깊이 – 모든 리프 노드가 정확히 같은 깊이에 있어, 찾고자 하는 키와 관계없이 예측 가능한 성능을 보장합니다

내부 노드 vs. 리프 노드

• 내부 노드는 키와 자식 페이지에 대한 포인터를 포함하며, 순수하게 탐색용으로 사용됩니다.
• 리프 노드는 키와 실제 행에 대한 포인터를 포함합니다.

구현 세부 사항은 다음과 같이 다릅니다:

리프 노드들은 보통 좌‑우로 연결되어 있어, 데이터베이스가 루트로 다시 올라가지 않고도 범위 스캔을 수행할 수 있습니다.

조회가 작동하는 방식

다음 쿼리를 고려해 보세요:

SELECT * FROM users WHERE email = 'a@b.com';

1. 루트 페이지에서 시작합니다.
2. 검색 키를 노드에 있는 키와 비교하여 올바른 범위를 찾습니다.
3. 자식 포인터를 따라 다음 페이지로 이동합니다.
4. 리프 노드에 도달할 때까지 반복합니다.
5. 행 포인터(또는 행 자체)를 가져옵니다.

각 단계는 페이지 읽기이며, 행‑별 연산이 아닙니다.

왜 B‑Tree 높이는 작게 유지되는가

각 노드가 많은 키를 보유하기 때문에 트리는 넓게 성장하고, 높게는 성장하지 않습니다.

전형적인 수치:

• 페이지 크기: 8 KB
• 키 + 포인터: ~40 bytes
• 노드당 키 수 (fan‑out): ~200

높이가 3인 트리는 다음을 지원할 수 있습니다:

200³ ≈ 8,000,000 entries

따라서 B‑Tree 조회는 대규모에서도 매우 빠르게 유지됩니다.

삽입 및 노드 분할

새로운 행을 삽입할 때, 데이터베이스는 B‑Tree를 업데이트해야 합니다:

1. 올바른 리프 노드를 찾습니다.
2. 노드에 공간이 있으면 키를 삽입합니다 (간단).
3. 노드가 가득 차면 분할하여 두 개의 노드로 나눕니다.
4. 중간 키를 부모 노드로 승격시킵니다.
5. 분할은 루트까지 위로 전파될 수 있지만, 실제로는 드뭅니다.

이 균형 맞추기 작업은 향후 읽기 작업을 효율적으로 유지하기 위해 지불하는 세금입니다.

범위 쿼리와 정렬

B‑Trees가 키를 정렬된 상태로 유지하기 때문에 효율적인 범위 스캔이 가능합니다:

SELECT * FROM orders
WHERE created_at BETWEEN '2025-01-01' AND '2025-01-31';

• 표준 조회를 사용해 첫 번째 키('2025‑01‑01')를 찾습니다.
• 범위의 끝에 도달할 때까지 연결된 리프 노드를 순차적으로 탐색합니다.

결과:

• B‑Trees는 ORDER BY를 기본적으로 지원합니다.
• 접두사 스캔을 지원합니다(예: LIKE 'abc%').
• 해시 인덱스는 이들 중 어느 것도 할 수 없습니다.

복합 인덱스

여러 열에 대해 인덱스를 생성할 때, 예를 들어 (user_id, created_at)와 같이 하면 B‑Tree는 먼저 user_id로, 그 다음 created_at으로 정렬합니다. 이러한 정렬 순서는 선행 열에 대해 필터링하는 쿼리가 인덱스의 이점을 얻을 수 있게 하며, 선행 열이 고정된 경우 후행 열에 대한 효율적인 범위 스캔도 가능하게 합니다.

B‑Tree 인덱스: 빛을 발할 때와 그렇지 않을 때

B‑Tree 작동 방식

• 구조 – 각 노드가 키 값 범위와 자식 페이지에 대한 포인터를 보유하는 균형 잡힌 트리.
• 검색 – 루트에서 시작해 적절한 자식 포인터를 따라가며, 대상 키가 포함된 리프 페이지에 도달할 때까지 반복한다.
• 복잡도 – O(log N) 페이지 읽기, 여기서 N은 행 수이다. 페이지는 기본 스토리지(예: 8 KB)에 맞게 크기가 정해지므로, 매우 큰 테이블에서도 트리 높이는 낮게 유지된다.

일반적인 사용 사례

복합 (다중 컬럼) 인덱스

복합 인덱스는 정의된 순서대로 컬럼을 저장한다.
예시: CREATE INDEX ix_user_created ON events (user_id, created_at);

• 효율적인 경우

  • WHERE user_id = ?
  • WHERE user_id = ? AND created_at > ? (선행 컬럼이 사용되고, 두 번째 컬럼이 범위를 좁힌다)

• 비효율적인 경우

  • WHERE created_at = ?만 사용할 때 – created_at이 선행 컬럼이 아니므로 인덱스를 활용할 수 없다.

비유: (성, 이름) 순으로 정렬된 전화번호부를 생각해 보라. “Smith”라는 성을 찾는 것은 아주 쉽지만, “John”이라는 이름만으로 바로 찾아가려면 전체 책을 스캔해야 한다.

일반적인 오해

B‑Tree가 잘못된 선택인 경우

다음 상황에서는 B‑Tree 인덱스를 피하십시오:

1. 낮은 카디널리티 – 예: 행의 90 %가 is_active = true인 경우. 옵티마이저는 인덱스와 테이블을 모두 읽는 것이 비용이 더 크기 때문에 전체 테이블 스캔을 선호하는 경우가 많습니다.
2. 고빈도 동등성 전용 조회가 고유 키에만 적용되는 경우 – 해시 인덱스가 더 빠를 수 있습니다(다만 유연성은 떨어집니다).
3. 추가 전용 / 시계열 데이터 – 행이 시간 순으로 자연스럽게 정렬되고 테이블이 방대할 경우 **BRIN (Block Range Indexes)**을 고려하십시오.
4. 전체 텍스트 검색 – 큰 텍스트 필드 안의 단어를 검색하도록 설계된 GIN 또는 기타 역인덱스를 사용하십시오.

Practical Takeaways

• B‑Trees는 페이지‑최적화되어 있으며, CPU 사이클보다 디스크 I/O를 최소화하는 것을 목표로 합니다.
• 트리 높이는 전체 행 수보다 더 중요합니다; 얕은 트리는 빠른 조회를 제공합니다.
• 복합 인덱스에서 컬럼 순서는 매우 중요합니다; 인덱스가 유용하려면 선행 컬럼이 쿼리의 WHERE 절에 포함되어야 합니다.
• 새로운 인덱스를 추가하기 전에 항상 읽기‑대‑쓰기 비율을 고려하세요—인덱스가 많을수록 읽기는 빨라지지만 쓰기는 느려집니다.