데이터베이스 저장 구조Database Storage Structure
DBMS 가 표와 색인을 디스크 페이지에 놓고, 버퍼 풀로 읽고 쓰며, 색인 자료 구조로 원하는 행을 찾게 하는 저장 엔진의 구조다. 제자리에 고쳐 쓰는 B-Tree 와 모아서 덧붙여 쓰는 LSM 트리가 읽기 · 쓰기 비용을 어떻게 나눠 갖는지도 함께 다룬다.
1요약
- 데이터베이스 저장 구조는 DBMS 맨 아래 저장 관리자가 표 · 색인을 고정 크기 페이지로 디스크에 놓고 버퍼 풀로 오가게 하는 구조다(Hellerstein 2007 5장). 그 위에서 접근 방법(힙 · B+-Tree 색인)과 질의 실행기가 돈다(4.5절).
- 디스크의 순차 전송은 무작위 접근보다 10 ~ 100배 빠르다(5.1절) — 그래서 같은 행 하나를 써도 페이지를 제자리에 고쳐 쓰는 엔진과 모았다가 순차로 덧붙이는 엔진의 비용이 크게 갈린다.
- 「저장 쪽이 느리다」는 읽기 · 쓰기 · 공간 중 어느 비용이 올랐는가로 가른다 — 세 비용 가운데 둘을 낮추면 나머지 하나가 오른다(Athanassoulis 2016 3절).
2등장 배경
1970년 Bayer · McCreight 는 노드 하나를 디스크 페이지 하나에 맞춘 B-tree 로 큰 색인을 높이만큼의 페이지 읽기로 찾게 했다(Bayer · McCreight 1970). 그 뒤 관계형 DBMS 는 모두 힙 파일과 B+-tree 색인을 기본 접근 방법으로 갖췄다(Hellerstein 2007 4.5절).
남은 문제는 쓰기였다. 1996년 O'Neil 등은 새 기록을 메모리 요소에 모았다가 디스크 요소로 병합하는 LSM 트리를 냈고(O'Neil 1996), 지금은 commit log · memtable · SSTable · compaction 을 갖춘 저장 엔진으로 쓰인다(Cassandra Storage Engine).
2007년 Hellerstein 등은 저장 관리를 «어디에 놓나(공간 제어)»와 «언제 쓰나(시간 제어 · 버퍼)»로 정리했고(5.1 · 5.2절), 2016년 Athanassoulis 등은 접근 방법 설계를 읽기 · 쓰기 · 공간 세 비용의 맞바꿈(RUM)으로 정리했다(Athanassoulis 2016 1절).
3쉽게 이해하기 — 책 상자를 다루는 도서관 서고
사서 한 사람이 큰 도서관 서고를 맡는다. 책은 같은 크기 상자에 담겨 서고에 있고, 사서는 색인 카드함으로 어느 상자에 있는지 찾은 뒤 상자를 앞 선반으로 가져와 연다. 새 책이 오면 대출 장부에 먼저 적고, 바로 상자를 열어 꽂거나 반납 수레에 모았다가 한꺼번에 새 상자로 묶어 서고에 넣는다.
그림 1 · 사서는 카드함으로 상자를 찾아 앞 선반에서 열고, 새 책은 장부에 먼저 적은 뒤 바로 꽂거나 수레에 모아 묶어 넣는다.
그림 2 · 새 책 3권을 넣을 때 바로 꽂으면 상자 3개를 다시 정리하고, 수레에 모으면 새 상자 1개로 끝나지만 찾을 때 볼 곳이 늘어난다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 사서 | 접근 방법 · 실행기 | 검색 인자(SARG)를 받아 행을 하나씩 돌려준다(Hellerstein 2007 4.5절) |
| 책 상자 | 페이지 | 고정 크기 블록 · PostgreSQL 은 보통 8 KB(66.6절) |
| 서고 | 데이터 파일 | 페이지를 차례로 늘어놓은 큰 파일(5.1절) |
| 앞 선반 | 버퍼 풀 | 페이지 크기 프레임 배열 · dirty bit · pin count(5.3절) |
| 색인 카드함 | 인덱스 · B-Tree | 키로 행이 든 페이지를 찾는다 |
| 대출 장부 | WAL | 페이지보다 먼저 순차로 적는 로그(PostgreSQL 28.3) |
| 반납 수레 | memtable | 정렬된 메모리 요소 · 한도가 차면 SSTable 로 내린다(Cassandra) |
| 묶어 넣기 | compaction | SSTable 여럿을 하나로 합친다(Cassandra) |
⚠ 비유가 맞지 않는 곳: 도서관의 앞 선반은 사서 한 사람이 쓰지만 버퍼 풀은 여러 작업 스레드가 함께 쓰고, 쓰는 동안 pin count 로 상자를 묶어 둔다(Hellerstein 2007 5.3절). 또 수레에서 내린 SSTable 은 다시 고치지 않고, 바꾼 내용은 새 파일로만 쓴다(Cassandra).
4구조 — 저장 관리자와 아래 토픽
저장 구조는 위에서부터 접근 방법 · 버퍼 관리자 · 디스크 파일 세 계층으로 나뉜다. 아래 토픽 가운데 DBMS 구조는 버퍼와 페이지를, 인덱스는 접근 경로를, B-Tree 와 LSM 트리는 색인을 담는 두 방식을 맡는다.
그림 3 · 접근 방법이 버퍼 관리자에게 페이지를 달라고 하고, 버퍼 관리자는 언제 디스크에 쓸지를, 파일 배치는 어디에 놓을지를 정한다.
| 계층 | 맡는 일 | 대표 값 | 아래 토픽 | 근거 |
|---|---|---|---|---|
| 힙 파일 | 행을 순서 없이 담는다 | 색인 없으면 찾기 = 전체 스캔 | DBMS 구조 | Hellerstein 2007 4.5절 |
| 인덱스 | 키 → 행 위치 | 표가 바뀔 때마다 함께 갱신 | 인덱스 | PostgreSQL 11.1 |
| B-Tree | 정렬 키를 페이지 노드에 제자리로 | 찾기 = 높이만큼 페이지 | B-Tree | Bayer · McCreight 1970 |
| LSM 트리 | memtable → 불변 SSTable → compaction | 디스크 쓰기 = 순차만 | LSM 트리 | Cassandra Storage Engine |
| 버퍼 관리자 | 페이지 크기 프레임 배열 · 교체 | shared_ | DBMS 구조 | 5.3절 · PostgreSQL 19.4.1 |
| 페이지 | 머리 24바이트 + 항목 포인터 4바이트씩 | 보통 8 KB | DBMS 구조 | PostgreSQL 66.6 |
🔑 버퍼 관리자는 «언제» 쓸지를, 색인 방식은 «어떤 모양으로» 쓸지를 정한다 — B-Tree 는 페이지를 제자리에서 고치고, LSM 트리는 고치지 않고 새로 덧붙인다.
5동작 — 행 하나를 두 엔진에 쓰고 다시 찾기
설명용 가정 값 — 측정값 표에 100바이트 행 하나를 넣고 키로 다시 찾는다. 페이지 8,192바이트, B-Tree 색인 높이 3, LSM 은 크기 비율 T = 10 · 디스크 3수준이다.
- B-Tree 엔진이 색인 루트 → 내부 → 잎 3페이지를 찾는다 — 버퍼 풀 해시 표에서 루트 · 내부는 적중하고 잎만 디스크에서 8 KB 를 읽어 프레임에 놓는다(Hellerstein 2007 5.3절).
- 잎 페이지와 힙 페이지를 pin 하고 행 · 색인 항목을 넣은 뒤 두 페이지에 dirty bit 를 켠다(5.3절).
- WAL 레코드를 순차로 먼저 쓰고, 커밋은 WAL 만 flush 하고 돌아온다 — 데이터 페이지는 이때 쓰지 않는다(PostgreSQL 28.3).
- 체크포인트가 dirty 페이지 2장을 제자리에 덮어쓴다 — 두 페이지에 이 행만 바뀌었다면 물리 쓰기 16,384바이트 ÷ 논리 쓰기 100바이트 = 약 164배다(Athanassoulis 2016 2절 UO 정의 · 직접 계산).
- 같은 행을 LSM 엔진에 쓰면 commit log 에 덧붙이고 memtable 에 정렬해 넣고 끝난다 — 디스크 무작위 쓰기 0(Cassandra).
- memtable 이 한도에 차면 SSTable 하나로 순차 flush 되고, compaction 이 수준마다 이 행을 최대 T 번 다시 써 약 10 × 3 = 30배가 된다(Athanassoulis 2016 표 1 · T/B · log_T(N/B) 식 직접 계산).
- 키로 다시 찾으면 B-Tree 는 3페이지, LSM 은 수준마다 높이 3을 타 최악 9페이지 — 블룸 필터가 키 없는 수준을 메모리에서 거르면 3페이지로 준다(표 1 · Cassandra).
그림 4 · 같은 행 하나가 B-Tree 엔진은 체크포인트에서 페이지 2장을 덮어써 쓰기가 크고, LSM 엔진은 순차로 덧붙인 뒤 병합에서 다시 써 찾기가 늘어난다.
그림 5 · 읽기 · 쓰기 · 공간 세 비용은 한꺼번에 낮출 수 없다 — B-Tree 는 읽기 쪽, LSM 트리는 쓰기 쪽, 색인 없는 힙은 공간 쪽 꼭짓점에 가깝다.
🔑 쓰기를 모아 순차로 바꾸면 쓰기 비용은 내려가지만, 그 대가로 찾을 때 볼 파일이 늘고 병합 전 옛 값이 공간을 차지한다 — 셋 중 둘을 고르는 일이다(Athanassoulis 2016 3절).
6비교 — 관계 모델 · 질의 처리 · 트랜잭션 · 회복과의 경계
| 기술 | 맡는 일 | 데이터베이스 저장 구조와의 경계 | 넘기는 곳 |
|---|---|---|---|
| 데이터베이스 저장 구조 | 페이지 배치 · 버퍼 · 색인 자료 구조 | — | 접근 경로 선택 → 질의 처리 |
| 관계 모델 | 릴레이션 · 키의 논리 정의 | 저장 구조는 같은 키를 B-Tree 든 LSM 이든 물리로만 바꿔 담는다 | 키 · 제약 정의 → 관계 모델 |
| 데이터베이스 질의 처리 | 문장 해석 · 계획 · 실행 | 저장 구조는 SARG 를 받아 행을 돌려줄 뿐 어떤 색인을 쓸지 고르지 않는다(Hellerstein 2007 4.5절) | 계획 · 비용 추정 → 질의 처리 |
| 트랜잭션 · 회복 | 격리 · 커밋 · 장애 뒤 재실행 | 저장 구조는 dirty 페이지를 언제 쓸지 정하고, 그 순서의 규칙(WAL 먼저)은 회복 쪽이 정한다(5.2절) | 로그 · 체크포인트 → 트랜잭션 · 회복 |
분석같은 질의라도 계획이 바뀌어 느려졌으면 질의 처리, 디스크 읽기 · 쓰기 양 자체가 늘었으면 저장 구조, 커밋 응답만 늦으면 트랜잭션 · 회복부터 본다. 근거는 커밋이 WAL flush 만 기다리고 데이터 페이지 쓰기는 기다리지 않는다는 설계다(PostgreSQL 28.3).
7실무 진단 — 저장 쪽에서 오른 비용 가르기
분석먼저 표 · 색인별 버퍼 적중으로 읽기 비용을, 체크포인트 기록으로 쓰기 비용을, 쓰이지 않는 색인으로 공간 비용을 차례로 본다. 세 지표가 PostgreSQL 통계 뷰 한 곳에 있고(27.2절), 읽기 쪽 수치는 OS 캐시 적중을 따로 세지 않으므로 OS 도구와 함께 본다(27.2.13절).
| # | 증상 | 의심 원인 | 비용 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 같은 표 조회가 디스크를 많이 읽음 | 버퍼 풀이 작음 | 읽기 | SELECT relname, heap_blks_read, heap_blks_hit FROM pg_statio_user_tables; | read 가 hit 에 비해 크면 shared_ |
| 2 | 쓰기 많은 시간대에 I/O 가 튐 | 체크포인트가 잦음 | 쓰기 | SELECT num_timed, num_requested, buffers_written FROM pg_stat_checkpointer; | num_ |
| 3 | 쓰기는 느린데 조회는 빠름 | 쓰이지 않는 색인 유지 | 쓰기 · 공간 | SELECT indexrelname, idx_scan FROM pg_stat_user_indexes; | idx_ |
| 4 | LSM 엔진 조회가 점점 느려짐 | SSTable 이 쌓임 | 읽기 | nodetool compactionstats(Cassandra) | 대기 compaction 이 늘면 읽을 SSTable 이 는다(Cassandra Compaction) |
8시험 대비
시험에서는 DBMS 저장 구조의 구성 요소를 묻는 정의 · 특징형, B-Tree 와 LSM 트리의 읽기 · 쓰기 성능을 묻는 비교형으로 나올 수 있다. 정의형이면 그림 3 계층 표로 버퍼 · 페이지 · 색인을 나누고, 비교형이면 그림 4 의 쓰기 배수와 그림 5 의 세 비용 맞바꿈으로 결론을 낸다.
- 개요 — 정의(페이지 · 버퍼 · 색인으로 행을 저장하고 찾는 구조) · 질의 처리기 아래의 위치
- 구성 — 그림 3 계층(접근 방법 · 버퍼 관리자 · 데이터 파일 · WAL)과 공간 제어 · 시간 제어
- 버퍼 관리 — 프레임 · 해시 표 · dirty bit · pin count · 교체 정책(LRU-2)
- 쓰기 경로 비교 — 그림 4 사례(제자리 갱신 약 164배 · LSM 약 30배 · 찾기 3 · 9 · 3)
- 설계 판단 — 그림 5 RUM 세 비용과 블룸 필터 · compaction 의 역할
- 결론 — 읽기 많은 업무 표 = B-Tree · 쓰기 많은 이력 · 시계열 = LSM 트리
꼭 쓸 키워드
페이지버퍼 풀dirty bitpin count힙 파일제자리 갱신memtableSSTablecompactionRUM 추측
다른 답안과 차이를 내는 한 가지는 그림 4 의 쓰기 배수 계산이다 — 같은 100바이트 행을 «물리 쓰기 ÷ 논리 쓰기»로 두 엔진에서 셈하면 쓰기 성능 차이가 숫자로 보인다.
9오해와 사실
- 오해DBMS 는 OS 파일 캐시에 맡기면 따로 버퍼를 둘 필요가 없다.사실OS 캐시는 쓰기를 미루거나 순서를 바꿔 WAL 의 «로그 먼저» 규칙을 깨뜨릴 수 있어 DBMS 는 자기 버퍼 풀로 쓰는 때를 통제한다(Hellerstein 2007 5.2절).
- 오해LSM 트리는 쓰기만 빠르고 지우기는 따로 빨리 처리된다.사실지우기도 시각이 붙은 표지(tombstone)를 쓰는 쓰기이고, 그 표지는 compaction 때에야 사라진다(Cassandra Compaction).
- 오해색인은 많을수록 좋다.사실색인은 표가 바뀔 때마다 함께 갱신돼 쓰기 비용을 더하므로, 거의 쓰이지 않는 색인은 지우라고 권한다(PostgreSQL 11.1).
10핵심 정리
| 구분 | 맡는 일 | 단위 | 쓰는 방식 | 확인 지표 | 아래 토픽 |
|---|---|---|---|---|---|
| 페이지 | 행 · 색인 항목을 담음 | 보통 8 KB | 제자리 또는 새 파일 | 머리 24바이트 · 항목 4바이트 | DBMS 구조 |
| 버퍼 풀 | 페이지를 메모리에 둠 | 프레임 = 페이지 크기 | 체크포인트 · 교체 때 씀 | heap_ | DBMS 구조 |
| WAL | 페이지보다 먼저 기록 | 로그 레코드 | 순차 덧붙임 | 체크포인트 횟수 | 트랜잭션 · 회복 |
| 인덱스 | 키 → 행 위치 | 색인 페이지 | 표와 함께 갱신 | idx_ | 인덱스 |
| B-Tree | 정렬 키 노드 | 노드 = 페이지 | 제자리 갱신 | 높이 | B-Tree |
| LSM 트리 | memtable + SSTable | 불변 파일 | 덧붙임 + 병합 | 대기 compaction | LSM 트리 |
| RUM | 세 비용 맞바꿈 | 읽기 · 쓰기 · 공간 배수 | 둘을 고르면 하나가 오름 | 쓰기 배수 | — |
11참고 문헌
- 먼저 볼 문헌
- ★ Architecture of a Database System (Foundations and Trends in Databases 1(2) pp. 141-259) — 저장 관리자가 페이지를 어디에 놓고(공간) 언제 쓰는지(시간), 버퍼 풀이 무엇을 기록하는지 볼 때
- ★ Designing Access Methods: The RUM Conjecture (Proc. EDBT 2016 pp. 461-466) — 읽기 · 쓰기 · 공간 비용 셋을 한꺼번에 낮출 수 없다는 판단 틀과 B+-Tree · LSM 의 비용 식을 볼 때
- ★ PostgreSQL 18 Documentation 66.6 Database Page Layout — 실제 DBMS 한 곳의 페이지 크기 · 머리 · 항목 배치를 볼 때
- ★ Apache Cassandra 5.0 Documentation Storage Engine — LSM 방식 엔진의 commit log · memtable · SSTable · compaction 흐름을 볼 때
- ★ PostgreSQL 18 Documentation 28.3 Write-Ahead Logging (WAL) — 데이터 페이지를 커밋마다 쓰지 않아도 되는 까닭을 볼 때
- 본문 근거
- PostgreSQL 18 Documentation 19.4.1 Memory (shared_buffers) — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/runtime-config-resource.html· 확인 2026-11-14 - PostgreSQL 18 Documentation 27.2 The Cumulative Statistics System — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/monitoring-stats.html· 확인 2026-11-14 - PostgreSQL 18 Documentation 11.1 Introduction (Indexes) — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/indexes-intro.html· 확인 2026-11-14 - Apache Cassandra 5.0 Documentation Compaction Overview — Apache Software Foundation · 2026-11 ·
cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/overview.html· 확인 2026-11-14 - Organization and Maintenance of Large Ordered Indices (Proc. 1970 ACM SIGFIDET Workshop pp. 107-141) — R. Bayer · E. McCreight · 1970-07 ·
doi.org/10.1145/1734663.1734671· 확인 2026-11-14 - The Log-Structured Merge-Tree (LSM-Tree) (Acta Informatica 33(4) pp. 351-385) — Patrick O'Neil · Edward Cheng · Dieter Gawlick · Elizabeth O'Neil · 1996-06 ·
doi.org/10.1007/s002360050048· 확인 2026-11-14