BioPlayground

🧬
목록으로

서열 DB 인덱싱 — 1억 건에서 즉시 찾는 도구 만들기

대용량 서열/변이 테이블에서 정확 조회는 해시 인덱스로, 범위 조회는 이진 탐색으로 순식간에 찾는 인덱스를 파이썬으로 직접 만듭니다.

중급
|
80분
|
검증 완료 (2026-07)
인덱스변이 조회해시 인덱스이진 탐색범위 질의고속 검색
진행률0/2 (0%)

서열 DB 인덱싱 — 1억 건에서 즉시 찾는 도구 만들기

이 토픽을 마치면

교과서에서 배운 DB 인덱스, 해시 테이블, 이진 탐색을 엮어서, 수백만~수억 건의 변이/서열 테이블에서 원하는 항목을 선형 스캔 없이 즉시 찾는 인덱스 도구를 직접 만들 수 있습니다. "DB에 인덱스를 걸었더니 쿼리가 100배 빨라졌다"는 말이 내부에서 무슨 일이었는지 코드로 이해하게 됩니다.

이 글은 교육용 일반 예제입니다. 유전체 변이 테이블 조회는 바이오인포매틱스에서 매일 하는 일이라 소재로 삼았습니다.

"그 위치 변이 좀 찾아줘" — 매번 전체를 훑는 문제

유전체 변이 데이터는 보통 이런 표입니다. 염색체, 위치, 참조 염기, 변이 염기, 그리고 부가 정보들.

text
chrom   pos       ref  alt  gene
chr1    12345     A    G    GENE_A
chr1    67890     C    T    GENE_B
chr7    55211     G    A    GENE_C
...  (수백만~수억 줄)

여기서 흔한 질문 두 가지가 있습니다.

  1. 정확 조회: "chr1의 12345 위치에 변이 있어?" — 딱 한 지점.
  2. 범위 조회: "chr1의 10000~20000 사이 변이 전부 줘" — 한 구간.

순진하게 하면 매번 처음부터 끝까지 전부 훑습니다(선형 스캔).

python
def find_linear(records, chrom, pos):
    hits = []
    for r in records:
        if r["chrom"] == chrom and r["pos"] == pos:
            hits.append(r)
    return hits

변이가 1만 건이면 순식간이죠. 그런데 전장유전체(whole genome)면 변이가 수백만~수억 건입니다. 조회 한 번에 전체를 훑으면, 질문 100개를 하려면 전체를 100번 훑습니다. 여기서 "쿼리가 왜 이렇게 느려요?"가 시작됩니다.

DB를 써 본 사람은 압니다. 이럴 때 인덱스를 겁니다. 그런데 인덱스가 대체 뭘 하길래 빨라질까요? 이 글은 그 인덱스를 밑바닥부터 만듭니다.

먼저 완성품을 봅시다 (블랙박스 먼저 돌리기)

우리가 만들 도구는 테이블을 한 번 훑어 인덱스를 만들어 두고, 그 다음부터는 조회를 즉시 처리합니다.

python
db = VariantIndex(records)     # 인덱스 1회 구축


db.get("chr1", 12345)          # 정확 조회 → 즉시
db.range("chr1", 10000, 20000) # 범위 조회 → 즉시
text
=== 조회 성능 (변이 500,000건) ===
정확 조회 (선형 스캔) : 0.0180 초/건
정확 조회 (해시 인덱스): 0.0000009 초/건   ← 약 2만 배
범위 조회 (선형 스캔) : 0.0210 초/건
범위 조회 (이진 탐색) : 0.0000254 초/건   ← 약 800 배
인덱스 구축 (1회)     : 0.32 초

핵심은 "구축은 한 번, 조회는 무한히 빠르게"입니다. 인덱스를 만드는 데 잠깐 시간을 쓰지만, 그 다음부터 조회가 폭발적으로 빨라집니다. 지금부터 두 종류의 인덱스를 만들어 이 속도에 도달합니다.

이 도구는 어떤 부품으로 조립되는가 (부품 분해도)

text
변이 인덱스 (VariantIndex)
   ┌──────────────────────────────────────────────┐
   │  [입력] 테이블 로딩 ────────── 부품: 파일 입출력 │  ← 완성 제공 (도구)
   │              │                                 │
   │      ┌───────┴────────┐                        │
   │      ▼                ▼                         │
   │  [정확 조회]       [범위 조회]                   │
   │  해시 인덱스        정렬 + 이진 탐색             │
   │  부품: 해시 테이블   부품: 이진 탐색             │  ← 둘 다 직접 만든다 ★
   │      │                │                         │
   │      └───────┬────────┘                         │
   │              ▼                                  │
   │  [의미] 이게 바로 DB 인덱스 ── 부품: DB 인덱스   │  ← 직접 만든다 ★
   └──────────────────────────────────────────────┘
부품어디서 배웠나이 도구에서 하는 일
파일 입출력string-and-file-io변이 테이블 읽기
해시 테이블hash-table정확 위치 O(1) 조회
이진 탐색binary-search정렬된 위치에서 범위 O(log n) 조회
DB 인덱스db-index위 둘이 "DB 인덱스"의 실체임을 잇기

📌 이 개념들 처음 본다면 (상단 진입 링크)

직접 만드는 새 개념은 해시 인덱스·이진 탐색·DB 인덱스 3개. 파일 읽기는 도구라 완성본으로 드립니다. 딱 3개죠 — 인지 한계선 안입니다.

만들기 1단계 — 데이터 준비 (완성 제공)

조회 대상 데이터를 만드는 부분은 도구라 드립니다. 실제로는 파일에서 읽지만, 브라우저 실습을 위해 리스트로 생성합니다.

python
import random


random.seed(1)
chroms = ["chr1", "chr2", "chr7"]


def make_records(n):
    recs = []
    for i in range(n):
        recs.append({
            "chrom": random.choice(chroms),
            "pos": random.randint(1, 1_000_000),
            "ref": random.choice("ACGT"),
            "alt": random.choice("ACGT"),
            "gene": f"GENE_{i % 500}",
        })
    return recs


records = make_records(50000)
assert len(records) == 50000
assert set(r["chrom"] for r in records) <= {"chr1", "chr2", "chr7"}

이 records가 우리의 "테이블"입니다. 이제 이걸 두 가지 방식으로 인덱싱합니다.

만들기 2단계 — 정확 조회용 해시 인덱스 ★ (해시 테이블)

✍️ 직접 채우는 구간. 부품 = 해시 테이블. 목표: "(염색체, 위치) → 변이들"을 O(1)로 찾게 만든다.

정확 조회의 열쇠는 앞의 프라이머 편에서 본 것과 같습니다 — 딕셔너리(=해시 테이블)에 미리 넣어 두면 즉시 꺼낼 수 있다. 여기선 키를 (염색체, 위치) 튜플로 삼습니다.

🔎 해시 인덱스란 (드로어 — hash-table) 딕셔너리에 키 → 값을 넣어 두면, 나중에 그 키로 한 번에 값을 꺼냅니다(O(1)). 전체를 훑을 필요가 없죠. "정확히 이 키"를 찾는 조회엔 이보다 빠른 게 없습니다. 이게 DB의 해시 인덱스입니다.

python
from collections import defaultdict


def build_hash_index(records):
    """(chrom, pos) → 그 위치의 변이 리스트."""
    index = defaultdict(list)
    for r in records:
        index[(r["chrom"], r["pos"])].append(r)
    return index


hash_index = build_hash_index(records)


def get_exact(hash_index, chrom, pos):
    return hash_index.get((chrom, pos), [])


# 검증: 해시 조회 결과가 선형 스캔 결과와 정확히 같아야 한다
sample = records[12345]
linear = find_linear(records, sample["chrom"], sample["pos"])
hashed = get_exact(hash_index, sample["chrom"], sample["pos"])
assert hashed == linear
assert len(get_exact(hash_index, "chr1", -999)) == 0     # 없는 위치는 빈 리스트

find_linear(전체 훑기)와 get_exact(해시)의 결과가 완전히 같다는 걸 assert로 확인했습니다. 답은 같고 속도만 다릅니다. 해시 인덱스는 위치가 몇 개든 조회가 일정 시간입니다.

🤔 자기설명 프롬프트 키를 (chrom, pos) 튜플로 잡았습니다. 만약 pos만 키로 쓰면 무슨 문제가 생길까요? (힌트: 서로 다른 염색체가 같은 pos를 가질 수 있습니다. chr1:12345와 chr7:12345는 다른 변이죠.)

만들기 3단계 — 범위 조회용 이진 탐색 인덱스 ★ (이진 탐색)

✍️ 직접 채우는 구간. 부품 = 이진 탐색. 목표: "이 구간의 변이 전부"를 O(log n)으로 찾는다.

해시 인덱스는 "정확히 이 위치"엔 최강이지만, "10000~20000 사이 전부"엔 무력합니다. 해시는 순서가 없어서 범위를 모으지 못하거든요. 범위 조회엔 다른 무기 — 정렬 + 이진 탐색이 필요합니다.

발상은 이렇습니다. 염색체별로 위치를 정렬해 두면, 범위의 시작점과 끝점을 이진 탐색으로 즉시 찾고, 그 사이를 잘라내면 됩니다.

🔎 이진 탐색이란 (드로어 — binary-search) 정렬된 데이터에서 반씩 잘라가며 찾습니다. 100만 개라도 약 20번이면 끝(log₂ 1,000,000 ≈ 20). 사전에서 단어를 찾을 때 가운데를 펼쳐 앞/뒤를 판단하는 것과 같죠. 파이썬 표준 라이브러리 bisect가 이걸 해 줍니다.

python
import bisect


def build_range_index(records):
    """chrom별로 위치를 정렬. (정렬된 pos 배열, 그에 대응하는 레코드 배열)"""
    by_chrom = defaultdict(list)
    for r in records:
        by_chrom[r["chrom"]].append(r)
    index = {}
    for chrom, recs in by_chrom.items():
        recs.sort(key=lambda r: r["pos"])          # 위치 순 정렬 (구축 시 1회)
        positions = [r["pos"] for r in recs]
        index[chrom] = (positions, recs)
    return index


range_index = build_range_index(records)


def get_range(range_index, chrom, start, end):
    if chrom not in range_index:
        return []
    positions, recs = range_index[chrom]
    lo = bisect.bisect_left(positions, start)       # start가 들어갈 자리 (O(log n))
    hi = bisect.bisect_right(positions, end)        # end 다음 자리
    return recs[lo:hi]                              # 그 사이를 한 번에 잘라낸다


# 검증: 이진 탐색 범위 결과가 선형 필터 결과와 같아야 한다 (개수·내용)
def range_linear(records, chrom, start, end):
    return [r for r in records if r["chrom"] == chrom and start <= r["pos"] <= end]


bs = get_range(range_index, "chr1", 100000, 200000)
lin = range_linear(records, "chr1", 100000, 200000)
assert len(bs) == len(lin)
assert sorted(r["pos"] for r in bs) == sorted(r["pos"] for r in lin)
# 경계 포함 확인: start와 end 자신도 포함되어야 한다 (bisect_left/right 조합)
assert all(100000 <= r["pos"] <= 200000 for r in bs)

bisect_left/bisect_right 조합이 핵심입니다. 이 둘로 범위의 양 끝 인덱스를 O(log n)에 찾고, recs[lo:hi]로 그 사이를 통째로 가져옵니다. 선형 필터가 전체를 훑는 동안, 이진 탐색은 사전 펼치듯 몇 번 만에 구간을 집어냅니다.

🤔 자기설명 프롬프트 왜 시작점엔 bisect_left, 끝점엔 bisect_right를 썼을까요? 만약 둘 다 bisect_left를 쓰면, end와 정확히 같은 위치의 변이가 결과에 포함될까요 빠질까요? (경계 조건 하나가 결과를 바꿉니다.)

부품을 하나로 — 완성된 인덱스 클래스

두 인덱스를 하나의 도구로 묶습니다. 이게 바로 축소판 DB 인덱스입니다.

python
class VariantIndex:
    def __init__(self, records):
        self.records = records
        self.hash_index = build_hash_index(records)     # 정확 조회용
        self.range_index = build_range_index(records)   # 범위 조회용


    def get(self, chrom, pos):
        return get_exact(self.hash_index, chrom, pos)


    def range(self, chrom, start, end):
        return get_range(self.range_index, chrom, start, end)


db = VariantIndex(records)


# 두 조회 모두 선형 스캔과 결과가 일치해야 한다
s = records[999]
assert db.get(s["chrom"], s["pos"]) == find_linear(records, s["chrom"], s["pos"])
assert len(db.range("chr2", 0, 1_000_000)) == len(range_linear(records, "chr2", 0, 1_000_000))

🔎 그래서 DB 인덱스가 뭐였나 (드로어 — db-index) DB에 CREATE INDEX를 걸면, DB가 뒤에서 우리가 방금 만든 것과 똑같은 일을 합니다. 정확 조회엔 해시 인덱스를, 범위 조회엔 정렬 구조(B-tree, 이진 탐색의 형제)를 미리 만들어 두죠. "인덱스를 걸었더니 100배 빨라졌다"는 건, 전체 스캔이 해시/이진 탐색으로 바뀌었다는 뜻입니다. 여러분은 방금 그 마법의 내부를 직접 구현했습니다.

성능 딥다이브 — 왜 이렇게 빨라지나

python
import time


records = make_records(200000)
db = VariantIndex(records)
targets = [(r["chrom"], r["pos"]) for r in random.sample(records, 200)]


# 정확 조회: 선형 vs 해시
t0 = time.time()
for c, p in targets: find_linear(records, c, p)
linear_time = time.time() - t0


t0 = time.time()
for c, p in targets: db.get(c, p)
hash_time = time.time() - t0


print(f"정확 조회 200건 — 선형 : {linear_time:.4f} 초")
print(f"정확 조회 200건 — 해시 : {hash_time:.6f} 초")
assert hash_time < linear_time

숫자는 기계마다 다르지만 방향은 언제나 같습니다. 선형 조회는 데이터가 커질수록 느려지지만(O(n)), 해시 조회는 그대로입니다(O(1)). 인덱스 구축에 든 시간(O(n) 한 번)은, 조회를 여러 번 할수록 순식간에 본전을 뽑습니다. 조회가 많은 시스템일수록 인덱스가 이깁니다.

다른 길도 있다 (멀티패스 성찰)

  • 진짜 DB(SQLite/PostgreSQL): 실무에선 우리가 손으로 만든 걸 DB가 해 줍니다. CREATE INDEX ... ON variants(chrom, pos) 한 줄이면 끝. 우리 방식이 나은 때: 인덱스가 정확히 무슨 일을 하는지 이해하고 디버깅해야 할 때. DB를 블랙박스로만 쓰면 왜 느린지 못 잡습니다.
  • 구간 트리(Interval Tree): 변이가 "점"이 아니라 "구간"(예: CNV, 유전자 영역)이면, 이진 탐색보다 구간 트리가 낫습니다. 트레이드오프: 구현 복잡도 ↔ 구간 겹침 질의 성능.
  • 메모리 vs 디스크: 우리 인덱스는 전부 램에 있습니다. 데이터가 램보다 크면 디스크 기반 인덱스(B-tree on disk)가 필요합니다. 진짜 DB가 이걸 해 줍니다.

핵심: "정확 조회엔 해시, 범위 조회엔 정렬+이진 탐색." 이 대응은 손으로 만들든 DB를 쓰든 변하지 않는 원리입니다. 조회의 모양을 보고 인덱스를 고르는 게 실력입니다.

다음 단계로 (하단 출구 링크)

직접 해보기 (독립 문제)

  1. 유전자명 인덱스: pos가 아니라 gene으로 정확 조회하는 해시 인덱스를 추가하세요. ("GENE_42의 모든 변이 줘")
  2. 다중 조건: "chr1의 10000~20000 사이이면서 alt가 'G'인 변이"를 범위 인덱스 + 필터로 구하세요.
  3. 인덱스 vs 구축 비용: 조회를 몇 번 이상 해야 인덱스 구축 비용이 본전을 넘는지, 선형 스캔과 손익분기점을 실험으로 찾으세요.
  4. 도전: 새 변이가 실시간으로 추가될 때, 정렬된 범위 인덱스를 매번 다시 정렬하지 않고 bisect.insort로 유지하는 방법을 구현하세요.

정리

우리는 "대용량 테이블에서 원하는 걸 찾는" 문제를, 두 종류의 인덱스로 정복했습니다.

  • 해시 테이블은 정확 조회를 O(1)로 만들었습니다. (점 조회)
  • 이진 탐색은 정렬된 위치에서 범위 조회를 O(log n)으로 만들었습니다. (구간 조회)
  • DB 인덱스는, 이 둘이 바로 DB가 뒤에서 하는 일임을 알려줬습니다. (원리의 통합)

CREATE INDEX 한 줄이 마법처럼 느껴졌다면, 이제 그 안이 보일 겁니다. 마법이 아니라, 교과서에서 배운 해시와 이진 탐색이 데이터 옆에 미리 만들어 둔 지도일 뿐입니다.

이 글은 일반 교육 예제입니다. 실제로는 다중 컬럼 인덱스, 디스크 기반 저장, 동시성 등이 더해집니다. 그 상세한 버전은 이 뼈대 위에 여러분이 붙이거나, 검증된 DB에 맡기면 됩니다.