인덱스 개념 정리 (B+Tree 중심)

인덱스란?

인덱스(Index)는 테이블 전체를 탐색하지 않고 원하는 데이터를 빠르게 조회하기 위해 사용하는 검색용 데이터 구조입니다. 마치 책의 목차처럼, 특정 값을 빠르게 찾아가기 위한 일종의 검색 도우미 역할을 합니다.

인덱스 탐색은 무엇이 좋은가?

인덱스를 활용한 탐색과 단순 테이블 전체 탐색은 성능 면에서 큰 차이를 보입니다. 일반적으로 찾고자 하는 데이터는 디스크에 저장되어 있는데 인덱스 기반 탐색은 조건에 맞는 데이터만 디스크에서 읽어 온다. 반면 인덱스가 없는 경우에는 테이블의 모든 행을 순차적으로 읽어야 하며, 이는 I/O 비용을 크게 증가시킵니다.

탐색 방식	설명
인덱스 기반 탐색	인덱스에 따라 조건에 맞는 값만 찾아 디스크 접근
테이블 풀스캔	인덱스가 없을 경우, 디스크에서 전체 데이터를 읽어와서 모든 데이터를 확인

WHERE email = 'abc@example.com'
→ email에 인덱스가 없다면 테이블 전체를 읽고 비교 → 성능 저하

인덱스의 구조: B+Tree

대부분의 RDBMS(MySQL, PostgreSQL, Oracle 등)는 인덱스를 B+Tree 구조로 구현되어 있다.

B+Tree란?

B+Tree는 정렬된 키를 기반으로 구성된 트리 구조이다. 키는 인덱스를 생성하기 위해 지정한 컬럼 값을 의미한다. B+Tree는 루트, 내부, 리프 노드로 구성되어 있으며 각 노드들은 키를 갖고 있다. 루트 및 내부 노드에 저장된 키는 탐색 경로를 결정하는 데 사용된다. 리프 노드에는 검색 대상이 되는 키와 함께 해당 row를 식별할 수 있는 rowid나 PK 등의 위치 정보가 저장되어 있으며, 이를 통해 테이블에서 실제 데이터를 조회할 수 있습니다.

B+Tree 예시

아래와 같은 데이터가 DB에 저장되어 있다고 가정해보자. 데이터에서 product_code 컬럼에 인덱스를 생성한 경우 인덱스는 아래 이미지와 같은 구조로 구성되어 있다.

id	product_code	name	category	price	stock_quantity	released_date
1	A	AirPods Pro	Audio	249	100	2023-01-01
2	B	Galaxy Buds	Audio	149	75	2023-02-10
3	C	Sony WH-1000XM5	Audio	399	50	2022-10-20
4	D	iPhone 15	Phone	1199	20	2023-09-01
5	E	Galaxy S23	Phone	1099	35	2023-04-15
...	...	...	...	...	...	...
18	R	Kindle	Tablet	129	0	2021-12-12

노드 종류

B+Tree는 총 3가지 노드로 구성되어 있습니다. 루트 노드와 내부 노드는 데이터의 위치를 알고 있는 리프 노드까지의 경로를 안내하는 역할을 합니다. 내부 노드에서 검색 키와 일치하는 값을 찾았더라도, B+Tree에서는 반드시 리프 노드까지 내려가야 합니다. 리프노드가 실제 찾고자 하는 데이터의 위치를 알고 있기 때문이다.

노드 종류	역할
루트 노드	트리의 시작점. 탐색 방향 결정
내부 노드	중간 분기 노드. 키 비교로 자식 노드 결정
리프 노드	실제 인덱스 키 + 데이터 주소(ROWID 또는 PK) 저장

인덱스 탐색 흐름

SELECT * FROM products WHERE product_code = 'A';

1. 루트 노드부터 시작해 `A` 값에 해당하는 방향을 따라감
2. 내부 노드를 지나 리프 노드에 도달
3. 리프 노드에서 `A` 키를 찾고, 해당 rowid 또는 PK 값 획득
4. 테이블에서 해당 row를 찾아서 최종 결과 반환

왜 "Balanced Tree"라고 부르는가?

B+Tree는 모든 리프 노드가 동일한 깊이를 갖습니다. 깊이가 더 깊거나 짧은 노드는 존재하지 않습니다. 노드 간 깊이가 균일 하기 때문에 Balanced Tree라고 합니다.

B+Tree vs B-Tree 차이

B+Tree를 검색해보면 B-Tree라는 트리구조도 찾아볼 수 있다. B+Tree는 B-Tree에서 개선된 트리구조 입니다. B-Tree는 상용 디비에서 사용되는 데이터 구조는 아닙니다. B+Tree가 리프노드에만 데이터 포인터를 갖는 반면 B-Tree는 루트 및 내부 노드에도 **데이터와 연결된 포인터를 함께 저장**할 수 있어, 중간 노드에서 탐색이 종료되기도 합니다. 반면, B+Tree는 모든 실제 데이터 접근은 리프 노드를 통해서만 이루어지며, 루트/내부 노드는 탐색 경로만 담당합니다. 또한, B-Tree는 리프노드간 서로 연결되어 있지 않습니다. 때문에 범위 탐색(D ~ F 탐색을 하고자 하는 경우)을 하는 경우 루트 노드까지 올라가서 탐색을 다시 시작해야 합니다.

항목	B-Tree	B+Tree
데이터 저장 위치	루트, 내부, 리프 노드 모두 가능	✅ 리프 노드에만 저장
리프 노드 연결	❌ 없음	✅ Linked List로 연결
범위 탐색 성능	❌ 비효율적	✅ 매우 효율적
정렬된 순회	반복적 탐색 필요	✅ 리프 순회로 O(k) 처리 가능
실제 DB 사용 여부	거의 없음	✅ MySQL, PostgreSQL, Oracle 등 실무 사용

범위 탐색이란? 범위 탐색이 빠른 이유

범위 탐색 이란?

범위 탐색이란 WHERE 절이나 정렬 구문에서 지정된 범위에 해당하는 여러 값을 한 번에 조회하는 쿼리를 말합니다.

예를 들어:

SELECT * FROM users WHERE score BETWEEN 80 AND 90;

또는

SELECT * FROM products WHERE name LIKE 'galaxy%';

이처럼 조건에 해당하는 다수의 값을 연속적으로 탐색해야 할 때, 인덱스의 구조에 따라 성능 차이가 크게 납니다.

B+Tree에서 범위 탐색이 빠른 이유

B+Tree의 리프 노드는 인덱스 키 순으로 정렬되어 있을 뿐만 아니라, 서로 Linked List처럼 좌우로 연결되어 있습니다. 즉, 범위 탐색 시 시작 위치만 찾으면, 그 이후로는 다음 노드를 순차적으로 따라가기만 하면 됩니다.
예를 들어

SELECT * FROM products WHERE product_code BETWEEN 'C' AND 'H';

• C가 포함된 리프 노드를 먼저 찾음
• 이후 D, E, F, G, H는 리프 노드를 순차 순회하면서 한 번에 탐색됨
• 다시 루트로 올라갈 필요 없음 → 매우 빠름
• BETWEEN, LIKE 'abc%', ORDER BY, LIMIT에 최적화

클러스터형 인덱스 VS 보조 인덱스

클러스터형 인덱스(Clustered Index)는 인덱스 자체가 테이블 데이터를 포함하고 있어, 리프 노드에 전체 row 데이터가 저장됩니다.
보조 인덱스(Secondary 또는 Non-clustered Index)는 인덱스에 정렬된 키와 해딩 row를 찾기 위한 위치 정보(rowid 또는 PK)만 저장하며 실제 데이터를 조회하려면 테이블을 다시 접근해야 합니다.

구분	클러스터형 인덱스 (Clustered Index)	보조 인덱스 (Secondary / Non-clustered Index)
정의	인덱스 순서 = 데이터의 저장 순서	인덱스 순서 ≠ 데이터의 저장 순서
데이터 위치	리프 노드에 실제 row 전체 포함	리프 노드에 row 위치 정보(rowid 또는 PK)만 저장
물리적 테이블 정렬	정렬됨	정렬되지 않음
리프 노드	인덱스 키 + 전체 row	인덱스 키 + row 포인터
추가 접근 필요 여부	없음 (리프에 모든 데이터 있음)	있음 (row 포인터로 테이블 다시 조회 필요)
범위 검색	매우 빠름	빠르지만 추가 조회 비용 있음
사용 예	PK, 자주 정렬/범위 조회하는 컬럼	자주 필터링되지만 전체 row까지 필요 없는 컬럼

• 클러스터형 인덱스에서는 테이블의 레코드가 인덱스 키 순서대로 실제 디스크에 정렬되어 저장됨
• 보조 인덱스는 그저 인덱스만 정렬되어 있을 뿐, 테이블은 데이터는 인덱스와 무관하게 정렬되지 않고 저장됨
  • 인덱스(name)는 정렬되어 있지만 실제 테이블의 row는 디스크에 흩어져 있음

    → \`name BETWEEN 'A' AND 'C'\` → row 하나하나마다 따로 디스크 접근 필요 -> **랜덤 I/O** 발생 

예시

1. 클러스터형 인덱스 (예: MySQL InnoDB의 PK)

CREATE TABLE users (
  id BIGINT PRIMARY KEY,
  name VARCHAR(100),
  email VARCHAR(100)
);

• `id`가 클러스터형 인덱스
• 리프 노드에는 `id` 키와 함께 `name`, `email` 전체 row 데이터가 같이 저장됨

2. 보조 인덱스

CREATE INDEX idx_email ON users(email);

• `email`만 인덱스 키로 사용
• 리프 노드에는 `email` + `id` (PK 또는 rowid)만 저장
• `email='abc@example.com'` 검색 시:
  • 인덱스에서 `id=3`을 찾은 뒤
  • 다시 테이블에서 `id=3`을 조회해야 함 (추가 I/O)

접근 성능 비교 흐름

클러스터형 인덱스 탐색

SELECT * FROM users WHERE id = 3;

• 인덱스 탐색 → 리프 노드에서 전체 row 바로 반환
• 추가 테이블 접근 없이 즉시 조회 가능

보조 인덱스 탐색

SELECT * FROM users WHERE email = 'abc@example.com'; --id 3인 데이터

• 인덱스(email) 탐색 → `id=3` 반환 → 다시 테이블에서 `id=3` 검색
• 추가 I/O 발생

요약

인덱스는 B+Tree 구조로 구성되며, 리프 노드에 검색 대상 키와 데이터 위치 정보가 저장되어 빠른 조회가 가능하고, 특히 범위 검색과 정렬에 최적화된 성능을 제공합니다.

B+Tree 구조 시각화 도구

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
https://www.cs.usfca.edu/~galles/visualization/BTree.html