고급 데이터베이스 인덱싱 트리: 지리 정보 쿼리의 R-Tree 구조와 풀 텍스트 검색의 역인덱스(Inverted Index)

배달 앱 아키텍처를 설계하며 반경 3km 이내의 음식점을 검색하는 "WHERE lat BETWEEN AND lng BETWEEN" 방식의 쿼리를 일반 B-Tree 인덱스에 태웠다가 데이터베이스 I/O가 터져버린 적이 있습니다. B-Tree는 사전의 가나다순 배열처럼 1차원의 스칼라 값을 정렬하는 데는 신의 알고리즘이지만, 위도와 경도라는 독립된 2차원의 도메인이 결합되는 순간 인덱스의 효율이 반의반으로 깎여버립니다. 이 절망을 타파하는 자료 구조가 공간 인덱스, 대표적으로 R-Tree(Rectangle Tree)입니다. R-Tree는 공간을 좌표계의 점이 아니라, 여러 개의 최소 경계 사각형(MBR, Minimum Bounding Rectangle)들의 중첩 다각형으로 그룹화시켜 가지를 구축합니다. 사용자가 특정 반경의 원 형태 폴리곤을 던지면, 겹치지 않는 거대한 외곽 MBR 트랜치들은 애초에 진입조차 하지 않고 통째로 가지치기(Pruning) 당해버립니다. 이 수학적 공간 결합 덕에 수천만 건의 지리 픽셀 로우 중에서 정답만 O(log N)으로 꺼내올 수 있었습니다. 이와 완벽히 대척점에 서 있는 난제가 기사 본문 내용 전체를 기반으로 검색(Full Text Search)을 해야 할 때입니다. 본문 컬럼에 B-Tree를 생성해 봐야 인덱스는 무용지물이며, LIKE '%키워드%' 탐색은 풀 테이블 스캔이라는 사형 선고를 받습니다. 이때 등장하는 구원자가 Elasticsearch나 Lucene의 뼈대인 역인덱스(Inverted Index)입니다. 문서가 삽입되는 순간, 엔진은 책의 본문을 토크나이저(Tokenizer)로 잘게 쪼개어 무의미한 조사와 스톱 워드들을 날려버리고 어근을 추출합니다. 그리고는 문서에 포함된 단어들이 문서 번호를 가리키는 것이 아니라(일반 DB 형상), 반대로 개별 '단어(Term)'들을 딕셔너리의 인덱스 키(Key)로 세우고, 이 단어가 출현하는 '문서들의 ID 리스트(Posting List)'를 레코드로 저장하는 완벽한 역발상 구조를 완성합니다. "분산", "아키텍처"라는 단어를 검색하면 엔진은 단숨에 두 단어의 포스팅 리스트 두 개를 배열로 가져와 안달 달린 교집합(Bitwise AND) 연산만을 수행해 내어 즉석 랭킹을 뽑아냅니다. 빅데이터 엔지니어링은 결국 내가 던질 질의어의 디멘션 공간이 몇 차원인지, 그리고 그 공간에 알맞은 매트릭스를 창조해 내는 것임을 실감하는 순간들입니다.