[Data] 보조 색인에서 인메모리 DB까지 — 데이터를 찾는 다양한 전략

 

📌 데이터베이스 깊이 파기 시리즈 — 5편 들어가며

---

3편에서 B-Tree와 LSM-Tree라는 두 가지 핵심 스토리지 엔진 구조를 살펴보았습니다. 하지만 실제 데이터베이스에서는 기본 키(primary key) 하나만으로 데이터를 찾는 경우가 드뭅니다. "이메일이 user@example.com인 사용자를 찾아라", "서울에 있는 식당 중 평점 4.5 이상을 찾아라"처럼 기본 키가 아닌 다른 칼럼으로 검색하는 일이 훨씬 많습니다.

[Data] B-Tree vs LSM-Tree — RDB와 NoSQL은 왜 다른 스토리지 엔진을 선택했을까

 

 

이번 편에서는 이런 요구를 해결하는 보조 색인(Secondary Index)의 구조와 변형들을 살펴보고, 나아가 디스크 기반 저장소의 한계를 넘어서는 인메모리 데이터베이스까지 다뤄보겠습니다.

 

---

1. 보조 색인이 필요한 이유

기본 키 색인(Primary Index)은 각 행을 고유하게 식별합니다. B-Tree든 LSM-Tree든, 기본 키를 기준으로 데이터를 빠르게 찾을 수 있도록 구성되어 있습니다. 하지만 현실의 질의는 기본 키만으로 해결되지 않습니다.

-- 기본 키가 아닌 칼럼으로 검색
SELECT * FROM users WHERE email = 'user@example.com';
SELECT * FROM orders WHERE customer_id = 42;

 

보조 색인이 없다면, 데이터베이스는 테이블 전체를 처음부터 끝까지 스캔(Full Table Scan)해야 합니다. 수백만 건의 데이터에서 이런 방식은 치명적으로 느립니다. 보조 색인은 기본 키가 아닌 칼럼에 대해서도 빠른 검색을 가능하게 해 주는 추가적인 색인 구조입니다.

 

기본 키 색인과의 핵심적인 차이는 고유성 보장 여부입니다. 기본 키는 하나의 값이 정확히 하나의 행을 가리키지만, 보조 색인의 키는 여러 행을 가리킬 수 있습니다. 예를 들어 city = '서울'이라는 조건에 해당하는 행이 수천 개일 수 있습니다. 이러한 중복 키를 처리하는 방식은 구현마다 다릅니다. 하나의 키에 행 식별자 목록을 매달아 두는 방식(posting list)도 있고, 행 식별자를 키에 덧붙여 각 항목을 고유하게 만드는 방식도 있습니다. 어느 쪽이든 B-Tree나 LSM-Tree를 그대로 활용할 수 있습니다.

 

그렇다면 보조 색인이 가리키는 "행 식별자"로 실제 데이터를 어떻게 찾아갈까요? 여기서 힙 파일이라는 개념이 등장합니다.

 

---

2. 힙 파일: 실제 데이터가 사는 곳

2.1 힙 파일의 구조

힙 파일(Heap File)은 데이터가 특별한 정렬 순서 없이 저장되는 영역입니다. 새로운 행이 삽입되면, 빈 공간이 있는 곳 아무 데나 배치됩니다. 이름 그대로 데이터가 "쌓여 있는(heap)" 형태입니다.

 

보조 색인의 각 항목은 힙 파일 내의 특정 위치를 가리키는 포인터를 저장합니다. 이 포인터가 바로 행 식별자이며, 보통 파일 번호와 파일 내 오프셋의 조합으로 구성됩니다.

이 구조의 장점은 색인과 데이터의 분리입니다. 여러 보조 색인이 동일한 힙 파일의 같은 행을 가리킬 수 있으므로, 데이터를 복제할 필요가 없습니다. email 색인과 city 색인이 동시에 같은 사용자 행을 참조할 수 있습니다.

 

2.2 힙 파일의 한계

하지만 힙 파일 방식에는 대가가 따릅니다. 색인에서 포인터를 얻은 뒤, 실제 데이터를 읽으려면 힙 파일의 해당 위치로 한 번 더 디스크를 찾아가야 합니다. 이 추가 디스크 접근을 힙 조회(Heap Lookup)라고 부릅니다.

 

한두 건을 찾는 질의라면 힙 조회 비용은 크지 않습니다. 문제는 색인으로 찾은 행들이 힙 파일 내에서 물리적으로 흩어져 있는 경우입니다. 예를 들어 city = '서울'에 해당하는 수천 건의 행이 힙 파일 곳곳에 산재해 있다면, 각 행을 읽을 때마다 디스크 헤드가 서로 다른 위치로 이동해야 합니다. 이런 랜덤 I/O는 순차 I/O에 비해 수십~수백 배 느립니다. 이 문제를 해결하는 첫 번째 방법이 바로 클러스터드 색인입니다.

 

---

3. 클러스터드 색인: 데이터와 색인을 하나로

3.1 색인 안에 데이터를 넣다

클러스터드 색인(Clustered Index)은 색인의 리프 노드에 포인터 대신 행 데이터 자체를 저장하는 방식입니다. 색인과 데이터가 물리적으로 하나로 합쳐져 있으므로, 색인을 탐색하면 곧바로 데이터를 얻을 수 있습니다. 힙 조회가 필요 없습니다.

 

MySQL의 InnoDB는 대표적인 클러스터드 색인 구현체입니다. InnoDB에서는 기본 키 색인이 곧 클러스터드 색인이며, 테이블의 행 데이터가 기본 키의 B-Tree 리프 노드에 직접 저장됩니다. 즉 InnoDB에서 테이블 자체가 기본 키 색인이라고 할 수 있습니다.

3.2 보조 색인은 어떻게 동작하는가

클러스터드 색인 구조에서 보조 색인은 힙 파일의 물리적 위치가 아닌, 기본 키 값을 포인터로 사용합니다. 예를 들어 email 보조 색인에서 'user@example.com'을 찾으면, 리프 노드에는 해당 행의 기본 키 값(예: id = 42)이 저장되어 있습니다. 이 기본 키 값으로 클러스터드 색인(기본 키 B-Tree)을 다시 탐색하여 실제 행 데이터를 가져옵니다.

 

이 과정은 B-Tree를 두 번 탐색하는 것이므로, 기본 키로 직접 검색하는 것보다 느립니다. 하지만 물리적 포인터 대신 논리적인 기본 키 값을 사용하기 때문에, 행의 물리적 위치가 변경되더라도(예: 페이지 분할로 행이 다른 페이지로 이동하더라도) 보조 색인을 갱신할 필요가 없다는 중요한 장점이 있습니다.

 

3.3 클러스터드 색인의 트레이드오프

클러스터드 색인은 읽기 성능에서 확실한 이점을 제공하지만, 몇 가지 비용이 따릅니다.

 

첫째, 데이터가 색인 구조 안에 포함되므로 쓰기 시 오버헤드가 증가합니다. 행의 크기가 커서 기존 페이지에 들어가지 않으면 페이지 분할(page split)이 발생하고, 이는 연쇄적인 재배치로 이어질 수 있습니다.

 

둘째, 보조 색인이 기본 키 값을 저장하므로, 기본 키가 길수록(예: UUID) 모든 보조 색인의 크기가 함께 커집니다. 이런 이유로 InnoDB에서는 기본 키를 짧은 정수형(auto-increment)으로 설정하는 것이 일반적인 관행입니다.

 

---

4. 커버링 색인: 색인만으로 질의를 완결하다

4.1 불필요한 힙 조회를 제거하는 전략

클러스터드 색인이 "전체 행 데이터를 색인에 넣는" 전략이라면, 커버링 색인(Covering Index)은 "질의에 필요한 칼럼만 색인에 넣는" 절충안입니다. 색인에 포함된 칼럼만으로 질의를 완전히 처리할 수 있으면, 힙 파일이나 클러스터드 색인의 리프 노드를 찾아갈 필요가 없습니다. 이러한 상황을 "색인이 질의를 커버(cover)한다"고 표현합니다.

 

예를 들어, 다음과 같은 질의가 자주 실행된다고 가정해 봅시다.

SELECT name, email FROM users WHERE city = '서울';

city만으로 구성된 일반 보조 색인이 있다면, 색인에서 city = '서울'에 해당하는 행 식별자를 찾은 뒤, 각 행의 name과 email을 읽기 위해 힙 조회를 해야 합니다. 하지만 (city, name, email)을 포함하는 커버링 색인이 있다면, 색인 자체에서 모든 필요한 데이터를 얻을 수 있습니다.

 

4.2 커버링 색인의 트레이드오프

커버링 색인은 특정 질의의 읽기 성능을 극적으로 향상시킬 수 있습니다. 하지만 색인에 더 많은 칼럼을 포함할수록 색인의 크기가 커지고, 쓰기 시 갱신해야 할 데이터도 늘어납니다. 또한 색인이 특정 질의 패턴에 최적화되어 있으므로, 질의 패턴이 변하면 색인을 재설계해야 할 수 있습니다.

 

결국 힙 파일, 클러스터드 색인, 커버링 색인은 같은 문제 — "색인에서 실제 데이터까지의 거리를 어떻게 줄일 것인가" — 에 대한 서로 다른 수준의 답변입니다.

전략	색인에 저장하는 것	힙 조회	쓰기 비용	저장 공간
힙 파일 참조	포인터만	항상 필요	낮음	작음
클러스터드 색인	전체 행 데이터	불필요	높음	큼
커버링 색인	일부 칼럼	조건부 불필요	중간	중간

 

---

5. 다중 칼럼 색인: 여러 차원을 한 번에

5.1 결합 색인

지금까지 살펴본 색인은 모두 하나의 키를 기준으로 동작합니다. 하지만 현실의 질의는 여러 칼럼을 동시에 조건으로 사용하는 경우가 많습니다.

SELECT * FROM users WHERE last_name = '김' AND first_name = '민수';

 

결합 색인(Concatenated Index)은 가장 일반적인 다중 칼럼 색인 형태입니다. 여러 칼럼의 값을 하나의 키로 연결하여 정렬합니다. (last_name, first_name) 결합 색인은 성(姓)을 기준으로 먼저 정렬하고, 같은 성 내에서 이름을 기준으로 다시 정렬합니다.

 

이 방식은 전화번호부와 같은 원리입니다. 전화번호부에서 "김민수"를 찾을 때, 먼저 "김"씨 섹션으로 이동한 뒤 "민수"를 찾습니다. 하지만 이름만 알고 성을 모르는 경우에는 전화번호부가 도움이 되지 않습니다.

 

이것이 결합 색인의 핵심 제약입니다. 칼럼 순서가 중요합니다. (last_name, first_name) 색인은 last_name 단독 검색이나 last_name + first_name 검색에는 효과적이지만, first_name 단독 검색에는 사용할 수 없습니다. 색인 설계 시 가장 빈번한 질의 패턴을 고려하여 칼럼 순서를 결정해야 합니다.

 

5.2 다차원 색인

결합 색인은 칼럼들을 하나의 축으로 이어 붙이는 방식이기 때문에, 두 칼럼을 동시에 범위로 좁히는 질의에는 적합하지 않습니다. 다음과 같은 질의를 생각해 봅시다.

-- 특정 지역 내의 식당 검색 (위도/경도 범위)
SELECT * FROM restaurants
WHERE latitude BETWEEN 37.50 AND 37.55
  AND longitude BETWEEN 126.95 AND 127.00;

 

 

(latitude, longitude) 결합 색인이 있다면, 위도 범위에 해당하는 행들을 먼저 찾을 수 있습니다. 하지만 그 안에서 경도 범위를 걸러내려면 결국 위도 범위에 해당하는 모든 행을 스캔해야 합니다. 두 차원을 동시에 효율적으로 좁혀 나갈 수 없습니다.

 

 

이 문제를 해결하기 위해 고안된 것이 다차원 색인입니다. 대표적인 구현 방식으로는 다음과 같은 것들이 있습니다.

 

R-Tree는 공간 데이터를 위한 색인 구조로, PostGIS 등에서 널리 사용됩니다. 핵심 아이디어는 인접한 데이터 포인트들을 최소 경계 사각형(MBR, Minimum Bounding Rectangle)으로 묶고, 이 사각형들을 다시 더 큰 사각형으로 묶어 트리 구조를 만드는 것입니다. 범위 질의가 들어오면, 질의 영역과 겹치지 않는 사각형은 즉시 건너뛸 수 있으므로 탐색 범위가 빠르게 줄어듭니다.

 

공간 채움 곡선(Space-Filling Curve) 방식은 2차원 좌표를 1차원 값으로 변환하여 일반적인 B-Tree에 저장합니다. 대표적인 예가 Z-order 곡선(Morton Code)과 Hilbert 곡선입니다. 이 방식은 기존의 B-Tree 인프라를 그대로 활용할 수 있다는 장점이 있지만, 변환 과정에서 공간적 인접성이 완벽하게 보존되지 않는 한계도 있습니다.

 

5.3 공간을 넘어선 다차원 질의

다차원 색인은 지리 좌표만을 위한 것이 아닙니다. 본질적으로 "여러 축의 범위를 동시에 좁혀야 하는" 모든 질의에 적용할 수 있습니다.

 

예를 들어, 전자상거래 플랫폼에서 (가격, 평점, 리뷰 수) 세 축을 동시에 범위 검색해야 한다면, 이것도 다차원 질의입니다. 날씨 데이터에서 (날짜, 온도, 습도) 범위로 검색하는 것도 마찬가지입니다. 결합 색인으로는 첫 번째 칼럼의 범위만 효율적으로 좁힐 수 있지만, 다차원 색인은 모든 축을 동시에 활용할 수 있습니다.

 

---

6. 인메모리 데이터베이스: 디스크를 넘어서

6.1 왜 디스크를 버리는가

지금까지 다룬 모든 색인 구조는 근본적으로 하나의 제약과 싸우고 있습니다. 디스크 I/O는 느리다는 것입니다. 힙 조회를 줄이려는 클러스터드 색인도, 색인만으로 질의를 완결하려는 커버링 색인도, 결국 디스크 접근 횟수를 최소화하기 위한 전략입니다.

 

그렇다면 아예 모든 데이터를 메모리에 올려놓으면 어떨까요? RAM 가격이 지속적으로 하락하고, 많은 데이터셋이 수십 GB 이내에 들어가는 현실을 고려하면, 이것은 충분히 실용적인 선택입니다.

 

인메모리 데이터베이스(In-Memory Database)는 데이터 전체를 RAM에 유지하여, 디스크 I/O라는 병목 자체를 제거하는 접근 방식입니다. 대표적인 인메모리 데이터베이스로는 Redis, Memcached, VoltDB, MemSQL(현재 SingleStore) 등이 있습니다.

 

6.2 인메모리 DB의 진짜 장점

인메모리 데이터베이스가 빠른 이유가 단순히 "디스크를 읽지 않아서"라고 생각하기 쉽습니다. 하지만 이것만이 전부는 아닙니다. 디스크 기반 데이터베이스도 충분한 메모리가 있으면 운영체제의 페이지 캐시 덕분에 대부분의 읽기를 메모리에서 처리할 수 있습니다. 즉, 읽기 성능만 놓고 보면 디스크 기반 DB도 인메모리 DB에 근접할 수 있습니다.

 

인메모리 데이터베이스의 진짜 성능 우위는 디스크 기반 자료 구조의 오버헤드를 제거할 수 있다는 점에서 나옵니다. 디스크 기반 엔진은 데이터를 디스크에 쓸 수 있는 형태로 인코딩해야 합니다. 고정 크기 페이지로 나누고, 페이지 내 슬롯을 관리하고, 단편화를 처리하는 등의 오버헤드가 존재합니다. 인메모리 데이터베이스는 이런 제약 없이, 메모리에 최적화된 자료 구조를 자유롭게 사용할 수 있습니다.

 

예를 들어, Redis의 정렬된 집합(Sorted Set)은 스킵 리스트(Skip List)로 구현되어 있습니다. 스킵 리스트는 포인터 기반의 자료 구조로, 디스크에 효율적으로 직렬화하기 어렵지만 메모리에서는 매우 빠르게 동작합니다. 우선순위 큐나 집합 연산 같은 구조도 마찬가지입니다. 디스크 기반 DB에서는 이런 구조를 B-Tree나 해시 테이블에 맞춰야 하지만, 인메모리 DB는 각 용도에 가장 적합한 자료 구조를 자유롭게 선택할 수 있습니다.

 

정리하면, 인메모리 데이터베이스의 성능 우위는 단순히 "메모리라서 빠르다"가 아니라, 디스크 제약에서 벗어난 자료 구조 설계에서 비롯됩니다.

 

6.3 영속성 문제와 해결책

"메모리에만 데이터가 있으면 서버가 꺼질 때 다 사라지지 않는가?"라는 질문은 자연스럽습니다. 인메모리 데이터베이스는 이 문제를 여러 방식으로 해결합니다. Redis를 예로 들면 두 가지 영속성 메커니즘을 제공합니다.

 

첫째, AOF(Append-Only File) 방식입니다. 모든 쓰기 연산을 순차적으로 디스크에 추가 기록합니다. 서버가 재시작되면 이 로그를 처음부터 재생하여 메모리 상태를 복원합니다. 3편에서 다룬 WAL과 유사한 원리이며, 모든 연산을 기록하므로 데이터 손실을 최소화할 수 있습니다. 다만 로그 파일이 계속 커지므로, Redis는 주기적으로 AOF를 다시 쓰는(rewrite) 과정을 통해 파일 크기를 줄입니다. 이 과정에서 중간 연산들을 생략하고 각 키의 최종 상태만 기록하여, 동일한 결과를 훨씬 작은 파일로 표현합니다.

 

둘째, RDB 스냅샷(Snapshot) 방식입니다. 일정 간격으로 메모리의 전체 상태를 바이너리 파일로 디스크에 기록합니다. AOF보다 복구 속도가 빠르지만, 마지막 스냅샷 이후의 변경 사항은 유실될 수 있습니다. 실무에서는 AOF와 RDB를 함께 사용하여 각각의 단점을 보완하는 경우가 많습니다.

 

이 외에도 다른 머신에 복제(Replication)하여 내구성을 확보하는 방법이 있습니다. 한 대의 서버가 장애를 겪더라도, 복제본에서 데이터를 복구할 수 있습니다.

 

중요한 점은, 이러한 디스크 기록은 내구성(Durability)을 위한 것이지 읽기 경로에 관여하지 않는다는 것입니다. 읽기는 항상 메모리에서 이루어지고, 디스크는 오직 장애 복구를 위한 보험 역할만 합니다.

 

6.4 안티캐싱: 메모리 한계를 넘어서

인메모리 데이터베이스의 명백한 제약은 데이터 크기가 가용 메모리를 초과할 수 없다는 점입니다. 이에 대한 흥미로운 해결책으로 안티캐싱(Anti-Caching) 접근 방식이 있습니다.

 

전통적인 디스크 기반 데이터베이스는 "디스크에 데이터가 있고, 자주 접근하는 것을 메모리에 캐싱"합니다. 안티캐싱은 이것을 정확히 뒤집습니다. "메모리에 데이터가 있고, 오래 접근하지 않은 것을 디스크로 내보냅니다." 비유하자면, 전통적 방식은 창고(디스크)에서 필요한 물건을 책상(메모리)으로 가져오는 것이고, 안티캐싱은 책상 위에 모든 것을 두되 공간이 부족해지면 안 쓰는 것을 창고로 치우는 것입니다.

 

핵심적인 차이는 메모리 관리의 주체입니다. 운영체제의 가상 메모리(페이지 스왑)도 비슷한 일을 하지만, OS는 어떤 데이터가 "뜨겁고(hot)" 어떤 데이터가 "차가운지(cold)" 알지 못합니다. 반면 데이터베이스는 접근 패턴을 직접 추적하므로, 튜플(행) 단위로 더 세밀하고 효율적인 방출(eviction) 결정을 내릴 수 있습니다. 이 접근 방식을 통해 인메모리 데이터베이스도 물리적 메모리보다 큰 데이터셋을 다룰 수 있게 됩니다.

 

---

7. 마무리: 데이터를 찾는 전략의 스펙트럼

이번 편에서 다룬 내용을 하나의 흐름으로 정리하면, "색인에서 실제 데이터까지의 거리를 줄이기 위한 진화 과정"으로 볼 수 있습니다.

 

힙 파일은 색인과 데이터를 분리하여 유연성을 확보하지만, 힙 조회라는 추가 비용이 발생합니다. 클러스터드 색인은 데이터를 색인 안에 넣어 이 거리를 완전히 제거하고, 커버링 색인은 필요한 칼럼만 색인에 포함시켜 절충합니다.

 

다중 칼럼 색인은 단일 칼럼의 한계를 넘어 여러 차원의 데이터를 효율적으로 탐색할 수 있게 해 줍니다. 결합 색인이 1차원적 연결이라면, R-Tree나 공간 채움 곡선은 진정한 다차원 탐색을 가능하게 합니다.

 

그리고 인메모리 데이터베이스는 가장 근본적인 접근 방식으로, 디스크 I/O라는 제약 자체를 제거합니다. 단순히 "메모리라서 빠른" 것이 아니라, 디스크 기반 자료 구조의 오버헤드를 제거하고 메모리에 최적화된 자료 구조를 자유롭게 사용할 수 있다는 것이 핵심이었습니다.

 

다음 편에서는 관점을 완전히 바꿔, OLTP와 OLAP이라는 두 가지 근본적으로 다른 워크로드를 살펴보겠습니다. 지금까지 다룬 색인과 스토리지 엔진은 주로 OLTP(트랜잭션 처리)에 최적화된 구조입니다. 하지만 대규모 분석(OLAP)에는 전혀 다른 접근이 필요하며, 이를 위해 데이터 웨어하우스와 칼럼 지향 저장소라는 새로운 세계가 열립니다.

 

---

레퍼런스

데이터 중심 애플리케이션 설계 - 마틴 클레프만

 

---

읽어주셔서 감사합니다! 잘못된 내용이나 보완할 점이 있다면 댓글로 알려주세요!