데이터베이스 인덱스 내부 구조 — B-Tree와 LSM-Tree 비교

인덱스의 역할과 중요성

데이터베이스 인덱스는 테이블 전체를 스캔하지 않고 원하는 데이터에 빠르게 접근하는 자료구조입니다. 인덱스 설계는 데이터베이스 성능에 가장 큰 영향을 미치는 요소이며, 내부 구조를 이해해야 올바른 인덱스 전략을 세울 수 있습니다.

B-Tree 구조

B-Tree(Balanced Tree)는 관계형 데이터베이스의 기본 인덱스 구조입니다. 정렬된 키를 균형 잡힌 트리에 저장하여 O(log N)의 검색, 삽입, 삭제를 보장합니다.

-- B-Tree 인덱스 동작 시각화
-- 루트 노드: [30 | 70]
--           /    |     \
-- 리프:  [10,20] [40,50,60] [80,90,100]

-- PostgreSQL에서 인덱스 내부 구조 확인
CREATE EXTENSION pageinspect;

-- 메타 페이지 확인
SELECT * FROM bt_metap('idx_users_email');

-- 루트 페이지 항목 확인
SELECT * FROM bt_page_items('idx_users_email', 1);

-- 인덱스 통계 확인
SELECT schemaname, tablename, indexname,
       idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
WHERE tablename = 'users';

B-Tree의 읽기/쓰기 특성

LSM-Tree 구조

LSM-Tree(Log-Structured Merge Tree)는 쓰기 최적화 자료구조입니다. 메모리의 MemTable에 먼저 쓰고, 가득 차면 정렬된 SSTable 파일로 디스크에 플러시합니다.

# LSM-Tree 동작 흐름 (의사코드)
class LSMTree:
    def __init__(self):
        self.memtable = SortedDict()      # 메모리 (Red-Black Tree)
        self.immutable_memtable = None
        self.sstables = []                 # Level 0, 1, 2, ...
        self.wal = WriteAheadLog()         # 복구용
        self.memtable_size_limit = 4 * 1024 * 1024  # 4MB

    def put(self, key, value):
        self.wal.append(key, value)        # WAL에 먼저 기록
        self.memtable[key] = value
        if self.memtable.size() > self.memtable_size_limit:
            self.flush()

    def flush(self):
        self.immutable_memtable = self.memtable
        self.memtable = SortedDict()
        sstable = SSTable.from_sorted(self.immutable_memtable)
        self.sstables[0].append(sstable)
        self.maybe_compact()               # 백그라운드 컴팩션

    def get(self, key):
        # 1. MemTable 검색
        if key in self.memtable:
            return self.memtable[key]
        # 2. Immutable MemTable 검색
        if self.immutable_memtable and key in self.immutable_memtable:
            return self.immutable_memtable[key]
        # 3. SSTable 검색 (Bloom Filter로 빠른 필터링)
        for level in self.sstables:
            for sstable in reversed(level):
                if sstable.bloom_filter.might_contain(key):
                    result = sstable.search(key)
                    if result is not None:
                        return result
        return None

B-Tree vs LSM-Tree 성능 비교

실무 선택 기준

• 읽기 중심 OLTP: B-Tree 기반 (PostgreSQL, MySQL) — 포인트/범위 조회 모두 효율적
• 쓰기 집중 워크로드: LSM-Tree 기반 (Cassandra, ScyllaDB) — 로그, 이벤트, 시계열 데이터
• 하이브리드: TiDB의 TiKV — LSM-Tree 기반이지만 Raft로 일관성 보장
• 키-값 스토어: RocksDB — LSM-Tree 기반, 임베디드 엔진으로 널리 사용

인덱스 내부 구조를 이해하면 EXPLAIN 분석에서 실행 계획을 정확히 해석할 수 있고, 워크로드에 최적화된 인덱스 전략을 수립할 수 있습니다.