IT › 데이터 › 데이터베이스

데이터베이스 저장 구조Database Storage Structure

DBMS 가 표와 색인을 디스크 페이지에 놓고, 버퍼 풀로 읽고 쓰며, 색인 자료 구조로 원하는 행을 찾게 하는 저장 엔진의 구조다. 제자리에 고쳐 쓰는 B-Tree 와 모아서 덧붙여 쓰는 LSM 트리가 읽기 · 쓰기 비용을 어떻게 나눠 갖는지도 함께 다룬다.

1요약

  1. 데이터베이스 저장 구조는 DBMS 맨 아래 저장 관리자가 표 · 색인을 고정 크기 페이지로 디스크에 놓고 버퍼 풀로 오가게 하는 구조다(Hellerstein 2007 5장). 그 위에서 접근 방법(힙 · B+-Tree 색인)과 질의 실행기가 돈다(4.5절).
  2. 디스크의 순차 전송은 무작위 접근보다 10 ~ 100배 빠르다(5.1절) — 그래서 같은 행 하나를 써도 페이지를 제자리에 고쳐 쓰는 엔진과 모았다가 순차로 덧붙이는 엔진의 비용이 크게 갈린다.
  3. 「저장 쪽이 느리다」는 읽기 · 쓰기 · 공간 중 어느 비용이 올랐는가로 가른다 — 세 비용 가운데 둘을 낮추면 나머지 하나가 오른다(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쉽게 이해하기 — 책 상자를 다루는 도서관 서고

사서 한 사람이 큰 도서관 서고를 맡는다. 책은 같은 크기 상자에 담겨 서고에 있고, 사서는 색인 카드함으로 어느 상자에 있는지 찾은 뒤 상자를 앞 선반으로 가져와 연다. 새 책이 오면 대출 장부에 먼저 적고, 바로 상자를 열어 꽂거나 반납 수레에 모았다가 한꺼번에 새 상자로 묶어 서고에 넣는다.

사서가 책 상자를 다루는 길 사서 응용 · 질의 책을 찾고 새 책을 넣는다 카드함 인덱스 책 이름 → 상자 번호 앞 선반 버퍼 풀 자주 여는 상자를 꺼내 둔다 서고 디스크 페이지 같은 크기 상자 = 8 KB 페이지 1 2 3 대출 장부 WAL 먼저 적는다 반납 수레 memtable 새 책을 모은다 묶어 넣기 compaction 새 상자로 합친다 4 5 6 배지 = 실제 기술 이름 · 위 줄 = 찾고 바로 꽂는 길(B-Tree) · 아래 줄 = 모아서 묶어 넣는 길(LSM 트리)

그림 1 · 사서는 카드함으로 상자를 찾아 앞 선반에서 열고, 새 책은 장부에 먼저 적은 뒤 바로 꽂거나 수레에 모아 묶어 넣는다.

찾기카드함으로 상자 번호
꺼내기앞 선반에 상자
적기장부에 먼저
바로 꽂기상자를 열어 넣음
모으기수레에 쌓음
묶어 넣기새 상자로 합침
바로 꽂기 B-Tree 상자 12 다시 정리 상자 47 다시 정리 상자 90 다시 정리 넣기 = 상자 3개를 제자리에서 고침 찾기 = 카드함 따라 상자 1곳 모아 꽂기 LSM 트리 수레 새 상자 1개 옛 상자들 넣기 = 새 상자 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)
묶어 넣기compactionSSTable 여럿을 하나로 합친다(Cassandra)

⚠ 비유가 맞지 않는 곳: 도서관의 앞 선반은 사서 한 사람이 쓰지만 버퍼 풀은 여러 작업 스레드가 함께 쓰고, 쓰는 동안 pin count 로 상자를 묶어 둔다(Hellerstein 2007 5.3절). 또 수레에서 내린 SSTable 은 다시 고치지 않고, 바꾼 내용은 새 파일로만 쓴다(Cassandra).

4구조 — 저장 관리자와 아래 토픽

저장 구조는 위에서부터 접근 방법 · 버퍼 관리자 · 디스크 파일 세 계층으로 나뉜다. 아래 토픽 가운데 DBMS 구조는 버퍼와 페이지를, 인덱스는 접근 경로를, B-Tree 와 LSM 트리는 색인을 담는 두 방식을 맡는다.

질의 처리기 — init() · get_next() 로 접근 방법을 부른다 힙 파일 순서 없는 행 B-Tree 제자리 갱신 LSM 트리 덧붙여 쓰기 + 병합 버퍼 관리자 프레임 배열 · 해시 표(페이지 → 프레임) · dirty bit · pin count 데이터 파일 8 KB 페이지 배열 WAL 페이지보다 먼저 · 순차 인덱스 B-Tree · LSM 트리 DBMS 구조 버퍼 · 페이지 시간 제어 언제 쓰나 공간 제어 어디에 놓나 데이터 색인 키 버퍼 제어 로그 · 회복(트랜잭션 · 회복)

그림 3 · 접근 방법이 버퍼 관리자에게 페이지를 달라고 하고, 버퍼 관리자는 언제 디스크에 쓸지를, 파일 배치는 어디에 놓을지를 정한다.

계층맡는 일대표 값아래 토픽근거
힙 파일행을 순서 없이 담는다색인 없으면 찾기 = 전체 스캔DBMS 구조Hellerstein 2007 4.5절
인덱스키 → 행 위치표가 바뀔 때마다 함께 갱신인덱스PostgreSQL 11.1
B-Tree정렬 키를 페이지 노드에 제자리로찾기 = 높이만큼 페이지B-TreeBayer · McCreight 1970
LSM 트리memtable → 불변 SSTable → compaction디스크 쓰기 = 순차만LSM 트리Cassandra Storage Engine
버퍼 관리자페이지 크기 프레임 배열 · 교체shared_buffers 기본 128 MBDBMS 구조5.3절 · PostgreSQL 19.4.1
페이지머리 24바이트 + 항목 포인터 4바이트씩보통 8 KBDBMS 구조PostgreSQL 66.6

🔑 버퍼 관리자는 «언제» 쓸지를, 색인 방식은 «어떤 모양으로» 쓸지를 정한다 — B-Tree 는 페이지를 제자리에서 고치고, LSM 트리는 고치지 않고 새로 덧붙인다.

5동작 — 행 하나를 두 엔진에 쓰고 다시 찾기

설명용 가정 값 — 측정값 표에 100바이트 행 하나를 넣고 키로 다시 찾는다. 페이지 8,192바이트, B-Tree 색인 높이 3, LSM 은 크기 비율 T = 10 · 디스크 3수준이다.

  1. B-Tree 엔진이 색인 루트 → 내부 → 잎 3페이지를 찾는다 — 버퍼 풀 해시 표에서 루트 · 내부는 적중하고 잎만 디스크에서 8 KB 를 읽어 프레임에 놓는다(Hellerstein 2007 5.3절).
  2. 잎 페이지와 힙 페이지를 pin 하고 행 · 색인 항목을 넣은 뒤 두 페이지에 dirty bit 를 켠다(5.3절).
  3. WAL 레코드를 순차로 먼저 쓰고, 커밋은 WAL 만 flush 하고 돌아온다 — 데이터 페이지는 이때 쓰지 않는다(PostgreSQL 28.3).
  4. 체크포인트가 dirty 페이지 2장을 제자리에 덮어쓴다 — 두 페이지에 이 행만 바뀌었다면 물리 쓰기 16,384바이트 ÷ 논리 쓰기 100바이트 = 약 164배다(Athanassoulis 2016 2절 UO 정의 · 직접 계산).
  5. 같은 행을 LSM 엔진에 쓰면 commit log 에 덧붙이고 memtable 에 정렬해 넣고 끝난다 — 디스크 무작위 쓰기 0(Cassandra).
  6. memtable 이 한도에 차면 SSTable 하나로 순차 flush 되고, compaction 이 수준마다 이 행을 최대 T 번 다시 써 약 10 × 3 = 30배가 된다(Athanassoulis 2016 표 1 · T/B · log_T(N/B) 식 직접 계산).
  7. 키로 다시 찾으면 B-Tree 는 3페이지, LSM 은 수준마다 높이 3을 타 최악 9페이지 — 블룸 필터가 키 없는 수준을 메모리에서 거르면 3페이지로 준다(표 1 · Cassandra).
1 B-Tree 탐색 루트 · 내부 = 버퍼 적중 · 잎 = 디스크 8 KB 페이지 3 (디스크 1) 2 pin · dirty 잎 · 힙 페이지에 행 100바이트 바뀐 페이지 2 3 WAL 기록 순차로 먼저 · 커밋 = WAL 만 flush 데이터 페이지 쓰기 0 4 체크포인트 dirty 페이지 2장을 제자리에 덮어씀 16,384 ÷ 100 ≈ 164배 5 LSM 쓰기 commit log 덧붙임 + memtable 정렬 무작위 쓰기 0 6 flush · 병합 SSTable 로 순차 · 수준마다 최대 T 번 10 × 3 = 30배 7 다시 찾기 B-Tree 높이 3 · LSM 3수준 × 높이 3 3 · 9 → 필터 뒤 3 굵은 테두리 = 쓰기 배수(물리 쓰기 ÷ 논리 쓰기) · 1 ~ 4 = B-Tree 엔진 · 5 ~ 6 = LSM 엔진 · 값은 모두 설명용 가정 값 색인 버퍼 제어 로그 데이터 페이지 응용의 조회

그림 4 · 같은 행 하나가 B-Tree 엔진은 체크포인트에서 페이지 2장을 덮어써 쓰기가 크고, LSM 엔진은 순차로 덧붙인 뒤 병합에서 다시 써 찾기가 늘어난다.

읽기 비용 최소 쓰기 비용 최소 공간 비용 최소 B-Tree 찾기 3 · 쓰기 ≤ 164배 해시 색인 LSM 트리 쓰기 30배 · 찾기 3 ~ 9 색인 없는 힙 공간 1.0 · 찾기 = 전체 스캔 블룸 필터 · 존 맵 꼭짓점에 가까울수록 그 비용이 낮다 · 동그라미 = 저장 구조 방식 · 네모 = 비교용 다른 방식 · 수치 = 그림 4 가정 값

그림 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_buffers 검토 — 전용 서버는 메모리 25% 에서 시작(19.4.1절)
2쓰기 많은 시간대에 I/O 가 튐체크포인트가 잦음쓰기SELECT num_timed, num_requested, buffers_written FROM pg_stat_checkpointer;num_requested 가 num_timed 보다 크면 시간 주기가 아닌 요청으로 체크포인트가 도는 것(27.2.15절)
3쓰기는 느린데 조회는 빠름쓰이지 않는 색인 유지쓰기 · 공간SELECT indexrelname, idx_scan FROM pg_stat_user_indexes;idx_scan 0 인 색인은 삭제 후보(PostgreSQL 11.1 · 27.2.20절)
4LSM 엔진 조회가 점점 느려짐SSTable 이 쌓임읽기nodetool compactionstats(Cassandra)대기 compaction 이 늘면 읽을 SSTable 이 는다(Cassandra Compaction)

8시험 대비

시험에서는 DBMS 저장 구조의 구성 요소를 묻는 정의 · 특징형, B-Tree 와 LSM 트리의 읽기 · 쓰기 성능을 묻는 비교형으로 나올 수 있다. 정의형이면 그림 3 계층 표로 버퍼 · 페이지 · 색인을 나누고, 비교형이면 그림 4 의 쓰기 배수와 그림 5 의 세 비용 맞바꿈으로 결론을 낸다.

답안 목차
  1. 개요 — 정의(페이지 · 버퍼 · 색인으로 행을 저장하고 찾는 구조) · 질의 처리기 아래의 위치
  2. 구성 — 그림 3 계층(접근 방법 · 버퍼 관리자 · 데이터 파일 · WAL)과 공간 제어 · 시간 제어
  3. 버퍼 관리 — 프레임 · 해시 표 · dirty bit · pin count · 교체 정책(LRU-2)
  4. 쓰기 경로 비교 — 그림 4 사례(제자리 갱신 약 164배 · LSM 약 30배 · 찾기 3 · 9 · 3)
  5. 설계 판단 — 그림 5 RUM 세 비용과 블룸 필터 · compaction 의 역할
  6. 결론 — 읽기 많은 업무 표 = 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_blks_read · hitDBMS 구조
WAL페이지보다 먼저 기록로그 레코드순차 덧붙임체크포인트 횟수트랜잭션 · 회복
인덱스키 → 행 위치색인 페이지표와 함께 갱신idx_scan인덱스
B-Tree정렬 키 노드노드 = 페이지제자리 갱신높이B-Tree
LSM 트리memtable + SSTable불변 파일덧붙임 + 병합대기 compactionLSM 트리
RUM세 비용 맞바꿈읽기 · 쓰기 · 공간 배수둘을 고르면 하나가 오름쓰기 배수—

11참고 문헌

  1. 먼저 볼 문헌
  2. ★ Architecture of a Database System (Foundations and Trends in Databases 1(2) pp. 141-259) — 저장 관리자가 페이지를 어디에 놓고(공간) 언제 쓰는지(시간), 버퍼 풀이 무엇을 기록하는지 볼 때
    J. M. Hellerstein · M. Stonebraker · J. Hamilton (UC Berkeley 공개판) · 2007-11 · dsf.berkeley.edu/papers/fntdb07-architecture.pdf · 확인 2026-11-14
  3. ★ Designing Access Methods: The RUM Conjecture (Proc. EDBT 2016 pp. 461-466) — 읽기 · 쓰기 · 공간 비용 셋을 한꺼번에 낮출 수 없다는 판단 틀과 B+-Tree · LSM 의 비용 식을 볼 때
    M. Athanassoulis 외 6인 (OpenProceedings · CC BY-NC-ND 4.0) · 2016-03 · openproceedings.org/2016/conf/edbt/paper-12.pdf · 확인 2026-11-14
  4. ★ PostgreSQL 18 Documentation 66.6 Database Page Layout — 실제 DBMS 한 곳의 페이지 크기 · 머리 · 항목 배치를 볼 때
    PostgreSQL Global Development Group · 2026-11 · www.postgresql.org/docs/current/storage-page-layout.html · 확인 2026-11-14
  5. ★ Apache Cassandra 5.0 Documentation Storage Engine — LSM 방식 엔진의 commit log · memtable · SSTable · compaction 흐름을 볼 때
    Apache Software Foundation · 2026-11 · cassandra.apache.org/doc/latest/cassandra/architecture/storage-engine.html · 확인 2026-11-14
  6. ★ PostgreSQL 18 Documentation 28.3 Write-Ahead Logging (WAL) — 데이터 페이지를 커밋마다 쓰지 않아도 되는 까닭을 볼 때
    PostgreSQL Global Development Group · 2026-11 · www.postgresql.org/docs/current/wal-intro.html · 확인 2026-11-14
  7. 본문 근거
  8. 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
  9. 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
  10. PostgreSQL 18 Documentation 11.1 Introduction (Indexes) — PostgreSQL Global Development Group · 2026-11 · www.postgresql.org/docs/current/indexes-intro.html · 확인 2026-11-14
  11. 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
  12. 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
  13. 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