역색인 - 문서에서 낱말이 아니라 낱말에서 문서로

앞 글에서 700쪽짜리 책을 매번 처음부터 넘기고 있었다. 이제 책 뒤를 펴 볼 차례다.

찾아보기는 이미 그렇게 생겼다

기술서 맨 뒤 몇 쪽을 보면 이런 게 붙어 있다.

격리 수준 ......... 214, 301, 302
데드락 ............ 198, 214
인덱스 ............ 88, 90, 91, 214, 377

여기엔 본문이 한 글자도 없다. 낱말과 쪽 번호뿐이다. 그런데 이것만 있으면 700쪽 중 어디를 펴야 할지 즉시 안다.

핵심은 이 목록이 본문과 방향이 반대라는 것이다. 본문은 쪽을 펴면 그 쪽에 있는 낱말들이 나온다. 찾아보기는 낱말을 짚으면 그 낱말이 있는 쪽들이 나온다. 우리가 검색할 때 던지는 질문이 바로 뒤엣것이다.

방향을 뒤집는다

문서를 저장한 그대로 두면 구조는 이렇다. 문서 하나 → 그 안의 낱말들. 이걸 정방향이라 부른다. 이 방향으로는 “이 문서에 무슨 말이 있나”는 알아도 “이 말이 어느 문서에 있나”는 모른다. 알려면 문서를 전부 열어봐야 한다.

그래서 뒤집는다. 낱말 하나 → 그 낱말이 든 문서들.

이게 역색인이다. 이름이 거창하지만 방향을 뒤집었다는 뜻 이상이 없다. 문서가 백만 건이어도 장바구니라는 낱말은 목록에서 한 줄이고, 그 한 줄만 읽으면 답이 나온다.

그리고 이 뒤집기가 앞 글에서 막혔던 자리를 그대로 푼다. 본문 한 건이 낱말 수백 개를 만들어 내도 괜찮다. 낱말 하나하나가 키가 되는 게 원래 목적이기 때문이다.

포스팅 리스트

낱말 뒤에 달린 문서 번호 목록에는 이름이 있다. 포스팅 리스트다.

장바구니 → [3, 17, 88, 204, 991]
결제     → [17, 88, 512]
쿠폰     → [88, 204]

왼쪽 낱말들의 모음을 사전이라 부르고, 오른쪽 목록들을 포스팅 리스트라 부른다. 역색인은 이 둘로 끝이다.

여기서 눈여겨볼 게 하나 있다. 문서 번호가 오름차순으로 정렬돼 있다. 우연이 아니라 일부러 그렇게 만든다. 이 정렬이 다음 절의 모든 것을 가능하게 한다.

두 낱말을 한꺼번에 찾을 때

사용자가 장바구니 쿠폰이라고 쳤다. 둘 다 든 문서를 찾아야 한다.

장바구니 → [3, 17, 88, 204, 991]
쿠폰     → [88, 204]

눈으로는 88, 204가 답인 게 보인다. 기계는 어떻게 하나. 한쪽 목록의 항목마다 다른 쪽 목록을 전부 뒤지면 곱셈만큼 일하게 된다. 그럴 필요가 없다. 둘 다 정렬돼 있기 때문이다.

양쪽 목록 맨 앞에 손가락을 하나씩 얹고, 작은 쪽 손가락만 한 칸 내린다. 두 손가락이 같은 번호를 가리키면 그건 양쪽에 다 있는 문서다. 이렇게 하면 각 목록을 한 번씩만 훑고 끝난다.

이 손가락 놀이 하나로 검색의 논리 연산이 전부 나온다.

• 둘 다 든 문서(AND): 같은 번호에서만 뽑는다
• 둘 중 하나라도(OR): 두 목록을 합치되 중복을 지운다
• 하나는 들고 하나는 안 든 문서(NOT): 왼쪽에만 있는 번호를 뽑는다

그래서 낱말을 여러 개 넣어도 비용이 폭발하지 않는다. 문서 수가 아니라 걸린 목록의 길이에 비례해 일한다.

자리까지 적어두면 구문 검색이 된다

지금 구조로는 못 하는 게 하나 있다. "무료 배송"처럼 붙어 있는 말을 찾는 것이다.

무료와 배송이 둘 다 든 문서는 찾을 수 있다. 하지만 그 문서에서 두 낱말이 나란히 있었는지, 아니면 첫 문단과 마지막 문단에 따로 있었는지는 알 수 없다.

그래서 포스팅 리스트에 하나를 더 적는다. 몇 번째 낱말이었는지다.

무료 → 88번 문서의 [12, 40]번째 낱말
배송 → 88번 문서의 [13, 77]번째 낱말

12 다음이 13이다. 두 낱말이 실제로 붙어 있었다. 이렇게 자리를 같이 저장하면 구문 검색이 되고, “두 낱말이 다섯 낱말 이내에 있는 문서” 같은 것도 된다. 대신 색인이 커진다. 늘 그렇듯 교환이다.

낱말 목록 자체는 어떻게 찾나

한 가지가 남았다. 장바구니라는 줄을 사전에서 찾는 일은 어떻게 하나. 낱말이 수백만 개면 그 목록도 처음부터 훑을 순 없다.

여기서는 낱말을 정렬해 둔다. 정렬돼 있으니 이진 탐색이 먹고, 디스크에 있다면 B-tree 같은 구조를 쓰기도 한다.

재미있는 건 이 대목이다. 앞 글에서 못 쓴다고 했던 그 B-tree가 여기서는 쓰인다. 다만 쓰이는 자리가 다르다. 예전엔 본문 전체가 키였는데, 지금은 장바구니라는 낱말 하나가 온전한 키다. 키가 짧고 정확해졌으니 정렬이 다시 힘을 쓴다.

역색인은 B-tree를 대체한 게 아니라, B-tree가 쓸 수 있는 모양으로 데이터를 바꿔 놓은 것이다.

색인은 공짜가 아니다

찾아보기를 만들려면 책을 처음부터 끝까지 한 번 읽어야 한다. 역색인도 같다.

• 원문만큼의 공간을 더 쓴다. 자리 정보까지 담으면 원문보다 커지기도 한다. 실제로는 압축을 쓴다. 문서 번호가 정렬돼 있으니 [3, 17, 88]을 [3, +14, +71]처럼 차이만 저장하면 훨씬 작아진다.
• 문서를 넣을 때 일한다. 문서 하나를 색인하면 그 안의 낱말 수백 개의 목록을 전부 건드려야 한다.
• 읽기와 쓰기의 짐이 반대다. 읽기는 아주 싸지고, 쓰기는 비싸진다.

세 번째가 특히 크다. 검색이 그렇게 빠른 대가를 글을 쓸 때 미리 치르는 구조이기 때문이다. 이 대가가 어떻게 나타나는지는 뒤에 색인 갱신을 다룰 때 본다.

실무에서: 이 구조가 만들어 낸 기능들

검색 제품에서 당연하게 쓰는 기능들이 사실 대부분 이 구조에서 그냥 떨어져 나온 것이다. 새로 발명한 게 아니라 포스팅 리스트를 다르게 조합한 것이다.

필터가 검색과 같은 값이다. 카테고리:신발도 결국 낱말 하나다. 포스팅 리스트를 하나 더 만들어 두고 교집합에 끼워 넣으면 끝난다. 그래서 검색엔진에서는 조건 필터가 본문 검색만큼 싸다.

개수 집계가 미리 되어 있다. 쇼핑몰 옆에 붙은 “신발 (1,204) / 가방 (88)“은 각 낱말의 포스팅 리스트 길이를 세는 일에 가깝다. DB에서 GROUP BY COUNT를 도는 것과는 비용이 다르다.

자동완성도 사전에서 나온다. 낱말이 정렬돼 있으니 장바로 시작하는 구간을 짚으면 그 뒤가 후보다. 앞 글에서 본 LIKE '장바%'가 인덱스를 타던 그 성질이 여기서 그대로 쓰인다.

그리고 여기서 문제가 하나 생긴다. 지금까지 낱말은 그냥 주어진 것처럼 다뤘다. 그런데 장바구니를은 장바구니와 같은 낱말인가 다른 낱말인가. 색인에 어느 쪽을 적어 두느냐에 따라 검색이 되기도 하고 안 되기도 한다.

정리

• 역색인은 아이디어 하나다. 문서 → 낱말을 낱말 → 문서로 뒤집는다. 책 뒤의 찾아보기와 같은 구조다.
• 낱말들의 모음이 사전, 낱말 뒤에 달린 문서 번호 목록이 포스팅 리스트다. 이 둘로 끝이다.
• 문서 번호를 정렬해 두기 때문에 여러 낱말을 손가락 두 개로 한 번씩만 훑어 합칠 수 있다. AND·OR·NOT이 전부 여기서 나온다.
• 낱말의 자리까지 적으면 구문 검색이 된다. 색인이 커지는 대가를 낸다.
• 읽기가 싸진 만큼 쓰기가 비싸졌다. 검색이 빠른 값은 글을 넣을 때 미리 치른 것이다.