yeolyi.com성열의 컴퓨터공학

인덱스

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

회원 표에서 전화번호가 2596인 회원을 찾아 봅시다.

SELECT * FROM members WHERE phone = '2596';

*는 모든 열을 뜻합니다. 행은 가입 순서대로 쌓이니 전화번호는 페이지마다 뒤죽박죽입니다. 이 회원이 어느 페이지에 있는지 알 길이 없습니다.

전체 훑기

가장 단순한 방법은 표의 페이지를 처음부터 끝까지 읽는 것입니다. 선형 탐색과 같고, 전체 테이블 스캔(full table scan)이라 합니다.

찾는 값: 2596 · 읽은 페이지: 0
회원 표의 페이지 (가입 순서, 값을 눌러 찾을 값으로)
페이지 1
페이지 2
페이지 3
페이지 4
페이지 5
페이지 6
페이지 7
페이지 8
페이지 9
페이지 10
페이지 11
페이지 12

다음을 누르면 페이지를 하나씩 읽습니다.

페이지와 버퍼 풀 글에서 본 대로 속도는 디스크에서 페이지를 몇 번 읽느냐에 달렸습니다. 회원이 천만 명이고 페이지 하나에 100명씩 들어 있다면, 한 명을 찾는 데 페이지를 10만 번 읽어야 할 수도 있습니다.

찾아보기

두꺼운 책에서 낱말을 찾을 때는 책 뒤의 찾아보기를 봅니다. 낱말이 가나다순으로 정렬되어 있고 쪽 번호가 적혀 있습니다.

데이터베이스도 찾을 열의 값(키)과 행의 자리를 짝지어 키 순서로 정렬해 따로 저장해 둡니다. 이것이 인덱스(index)입니다. 정렬되어 있으니 이진 탐색을 쓸 수 있습니다.

그런데 이진 탐색은 매번 멀리 건너뛰니 키 하나를 볼 때마다 페이지를 하나 읽습니다. 한 페이지에 키가 수백 개 있어도 그중 하나만 보고 다른 페이지로 건너갑니다.

B-트리

이진 탐색 트리는 노드마다 키가 하나, 자식이 둘입니다. 노드 하나에 키를 3개 넣으면 범위가 4구간으로 나뉘고 자식도 4개가 됩니다.

여기서 노드 하나를 페이지 하나 크기로 만듭니다. 그러면 페이지를 한 번 읽을 때 키 수백 개와 비교해 수백 갈래 중 하나로 내려갑니다. 이런 트리를 B-트리(B-tree)라 합니다. 맨 아래 잎에는 그 행이 든 페이지 번호가 적혀 있습니다.

찾는 값: 2596 · 읽은 페이지: 0
인덱스 (B-트리)
29296991
195020282486
347145175744
785181049711
1614176317911812
1950196819762013
2028214421862408
2486254225962688
2929302831813363
3471396140784374
4517462246574943
5744605461466305
6991710174687499
7851786779558005
8104862891339313
9711977998589974
회원 표의 페이지 (가입 순서, 값을 눌러 찾을 값으로)
페이지 1
페이지 2
페이지 3
페이지 4
페이지 5
페이지 6
페이지 7
페이지 8
페이지 9
페이지 10
페이지 11
페이지 12

다음을 누르면 페이지를 하나씩 읽습니다.

끝까지 내려간 뒤 “전체 훑기”로 바꿔 읽은 페이지 수를 비교해 봅시다.

행이 늘면 어떻게 될까요? 페이지 하나에 키가 100개 들어간다고 하고 비교해 봅시다.

행 수 1,000,000 (100만)
방법읽는 페이지 (최악)
전체 훑기10,000
정렬된 인덱스 + 이진 탐색15
B-트리 인덱스4

행이 100배 늘면 전체 훑기도 100배가 되지만, B-트리는 한 층만 깊어져 페이지를 하나 더 읽습니다. 노드가 가득 차면 둘로 쪼개 부모에 키를 올리며 위로 자라므로, 모든 잎이 늘 같은 깊이에 있습니다.

인덱스의 비용

인덱스는 공짜가 아닙니다. 행을 넣거나 고칠 때마다 인덱스도 고쳐야 하고 공간도 더 씁니다. 그래서 자주 찾는 열에만 만듭니다.

CREATE INDEX members_phone ON members (phone);

만든 뒤에도 쿼리는 그대로입니다. 인덱스를 쓸지는 데이터베이스가 정합니다.

도전 문제

members 표의 phone 열에만 B-트리 인덱스가 있습니다. 다음 쿼리 중 인덱스를 루트부터 한 번 내려가 맞는 값이 모인 곳만 읽으면 맞는 행을 모두 찾을 수 있는 것을 모두 고르세요. LIKE '%96' 은 96 으로 끝나는 값을 뜻합니다. 번호를 작은 것부터 이어 답하세요(예: 24).

1. SELECT * FROM members WHERE phone = '2596';
2. SELECT * FROM members WHERE phone >= '2500' AND phone < '2600';
3. SELECT * FROM members WHERE phone LIKE '%96';
4. SELECT * FROM members WHERE name = '민지';
5. SELECT * FROM members WHERE phone = '2596' OR name = '민지';