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

처음엔 한 줄씩 훑어 찾아요

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

찾고 싶은 값을 눌러봐요. 맨 위부터 한 칸씩 훑어 내려가며, 도달까지 몇 번 봤는지 세어줘요.

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

데이터가 폭증하면 훑기가 느려져요

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

건수를 클릭으로 키워봐요. 맨 끝 값을 전체 검색으로 찾는 데 드는 횟수가 막대로 가파르게 늘어요.

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

색인을 만들어 바로 점프해요

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

정렬된 색인에서 이름표를 눌러봐요. 표를 훑지 않고 클릭 한두 번에 바로 그 줄로 점프해요.

색인을 짚으니
표를 훑지 않고도 바로 갔죠.
맨 끝에 있는 값이라도
클릭 한두 번이면 충분했어요.
비결은 색인이 미리
가지런히 정렬돼 있다는 점이에요.
정렬돼 있으면 어디쯤 있는지
금방 좁혀 짚을 수 있거든요.
전체를 다 볼 필요가 사라진 거죠.

전체 검색과 색인을 견줘봐요

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

건수를 고르고 양쪽 찾기를 눌러봐요. 전체 검색과 색인이 같은 값을 찾는 데 든 횟수를 나란히 비교해요.

건수를 키울수록
전체 검색 막대는 쭉쭉 늘었지만
색인 막대는 거의 그대로였죠.
바로 이 차이 때문에
큰 데이터일수록 색인이 빛나요.
물론 색인도 공짜는 아니에요.
미리 만들고 정렬을 유지하는
수고가 들거든요.
그래도 자주 찾는다면 그만한 값을 해요.

정리해볼까요

한 줄로 모으면 이래요.
가장 단순한 찾기는 전체 검색,
곧 처음부터 한 줄씩 다 훑기예요.
데이터가 적으면 충분해요.
하지만 수억 건으로 폭증하면
훑는 비용이 가파르게 늘어요.
그래서 미리 색인을 만들어
클릭 한두 번에 바로 점프해요.
같은 건수라도 색인이 훨씬 적게 봐요.

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

이제 데이터베이스가
전체 검색에서 색인으로
왜 넘어가는지 알게 됐어요.
그런데 그 색인을
실제로는 어떻게 만들까요?
정렬된 목록 말고도
해시와 트리 같은 방법이 있어요.
그 똑똑한 색인 구조를
다음 강들에서 하나씩 따라가봐요.