인덱스는 책 뒤의 찾아보기처럼, 값과 그 값이 있는 행의 위치를 정렬해 둔 별도의 자료구조입니다. 대부분의 DB는 B+트리로 인덱스를 만들어, 수백만 행에서도 페이지 몇 개만 읽고 원하는 행을 찾습니다.
B+트리 인덱스 탐색과 전체 테이블 스캔을 비교하는 시뮬레이터
1. 찾을 값과 방법을 고르세요
위쪽 트리가 id 열에 만든 인덱스이고, 아래쪽 다섯 칸이 실제 행이 저장된 테이블 페이지입니다. 테이블 페이지는 정렬되어 있지 않다는 점을 눈여겨보세요.
B+트리의 세 가지 성질
첫째, 모든 노드가 정렬된 키를 여러 개 갖고, 키 사이사이에 자식 포인터가 있습니다. 노드 하나가 디스크 페이지 하나라서 한 번 읽을 때 수백 개의 키를 비교하므로, 트리가 아주 낮습니다. 둘째, 실제 행의 위치는 맨 아래 리프에만 있습니다. 셋째, 리프끼리 옆으로 연결되어 있어서 범위 조건(BETWEEN, >, <)은 시작 리프만 찾은 뒤 옆으로 따라가면 됩니다.
인덱스가 항상 빠르지는 않습니다
인덱스로 찾은 행마다 테이블 페이지를 따로 읽어야 하므로, 조건에 맞는 행이 테이블의 큰 비율을 차지하면 차라리 전체 스캔이 빠릅니다. 범위를 넓혀 실행해 보면 읽는 테이블 페이지 수가 전체 스캔과 비슷해지는 것을 볼 수 있습니다. DB의 옵티마이저는 이 비용을 계산해 인덱스를 쓸지 정합니다.
면접에서 자주 묻는 것: 인덱스를 못 타는 경우
열에 함수나 연산을 씌우면(WHERE YEAR(가입일) = 2024, WHERE 가격 * 2 > 100) 정렬된 값을 쓸 수 없어 인덱스를 못 탑니다. LIKE '%검색어'처럼 앞에 와일드카드가 오면 마찬가지입니다. (a, b) 복합 인덱스는 a로 먼저 정렬되어 있으므로 a 조건 없이 b만으로는 효율적으로 찾지 못합니다(왼쪽 접두사 규칙). 인덱스가 많을수록 INSERT, UPDATE, DELETE 때 모든 인덱스를 함께 고쳐야 해서 쓰기가 느려집니다.