초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
회원 표에서 전화번호가 2596인 회원을 찾아 봅시다.
SELECT * FROM members WHERE phone = '2596';
*는 모든 열을 뜻합니다. 행은 가입 순서대로 쌓이니 전화번호는 페이지마다
뒤죽박죽입니다. 이 회원이 어느 페이지에 있는지 알 길이 없습니다.
가장 단순한 방법은 표의 페이지를 처음부터 끝까지 읽는 것입니다. 선형 탐색과 같고, 전체 테이블 스캔(full table scan)이라 합니다.
다음을 누르면 페이지를 하나씩 읽습니다.
페이지와 버퍼 풀 글에서 본 대로 속도는 디스크에서 페이지를 몇 번 읽느냐에 달렸습니다. 회원이 천만 명이고 페이지 하나에 100명씩 들어 있다면, 한 명을 찾는 데 페이지를 10만 번 읽어야 할 수도 있습니다.
두꺼운 책에서 낱말을 찾을 때는 책 뒤의 찾아보기를 봅니다. 낱말이 가나다순으로 정렬되어 있고 쪽 번호가 적혀 있습니다.
데이터베이스도 찾을 열의 값(키)과 행의 자리를 짝지어 키 순서로 정렬해 따로 저장해 둡니다. 이것이 인덱스(index)입니다. 정렬되어 있으니 이진 탐색을 쓸 수 있습니다.
그런데 이진 탐색은 매번 멀리 건너뛰니 키 하나를 볼 때마다 페이지를 하나 읽습니다. 한 페이지에 키가 수백 개 있어도 그중 하나만 보고 다른 페이지로 건너갑니다.
이진 탐색 트리는 노드마다 키가 하나, 자식이 둘입니다. 노드 하나에 키를 3개 넣으면 범위가 4구간으로 나뉘고 자식도 4개가 됩니다.
여기서 노드 하나를 페이지 하나 크기로 만듭니다. 그러면 페이지를 한 번 읽을 때 키 수백 개와 비교해 수백 갈래 중 하나로 내려갑니다. 이런 트리를 B-트리(B-tree)라 합니다. 맨 아래 잎에는 그 행이 든 페이지 번호가 적혀 있습니다.
다음을 누르면 페이지를 하나씩 읽습니다.
끝까지 내려간 뒤 “전체 훑기”로 바꿔 읽은 페이지 수를 비교해 봅시다.
행이 늘면 어떻게 될까요? 페이지 하나에 키가 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 = '민지';