이진 탐색과 B-트리

정렬돼 있으면 절반씩 버릴 수 있다

값 27개 중에서 하나를 찾습니다. 처음부터 하나씩 볼 수도 있고, 정렬돼 있다면 가운데를 보고 절반을 버릴 수도 있고, 한 번에 여러 갈래로 나누는 B-트리를 쓸 수도 있습니다.

실행으로 대조 · 화면의 탐색은 알고리즘을 실제로 실행한 결과

이 실습에 나오는 개념

이진 탐색: 정렬된 데이터에서 가운데 값과 비교해 찾는 범위를 절반씩 줄여 나가는 탐색 방법이다. 시간 복잡도는 O(log n)이다. 데이터가 정렬되어 있어야만 사용할 수 있다. 데이터베이스의 B-트리 인덱스도 정렬된 상태에서 범위를 좁혀 가는 같은 원리를 이용한다.
시간 복잡도(Big-O): 입력 크기 n이 커질 때 알고리즘의 연산 횟수가 얼마나 빠르게 늘어나는지를 나타내는 표기다. O(1)은 크기와 무관하게 일정, O(log n)은 크기가 두 배가 되어도 한 단계만 늘어남, O(n)은 크기에 비례, O(n²)은 크기의 제곱에 비례함을 뜻한다. 데이터가 많아질 때 어떤 방식이 버티는지 판단하는 기준이다.
B-트리 인덱스: 대부분의 관계형 데이터베이스가 기본으로 쓰는 인덱스 구조다. 값이 정렬된 상태로 유지되는 균형 잡힌 트리이며, 한 노드에 많은 키를 담아 트리의 높이가 낮다. 루트에서 몇 단계만 내려가면 원하는 값을 찾을 수 있고, 값이 정렬되어 있어 같은 값 조회뿐 아니라 범위 조회와 정렬에도 사용된다.
풀 테이블 스캔: 조건에 맞는 행을 찾기 위해 테이블의 모든 행을 처음부터 끝까지 읽는 방식이다. 조건에 쓸 인덱스가 없거나, 인덱스가 있어도 조건에 해당하는 행이 너무 많아 전체를 읽는 편이 낫다고 옵티마이저가 판단할 때 선택된다. 큰 테이블에서 소수의 행을 찾는 데 이 방식이 쓰이면 성능 문제의 원인이 된다.
인덱스: 테이블에서 원하는 행을 빨리 찾기 위해 특정 컬럼의 값을 정렬된 형태로 따로 유지하는 자료구조다. 인덱스가 없으면 조건에 맞는 행을 찾기 위해 테이블 전체를 읽어야 한다. 조회는 빨라지지만 데이터를 추가, 수정, 삭제할 때마다 인덱스도 갱신해야 하므로 쓰기 성능과 저장 공간에 비용이 든다.

이렇게 바꿔 보세요

처음 설정으로 — 처음부터 하나씩. 뒤쪽 값까지 23번 봅니다.
이진 탐색으로 — 같은 값을 5번 만에 찾습니다.
B-트리로 — 노드 3개만 읽으면 어떤 값이든 찾습니다.
없는 값을 하나씩 찾으면 — 끝까지 다 봐야 없다는 것을 압니다.
없는 값을 B-트리로 — 없다는 것도 노드 3개로 확인합니다.
10억 건이라면 — 아래 표에서 방식별 횟수 차이를 보세요.

처음 설정으로 실행하면

값 27개가 정렬되지 않은 채 쌓여 있다고 봅니다(화면에는 보기 쉽게 크기 순으로 놓았습니다). 어디에 있는지 알 단서가 없으므로 앞에서부터 하나씩 확인합니다.
1번째 확인: 10 → 아닙니다. 다음 칸으로 갑니다.
2번째 확인: 20 → 아닙니다. 다음 칸으로 갑니다.
6번째 확인: 60 → 아닙니다. 다음 칸으로 갑니다.
12번째 확인: 120 → 아닙니다. 다음 칸으로 갑니다.
18번째 확인: 180 → 아닙니다. 다음 칸으로 갑니다.
23번째 확인: 230 → 찾았습니다.

실행 결과

하나씩 찾는 방식은 데이터가 10배가 되면 확인 횟수도 10배가 됩니다(O(n)). 없는 값은 끝까지 봐야 합니다. 인덱스가 없는 컬럼으로 조회하면 DB가 하는 일이 이것입니다.
세 방식의 차이는 "정렬해 두었는가"와 "한 번에 얼마나 많이 버리는가"입니다. DB 인덱스는 값을 정렬해 B-트리로 저장해 두는 것이고, 그 대가로 넣고 고칠 때마다 트리도 함께 고쳐야 합니다.

코드

// 정렬돼 있지 않으면 앞에서부터 전부 확인하는 수밖에 없다
for (int i = 0; i < rows.length; i++) {
    if (rows[i] == target) return i;
}
return -1;                              // 끝까지 봐야 "없다"를 안다

-- DB에서는 인덱스가 없는 컬럼으로 찾는 것과 같다 (풀 테이블 스캔)
SELECT * FROM orders WHERE amount = 230;

이 모형의 전제

27건에서의 탐색 과정과 횟수는 이 페이지가 알고리즘을 실제로 실행한 결과입니다. 큰 건수의 횟수는 "한 번에 몇 갈래로 나누는가"로 계산한 최대 단계 수입니다. 화면의 B-트리는 값이 잎 노드에만 있는 B+트리 모양으로, MySQL InnoDB의 인덱스가 이 구조입니다. 실제 인덱스에서 노드 하나에 몇 개의 값이 들어가는지는 키의 크기에 따라 달라지며 500은 예시로 든 값입니다. 뿌리와 가지 노드는 보통 메모리에 올라와 있어 실제 디스크 읽기는 더 적습니다.

앞 실습: 뷰, 프로시저, 트리거 · 다음 실습: 인덱스와 풀 스캔

이 실습에 나오는 개념

이 실습에서 보는 것

설정

실행 전에 결과 예측하기

코드

그림

실행 비교