Chapter 13. Data Storage Structures

한 줄 핵심: 데이터베이스는 디스크 위의 파일(=레코드의 나열) 묶음이고, 모든 설계의 목표는 단 하나 — 디스크 블록 전송 횟수를 최소화하는 것이다. 레코드를 바이트로 표현하고, 파일 안에 배치하고, 메타데이터를 보관하고, 버퍼로 메모리를 관리하는 모든 기법이 이 목표를 향한다.

이 챕터가 답하는 핵심 질문

Q1. 데이터베이스는 디스크 위에서 어떻게 구성되는가? (file–record–block)

Q2. 고정 길이 레코드(fixed-length)는 어떻게 저장·삭제·삽입하는가?

Q3. 가변 길이 레코드(variable-length)와 slotted page는 어떻게 동작하는가?

Q4. 레코드들을 파일 안에 어떻게 배치하는가? (heap/sequential/clustering/B⁺-tree/hashing)

Q5. 메타데이터(data dictionary)는 어디에 어떻게 두는가?

Q6. 디스크 I/O를 줄이려면 메모리를 어떻게 쓰는가? (buffer manager)

Q7. 버퍼가 꽉 차면 누구를 쫓아내는가? (교체 정책)

Q1. 데이터베이스는 디스크 위에서 어떻게 구성되는가? ✅

A. DB는 파일들의 모음이며, 파일 = 레코드의 시퀀스, 레코드 = 필드의 시퀀스이고, 레코드는 블록(block) 단위로 디스크에 매핑된다.

파일(file) = 레코드(record)들의 시퀀스
레코드(record) = 필드(field)들의 시퀀스 (테이블의 한 행)
레코드는 디스크 블록보다 작다고 가정한다.
블록은 저장 공간 할당과 데이터 전송의 단위 — 기본 4 또는 8 KB.
비유: 디스크는 거대한 창고, 블록은 한 번에 꺼내는 “상자”. 레코드 1개만 필요해도 상자(블록) 통째로 가져온다.

file → block → record 한눈에 (실제 수치)
한 레코드가 53 B, 한 블록이 4 KB(4096 B) 라면, 블록 하나에 $⌊ 4096/53 ⌋ = 77$ 개 레코드가 들어가고 끝에 자투리(buffer) 15 B가 남는다.
instructor 파일 = 블록들의 나열
┌─ block 0 ──────────────┐ ┌─ block 1 ──────────────┐
│ [rec0][rec1]...[rec76] █│ │ [rec77]...[rec153]    █ │ ...
└────────────────────────┘ └────────────────────────┘
  77개 레코드 + 자투리(█)

레코드 하나 = 필드들의 나열:
  [ 10101 | Srinivasan | Comp. Sci. | 65000 ]
     ID        name        dept_name   salary
rec40 하나만 필요해도 block 0 전체(4 KB)를 메모리로 읽는다. 디스크 I/O의 단위가 블록이기 때문 → “한 블록에 함께 쓸 레코드를 모아두면 I/O가 준다”는 이 챕터 전체의 목표가 여기서 나온다.

가장 단순한 접근(one approach):

레코드 크기는 고정(fixed)이라 가정
한 파일에는 한 가지 타입의 레코드만 저장
서로 다른 릴레이션은 서로 다른 파일에
→ 구현이 가장 쉬움. 가변 길이는 Q3에서.

Q2. 고정 길이 레코드(fixed-length)는 어떻게 저장·삭제·삽입하는가? ✅

A. 크기가 모두 $n$ 바이트로 같으면 **record $i$ 의 시작 = $n \times (i - 1)$ 산술 계산으로 즉시 위치가 나온다 (배열처럼).

$record i 의 시작 위치 = n \times (i - 1)$

예: instructor(ID char(5), name char(20), dept_name char(20), salary numeric(8,2)) → 레코드 크기 53바이트. record 0은 0, record 1은 53, record 2는 106번 바이트.

블록 경계 문제

53이 블록 크기(예: 4096)의 약수가 아니면 레코드가 블록 경계에 걸칠(cross blocks) 수 있다.

수정안: 레코드가 블록 경계를 넘지 못하게 한다 (블록 끝 자투리는 버림).

삭제(Deletion of record $i$ ) — 3가지 대안:

대안	방법	특징
① 전체 당기기	$i + 1, \dots, n$ 을 $i, \dots, n - 1$ 로 이동	순서 유지, 이동 비용 큼
② 마지막으로 메우기	record $n$ 을 $i$ 자리로	이동 1번, 순서 깨짐
③ free list	안 옮기고 빈 자리를 free list로 연결	이동 비용 0

Free list: 파일 header에 “첫 빈 레코드” 포인터, 각 빈 자리에는 “다음 빈 레코드” 포인터 → 빈 자리가 연결 리스트로 꿰임 (빈 사물함마다 “다음 빈 사물함 번호” 쪽지).

free list가 실제로 어떻게 꿰이나 (record 1, 4번 삭제 후)
레코드 8개짜리 파일에서 record 1과 record 4를 삭제했다고 하자. 빈 자리는 데이터 대신 “다음 빈 자리 번호” 만 들고 있다.
header ─────────────────────┐
                             ▼
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│rec 0 │ FREE │rec 2 │rec 3 │ FREE │rec 5 │rec 6 │
│ 데이터│ →4   │ 데이터│ 데이터│ →∅   │ 데이터│ 데이터│
└──────┴──┬───┴──────┴──────┴──────┴──────┴──────┘
          └──────────────────▲ (record 1이 record 4를 가리킴)

빈 자리 체인:  header → [1] → [4] → ∅ (끝)
삽입: header가 가리키는 **[1]**번 자리에 새 레코드를 쓰고, header를 [1]이 가리키던 **[4]**로 갱신. → 빈 자리를 찾으려고 파일 전체를 훑지 않아도 됨 (O(1)).

데이터가 차지하던 공간을 그대로 포인터 저장에 재활용하므로 추가 메모리 0. 빈 사물함 안쪽에 “다음 빈 사물함 번호” 쪽지를 붙여두는 것과 똑같다.

삽입(Insertion):

header가 가리키는 빈 자리를 사용.
header 포인터를 다음 빈 레코드로 갱신.
빈 공간이 없으면 파일 끝에 추가.

Q3. 가변 길이 레코드(variable-length)와 slotted page는 어떻게 동작하는가? ✅

A. 가변 길이 속성은 고정 크기 (offset, length) 쌍으로 앞에 두고 실데이터는 뒤에 저장하며, 블록 내에서는 slotted page 구조로 관리한다.

가변 길이 레코드가 생기는 경우:

한 파일에 여러 레코드 타입을 저장할 때
필드 자체가 가변일 때 — 예: varchar

레코드 내부 표현:

속성들은 순서대로 저장.
가변 길이 속성 = 고정 크기 (offset, length) 쌍으로 앞에 두고, 실데이터는 모든 고정 길이 속성 뒤에 저장.
Null 값은 null-value bitmap(속성마다 1비트, “이 칸은 빔” 표시).

예: instructor(ID varchar(5), name varchar(20), dept_name varchar(20), salary numeric(8,2)) 의 한 레코드:

바이트	0–3	4–7	8–11	12–19	20	21–25	26–35	36–44
내용	(21,5)	(26,10)	(36,10)	65000	`0000`	`10101`	`Srinivasan`	`Comp. Sci.`
의미	ID (off,len)	name (off,len)	dept (off,len)	salary 고정	null bitmap	ID 실값	name 실값	dept 실값

비유: 상자 앞면에 “A는 21에서 5만큼, B는 26에서 10만큼…” 적은 목차 스티커(고정 크기) + 실제 물건은 뒤에 차곡차곡.

아아디어 : 고정되어 있어 길이가 변하지 않는 것들을 값을 포함해서 죄다 앞으로 몰아두자.

salary가 앞에 잇는 이유.

Slotted Page Structure — 블록 안에서 가변 길이 레코드 관리:

Slotted page는 가변 길이 레코드를 블록(페이지)에 담는 표준 구조. Block header에 담기는 3가지:

레코드 엔트리 개수(# entries)
블록 내 free space 끝 위치
각 레코드의 위치(location)·크기(size)

구조: 헤더는 블록 앞에서, 레코드는 블록 뒤에서 앞으로 자라며 가운데가 free space.

slotted page 한 장 실제 모습
 블록(페이지) 4 KB
 ┌────────────────────────────────────────────────────────┐
 │ #entries=3 │ free末 │ [loc,sz][loc,sz][loc,sz] │ ····· →│←
 │   헤더 ──────────── 앞에서 뒤로 자람 ──────────→        │ │
 │                    ← free space (가운데) →             │ │
 │              ←──── 레코드는 뒤에서 앞으로 채움 ──────    │ │
 │ ·····│  Record 3  │  Record 2  │       Record 1        │←┘
 └────────────────────────────────────────────────────────┘
   slot[0]→Record1,  slot[1]→Record2,  slot[2]→Record3
헤더(slot 배열)는 왼→오, 레코드는 오→왼으로 자라 가운데에서 만난다 → 양쪽이 만나기 전까진 빈 공간을 한 덩어리로 알차게 쓴다.

Record 2를 지우면: slot[1]을 “빈 칸”으로 표시하고, 남은 레코드를 오른쪽으로 밀어 빈틈을 메운다(조각모음). 이때 slot 배열의 loc 값만 고쳐주면 외부에서 보는 주소(slot 번호)는 안 변한다.

비유: 책장 앞에 붙인 색인표(slot) 와 실제 책(record) 을 분리 — 책을 옮겨 꽂아도 색인표 위치만 같으면 “3번 책” 하면 항상 찾을 수 있다.

핵심 성질 2가지:

레코드는 페이지 안에서 자유롭게 이동(move around) 시켜 빈틈 없이 연속 유지 가능 — 단, 헤더 엔트리만 갱신 (조각모음 가능).
외부 포인터는 레코드를 직접 가리키지 말고, 헤더 엔트리(slot)를 가리켜야 한다. → 레코드가 이사 다녀도 외부 포인터가 안 깨짐 (간접 주소의 힘).

비교: Fixed vs Variable:

구분	Fixed-Length	Variable-Length
발생 원인	char 등 고정 필드만	varchar, 여러 레코드 타입
위치 계산	$n (i - 1)$ 즉시	(offset,length)·slot 경유
삭제	free list (또는 이동)	slotted page 내 압축·헤더 갱신
Null	해당 없음	null-value bitmap
난이도	가장 쉬움	헤더/간접 참조 필요

Q4. 레코드들을 파일 안에 어떻게 배치하는가? ✅

A. 5가지 파일 조직 방식이 있으며, 핵심은 함께 조회되는 레코드를 한 블록에 모아 I/O를 줄이는 것이다. (구체적으로 특정 레코드를 어디 블록에 배치할 건데? )

방식	핵심 아이디어
Heap	빈 공간이 있는 아무 곳에나 배치
Sequential	search key 값 순서대로 정렬 저장
Multitable clustering	여러 릴레이션을 같은 파일·블록에 저장 (관련 레코드 모아 I/O 최소화)
B⁺-tree	삽입/삭제에도 정렬 유지 (14장)
Hashing	search key에 hash 함수 적용 결과가 들어갈 블록 결정 (14장)

Heap File Organization

정렬·규칙 없이 빈 공간이 있는 아무 블록에나 놓고, 한 번 할당되면 보통 이동 안 함. 삽입은 쉽지만 →
관건: 빈 공간이 있는 블록을 어떻게 빨리 찾나? (파일이 블록 수천 개면 다 열어볼 수 없음) → Free-space map.

Free-space map = 빈 공간 현황 요약 목차 (블록마다 “얼마나 비었나”만 숫자로 기록 → 실제 블록을 안 열고 숫자만 보고 들어갈 곳 결정):

블록당 칸(엔트리) 1개. 칸을 3비트로 잡으면 0~7 표현, 적힌 값 ÷ 8 = 빈 비율.

블록 번호	0	1	2	3	4	5	6	7
free map 값	4	2	1	4	7	3	6	5
빈 비율	50%	25%	12%	50%	87%	37%	75%	62%

활용 예: 30%(≈3/8) 차지하는 레코드 삽입 → map에서 값 ≥ 3인 칸을 훑어 첫 후보(블록 0) 선택. 실제 블록 I/O 없이 결정.

2단계(second-level) free-space map — “목차의 목차” (1단계도 길어지면 그 위에 또 요약):

1단계 칸 4개를 한 묶음으로 묶어 그 묶음의 최댓값만 2단계에 기록.

1단계:  [4  2  1  4]   [7  3  6  5]
            ↓             ↓     (각 묶음의 최댓값)
2단계:      4             7

빈 공간 큰 블록 찾기: 짧은 2단계 먼저 보고(“두 번째 묶음이 최대 7”) → 그 묶음(블록 4~~7)만 1단계로 드릴다운. 앞 묶음(0~~3)은 통째로 스킵 → 큰 파일에서 탐색 가속.

왜 낡은(stale) 값이어도 OK?

map은 정답이 아니라 힌트다. 디스크엔 가끔만 기록해 실제와 어긋날 수 있는데, “여기 빈 것 같다” 갔다가 꽉 찼으면 다음 후보로 넘어가면 그만 → 항상 정확히 맞출 필요가 없어 갱신 비용을 아낀다.

Sequential File Organization

파일 전체를 순차 처리하는 응용에 적합.
레코드를 search-key 순으로 정렬 저장 (예: instructor를 ID 순). 빠른 탐색 위해 포인터로 체인 연결.
삭제: 포인터 체인만 조정 (물리적으로 안 당김).
삽입: 들어갈 위치를 찾고 →
1. 빈 공간 있으면 거기 삽입
2. 없으면 overflow block에 삽입
3. 어느 경우든 포인터 체인 갱신.

ID 순 정렬 파일에 ID=32222를 삽입하면 (overflow 발생)
instructor를 ID 순으로 저장했고, 10101과 33456 사이에 빈칸이 없다고 하자. 32222는 둘 사이에 와야 하는데 자리가 없으니 overflow block에 넣고, 포인터로 “논리적 순서”를 유지한다.
본체(물리적으로 연속):
  ┌─────────┐   ┌─────────┐   ┌─────────┐
  │ 10101 ●─┼──→│ 33456 ●─┼──→│ 45565 ●─┼──→ ...
  └────▲────┘   └─────────┘   └─────────┘
       │ (포인터로 '논리적 다음'을 가리킴)
       └────────────┐
  overflow block:   │
  ┌─────────┐       │
  │ 32222 ●─┼───────┘  (10101 → 32222 → 33456 순서가 포인터로 유지됨)
  └─────────┘
읽는 순서(포인터 따라감): 10101 → 32222(overflow로 점프) → 33456 → 45565 … → 정렬 순서는 맞다.

문제: 32222 하나 읽으려고 헤드가 본체↔overflow를 왔다 갔다(=seek) → 순차 읽기의 장점(seek 1번)이 깨진다.

재조직(reorganization)

overflow가 쌓이면 논리적 순서(포인터)와 물리적 순서가 어긋나 순차 읽기가 느려짐 → 때때로 파일을 재조직해 물리적 순차 순서를 복원. (위 그림에서 32222를 본체의 제자리로 끼워 넣고 전체를 다시 줄세우는 작업. 비용이 크므로 자주 하진 않음.)

Multitable Clustering File Organization

여러 릴레이션을 하나의 파일에 섞어 저장.

동기: 함께 조회되는 관련 레코드를 같은 블록에 두어 I/O 최소화.
예: department 레코드 뒤에 그 학과 소속 instructor들을 붙여 저장 (학과 서랍 한 칸에 학과+교수 서류).

한 블록 안이 실제로 어떻게 생겼나
보통 방식은 두 테이블이 다른 파일에 따로 있어, 조인하려면 양쪽 블록을 각각 읽어야 한다. clustering은 한 블록에 섞어 둔다.
[일반 방식]  department 파일 ─ 블록 A
             instructor 파일 ─ 블록 B   → 조인 시 A, B 둘 다 읽음 (I/O 2번)

[multitable clustering]  하나의 블록:
  ┌────────────────────────────────────────┐
  │ Comp. Sci. | Taylor | 100000   ← dept   │
  │   45565 | Katz       | 75000   ← instr  │
  │   10101 | Srinivasan | 65000   ← instr  │  같은 학과끼리
  │   83821 | Brandt     | 92000   ← instr  │  한 곳에 묶임
  │ Physics    | Watson | 70000    ← dept   │
  │   33456 | Gold       | 87000   ← instr  │
  └────────────────────────────────────────┘
“Comp. Sci. 학과와 소속 교수 전체”를 보려면 → 블록 1개만 읽으면 끝 (I/O 1번). 조인이 공짜에 가까워진다.

반대로 “모든 학과 이름만” 보려면 → 사이사이 끼인 instructor 행을 다 건너뛰며 읽어야 해서 손해. → 무엇을 자주 조회하느냐에 따라 이득/손해가 갈린다.

쿼리 유형	유불리
$d e p a r t m e n t ⋈ in s t r u c t or$ , 특정 학과+교수 조회	좋음 (한 블록 읽기)
`department`만 조회	나쁨 (사이의 instructor까지 읽어야)

결과적으로 가변 크기 레코드가 됨.
특정 릴레이션 레코드만 따라가도록 포인터 체인 추가 가능.

Q5. 메타데이터(data dictionary)는 어디에 어떻게 두는가? ✅

A. Data dictionary(=system catalog)는 metadata, 즉 “데이터에 대한 데이터”를 저장하는 DBMS의 자기 장부다. 디스크엔 릴레이션 형태로, 메모리엔 전용 자료구조로 둔다.

저장 내용:

릴레이션 정보: 릴레이션 이름 / 속성의 이름·타입·길이 / 뷰(view) 이름·정의 / 무결성 제약
사용자·계정 정보 (비밀번호 포함)
통계·기술 데이터: 각 릴레이션의 튜플 수 등
물리적 파일 구성: 어떻게 저장되는지(sequential/hash/…), 물리적 위치
인덱스 정보 (14장)

메타데이터의 표현 방식:

디스크 위에서는 릴레이션(테이블) 형태. 예:
- Relation_metadata(relation_name, number_of_attributes, storage_organization, location)
- Attribute_metadata(relation_name, attribute_name, domain_type, position, length)
- Index_metadata(...), View_metadata(...), User_metadata(user_name, encrypted_password, group)
메모리 안에서는 빠른 접근 위해 특수 설계된 자료구조 사용.

"메타데이터도 그냥 테이블이다" — 실제 catalog 모습

instructor(ID, name, dept_name, salary) 테이블을 만들면, DBMS는 그 설계 정보 자체를 아래처럼 catalog 테이블의 행(row)으로 저장한다.

Attribute_metadata (속성 목록을 담는 카탈로그):

relation_name attribute_name domain_type position length
instructor ID varchar 1 5
instructor name varchar 2 20
instructor dept_name varchar 3 20
instructor salary numeric 4 8

신기한 점: DBMS는 “테이블을 다루는 법”을 이미 알고 있으므로, 자기 자신의 메타데이터도 똑같은 테이블로 저장하면 새 코드가 거의 필요 없다. (장부를 적는 도구로 그 장부의 목차까지 적는 셈.)

SELECT * FROM instructor를 실행하면 DBMS는 먼저 이 catalog를 읽어 “instructor는 컬럼 4개, 각각 무슨 타입/길이”인지 파악한 뒤에야 실제 데이터 블록을 해석한다.

그런데 catalog는 거의 모든 쿼리마다 읽히므로(매번 디스크에서 꺼내면 너무 느림), 메모리에 상주시키고 빠른 자료구조로 둔다 → Q7의 “data dictionary 블록은 메모리에 상주” 휴리스틱과 연결.

relation_name	attribute_name	domain_type	position	length
instructor	ID	varchar	1	5
instructor	name	varchar	2	20
instructor	dept_name	varchar	3	20
instructor	salary	numeric	4	8

Q6. 디스크 I/O를 줄이려면 메모리를 어떻게 쓰는가? ✅

A. Buffer(디스크 블록 복사본을 담는 메인 메모리)와 Buffer manager(버퍼 공간 할당 담당)로, 디스크↔메모리 블록 전송 횟수를 최소화한다.

비유: 디스크=지하 서고, 버퍼=책상 위. 서고 왕복(느림)을 줄이려 자주 보는 책을 책상(빠름)에 올린다. 사서(buffer manager)가 무엇을 올리고 내릴지 결정.

데이터 접근의 두 층위:

디스크 ↔ 버퍼: input(A) = 블록 A를 버퍼로 읽음 / output(B) = 버퍼 블록 B를 디스크에 씀.
버퍼 ↔ 트랜잭션 작업 영역: read(X) = 버퍼의 X를 지역 변수 $x_{1}$ 로 / write(Y) = 지역 변수를 버퍼의 Y로.
트랜잭션 $T_{1}, T_{2}$ 는 디스크를 직접 안 만지고 항상 버퍼를 거친다.

Buffer Manager 동작 (블록 요청 시):

버퍼에 이미 있으면 → 메인 메모리 주소 즉시 반환 (디스크 접근 0회).
버퍼에 없으면:
1. 공간 할당 — 모자라면 다른 블록을 쫓아냄(replace). 쫓겨나는 블록은 마지막 write/fetch 이후 수정(modified)된 경우에만 디스크에 다시 기록 (안 바뀌었으면 사본과 같으니 그냥 버림).
2. 디스크에서 블록을 읽어온 뒤 주소를 요청자에게 반환.

Pinned block과 버퍼 락:

Pinned block: 디스크로 쫓겨나는 것이 허용되지 않는 메모리 블록.
- Pin: 읽기/쓰기 전, Unpin: 끝난 후.
- 여러 프로세스가 동시 pin/unpin 가능 → pin count 유지, pin count = 0일 때만 evict 가능 (책에 “사용 중” 포스트잇).
Shared / Exclusive lock — 한 페이지를 여럿이 동시에 만질 때 충돌 방지:
- 필요 이유: slotted page는 레코드를 페이지 안에서 **이동(재조직)**시킨다(Q3). A가 옮기는 도중 B가 읽으면 반쯤 옮겨진 깨진 데이터를 본다 → 이를 막는 표시가 buffer lock.
- Shared lock (S) = 읽기용: 읽기는 데이터를 안 바꿔 서로 방해 없음 → 여러 reader 동시 보유 가능.
- Exclusive lock (X) = 쓰기·갱신·재조직용: 쓰는 동안 누구도(읽는 이조차) 끼면 안 됨 → 한 번에 한 프로세스만, X 보유 중엔 S도 불가.

상황	가능?
S + S (읽기+읽기)	✅ 여럿 동시
S + X (읽기+쓰기)	❌ 공존 불가
X + X (쓰기+쓰기)	❌ 하나만

비유: 공용 화이트보드 — 같이 보기는 OK, 누가 지우고 다시 배치하려면 끝날 때까지 모두 비켜야.
구분(중요): 이건 페이지의 물리적 구조를 잠깐 지키는 가벼운 잠금(=latch). Ch18의 트랜잭션 단위 lock(직렬성 보장, 트랜잭션 끝까지 유지)과는 목적·수명이 다르다.

Q7. 버퍼가 꽉 차면 누구를 쫓아내는가? ✅

A. OS는 보통 LRU를 쓰지만, DB는 쿼리로 미래 접근 패턴을 알 수 있어 옵티마이저 힌트 기반의 MRU·toss-immediate 같은 mixed strategy가 더 낫다.

LRU (Least Recently Used):

대부분 OS가 쓰는 정책: 가장 오래 전 사용된 블록 교체.
아이디어: 과거 참조 패턴 = 미래 예측 (“최근 안 쓴 건 앞으로도 안 쓸 것”).
그러나 일부 쿼리에서 오히려 나쁠 수 있다.

왜 DB는 OS와 다른가:

쿼리는 잘 정의된 접근 패턴(예: sequential scan)을 가져, DB는 쿼리로 미래 참조를 예측 가능 — 과거만 보는 LRU보다 유리.
통계 정보도 활용: 예) data dictionary는 매우 자주 접근 → 휴리스틱: data-dictionary 블록은 메모리에 상주시켜라.

LRU가 망하는 예 — Nested-Loop Join:

for each tuple i of instructor do
    for each tuple d of department do
        if i[dept_name] = d[dept_name] then
            include x in result of instructor ⋈ department

구조: 바깥 루프(instructor)는 한 블록을 잡아두고, 안쪽 루프(department)를 처음부터 끝까지 전체 훑기를 반복 → department는 dept1 → dept2 → dept3 → (다시) dept1 → … 순환(cyclic) 참조.
메모리 3칸, 디스크에 inst1~3, dept1~3.

접근 순서 추적 (왜 dept1이 빠지나):

1) inst1 적재   →  [inst1]
2) dept1 적재   →  [inst1, dept1]          (inst1·dept1 사용)
3) dept2 적재   →  [inst1, dept1, dept2]   꽉 참! (inst1·dept2 사용)
4) dept3 필요 → 자리 없음 → LRU 퇴출 판단

4단계 시점, 메모리 블록	마지막 사용 시각
dept1	2단계 (가장 옛날) ← 퇴출
dept2	3단계
inst1	3단계 (계속 쓰임)

dept1이 빠지는 이유: 4단계에서 메모리 안 블록 중 dept1이 가장 오래 전(2단계)에 쓰여 LRU 대상. 비극은 순환이라 dept3 다음 곧바로 dept1이 다시 필요하다는 것 → 매번 “바로 다음 쓸 블록”을 골라 버리는 최악 반복.
inst1이 안 빠지는 이유: 안쪽 비교 i[dept_name]=d[dept_name]마다 inst1을 매번 함께 읽음 → 항상 “방금 쓴 블록”이라 결코 가장 오래된 게 안 됨. (우리도 inst1은 계속 필요하니 다행.)
순환 패턴에서 LRU는 항상 곧 쓸 블록을 쫓아내는 최악의 선택을 반복.

대안 전략:

전략	동작	언제 좋은가
Toss-immediate	블록의 마지막 튜플 처리 직후 즉시 공간 해제	바깥 릴레이션(instructor) — 한 번 훑으면 끝
MRU	처리 중 블록은 pin; 마지막 튜플 후 unpin하면 most recently used가 되어 가장 먼저 교체 대상	안쪽 릴레이션(department) — 순환 참조엔 “방금 다 쓴 것”을 버림

같은 4단계(dept3 적재)에서 정책별로 어떻게 달라지나:

정책	dept3 적재 시 퇴출 대상	직후 결과
LRU	dept1 (가장 오래됨)	순환 재시작 시 dept1이 바로 필요 → miss (최악)
MRU	dept2 (방금 다 씀)	dept1이 메모리에 남음 → 순환 재시작 시 dept1 = HIT

MRU가 통하는 원리: 순환 스캔에선 방금 다 쓴 블록(dept2)이 한 바퀴 돌아야 다시 필요 = 가장 나중에 필요하다. 그러니 그걸 버리고, 먼저 다시 필요할 오래된 블록(dept1)은 유지 → LRU가 miss 내던 자리에서 hit이 난다. (처리 중 블록은 pin 해두고, 다 쓰면 unpin해 가장 먼저 교체 대상으로.)
Toss-immediate가 통하는 원리 (바깥 instructor): 바깥 릴레이션의 각 블록(inst1 등)은 조인 내내 딱 한 번만 훑고 끝이다. 마지막 튜플을 처리한 직후 곧바로 버려도 다시 볼 일이 없으니, 그 자리를 순환하는 department 블록에 양보 → 안쪽 캐시 효율 ↑.
요약: 안쪽(순환)=MRU, 바깥(1회 스캔)=toss-immediate. 둘 다 “이 블록을 또 볼지”를 쿼리 계획으로 미리 알기에 가능.
Query optimizer가 힌트를 주는 mixed strategy가 바람직 (쿼리 계획을 아는 쪽이 미래를 앎).

LRU vs MRU 직관 + 시험 포인트

LRU: “오래 안 쓴 것 버리기” — 지역성 있는 접근에 적합.

MRU: “방금 다 쓴 것 버리기” — 순환 스캔에선 방금 끝낸 블록이 가장 늦게 다시 필요하므로 최적. nested-loop 안쪽 루프가 대표.

시험: “to access dept3, LRU는 어느 블록을 쫓아내는가?” → dept1 (그게 바로 다음 필요해서 비효율).

정책	쫓아내는 대상	근거	비고
LRU	가장 오래된 블록	과거=미래 예측	nested-loop join에서 최악
MRU	가장 최근에 다 쓴 블록	순환 패턴	처리 중 블록은 pin 필요
Toss-immediate	마지막 튜플 직후 그 블록	다시 안 봄을 앎	옵티마이저 힌트
통계 휴리스틱	—	자주 쓰는 건 상주	data dictionary 메모리 유지

Juhyeon's Blog

탐색기

Ch13_Data_Storage_Structures

Chapter 13. Data Storage Structures

Q1. 데이터베이스는 디스크 위에서 어떻게 구성되는가? ✅

Q2. 고정 길이 레코드(fixed-length)는 어떻게 저장·삭제·삽입하는가? ✅

Q3. 가변 길이 레코드(variable-length)와 slotted page는 어떻게 동작하는가? ✅

Q4. 레코드들을 파일 안에 어떻게 배치하는가? ✅

Heap File Organization

Sequential File Organization

Multitable Clustering File Organization

Q5. 메타데이터(data dictionary)는 어디에 어떻게 두는가? ✅

Q6. 디스크 I/O를 줄이려면 메모리를 어떻게 쓰는가? ✅

Q7. 버퍼가 꽉 차면 누구를 쫓아내는가? ✅

그래프 뷰

목차

Properties