B-Tree 인덱스의 구조와 데이터베이스 설계 전략

균형을 유지하는 인덱스 트리

관계형 데이터베이스의 인덱스는 원하는 레코드까지 가는 경로를 짧게 만드는 구조다. B-Tree는 모든 리프 노드를 같은 깊이에 두는 자체 균형 트리이며, 데이터 규모가 커져도 검색·삽입·삭제 작업을 O(log n)으로 처리한다.

노드에는 여러 키와 포인터가 들어가고, 키는 오름차순으로 정렬된다. 차수(order)를 m으로 둘 때 노드는 최소 m/2-1개, 최대 m-1개의 키를 가진다. 루트 외 노드는 최소 절반 이상 채워지며, 리프 노드는 모두 같은 깊이에 놓인다.

⤢✕

B+Tree가 범위 조회에 맞는 이유

데이터베이스에서는 B-Tree의 변형인 B+Tree를 더 자주 사용한다. B+Tree는 실제 데이터를 리프 노드에만 저장하고, 내부 노드는 탐색을 위한 인덱스 역할을 맡는다. 내부 노드와 리프 노드에 같은 키가 존재할 수 있다.

리프 노드가 링크드 리스트로 이어져 있다는 점도 중요하다. 시작 지점을 찾은 뒤 인접한 리프를 순서대로 따라갈 수 있어 범위 검색과 순차 접근에 유리하다.

⤢✕

키 비교로 리프까지 내려가는 과정

탐색은 루트에서 시작한다. 현재 노드의 키를 비교해 다음 자식 노드를 고르고, 리프 노드에 도달할 때까지 이를 반복한다. 리프에서 대상 키를 찾거나 존재하지 않음을 확인한다.

값 75를 찾는 경우에는 루트 노드의 50과 비교해 오른쪽 자식으로 이동한다. 내부 노드의 70, 85에서는 70 < 75 < 85이므로 중간 자식으로 내려가며, 리프 노드의 75, 80에서 75를 찾는다.

노드 크기를 일반적으로 디스크 블록 크기에 맞추는 이유도 여기에 있다. 디스크 접근 한 번으로 여러 키를 비교하고, 트리 깊이를 낮춰 디스크 I/O 횟수를 줄일 수 있다. 노드 공간은 최소 50% 이상 활용되며 트리는 균형을 유지한다.

쿼리 패턴에 맞는 B-Tree 인덱스

B-Tree 인덱스는 정확한 일치 검색, 범위 검색, 정렬 결과 조회, 접두사 검색에 사용할 수 있다.

SELECT * FROM employees WHERE employee_id = 1001;

SELECT * FROM products WHERE price BETWEEN 100 AND 500;

SELECT * FROM orders ORDER BY order_date;

SELECT * FROM customers WHERE name LIKE 'Kim%';

선택도와 조회 조건을 함께 보는 설계

인덱스를 설계할 때는 중복이 적은 높은 선택도의 컬럼을 우선 검토한다. 주민등록번호나 이메일 주소가 예시다.

여러 컬럼을 묶는 복합 인덱스에서는 컬럼 순서가 중요하다. WHERE 절에서 사용하는 조건 순서와 맞춰 설계하며, (department_id, hire_date) 같은 구성이 가능하다.

커버링 인덱스는 쿼리에 필요한 컬럼을 인덱스에 포함해 테이블 접근 없이 처리할 수 있도록 한다.

CREATE INDEX idx_emp_dept_sal ON employees(department_id, salary);
SELECT department_id, salary FROM employees WHERE department_id = 10;

자주 쓰는 조건을 대상으로 필터링 인덱스를 둘 수도 있다.

CREATE INDEX idx_active_users ON users(user_id) WHERE status = 'active';

쓰기 비용과 인덱스가 맞지 않는 조건

인덱스는 저장 공간을 추가로 사용하며, INSERT, UPDATE, DELETE 때마다 유지 비용이 발생한다. 중복이 많은 낮은 선택도 컬럼, 테이블의 대부분(20% 이상)을 스캔해야 하는 조회, 수천 행 이하의 작은 테이블에서는 인덱스가 비효율적일 수 있다.

컬럼에 함수나 연산을 적용하면 기존 인덱스를 활용하지 못할 수 있다. 함수 기반 인덱스를 만들거나 조건을 다시 작성하는 방법을 검토한다.

-- 인덱스 활용 불가
SELECT * FROM employees WHERE YEAR(hire_date) = 2022;

-- 대안 (함수 기반 인덱스 또는 조건 재작성)
CREATE INDEX idx_hire_year ON employees(YEAR(hire_date));
-- 또는
SELECT * FROM employees WHERE hire_date BETWEEN '2022-01-01' AND '2022-12-31';

데이터 변경이 많이 일어난 뒤에는 인덱스 단편화(Fragmentation)로 성능이 저하될 수 있어 주기적인 인덱스 재구성(REBUILD)이 필요하다.

DBMS별 구현에서 확인할 점

Oracle은 B+Tree 구조를 사용하며 인덱스는 브랜치 블록과 리프 블록으로 구성된다. 리프 블록은 양방향 링크드 리스트로 연결되고, 비트맵 인덱스와 함수 기반 인덱스 같은 확장도 지원한다.

MySQL의 InnoDB도 B+Tree를 사용한다. 클러스터형 인덱스(Clustered Index)를 기본 적용하고, 보조 인덱스(Secondary Index)에는 PK 값이 포함된다. 균형은 페이지 분할(Page Split)로 유지한다.

SQL Server는 B+Tree를 사용하고 페이지 단위(8KB)로 데이터를 관리한다. 필터링된 인덱스와 인덱스된 뷰를 지원하며, 인덱스 힌트로 세밀하게 제어할 수 있다.

PostgreSQL은 B+Tree 구조를 기반으로 하면서 GiST, GIN, BRIN 같은 인덱스 타입도 제공한다. HOT(Heap-Only Tuples) 기능으로 인덱스 오버헤드를 줄이고, 부분 인덱스(Partial Index)를 활용할 수 있다.

실행 계획에서 시작하는 인덱스 관리

운영 중에는 실행 계획(Execution Plan), 인덱스 사용률 통계, 누락된 인덱스를 함께 확인한다. 단편화 관리는 DBMS별 명령으로 수행할 수 있다.

-- Oracle
ALTER INDEX employee_idx REBUILD;

-- SQL Server
ALTER INDEX employee_idx ON employees REORGANIZE;
-- 또는
ALTER INDEX employee_idx ON employees REBUILD;

-- MySQL
OPTIMIZE TABLE employees;

통계도 최신 상태로 유지해야 한다.

-- Oracle
ANALYZE TABLE employees COMPUTE STATISTICS;

-- SQL Server
UPDATE STATISTICS employees;

-- MySQL
ANALYZE TABLE employees;

-- PostgreSQL
ANALYZE employees;

중복 기능을 하는 인덱스는 통합하고, 오랜 기간 사용되지 않은 인덱스는 제거 대상으로 검토한다. 복합 인덱스로 단일 인덱스를 대체할 수 있는지도 함께 확인한다.