db · 03

인덱스

DB인덱스B-Tree

인덱스는 데이터를 정렬된 트리(B-Tree) 구조로 따로 관리해서, 특정 값을 찾을 때 테이블 전체를 뒤지지 않고 트리를 몇 단계만 타고 내려가도록 해주는 자료구조입니다. 인덱스가 없으면 원하는 값을 찾기 위해 처음부터 끝까지 한 행씩 확인해야 합니다(Full Table Scan) — 인덱스는 바로 이 비교 횟수를 극적으로 줄여줍니다.

핵심 개념

B-Tree 구조

루트 노드가 기준값을 갖고 자식 방향을 정하고, 리프 노드에 실제 값이 정렬된 채로 나뉘어 저장됩니다.

핵심 개념

Full Table Scan

인덱스가 없을 때 사용하는 방식으로, 조건에 맞는 행을 찾기 위해 테이블의 모든 행을 처음부터 순서대로 확인합니다. O(n).

핵심 개념

인덱스 탐색

루트에서 기준값과 비교해 방향을 정하고, 해당 리프 하나만 확인합니다. 나머지 리프는 아예 들여다보지 않습니다. O(log n).

핵심 개념

정렬 순서 유지

B-Tree는 항상 왼쪽 자식 < 자신의 키 ≤ 오른쪽 자식 순서를 유지합니다. 그래서 "더 크다/작다"만으로 방향을 정할 수 있습니다.

핵심 개념

인덱스의 비용

인덱스는 공짜가 아닙니다 — 데이터를 추가·수정·삭제할 때마다 트리도 함께 갱신해야 해서, 쓰기 성능은 오히려 느려질 수 있습니다.

핵심 개념

어떤 컬럼에 걸어야 할까

WHERE·JOIN·ORDER BY에 자주 쓰이는 컬럼이 좋은 후보입니다. 반대로 거의 조회하지 않는 컬럼에 거는 인덱스는 쓰기 비용만 늘립니다.

같은 값을 두 방식으로 찾아보세요 — 이 시각화는 정확히 같은 target 값을 "풀 스캔" 탭과 "인덱스 탐색" 탭에서 각각 찾습니다. 비교 횟수와, 무엇보다 "몇 개의 노드/값을 들여다봤는지"를 비교해보세요.

작은 예제라 차이가 작아 보일 수 있습니다 — 여기서는 값이 12개뿐이라 7번 vs 6번으로 큰 차이가 안 나 보이지만, 실제 테이블처럼 수만~수백만 건이 되면 풀 스캔은 그 수만큼 늘어나고 인덱스는 트리 단계 수(대개 몇 단계)만큼만 늘어납니다.

인덱스 탐색에서 건너뛴 리프에 주목하세요 — 루트에서 방향을 정하고 나면 나머지 리프들은 확인할 필요가 전혀 없습니다. 이렇게 "안 봐도 되는 데이터"를 통째로 건너뛰는 것이 인덱스의 핵심 아이디어입니다.

이 시각화에서 확인할 것 — "인덱스 구조" 탭에서 루트/리프 용어와 정렬 순서를 먼저 익히고, "풀 스캔"과 "인덱스 탐색" 탭에서 같은 값을 찾는 과정을 STEP으로 하나씩 비교해보세요.

B-Tree가 쓰이는 이유

정렬된 배열은 이진 탐색으로 빠르게 찾지만 중간에 끼워 넣을 때마다 뒤를 모두 밀어야 합니다. B-Tree는 한 노드에 키를 여러 개 담는 균형 트리라서, 삽입과 삭제 뒤에도 트리 높이를 낮게 유지하면서 정렬 순서를 지킵니다. 노드 하나가 디스크 페이지 하나에 대응하도록 만들 수 있어서, 디스크에서 읽는 횟수를 줄이는 데 맞는 구조입니다. 이 구조는 Bayer와 McCreight가 1970년대 초에 제안한 것으로 알려져 있고, 많은 데이터베이스가 이 B-Tree 계열(리프에 데이터 위치를 두는 B+Tree형)을 씁니다.

숫자로 확인하기

트리 높이 계산(설명용 가정) — 8KB 페이지에 키와 포인터를 합쳐 16바이트씩 넣는다고 가정하면 노드 하나에 약 512개를 담습니다. 512개씩 갈라지는 트리는 3단계로 512³ = 134,217,728건(약 1.3억)까지 가리킵니다. 그래서 수백만 건이어도 몇 단계만 내려가면 됩니다.

풀 스캔과의 비교 — 100만 건에서 풀 스캔은 최대 100만 번 비교하고, 이진 탐색 방식의 비교는 log₂(1,000,000) ≈ 20번입니다. B-Tree는 한 노드 안에서 여러 키를 한 번에 읽으므로 디스크 읽기는 트리 높이 수준입니다.

자주 하는 오해

WHERE에 컬럼이 있으면 항상 인덱스를 탄다 — 컬럼에 함수를 씌우면 일반 인덱스를 쓰지 못할 수 있습니다. PostgreSQL 문서는 lower(col1) = 'value' 조건이 col1 일반 인덱스를 쓰지 못하고, lower(col1)에 만든 인덱스(표현식 인덱스)가 있으면 쓸 수 있다고 안내합니다.

LIKE는 어디에 와일드카드가 있어도 인덱스를 쓴다 — B-Tree 인덱스는 패턴이 문자열 맨 앞에서 고정된 상수일 때(LIKE 'abc%') 쓸 수 있고, LIKE '%abc'처럼 앞이 열려 있으면 쓸 수 없습니다.

복합 인덱스는 컬럼 순서와 상관없다 — 복합 인덱스는 앞쪽(선두) 컬럼에 조건이 있을 때 가장 효율적입니다. PostgreSQL 문서는 선두 컬럼이 아닌 컬럼만으로도 쓸 수는 있지만 효율이 떨어진다고 설명합니다.

인덱스는 많을수록 좋다 — 인덱스마다 쓰기 때 갱신해야 하고 저장 공간도 차지합니다. 조회에 거의 쓰이지 않는 인덱스는 비용만 늘립니다.

면접에서 이렇게 물어요

면접 질문

왜 인덱스에 해시 테이블이 아니라 B-Tree를 많이 쓰나요?

해시는 같은 값 찾기(=)에는 빠르지만 정렬 순서가 없어 범위 조회(BETWEEN, <, >)와 정렬(ORDER BY)에 쓰기 어렵습니다. B-Tree는 정렬된 순서를 유지해서 같은 값과 범위를 모두 지원합니다.

면접 질문

복합 인덱스에서 컬럼 순서는 어떻게 정하나요?

자주 조건으로 쓰는 컬럼, 특히 같음(=) 조건에 쓰는 컬럼을 앞에 둡니다. 선두 컬럼에 조건이 없으면 인덱스를 효율적으로 쓰기 어렵기 때문입니다.

면접 질문

커버링 인덱스란 무엇인가요?

쿼리에 필요한 컬럼이 모두 인덱스에 들어 있어 테이블 본체를 읽지 않고 인덱스만으로 답하는 경우입니다. PostgreSQL은 이를 인덱스 전용 스캔(index-only scan)이라고 부릅니다. 다만 해당 페이지가 모두 보이는(all-visible) 상태로 기록되어 있어야 테이블 확인을 건너뛸 수 있어서, 항상 본체를 안 읽는 것은 아닙니다.

면접 질문

인덱스를 걸면 INSERT가 느려지는 이유는 무엇인가요?

행을 넣을 때 테이블뿐 아니라 걸려 있는 모든 인덱스에도 새 키를 정렬된 위치에 넣어야 해서 작업이 늘어납니다.

실제 시스템에서는

PostgreSQL의 인덱스 사용 확인 — pg_stat_user_indexes 뷰의 idx_scan 값으로 인덱스가 스캔된 횟수를 볼 수 있습니다(IN이나 OR 조건에서는 쿼리 하나가 여러 번으로 셀 수 있습니다). 한 번도 쓰이지 않은 인덱스는 정리 후보로 볼 수 있습니다.

이 사이트의 태그 조회 — topic_tag 테이블에는 조회용 인덱스 두 개가 걸려 있습니다(docs/ddl.sql). 태그와 토픽으로 찾는 조회가 풀 스캔이 되지 않게 하기 위한 것입니다.

기본키와 인덱스 — PostgreSQL에서 기본키를 선언하면 유일성을 보장하는 B-Tree 인덱스가 자동으로 만들어집니다.

함께 보면 좋은 토픽

쿼리 실행 계획 — 옵티마이저가 인덱스를 쓸지 풀 스캔을 할지 고르는 기준을 봅니다.

SQL JOIN — 조인 조건 컬럼에 인덱스가 왜 중요한지 이어서 봅니다.

RDBMS 기초 — 기본키와 UNIQUE가 인덱스로 구현되는 배경을 봅니다.

트리 — B-Tree의 바탕이 되는 트리 구조를 봅니다.

전문 검색(역색인) — 단어에서 그 단어가 든 문서를 바로 찾는 역색인을 봅니다.

참고 자료

PostgreSQL 인덱스 — Indexes — PostgreSQL Documentation

인덱스 전용 스캔 — Index-Only Scans and Covering Indexes — PostgreSQL Documentation

원 논문 — Bayer, McCreight, "Organization and Maintenance of Large Ordered Indexes", Acta Informatica, 1972

교재 — Silberschatz, Korth, Sudarshan, "Database System Concepts" 7판, "Indexing" 장

SQL — 인덱스 생성과 EXPLAIN으로 확인하기

-- email 컬럼에 인덱스 생성
CREATE INDEX idx_users_email ON users(email);

-- 인덱스 적용 전: type = ALL → 풀 스캔(이 시각화의 "풀 스캔" 탭과 동일)
EXPLAIN SELECT * FROM users WHERE email = '[email protected]';

-- 인덱스 적용 후: type = ref → 인덱스 탐색(이 시각화의 "인덱스 탐색" 탭과 동일)
EXPLAIN SELECT * FROM users WHERE email = '[email protected]';

EXPLAIN의 type 컬럼이 ALL이면 테이블 전체를 훑었다는 뜻이고, ref·range·const 등이면 인덱스를 탄 것입니다.
rows 컬럼(예상 스캔 행 수)도 함께 보면, 인덱스 적용 전후로 이 시각화의 "비교 횟수"에 해당하는 수치가 실제로 얼마나 줄어드는지 확인할 수 있습니다.

Java — JPA Entity에 인덱스 선언하기

@Entity
@Table(
    name = "users",
    indexes = {
        @Index(name = "idx_users_email", columnList = "email")
    }
)
public class User {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;              // PK는 기본적으로 이미 인덱스가 걸려 있음

    @Column(nullable = false, unique = true)
    private String email;         // 자주 WHERE에 쓰이므로 인덱스 후보
}

@Table(indexes = ...)는 엔티티 기준 DDL 자동 생성 시 인덱스를 함께 만들어 줍니다 — 이 프로젝트처럼 스키마를 직접 SQL로 관리한다면 위의 CREATE INDEX 문이 실제로 적용되는 부분입니다.
기본키(@Id)는 대부분의 DBMS에서 자동으로 인덱스가 생성되므로, 이 시각화의 B-Tree는 사실 id 같은 기본키 조회에도 이미 똑같이 적용되고 있는 구조입니다.

SQL — 복합 인덱스와 컬럼 순서(최左 접두 규칙)

-- (user_id, product) 순서로 복합 인덱스 생성
CREATE INDEX idx_orders_user_product ON orders(user_id, product);

-- OK: 인덱스를 탄다 (맨 앞 컬럼 user_id로 시작)
SELECT * FROM orders WHERE user_id = 1 AND product = '노트북';
SELECT * FROM orders WHERE user_id = 1;

-- 인덱스를 타지 못함: product만으로는 루트에서 방향을 정할 수 없음
SELECT * FROM orders WHERE product = '노트북';

이 시각화의 B-Tree 루트가 user_id 하나만 기준값으로 갖고 있듯, 복합 인덱스도 맨 앞 컬럼(user_id) 없이는 트리를 어느 쪽으로 내려가야 할지 정할 수 없습니다.
그래서 마지막 쿼리처럼 뒤쪽 컬럼(product)만으로 조회하면 이 인덱스를 전혀 활용하지 못하고 풀 스캔으로 돌아갑니다.

B-Tree 인덱스가 탐색 속도를 높이는 원리는?

이진 탐색 트리와 비슷하게 절반씩 좁혀갑니다.

B-Tree 인덱스는 값을 정렬된 트리 구조로 저장해, 루트에서부터 비교하며 탐색 범위를 매번 좁혀 O(log n)에 가까운 속도로 원하는 데이터를 찾습니다.

인덱스를 걸면 항상 조회 성능이 좋아지는 것은 아닌 이유는?

인덱스 스캔도 공짜가 아닙니다 — 흩어진 행을 찾아가는 비용이 있습니다.

조건에 맞는 행 비율(선택도)이 높으면 인덱스를 타고 흩어진 행을 일일이 찾아가는 것보다 테이블을 순서대로 읽는 풀 스캔이 더 빠를 수 있습니다.

인덱스를 추가할 때 감수해야 하는 비용은?

인덱스도 데이터라서 최신 상태로 유지해야 합니다.

인덱스는 조회를 빠르게 하지만, 데이터가 변경될 때마다 인덱스 구조도 함께 갱신해야 하므로 쓰기 성능이 느려지고 추가 저장 공간이 필요합니다.