어떻게 찾기를 빠르게, 인덱스

책 뒤에는 찾아보기가 있다

앞 레슨들에서 데이터베이스가 원하는 줄을 어떻게 찾는지, 그리고 해시와 균형 트리가 어떻게 빠르게 찾는지 보았다. 이제 그 도구들이 데이터베이스 안에서 어떻게 쓰이는지 볼 차례다.
데이터가 아주 많으면 처음부터 끝까지 훑는 것은 느리다. 두꺼운 책에서 단어를 첫 장부터 찾는 것과 같아요. 그래서 책 뒤에는 단어 옆에 페이지 번호를 적은 찾아보기가 있다.

본문을 처음부터 훑기와 찾아보기로 건너가기를 눌러 견주어 보자. 몇 번 만에 찾는지 세어 줘요.

찾아보기로 건너가니 훨씬 적은 횟수로 찾았다. 데이터베이스의 인덱스가 바로 이 찾아보기예요. 표의 한 열을 골라 그 값과 줄의 위치를 짝지어 미리 적어 둔 목록이다.
그런데 찾아보기에도 종류가 있다. 정확한 값 하나를 찾을 때와 범위를 찾을 때 알맞은 방법이 다르기 때문이다.

정확한 값에는 해시 인덱스

'김철수'처럼 딱 하나의 정확한 값을 찾고 싶을 때가 있다. 이럴 때는 해시 인덱스가 좋다.
앞에서 본 해시가 이름을 받아 곧장 자리 번호를 계산해 준다. 그래서 줄줄이 훑을 필요 없이 그 자리로 한 번에 건너가요. 사물함 번호를 외워 두고 그 칸을 바로 여는 것과 같다.

이름을 누르면 해시가 자리 번호를 계산해 그 칸으로 한 번에 건너가요.

이름 하나로 곧장 자리를 찾아냈다. 해시 인덱스는 이렇게 정확한 값을 찾는 데 아주 빠르다.
하지만 약점이 있어요. 해시는 값을 크기와 상관없이 흩어 놓기 때문에 '20살부터 30살까지'처럼 범위로 찾는 일은 하지 못한다. 그럴 때는 다른 인덱스가 필요하다.

범위에는 트리 인덱스

'20살부터 30살까지'처럼 범위로 찾고 싶을 때가 있다. 이럴 때는 트리 인덱스가 좋다. 트리 인덱스는 앞 레슨의 균형 트리로 만들어서 값을 작은 것부터 큰 것까지 정렬해 둔다.
그래서 시작 값을 찾으면 그 옆으로 죽 이어서 범위 안의 값을 차례로 훑을 수 있어요. 사전이 가나다순으로 되어 있는 것과 닮았다. 실제 데이터베이스는 대부분 이 트리 인덱스를 기본으로 쓴다.

찾을 범위를 눌러 정해 보자. 정렬된 트리 인덱스가 시작 값을 찾아 범위 안을 죽 훑어요.

정렬되어 있으니 범위가 옆으로 쭉 이어졌다. 해시는 한 점을 콕 집어 찾고, 트리는 한 줄을 죽 훑는다.
그래서 무엇을 자주 찾느냐에 따라 알맞은 인덱스가 달라요. 정확한 값을 많이 찾으면 해시, 범위를 많이 찾으면 트리다. 그런데 인덱스는 공짜가 아니다.

인덱스는 공짜가 아니다

인덱스에 좋은 점만 있는 것은 아니다. 첫째, 자리를 더 차지한다. 찾아보기를 따로 적어 두니 그만큼 저장 공간이 더 든다.
둘째, 데이터가 바뀌면 인덱스도 함께 고쳐야 해요. 새 줄을 넣거나 지울 때마다 찾아보기도 고쳐야 하니, 쓰는 일이 그만큼 느려진다. 그래서 무턱대고 많이 만들면 오히려 손해다.

줄을 넣거나 지워 보자. 데이터가 바뀔 때마다 인덱스도 따라서 고쳐지고, 쓰는 자리도 늘어나요.

데이터를 바꿀 때마다 인덱스도 따라 움직였고, 자리도 점점 더 차지했다. 그래서 인덱스는 자주 찾는 열에만 골라서 만든다.
빨라지는 이득과, 공간과 고치는 수고라는 비용을 저울에 달아 보는 것이에요. 잘 고르면 찾기가 훨씬 빨라진다.

정리

한 줄로 모으면 이렇다. 인덱스는 책 뒤 찾아보기처럼 원하는 자리로 바로 건너가게 해 주는 목록이다. 해시 인덱스는 정확한 값 하나를 한 번에 콕 찾아 주고, 트리 인덱스는 정렬되어 있어서 범위를 죽 훑기에 좋다.
다만 자리를 더 쓰고, 데이터가 바뀔 때마다 함께 고쳐야 해요. 그래서 자주 찾는 열에만 골라서 만든다.

핵심을 차례로 눌러 되짚어 보자. (책 뒤 찾아보기 → 정확한 값엔 해시 → 범위엔 트리 → 공짜가 아니에요)

이제 인덱스가 어떻게 찾기를 빠르게 하는지 알았다. 지금까지는 표에 줄지어 담긴 데이터를 다뤘다.
그런데 친구 관계나 지하철 노선처럼, 데이터 사이의 연결 자체가 중요한 경우도 있어요. 다음 레슨에서는 점과 선으로 이어 담는 데이터, 그래프를 만난다.