데이터베이스는 어떻게 그 안에서 찾아낼까

처음에는 한 줄씩 훑는다

앞 레슨에서 데이터베이스는 정보를 표 모양으로 줄지어 정리한다고 했다. 그 안에서 무언가를 찾는 가장 단순한 방법은 맨 윗줄부터 한 줄씩 맞는지 보며 아래로 내려가는 것이다.
맞는 줄을 만나면 멈춘다. 이렇게 처음부터 끝까지 차례로 훑는 것을 전체 검색이라고 해요.

찾고 싶은 값을 눌러 보자. 맨 위부터 한 칸씩 훑어 내려가며, 닿을 때까지 몇 번 보았는지 세어 줘요.

위쪽에 있는 값은 몇 번 만에 금방 찾았다. 아래쪽에 있는 값은 그 위를 모두 지나야 닿았다. 찾는 값이 맨 끝에 있으면 결국 모든 줄을 다 본 셈이다.
줄 수가 적을 때는 이렇게 해도 충분히 빨라서 문제가 없어요. 그렇다면 줄이 아주 많아지면 어떻게 될까?

데이터가 늘면 훑기가 느려진다

실제 데이터베이스는 줄 수가 어마어마하다. 수백만 줄, 수억 줄도 흔하다. 전체 검색으로 맨 끝 값을 찾으려면 그 모든 줄을 한 번씩 봐야 한다.
그러니 줄이 두 배가 되면 봐야 할 횟수도 두 배가 돼요. 줄이 늘어난 만큼 찾는 비용이 그대로 따라 늘어나는 것, 이것이 전체 검색의 한계다.

눌러서 건수를 늘려 보자. 맨 끝 값을 전체 검색으로 찾는 데 드는 횟수가 막대로 가파르게 늘어요.

건수를 늘릴수록 막대가 쑥쑥 길어졌다. 작은 표에서는 대수롭지 않던 일이 큰 표에서는 큰 부담이 된다.
매번 처음부터 끝까지 훑는 한 이 비용은 피할 수 없어요. 그렇다면 훑지 않고 그 자리로 바로 가는 방법은 없을까? 다행히 똑똑한 방법이 있다.

색인을 만들어 바로 건너간다

책 뒤에 붙은 찾아보기를 떠올려 보자. 낱말이 가나다순으로 정렬되어 있고, 옆에 몇 쪽인지 적혀 있다. 책을 처음부터 넘기지 않고 찾아보기에서 낱말을 짚어 그 쪽을 바로 펼친다.
데이터베이스도 이런 목록을 미리 만들어 둘 수 있어요. 이것을 색인, 곧 인덱스라고 한다.

정렬된 색인에서 이름표를 눌러 보자. 표를 훑지 않고 한두 번 만에 그 줄로 바로 건너가요.

색인을 짚으니 표를 훑지 않고도 바로 갔다. 맨 끝에 있는 값이라도 한두 번이면 충분했다.
비결은 색인이 미리 가지런히 정렬되어 있다는 데 있다. 정렬된 목록에서는 가운데를 보고 찾는 값이 앞쪽인지 뒤쪽인지 정해 절반을 버리는 일을 되풀이할 수 있어요. 그렇게 하면 백만 개 가운데서도 스무 번 남짓이면 찾는다.

전체 검색과 색인을 견준다

두 방법을 나란히 두고 같은 건수에서 견주어 보자. 전체 검색은 줄 수만큼 많은 횟수를 봐야 한다. 색인은 정렬을 이용해 아주 적은 횟수로 끝난다.
건수가 같아도 결과는 하늘과 땅 차이예요. 그래서 자주 찾는 항목에는 색인을 만들어 두는 것이 이득이다.

건수를 고르고 양쪽 찾기를 눌러 보자. 전체 검색과 색인이 같은 값을 찾는 데 든 횟수를 나란히 견줘요.

건수를 늘릴수록 전체 검색 막대는 쭉쭉 늘었지만 색인 막대는 거의 그대로였다. 바로 이 차이 때문에 데이터가 클수록 색인이 빛난다.
물론 색인도 공짜는 아니에요. 색인을 담을 자리가 더 필요하고, 새 줄이 들어올 때마다 색인도 정렬된 채로 고쳐야 한다. 그래도 자주 찾는 항목이라면 그만한 값을 한다.

정리

한 줄로 모으면 이렇다. 가장 단순한 찾기는 처음부터 한 줄씩 다 훑는 전체 검색이다. 데이터가 적으면 이것으로 충분하다.
하지만 수억 건으로 늘면 훑는 비용이 가파르게 늘어요. 그래서 미리 색인을 만들어 두고 한두 번 만에 바로 건너간다. 같은 건수라도 색인은 훨씬 적게 본다.

핵심을 차례로 눌러 되짚어 보자. (한 줄씩 훑기 → 데이터 폭증 → 색인으로 점프 → 전체검색 vs 색인)

이제 데이터베이스가 왜 전체 검색에서 색인으로 넘어가는지 알았다. 그렇다면 그 색인은 실제로 어떻게 만들까?
정렬된 목록 말고도 해시와 트리 같은 방법이 있다. 다음 레슨에서는 그 가운데 이름표 하나로 자리를 바로 계산해 내는 해시를 먼저 살펴봐요.