인덱스란 테이블에서 데이터를 찾을 때 모든 행을 순서대로 찾지 않고 미리 정렬된 목록을 이용해 빠르게 데이터를 찾을 수 있는 기술이다.
예를 들어 users 테이블에서 name이 lucy인 데이터를 찾는다고 할 때,
만약 유저가 10만명이 있다면 그 유저 데이터를 모두 순서대로 읽어가며 name이 lucy인 유저를 찾아야 한다.
이런식으로 찾는걸 DB에서는 풀테이블 스캔, 풀스캔 이라고 하는데, 풀스캔으로 데이터를 찾게 되면 당연히 데이터가 많아질수록 엄청나게 느려질수밖에 없다.
일반적으로 서비스는 최대 1~3초 안에는 응답해야 사용자 경험에 좋은데, 10만명의 유저 중에서 하나의 유저를 찾기 위해 풀스캔을 돌리면 최악의 경우 3초보다 더 긴 시간동안 기다려야 할수도 있다.
그래서 인덱스는 지정한 컬럼과 해당 값을 가진 실제 위치를 한쌍으로 저장하고, 그 값을 기준으로 미리 정렬을 해놓기 때문에 전체 데이터를 순차적으로 읽지 않고 몇번의 읽기만으로 빠르게 데이터를 찾을 수 있다.
예를 들어, users 테이블의 name 을 인덱스로 설정한다면 (’lucy’, 1) 처럼 저장해놓고 실제 조회 시 ‘lucy’ 라는 값을 인덱스에서 찾은 후, 그 값과 같이 저장된 PK 를 이용해 원본 테이블에서 빠르게 조회할 수 있다.
물론 원본 테이블의 위치는 PK 말고 주소값, 포인터 등 다양한 값으로 저장할 수도 있고, 이는 인덱스의 종류에 따라 다르다.
인덱스는 일반적으로 트리 자료구조를 통해 구현되는데, 트리를 대략적으로 설명하면 다음과 같다.
일단 트리는 이진 탐색 트리 구조를 기반으로 한다. 이진 탐색 트리는 데이터를 빠르게 찾을 수 있도록 저장 시점에 미리 정렬해놓는 트리이다.
예를 들어 작은 값을 왼쪽에 저장한다고 하면
빈 트리에 처음으로 10을 넣으면 [10] 으로 저장되고, 이 첫번째 값이 루트가 된다.
그 후 5를 저장한다면 5는 10보다 작으므로 [10, 5] 로 저장된다. 그후 15를 저장한다면 [10, 5, 15] 로 저장된다.
그 후 만약 6을 저장한다면 6은 10보다 작으므로 왼쪽으로 가고, 그 다음 5보다는 크므로 오른쪽으로 가서 [10, 5, 15, 6] 처럼 저장된다. 그후 1을 저장하면 1은 10보다 작으므로 왼쪽, 5보다도 작으므로 왼쪽으로 가서 아래와 같이 저장된다.
[10, 5, 15, 1, 6]
이는 일단 논리적인 순서이고, 실제 구현시에는 링크드 리스트를 활용하는 것처럼 조금 달라질 수도 있다.
여기서 만약 1 이라는 값을 찾는다면 아래와 같이 찾을 수 있다.