CHAPTER 14 인덱싱

1. 기본 개념 (Basic Concepts)

• 인덱스(Index) 역할

  • 책의 색인과 유사: 원하는 정보를 빠르게 찾기 위한 “검색 가속” 구조
  • 테이블 전체를 모두 읽지 않고도 필요한 레코드를 찾아갈 수 있음

• 인덱스 필요성

  • 대규모 데이터를 전부 탐색(Full Scan)하지 않고 원하는 정보만 효율적으로 조회
  • 예) 특정 학생의 레코드만 조회할 때, 인덱스를 통해 빠른 접근 가능

• 단순 정렬 리스트의 한계

  • 인덱스 자체가 커질 수 있고, 검색 시간도 여전히 오래 걸릴 수 있음
  • 삽입·삭제 시 재정렬 등의 유지 비용이 매우 큼

• 인덱스의 기본 형태

  • 순서 인덱스(Ordered Indices)
    • 데이터 값을 정렬된 순서로 유지
    • 범위 검색(Range Query)에 유리
  • 해시 인덱스(Hash Indices)
    • 해시 함수를 통해 데이터를 균등하게 분산
    • 완전 일치 검색(Exact Match) 쿼리에 특히 효율적

• 인덱스 선택 시 고려사항

  • 검색(Access) 유형: 정확히 일치하는 값 검색인지, 범위 검색인지
  • 검색 시간(Access Time): 원하는 레코드에 도달하는 데 걸리는 시간
  • 삽입 시간(Insertion Time): 새로운 레코드를 인덱스에 반영하는 데 드는 시간
  • 삭제 시간(Deletion Time): 기존 레코드를 삭제하는 데 드는 시간
  • 추가 공간(Space Overhead): 인덱스 유지를 위해 필요한 추가 저장소

• 다중 인덱스(Multiple Indices)

  • 하나의 테이블에 여러 개의 인덱스를 둘 수 있음
  • 예) 도서 테이블에서 저자, 제목, 주제 각각에 대해 인덱스 생성

• 검색 키(Search Key)

  • 인덱스를 통해 레코드를 찾을 때 사용하는 속성(또는 속성들의 집합)
  • 기본 키나 후보 키가 아니라도, 검색을 위해 사용되는 속성이면 모두 검색 키가 될 수 있음

2. 순서 인덱스 (Ordered Indices)

1. 밀집 인덱스(Dense Index)와 희소 인덱스(Sparse Index)

1.1 밀집 인덱스 (Dense Index)

• 모든 검색 키에 대해 인덱스 엔트리가 존재
• 인덱스 엔트리는 (검색 키 값, 레코드(들)에 대한 포인터)로 구성
• 클러스터링/논클러스터링 여부와 상관없이 각 값에 대한 포인터 목록 관리 가능

장단점

• 장점: 원하는 레코드를 직접 찾아가기 쉬워 검색 속도 빠름
• 단점: 인덱스 크기가 커지고, 삽입/삭제 시 유지 비용이 큼

1.2 희소 인덱스 (Sparse Index)

• 일부 검색 키에 대해서만 인덱스 엔트리를 생성
• 테이블(파일)이 검색 키 순으로 물리적으로 정렬(클러스터링)되어 있어야 사용 가능
• 인덱스 엔트리는 (검색 키 값, 해당 레코드가 존재하는 최초 블록 포인터) 형태
• 원하는 검색 키가 인덱스에 없을 경우, 직전에 해당하는 검색 키 엔트리부터 순차적으로 스캔하여 레코드 탐색

장단점

• 장점: 인덱스 크기가 작고, 삽입/삭제 시 유지 비용이 상대적으로 적음
• 단점: 직접 포인터가 없으므로 추가 스캔 필요 → 밀집 인덱스보다 검색 속도 낮을 수 있음

2. 다단계 인덱스(Multilevel Indices)

• 인덱스가 매우 커서 메모리에 전부 적재 불가능할 때 사용
• 인덱스를 “파일”로 보고, 그 위에 또 다른 희소 인덱스(Outer Index) 를 씌움
  • 예: 내부 인덱스(Inner Index) → 외부 인덱스(Outer Index) → …
• 장점: 검색 시 상위 레벨 인덱스(작은 크기)를 통해 빠른 범위 축소, 디스크 I/O 횟수 크게 감소
• 구현: B+-트리 구조(14.3절)로 자주 구현

3. 인덱스 갱신(Index Update)

3.1 삽입(Insertion)

1. 밀집 인덱스
   • 새 검색 키가 기존에 없으면, 인덱스 엔트리 추가
   • 기존에 있으면, 해당 인덱스 엔트리의 포인터 리스트에 새 레코드 포인터 추가
2. 희소 인덱스
   • 새로운 블록이 생성된 경우, 그 블록의 첫 번째 검색 키 값을 인덱스에 추가
   • 기존 블록에 삽입 시, 가장 작은 값이 변경되면 인덱스 갱신

3.2 삭제(Deletion)

1. 밀집 인덱스
   • 해당 검색 키를 갖는 레코드가 더 이상 없다면, 인덱스 엔트리 자체 삭제
   • 검색 키가 여전히 남아 있다면, 인덱스 엔트리의 포인터 목록에서 해당 포인터만 제거
2. 희소 인덱스
   • 삭제된 레코드의 검색 키가 인덱스에 없으면 아무 일도 하지 않음
   • 해당 검색 키가 인덱스에 있고, 그 키에 대한 레코드가 더 이상 없으면 인접 키로 대체하거나 제거

다단계 인덱스에서도 동일 원리 적용 (최하위 인덱스 갱신 → 상위 인덱스가 그 인덱스를 “파일”로 보고 동일한 갱신 수행)

4. 보조(논클러스터링) 인덱스(Secondary Indices)

• 테이블의 물리적 정렬 순서와 다른 속성(또는 속성 집합)에 대한 인덱스
• 항상 밀집 인덱스 형태이어야 함
  • 테이블이 해당 키 순으로 정렬되어 있지 않으므로, 희소 인덱스로는 중간값들을 찾기 어려움
• 후보 키가 아닌 속성(중복 가능)을 인덱스 키로 사용할 경우, 한 키 값에 여러 레코드 → 각 레코드로 가는 포인터 리스트 관리 필요
• 장점: 클러스터링 인덱스로 처리 불가능한 속성 조건의 검색 속도 향상
• 단점: 인덱스 유지(삽입/삭제) 부담 증가, 디스크 공간 추가 소모

5. 다중 키 인덱스(Composite Keys)

• 인덱스의 검색 키가 여러 속성으로 이루어진 경우
  • 예: (course_id, semester, year)
• 사전식(lexicographic) 정렬 사용
  • 예) (a1, a2) < (b1, b2) 은 a1 < b1 이거나 a1 = b1이고 a2 < b2일 때 성립
• 다중 속성 검색, 결합 조건(query)에 유리

3. B+-트리 인덱스 파일 (B+-Tree Index Files)

1. 배경

• Index-Sequential 방식의 단점: 데이터 양이 커지면 정렬 순서 유지 비용 증가(삽입·삭제에 따른 재조직화 비용 큼).
• B+-트리: 삽입·삭제 시에도 균형(Balanced) 을 유지해, 재조직화 없이 효율적인 인덱싱 가능.
  • 모든 리프(leaf)까지의 경로 길이가 동일 → 균형 트리
  • 노드 간 포인터 개수(child 수)가 일정 범위(⌈n/2⌉ ~ n)를 유지

2. B+-트리 구조

2.1 노드 구조

• 리프 노드(leaf node)
  • 최대 (n-1)개의 검색 키와 (n-1)개의 레코드 포인터 보관
  • 추가로 오른쪽 리프를 가리키는 포인터(Pn)가 있어 리프들끼리 연결 리스트 형태 유지 (순차 접근 편의)
• 비리프(내부) 노드(internal node)
  • 최대 n개의 자식 포인터 보관 (최소 ⌈n/2⌉개 보관)
  • 검색 키들은 자식 범위를 나누는 기준 값

2.2 균형 트리

• 루트(root)에서 리프까지의 높이가 동일 (균형)
• 노드가 반쯤 차 있어도(최소 ⌈n/2⌉ 포인터/값) 재분배나 합병으로 유지 가능 → 삽입·삭제 시에도 트리 높이가 크게 변하지 않음

2.3 중복 키

• 보통은 (검색 키 + 유일 속성) 으로 복합 키(composite key)를 생성해 중복을 제거
• 실제 구현에서 Record ID, Primary Key 등을 추가하여 검색 키를 유일하게 만듦
  • 삭제 시, 특정 레코드를 유일 키로 바로 찾을 수 있어 효율적

3. B+-트리를 이용한 연산

3.1 검색 (Lookup)

1. 루트 노드부터 시작, 현재 노드에서 검색 키 범위를 확인하며 적절한 자식 포인터를 따라감
2. 리프 노드까지 내려간 후, 해당 리프 내에서 검색 키를 찾아 레코드 포인터 획득
3. (일치 키가 없으면) 해당 레코드가 존재하지 않음

• 범위 질의(Range Query)
  • 시작 값(lb)에 해당하는 리프 노드까지 내려간 뒤, 리프들을 순차로 따라가며 ub 이하의 모든 키 수집

3.2 삽입 (Insertion)

1. 삽입 위치(리프 노드) 찾은 후, 노드에 공간이 있으면 바로 삽입
2. 노드가 꽉 차면(split) 반을 나누어 새 노드를 만든 뒤, 상위 부모 노드에 새 노드 포인터와 경계 키 삽입
3. 부모 노드 역시 꽉 차면 재귀적으로 스플릿(split) 진행
4. 루트도 split되면 트리 높이 1 증가

3.3 삭제 (Deletion)

1. 리프 노드에서 키/포인터 삭제
2. 노드가 너무 적어(underfull) 지면, 형제 노드와 재분배(redistribute) 또는 합병(coalesce/merge)
   • 합병 시 부모에서 해당 노드 정보 삭제 → 부모 노드도 underfull이면 재귀적으로 처리
3. 루트 노드가 포인터 1개만 남으면, 해당 자식 노드가 새 루트가 되고 루트 삭제 (트리 높이 1 감소)

4. 성능 분석

• 트리 높이가 log( fanout )에 비례 → 검색·삽입·삭제 모두 평균적으로 O(log N)의 디스크 I/O
  • 일반적으로 n(=노드 내 최대 포인터 수)을 디스크 블록 크기 기준으로 설정
  • 실제로는 비리프 노드들이 메모리에 상주할 가능성이 높아, 디스크 접근 횟수는 매우 적음 (1~3회 정도)

5. 비유일(Nonunique) 검색 키 처리

• 실무에서는 검색 키에 레코드 ID나 기본키 등을 덧붙여 복합 키로 만들고, 중복 문제 해결
• 중복을 허용하는 구조도 구현 가능하나, 삭제 시 특정 레코드만 찾아 제거하기가 비효율적 (키가 여러 리프에 걸칠 수 있음)
• 따라서 DBMS에서는 보통 자동으로 유일 키를 구성하는 방식을 사용함

4. B+-트리 확장 (B+-Tree Extensions)

1. B+-트리 파일 구조 (B+-Tree File Organization)

• B+-트리 자체가 파일의 레코드 저장 및 관리를 담당
  • 리프 노드가 레코드 자체를 저장 (기존 인덱스처럼 ‘포인터’가 아니라 ‘실제 레코드’)
  • 삽입/삭제 시 블록 split/merge 과정을 B+-트리처럼 수행
• 장점: 오버플로(overflow) 블록 문제를 줄여 성능 저하 방지
• 단점: 레코드가 크면 리프 노드 당 저장 가능한 레코드 수가 감소 → 노드 수 증가 가능

형제 노드 간 확장(split)·합병(merge)의 다중 노드 재분배 기법

• 삽입 시 인접 형제 노드와 여유 공간을 재분배하여 split 최소화
• 삭제 시 한 노드가 과소 채워짐(underfull) 상태일 때, 형제 노드와 재분배하거나 3노드 이상 함께 합병
• 노드 병합/재분배로 중간 수준의 채움 상태(2/3 이상) 보장 → 공간 활용률↑

2. 보조 인덱스(Secondary Indices)와 레코드 이동 문제

• B+-트리 파일 구조에서 리프 노드 split으로 인해 레코드가 물리적 위치를 이동할 수 있음
  • 이때, 기존 보조 인덱스(secondary index)가 레코드 포인터를 직접 저장할 경우, 대규모 업데이트 필요
• 해결책: 보조 인덱스에는 주(클러스터링) 인덱스 키(예: 기본키)만 저장 → 레코드 위치 변경 시에도 무관
  1. 보조 인덱스 → (주 인덱스 키) 목록 확인
  2. 주(클러스터링) 인덱스를 통해 최종 레코드 위치 찾아감
• 장점: 레코드 물리 위치 변경 시 보조 인덱스 업데이트 불필요
• 단점: 보조 인덱스를 통한 레코드 접근 시 두 번 인덱스 검색(보조 인덱스 → 주 인덱스) 필요

3. 문자열 인덱싱 (Indexing Strings)

• 문자열(가변 길이) 은 키 길이가 달라 고정 개수로 노드 수를 계산하기 어려움
  • 노드에 남은 공간 기준으로 split/merge 판단
• 문자열 길이가 길 경우, 팬아웃(fanout) 이 작아져 트리 높이 증가
• Prefix Compression(접두어 압축) 기법
  • 비리프 노드에는 구분에 필요한 접두어만 저장 (예: Silberschatz 대신 Silb만 사용)
  • 중첩되는 문자열이 많은 경우 저장 공간과 트리 높이를 줄이는 데 효과적

4. 대량 로딩(Bulk Loading) 기법

• 대규모 레코드에 대해 하나씩 삽입 시, 리프 접근이 임의 I/O라서 비용 매우 큼
• 효율적인 로딩 절차:
  1. 새 인덱스에 들어갈 (검색키, 레코드포인터) 쌍 임시 파일 생성
  2. 검색키 순으로 정렬
  3. 정렬된 순서대로 트리에 삽입 (또는 바텀업 방식으로 한 번에 구성)
• 장점:
  • 리프 노드가 순차적으로 차기 때문에 블록 간 임의 탐색 최소화
  • 인덱스 생성 시 I/O 횟수 크게 감소
• 실무 팁: 대량 삽입 시, 보조 인덱스 등을 제거 후 삽입 완료 뒤 재생성 → 더 빠름

5. B-트리(B-Tree)와의 비교

• B-트리: 중간(내부) 노드에 검색 키가 유일하게 한 번만 나타남
  • 각 내부 노드가 추가 포인터(파일/버킷용)를 가짐
  • 리프 노드와 내부 노드에 있는 키가 겹치지 않음
• B+-트리:
  • 비리프 노드의 키가 리프에도 중복으로 존재
  • 팬아웃(fanout)이 커서 트리 높이가 낮아지는 경향
• 대부분 DBMS에서는 B+-트리 사용 (실제로 ‘B-트리’라고 말하지만 구현은 B+-트리)

6. 플래시 스토리지(Flash Storage)에서의 인덱싱

• 플래시(SSD)는 랜덤 읽기(random read) 가 자기 디스크 대비 매우 빠름 (수십 ~ 수백 µs)
• 쓰기는 블록 단위 erase 필요 → In-Place Update 어려움
• B+-트리 노드 크기를 플래시 페이지 크기에 맞추면 성능 향상
• Bulk Loading 시에도 쓰기 횟수 감소하여 플래시 쓰기 비용 절감
• 추가 기법:
  • 노드 내부 버퍼링(내부 노드에 변경 분을 임시 기록 후 한 번에 반영)
  • Log-Structured Merge Tree(LSM-트리) 등 다양한 변형 구조

7. 메인 메모리 상의 인덱싱

• 메모리에 전체 데이터 상주 가능한 경우 → B+-트리 그대로 사용 가능하지만, 다음 최적화 가능:
  1. 메모리 구조(캐시 라인 등)를 고려한 작은 노드 크기 → 캐시 미스 최소화
  2. 노드를 캐시 라인 크기에 맞춰 관리 → 트리 탐색 시 캐시 로드 횟수 감소
• 디스크 기반 접근 최적화(큰 노드)와 메모리 기반 접근 최적화(작은 노드)는 절충이 필요

5. 해시 인덱스 (Hash Indices)

1. 개요

• 해싱(Hashing): 검색 키를 해시 함수 h에 통과시켜 버킷(bucket) 위치를 결정
• 버킷(bucket): 실제 레코드(또는 레코드 포인터)들을 저장할 수 있는 단위 공간
• 오버플로 체이닝(Overflow Chaining) 방식
  • 버킷이 가득 차면 오버플로 버킷을 추가로 연결(체인)
  • 닫힌 주소 방식(closed addressing)이라고도 함

2. 해시 인덱스 연산

2.1 삽입 (Insertion)

1. 레코드의 검색 키 Ki에 대해 h(Ki) 값 계산
2. 해당 버킷이 공간 여유가 있으면 레코드를 저장
3. 공간이 없으면 오버플로 버킷을 만들어 연결

2.2 검색 (Lookup)

1. h(Ki)로 대상 버킷 위치 찾기
2. 해당 버킷(및 연결된 오버플로 버킷들)을 순차 검사
3. 검색 키와 일치하는 레코드 찾기

2.3 삭제 (Deletion)

1. h(Ki)로 대상 버킷 찾기
2. 버킷 내에서 검색 키가 Ki인 레코드 제거 (연결 리스트에서 노드 제거)

3. 특징 및 제한

• Equality(=) 검색에 최적화
  • 예: WHERE key = value
• 범위(range) 검색에는 부적합 (버킷을 통한 순서/범위 판단 불가)
• 버킷 오버플로 발생 가능
  • 레코드 분포의 불균형(해시 충돌)
  • 해시 함수 선택 잘못 → 특정 버킷에 몰림
• 효율을 위해 버킷 수를 (레코드 수 / 버킷당 수용 레코드 수) * (1 + d) 정도로 설정 (d는 여유율, 예: 0.2)

4. 정적 해싱(Static Hashing) vs 동적 해싱(Dynamic Hashing)

4.1 정적 해싱 (Static Hashing)

• 버킷 수 고정
• 레코드 수가 예상보다 많이 증가하면, 한 버킷에 너무 많은 레코드가 몰려 검색 효율 급락
• 해결책: 해시 인덱스 재구성(버킷 수 늘려 다시 빌드)
  • 대규모 데이터 시 비용(다운타임) 매우 큼

4.2 동적 해싱 (Dynamic Hashing)

• 레코드 수 증가에 맞춰 버킷을 점진적으로 늘릴 수 있는 기법
• 대표 기법: 선형 해싱(linear hashing), 확장성 해싱(extendible hashing)
• 필요할 때마다 부분적으로 버킷 확장 → 전면 재구축 불필요

6. 다중 키 접근 (Multiple-Key Access)

1. 다중 단일-키 인덱스(Multiple Single-Key Indices)

1.1 상황 예시

• instructor 테이블에 다음 두 인덱스가 존재:
  1. dept_name 컬럼에 대한 인덱스
  2. salary 컬럼에 대한 인덱스
• 질의 예: dept_name = 'Finance' AND salary = 80000

1.2 처리 전략

1. 단일 인덱스 사용 (예: dept_name 인덱스만 사용 후 레코드에서 salary=80000 필터링)
2. 다른 단일 인덱스 사용 (예: salary 인덱스만 사용 후 dept_name='Finance' 필터링)
3. 두 인덱스 동시 사용
   • dept_name 인덱스로 'Finance' 레코드 포인터 목록 획득
   • salary 인덱스로 80000 레코드 포인터 목록 획득
   • 두 포인터 집합의 교집합(Intersection) 취하기

주의사항

• 포인터 집합이 매우 커서 교집합 과정이 많으면 오히려 비효율적일 수 있음
  • 예) Finance 레코드가 매우 많고, salary=80000도 많으나 실제 교집합은 적을 경우

2. 다중 속성(Composite) 인덱스

2.1 복합 키 인덱스 (Composite Search Key)

• 검색 키를 (dept_name, salary) 같이 2개 이상의 속성으로 구성
• Ordered(B+-트리) 인덱스에서는 (dept_name, salary)가 사전순(lexicographic) 으로 정렬
• 장점
  • (dept_name='Finance' AND salary=80000) 형태의 정확 일치 쿼리에 매우 빠른 접근
  • dept_name='Finance' AND salary < 80000 같은 (첫째 항목==, 둘째 항목 range) 형태 쿼리도 범위 스캔 이용 가능
  • dept_name='Finance' 단일 조건만 있어도 ('Finance', -∞) ~ ('Finance', +∞) 범위 스캔 가능

2.2 한계

• 첫 속성(dept_name)에 대한 조건이 =Finance (정확 일치)가 아닌, <나 > 인 경우, 원하는 범위가 분산되어 I/O 증가
  • 예: dept_name < 'Finance' AND salary < 80000 → 트리 순서가 (dept_name, salary)이므로 효과 떨어짐
• 다중 비교 연산이 섞여 있는 경우 효율이 떨어질 수 있음
  • 예) (dept_name < 'X') AND (salary > 50000) 등

3. 커버링 인덱스(Covering Index)

• 보조(secondary) 인덱스에서 검색 키 외에 추가 속성값 일부를 함께 저장
  • 예: (ID 인덱스)에 salary 값까지 저장
• 장점
  • 어떤 쿼리가 검색 키 + 일부 속성만 요청 시, 실제 테이블에 접근 없이 인덱스만으로 결과 얻을 수 있음
  • 예) SELECT salary FROM instructor WHERE ID = 12345 → 인덱스 내에 salary 존재 시, 테이블 접근 불필요
• 효과
  • 단순 (ID, salary) 복합 키 인덱스를 만드는 것과 유사하나, 인덱스의 검색 키를 작게 유지하면서 추가 속성을 커버함으로써
    • 팬아웃(fanout) 상승 (비리프 노드에 더 많은 키를 저장 가능)
    • 인덱스 높이 감소 → I/O 비용 절감

7. 인덱스 생성 (Creation of Indices)

1. 인덱스 생성 문법

• SQL 표준에는 인덱스 생성 구문이 명시되어 있지 않지만, 대부분 DBMS에서 다음과 같은 구문 지원:

  create index <index_name>
  on <table_name> (<column_list>);
  
  drop index <index_name>;

• UNIQUE 인덱스:

  • create unique index 사용 시, 해당 속성(또는 속성 집합)을 후보 키(중복 불가)로 간주

• 인덱스 종류 지정:

  • DBMS별로 B+-트리, 해시 인덱스 등 여러 유형을 지원할 수 있으며, 구체적 구문은 DBMS 매뉴얼 참조

2. 인덱스 유형

• DBMS마다 B+-트리 인덱스, 해시 인덱스, 기타 특수 인덱스 등 다양한 형태를 지원
• 특정 DBMS의 매뉴얼을 통해 인덱스 유형과 구체적 작성법을 확인 가능

3. 인덱스 사용 시 장점

• 선택 조건이나 조인 조건에 자주 사용되는 속성에 인덱스를 두면 쿼리의 수행 시간이 크게 단축
• 예: 특정 ID만 조회해야 하는 경우, 인덱스가 없으면 테이블 전체 스캔, 인덱스가 있으면 특정 레코드에 직접 접근

4. 인덱스 사용 시 단점

• 테이블에 삽입, 삭제, 갱신이 일어날 때마다 모든 관련 인덱스도 갱신해야 함
  → 인덱스가 많으면 수정 연산이 느려질 수 있음

5. 인덱스 설계 시 고려 사항

• 개발·테스트 단계에서 쿼리 시간이 빠듯하지 않을 수도 있으나, 동시에 많은 사용자가 같은 쿼리를 실행하면 급격히 느려질 수 있음
• 핵심 속성(자주 조회/조인되는 열)에 대해서는 미리 인덱스를 만들어둬야 함
• Primary Key 선언 시, 대부분의 DBMS는 기본적으로 인덱스를 자동 생성 (중복키 검증에도 사용)
• Foreign Key 속성에도 인덱스를 만들면, 일반적인 PK-FK 조인에서 훨씬 빠른 검색 가능

6. 인덱스 튜닝 (Index Tuning)

• DBMS에서 제공하는 인덱스 튜닝 도구(Index Tuning Wizard/Advisor) 등을 통해 실제 사용되는 쿼리·갱신 패턴을 분석
• 최근 클라우드 DB 서비스: 과도한 테이블 풀 스캔이 감지되면 자동으로 인덱스를 생성해 주는 기능 지원

14.8 쓰기 최적화 인덱스 구조 (Write-Optimized Index Structures)

1. LSM(Log-Structured Merge) 트리

• B+-트리는 랜덤 쓰기가 많은 환경에서 디스크 탐색(I/O)이 빈번 → 삽입/갱신 속도 저하
• LSM 트리:
  1. 메모리 내 트리(L0)*에 삽입
  2. 일정 크기 넘으면 디스크에 있는 트리(L1, L2, …)와 병합(Merge)
  3. 순차 I/O 위주로 처리 → 랜덤 I/O 크게 감소
  • 삭제/업데이트는 별도 표시(“삭제” 레코드 등)를 추가 삽입하고, 이후 병합 과정에서 실제 삭제/갱신 반영
• 장점: 대규모 랜덤 쓰기에 효과적 (No in-place update)
• 단점:
  • 조회 시 여러 레벨 트리를 모두 검색 필요
  • 병합 시 데이터 전체를 재작성할 수도 있음

2. 버퍼 트리(Buffer Tree)

• 각 내부 노드에 버퍼를 두어, 삽입 시 루트 버퍼에 저장 후 여유 시 자식 노드로 한꺼번에 전달
• 랜덤 쓰기를 여러 레코드(버퍼에 모인)로 나눠서(Amortized) 처리 → 쓰기 횟수 절감
• 삽입 시 자식 노드를 한 번 읽고 쓸 때 여러 레코드를 처리하므로 효율적
• 장점:
  • B+-트리처럼 전체 구조가 유지되면서도 쓰기 비용 감소
• 단점:
  • 조회 시 내부 노드 버퍼도 확인해야 하므로 구현 복잡
  • 디스크 기반 무작위 접근이 매우 비싼 상황(디스크 탐색)이면 LSM 트리가 더 효과적일 수도 있음
• 응용: PostgreSQL의 GiST 인덱스 등에서 버퍼링 기법 활용

9. 비트맵 인덱스 (Bitmap Indices)

• 개념: 속성이 가질 수 있는 각 값에 대해, 레코드 개수만큼의 비트 배열(bitmap)을 구성
  • 레코드 i가 해당 값이면 i번째 비트를 1로, 아니면 0으로 표기
• 용도:
  • 속성 값이 중복이 많고(카디널리티 낮고), 결합 질의(여러 속성 동시 조건)에서 빠른 교집합 계산 시 유리
  • 예: gender가 ‘m’, ‘f’만 있는 경우, income_level 등 범주형 속성
• 장점:
  • AND/OR 등 비트 연산을 매우 빠르게 수행해 교집합, 합집합 등을 효율적으로 계산
  • 결과 비트마스크로 해당 레코드만 읽으면 됨
• 한계:
  • 속성 값 범위가 큰 경우(유니크 값 매우 많을 때)는 비트맵 크기가 커서 비효율적
  • 주로 OLAP 환경, 결합 질의가 많은 데이터 웨어하우스에서 활용

10. 공간 및 시간 데이터의 인덱스 (Indexing of Spatial and Temporal Data)

1. 공간(Spatial) 데이터 인덱싱

1.1 개요

• 공간 데이터: 2차원 이상의 좌표로 표현되는 객체(점·선·다각형 등)
• 공간 질의 예:
  • 범위 질의: 특정 영역(원/사각형 등) 내에 포함되는 객체 찾기
  • 최근접 질의: 특정 위치에서 가장 가까운 객체 찾기

1.2 전통적 인덱스(B+-트리, 해시) 한계

• 1차원 기반으로 설계 → 다차원 범위 질의 처리에 비효율

1.3 k-d 트리 (k-dimensional tree)

• 각 내부 노드가 한 차원을 기준으로 공간을 2등분
• 이진 트리 형태로 좌표를 재귀적으로 분할
• 예) 2차원 데이터에서 루트는 x축 기준으로, 자식은 y축 기준으로 분할, 그다음 레벨은 다시 x축…
• 범위 질의(사각형, 원 등) 처리 시, 트리를 내려가며 분할 영역이 질의 범위와 교차하는지 검사

1.4 R-트리

• 다차원 객체(다각형 등) 를 최소 경계 사각형(MBR: Minimum Bounding Rectangle)으로 묶어 B-트리 형태로 구성
• 리프 노드: 실제 객체(또는 그 객체의 MBR) 저장
• 내부 노드: 자식 노드들의 MBR을 저장하며, 자식 포인터 보관
• 질의 시, MBR들과의 겹침 여부를 검사해 하위 노드를 탐색
• 장점: 한 객체를 하나의 노드에만 저장 (중복 X), 균형 트리 유지
• 응용: GIS, 지도 서비스(대상 지역 범위 질의, 최근접 식당 찾기 등)에 활용

2. 시간(Temporal) 데이터 인덱싱

2.1 시간 데이터

• 튜플에 시작 시점(start time)과 종료 시점(end time)으로 표현되는 유효 기간(interval) 존재
• 종료 시점이 현재까지인 경우, end_time = ∞(매우 큰 값)으로 표시

2.2 전통 인덱스의 문제

• attribute = value인 튜플 중 특정 시간점(또는 구간)에 유효한 것만 빠르게 찾고 싶을 때, 단순 B+-트리로는 비효율적

2.3 R-트리 활용

• 1차원 값(a) + 1차원 시간(time) → 2차원으로 확장하여 R-트리(또는 k-d 트리) 사용
• (a, start_time) ~ (a, end_time) 구간을 다루는 직사각형으로 표현
• 다만, end_time = ∞(현재 유효)인 구간은 매우 큰 사각형이 될 수 있어 처리 시 주의 필요
  • 현재 유효 튜플은 별도 인덱스 분리(B+-트리 등) or 다른 방식으로 관리

2.4 다른 기법

• Interval B+-tree: 시간 구간(시작~종료)에 특화된 인덱스
• 실제 DB 구현에서는 R-트리 등 다차원 인덱스를 재사용해 간단히 처리하는 경우가 많음

Introduction to SQL

1. Overview of the SQL Query Language

• 역사와 발전
  • IBM의 System R 프로젝트에서 Sequel로 시작
  • ANSI/ISO 표준: SQL-86, SQL-89, SQL-92, SQL:1999, SQL:2003, SQL:2006, SQL:2008 등

• SQL의 구성 요소
  • `DDL: 테이블, 스키마, 무결성 제약, 인덱스, 보안 및 물리적 저장구조 정의
  • DML: 데이터 검색, 삽입, 삭제, 갱신
  • 기타: 트랜잭션 제어, 뷰 정의, 임베디드/동적 SQL, 권한 부여

2. SQL Data Definition

• 테이블 생성 및 스키마 정의

  • CREATE TABLE 명령으로 테이블 생성
  • 각 속성은 자료형과 선택적 제약조건을 가짐
  • 예시:

    create table department (
      dept_name varchar(20),
      building varchar(15),
      budget numeric(12,2),
      primary key (dept_name)
    );

• 기본 자료형

  • 문자열: char(n) (고정 길이), varchar(n) (가변 길이), nvarchar (유니코드 지원)
  • 숫자형: int, smallint, numeric(p,d), real, double precision, float(n)
  • NULL 값: 존재하지만 값이 없음을 의미하며, 각 자료형은 NULL을 가질 수 있음

• 무결성 제약

  • Primary Key: 고유하며 NULL 불가
  • Foreign Key: 다른 테이블의 기본키와 연계하여 참조 무결성 유지
  • Not Null: 속성에 NULL 값이 들어가지 않도록 강제

3. Basic Structure of SQL Queries

단일 테이블

• 모든 부서의 이름을 출력한다면

  select dept_name
  from instructor;

• 중복 제거는 DISTINCT 사용

  select distinct dept_name
  from instructor;
  

다중 테이블

• SELECT : 출력할 속성 또는 표현식 지정
• FROM : 검색할 테이블(들)을 지정하며, 기본적으로 Cartesian product(데카르트 곱)를 생성
• WHERE : 튜플을 선택하기 위한 조건을 지정

• 여러 테이블의 데카르트 곱을 생성하므로, 반드시 WHERE 조건으로 원하는 튜플만 선택해야 함

  select name, course_id
  from instructor, teaches
  where instructor.ID = teaches.ID;
  

<br>

### Natural Join

<br>

- 두 테이블 간 동일한 이름의 속성에 대해 자동으로 조인
- 아래 두 SQL문은 같은 결과를 출력한다

```sql
select name, course_id
from instructor natural join teaches;

select name, course_id
from instructor, teaches
where instructor.ID = teaches.ID;

Join ... USING

• 특정 속성만으로 조인하도록 지정
• 아래 두 SQL문은 같은 결과를 출력한다

select name, title
from (instructor natural join teaches) join course using (course_id);

select name, title
from instructor natural join teaches, course
where teaches.course_id = course.course_id;

4. Additional Basic Operations

Rename 또는 별칭 사용

• 속성 및 테이블 별칭: AS 를 사용하여 이름을 재정의

select T.name as instructor_name, S.course_id
from instructor as T, teaches as S
where T.ID = S.ID;

• SELF JOIN: 같은 테이블을 두 번 사용 시 별칭 필수

select distinct T.name
from instructor as T, instructor as S
where T.salary > S.salary and S.dept_name = 'Biology';

문자열 연산 및 패턴 매칭

• 문자열 표기: '로 감싸서 표현, 내부의 작은 따옴표라면 두 번 사용('')
• 문자열 함수: upper(), lower(), trim() 등
• 패턴 매칭: LIKE 연산자와 % , _ 등

select dept_name
from department
where building like '%Watson%';

• 이스케이프 문자: 특수문자는 일반 문자로 인식하기 위해 escape 키워드 사용

작성중입니다 .. . 쓸 게 굉장히 많네요 미친건가 .. . . .

📡 ICMP: 인터넷 제어 메시지 프로토콜 (Internet Control Message Protocol)

인터넷에서 호스트와 라우터가 서로 네트워크 계층 정보를 교환할 때 ICMP(Internet Control Message Protocol) 가 사용됩니다.
ICMP는 네트워크 오류 보고, 진단 및 제어 메시지를 전송하는 역할을 하며, RFC 792에 정의되어 있습니다.

이번 포스팅에서는 ICMP의 개념, 동작 원리, 주요 메시지 유형 및 Traceroute와의 관계에 대해 자세히 알아보겠습니다.

🧐 ICMP란?

ICMP(Internet Control Message Protocol) 는 네트워크 계층에서 네트워크 문제를 감지하고 보고하는 프로토콜입니다.
일반적으로 라우터와 호스트가 네트워크 오류를 알리거나, 진단 메시지를 주고받을 때 사용됩니다.

ex) 웹사이트에 접속할 때의 "Destination network unreachable" 오류

→ 네트워크에서 목적지를 찾을 수 없을 때, 라우터가 ICMP 메시지를 생성하여 오류를 보고

🛠 ICMP의 주요 특징

• IP 프로토콜과 밀접한 관계
  • ICMP 메시지는 IP 패킷 내에서 전송되며, IP 프로토콜 상위 계층에서 동작합니다.
  • TCP/UDP와 마찬가지로 IP 페이로드로 전송됩니다.
• 비연결형 프로토콜
  • ICMP는 상태를 유지하지 않는 비연결형 프로토콜(connectionless protocol) 입니다.
• 오류 감지 및 보고
  • 네트워크 오류가 발생하면, 해당 오류를 원래 송신자에게 알리는 역할을 합니다.

📜 ICMP 메시지 구조 및 유형

ICMP 메시지는 특정 타입과 코드로 분류됩니다.
각 메시지는 IP 헤더와 문제를 일으킨 원본 IP 패킷의 처음 8바이트를 포함합니다.
이 정보를 바탕으로 송신자는 오류 원인을 분석할 수 있습니다.

🔹 주요 ICMP 메시지 유형

📡 Ping 명령어와 ICMP Echo 메시지

📌 Ping이란?

ping 명령어는 네트워크 연결 상태를 테스트하는 데 사용됩니다.
ping을 실행하면 ICMP Echo Request(Type 8, Code 0) 메시지를 전송하고, 상대 호스트가 응답하면 ICMP Echo Reply(Type 0, Code 0) 메시지를 반환합니다.

🏓 Ping 동작 방식

1. 송신자는 대상 IP 주소로 ICMP Echo Request(Type 8, Code 0) 메시지를 전송
2. 대상 호스트는 수신 후 ICMP Echo Reply(Type 0, Code 0) 메시지를 응답
3. RTT(Round Trip Time) 측정하여 네트워크 상태 분석 가능

🔍 Traceroute와 ICMP Time Exceeded 메시지

📌 Traceroute란?

Traceroute는 네트워크 경로를 추적하는 도구입니다.
네트워크 패킷이 목적지까지 가는 모든 라우터를 확인하고, 각 구간의 지연 시간(RTT)을 측정하는 역할을 합니다.

🛠 Traceroute의 동작 원리

1. Traceroute는 UDP 패킷을 전송하지만, TTL(Time To Live) 값을 1부터 증가시키며 전송합니다.
2. 각 라우터는 TTL이 0이 되면, ICMP Time Exceeded(Type 11, Code 0) 메시지를 반환합니다.
3. 이를 통해 Traceroute는 각 경로의 라우터 IP 주소와 응답 시간을 확인합니다.
4. 마지막 패킷이 목적지에 도착하면, ICMP Destination Unreachable(Type 3, Code 3) 메시지를 반환하여 탐색을 종료합니다.
   
   

🚨 ICMP와 혼잡 제어: Source Quench 메시지

과거에는 혼잡 제어를 위해 ICMP Source Quench 메시지(더 이상 사용되지 않음)를 활용했습니다.

• 혼잡 발생 시, 라우터가 송신자에게 ICMP Source Quench 메시지를 보내 전송 속도를 줄이도록 유도
• 하지만, TCP 자체적인 혼잡 제어 메커니즘(예: 슬로우 스타트, AIMD)이 발전하면서 ICMP Source Quench 메시지는 더 이상 사용되지 않음

🌍 ICMPv6: IPv6에서의 확장

IPv6에서는 기존 ICMP 메시지를 정리하고, 새로운 기능을 추가한 ICMPv6 (RFC 4443) 가 정의되었습니다.

🆕 ICMPv6에서 추가된 주요 기능

• Packet Too Big: IPv6는 패킷 분할(fragmentation)을 지원하지 않기 때문에, 패킷 크기가 너무 클 경우 "Packet Too Big" 메시지를 전송
• Neighbor Discovery: ARP(Address Resolution Protocol)를 대체하여 IPv6 주소를 MAC 주소로 변환
• Router Solicitation & Advertisement: 동적 라우터 설정을 지원

TCP 혼잡 제어(TCP Congestion Control)

인터넷 환경에서 데이터 전송 시 네트워크의 혼잡을 효과적으로 관리하는 것은 매우 중요합니다. 특히 여러 장치가 동시에 데이터를 주고받는 상황에서는 네트워크 혼잡이 발생하기 쉽습니다. 이때 TCP 혼잡 제어(TCP Congestion Control) 메커니즘이 중요한 역할을 합니다.

이번 포스팅에서는 TCP 혼잡 제어의 개념, 동작 원리, 주요 알고리즘에 대해 자세히 알아보겠습니다.

📦 TCP 혼잡 제어란?

TCP 혼잡 제어(Congestion Control) 는 네트워크의 혼잡 상태를 감지하고, 이에 따라 데이터 전송 속도를 조절하여 네트워크의 안정성을 유지하는 메커니즘입니다.

✅ TCP 혼잡 제어의 필요성

• 네트워크 과부하 방지: 과도한 트래픽으로 인한 패킷 손실 방지
• 효율적인 대역폭 사용: 가용한 대역폭을 최대한 활용하면서도 안정적인 전송 유지
• 신뢰성 보장: 데이터가 안정적으로 전송되도록 손실과 재전송을 최소화

⚙️ TCP 혼잡 제어의 핵심 요소

TCP는 네트워크 혼잡을 감지하고 전송 속도를 조절하기 위해 다음과 같은 요소를 활용합니다.

1️⃣ 혼잡 윈도우 (Congestion Window, cwnd)

• 송신자가 네트워크로 보낼 수 있는 최대 데이터 양을 결정하는 변수입니다.
• cwnd 값이 커지면 전송 속도가 증가하고, 작아지면 전송 속도가 감소합니다.

2️⃣ 혼잡 신호 감지 방법

• 패킷 손실: 타임아웃 발생 또는 3중 중복 ACK(Duplicate ACK) 수신 시 혼잡 발생으로 간주
• ACK 수신 속도: ACK가 느리게 도착하면 혼잡 가능성으로 해석

3️⃣ 혼잡 제어 단계

TCP 혼잡 제어는 Slow Start → Congestion Avoidance → Fast Recovery 단계를 반복하며 혼잡 상태에 대응합니다.

🚀 TCP 혼잡 제어 알고리즘

TCP 혼잡 제어는 다음과 같은 3가지 주요 알고리즘으로 구성됩니다.

📈 1. 슬로우 스타트 (Slow Start)

• 초기 연결 시 또는 혼잡 발생 후 전송 속도를 빠르게 증가시키는 단계입니다.
• cwnd를 1 MSS(Maximum Segment Size)로 시작하고, ACK를 받을 때마다 1 MSS씩 증가합니다.
• 매 RTT마다 전송 속도가 2배로 증가 → 지수적 성장 (Exponential Growth)

동작 예시

1. cwnd = 1 MSS로 시작 → 첫 번째 패킷 전송
2. ACK 수신 → cwnd = 2 MSS로 증가
3. 2개의 패킷 전송 → 각각 ACK 수신 시 cwnd = 4 MSS로 증가
4. 이러한 과정이 계속되어 빠르게 전송 속도가 증가합니다.

슬로우 스타트 종료 조건:

• cwnd가 ssthresh(slow start threshold) 에 도달하면 혼잡 회피(Congestion Avoidance)로 전환
• 패킷 손실이 발생하면 다시 cwnd = 1 MSS로 초기화

📉 2. 혼잡 회피 (Congestion Avoidance)

• 슬로우 스타트 단계 이후 안정적인 전송 속도 유지를 목표로 합니다.
• cwnd를 선형적으로 증가(Additive Increase) 합니다:
  • 매 RTT마다 cwnd를 1 MSS씩 증가시켜 대역폭을 탐색
• 혼잡이 감지되면 cwnd를 절반으로 감소(Multiplicative Decrease) 합니다.

동작 예시

1. cwnd = 16 MSS일 때 패킷 손실 발생 → cwnd = 8 MSS로 감소
2. 이후 매 RTT마다 cwnd를 1 MSS씩 증가시켜 혼잡 여부를 탐색
3. 다시 혼잡 발생 시 cwnd를 절반으로 감소

이 방식은 AIMD(Additive Increase, Multiplicative Decrease) 원칙을 기반으로 합니다.

⚡ 3. 빠른 회복 (Fast Recovery)

• 3중 중복 ACK(Triple Duplicate ACK) 를 수신하면, 패킷 손실을 감지하고 빠르게 복구하는 단계입니다.
• 타임아웃 없이 즉시 손실된 패킷을 재전송하여 성능 저하를 최소화합니다.

동작 방식

1. 패킷 손실 감지(3중 중복 ACK 수신) → cwnd를 절반으로 감소
2. 손실된 패킷을 빠르게 재전송(Fast Retransmit)
3. 새로운 ACK가 도착하면 혼잡 회피(Congestion Avoidance) 단계로 전환

🔄 TCP 혼잡 제어의 전체 흐름

1️⃣ 연결 초기화
      ↓
2️⃣ Slow Start (지수적 증가)
      ↓ (cwnd ≥ ssthresh 또는 패킷 손실 발생)
3️⃣ Congestion Avoidance (선형적 증가)
      ↓ (패킷 손실 감지 시)
4️⃣ Fast Recovery (빠른 재전송 및 복구)
      ↓ (복구 완료)
5️⃣ 다시 Congestion Avoidance로 복귀

📊 AIMD: TCP 혼잡 제어의 핵심 원칙

TCP 혼잡 제어는 AIMD (Additive Increase, Multiplicative Decrease) 원칙에 기반합니다.

⚡ AIMD의 구성 요소

• Additive Increase (선형 증가):
  혼잡이 발생하지 않으면 cwnd를 매 RTT마다 1 MSS씩 선형적으로 증가합니다.
  → 네트워크의 여유 대역폭을 탐색하며 서서히 전송 속도를 높이는 방식입니다.
• Multiplicative Decrease (배수 감소):
  혼잡이 발생(예: 패킷 손실)하면 cwnd를 즉시 절반으로 감소하여 전송 속도를 급격히 줄입니다.
  → 네트워크 혼잡을 빠르게 완화하기 위한 대응입니다.

🚀 AIMD의 효과

• ✅ 혼잡 방지:
  혼잡 발생 시 즉각적인 속도 감소로 네트워크 과부하 방지
• ✅ 대역폭 최적화:
  여유 대역폭을 최대한 활용하기 위해 선형적으로 전송 속도 증가
• ✅ 공정성(Fairness):
  여러 TCP 연결이 병목 구간을 공유할 때 공평한 대역폭 분배 보장
• ✅ 안정성(Stability):
  급격한 혼잡 발생에도 빠르게 복구하고, 네트워크 안정성 유지

IP와 TCP

• IP(Internet Protocol)
  • 인터넷에서 데이터를 전송하기 위한 기본 프로토콜
  • 데이터를 작은 조각인 패킷으로 나누어 네트워크를 통해 전송
  • 특징:
    • 비신뢰적(Unreliable): 데이터가 손실되거나 순서가 뒤바뀔 수 있다.
    • 최선의 노력(Best-Effort): 데이터를 가능한 빨리 전송하지만, 성공 보장 X.
    • 경로 설정: 패킷이 목적지까지 도달할 최적 경로를 찾음.
• TCP(Transmission Control Protocol)
  • IP 위에서 동작하는 프로토콜
  • 신뢰적인 데이터 전송 서비스 제공
  • 특징:
    • 데이터 손실 방지: 손실된 데이터를 재전송합니다.
    • 데이터 순서 보장: 원래 순서대로 데이터를 정렬합니다.
    • 무결성 확인: 데이터가 손상되지 않았는지 확인합니다.

예를 들면,

IP가 배달원이라면 TCP는 매니저 역할이다.

• IP는 "주소만 보고" 패킷(데이터 조각)을 전달 → 잘못된 경로로 가거나 손실될 수 있음.
• TCP는 패킷이 제대로 도착했는지 확인, 문제가 생기면 수정. 모든 패킷을 순서대로 정리하여 완전한 데이터로 조립.

TCP가 신뢰적인 데이터 전송을 제공하는 방법

• 기다리는 순서 번호를 가진 순서에 맞는 세그먼트의 도착. 그 이전 순서까지의 모든 데이터들은 이미 확인 응답 된 상태라면?
  • 지연 ACK. 추가 세그먼트를 위해 대기. 만약 다른 세그먼트가 오지 않는다면 ACK 보냄. 온다면 두개를 합쳐서 ACK 보냄.
• 순서에 맞는 세그먼트의 도착. 이미 하나의 순서에 맞는 세그먼트가 있다면?
  • 하나의 누적된 ACK를 보냄
• 지연 ACK:
  • ACK 전송을 최대 500ms까지 지연하여 추가 데이터를 기다리는 것.
  • TCP에서는 네트워크 트래픽을 줄이기 위해 지연 ACK 메커니즘을 사용한다.

예시

• 송신자가 100바이트 크기의 데이터를 두 번에 나누어 보낸다고 가정하자
  • 첫 번째 세그먼트(Sequence Number = 1~100) 도착.
  • 두 번째 세그먼트(Sequence Number = 101~200) 아직 도착하지 않음.
• TCP Receiver의 행동:
  • 첫 번째 세그먼트에 대해 즉시 ACK를 보내지 않음.
  • 대신 500ms 동안 대기하며, 두 번째 세그먼트가 도착하는지 확인한다.
    • 두 번째 세그먼트가 500ms 내에 도착: 두 세그먼트에 대해 한 번의 ACK를 보냄.
    • 두 번째 세그먼트가 500ms 내에 도착하지 않음: 첫 번째 세그먼트에 대해 ACK를 보냄.

TCP와 GBN 프로토콜, SR 프로토콜

• Go-Back-N(GBN)의 특징
  • 누적 ACK:
    • 송신자는 수신자로부터 가장 최근에 성공적으로 수신된 순서대로 된 데이터에 대한 ACK만 받음.
    • 예:
      • 세그먼트 1, 2, 3, 4, 5를 보냈을 때, 세그먼트 3까지 성공적으로 수신되었으면, 수신자는 "세그먼트 3까지 잘 받았음"이라는 ACK를 보낸다.
      • 송신자는 ACK 3을 기준으로 4, 5 이후의 데이터를 전송 상태로 간주.
  • 손실 시 전체 재전송:
    • 만약 세그먼트 4가 손실되었다면, 세그먼트 4 이후의 모든 데이터를 재전송. (비효율적)
• Selective Repeat(SR)의 특징
  • 개별 ACK:
    • 수신자는 각 세그먼트마다 별도의 ACK를 보냄.
    • 예:
      • 세그먼트 1, 2, 3, 4, 5 중 세그먼트 4가 손실되었을 때, 수신자는 1, 2, 3, 5에 대해 ACK를 보낸다.
      • 송신자는 손실된 세그먼트(4)만 재전송.
  • 손실된 데이터만 재전송:
    • 개별 ACK 덕분에 손실된 데이터만 재전송 가능하며, 네트워크 리소스를 절약할 수 있음.

TCP에서의 혼합 동작

TCP는 위의 두 방식에서 효율적인 요소를 가져와 혼합하여 동작한다.

TCP의 기본 동작 (GBN 기반)

• TCP는 기본적으로 누적 ACK를 사용.
  • 수신자는 순서대로 도착한 가장 마지막 세그먼트에 대한 ACK만 송신자에게 보냄
  • 순서가 틀린 세그먼트가 도착하면, 즉시 중복 ACK(Duplicate ACK) 전송(다음에 기대하는 데이터의 순서 번호가 포함됨)

TCP의 효율화 (SR 요소 추가)

• TCP는 일부 구현에서 순서가 틀린 데이터도 임시로 저장 가능.
  • 송신자는 손실된 데이터만 재전송 → 효율 개선.

Selective Acknowledgment (SACK) 옵션

• 수신자는 누락된 데이터 외에도, 어떤 데이터가 성공적으로 수신되었는지 세부적으로 표시
• 송신자는 이 정보를 기반으로 손실된 데이터만 재전송

HTTP와 비지속적 연결

특징)

• 각 요청-응답 쌍을 개별 TCP 연결에서 처리.
• 요청된 객체를 서버가 전송한 후 연결이 종료됨.
• HTML 파일, 이미지 등 여러 객체를 다운로드하려면 객체마다 새로운 TCP 연결을 생성.

예시)

1. HTTP 클라이언트 프로세스가 서버80번 포트로 TCP 연결
2. 소켓을 통해 경로를 포함한 HTTP 요청 메시지를 서버로 전달
3. HTTP 서버 프로세스가 메시지 수신, 경로를 HTTP 응답 메시지에 캡슐화하여 클라이언트로 전송
4. 클라이언트가 응답 메시지 수신
5. TCP 연결 종료

• 만약 웹사이트가 1개의 html과 10개의 이미지로 구성되어 있다면, 총 11개의 TCP 연결 생성 → 각 TCP 연결은 한 번의 요청과 응답만 처리함.

장단점)

• 장점: 구현이 간단하며, 요청-응답이 독립적이라 연결 관리를 최소화.
• 단점:
  • 각 객체마다 새로운 TCP 연결을 설정해야 하므로 추가적인 오버헤드 발생.
  • RTT(왕복 시간)가 객체마다 2번씩 필요하므로 성능이 저하됨.
  • 서버와 클라이언트 모두에서 TCP 버퍼와 변수 관리에 부담.

HTTP와 지속적 연결

특징)

• 하나의 TCP 연결을 여러 요청-응답 쌍에서 재사용.
  • 기존 비지속적 연결에서 11개의 TCP 연결을 생성했던 것과 달리, 하나의 연결에서 연속적으로 전송(파이프라이닝).
• 연결이 일정 시간 동안 유지되며, 동일한 서버에서 여러 객체를 전송 가능.
• HTTP 1.1의 기본 설정.

장단점)

• 장점:
  • TCP 연결 설정/종료에 소요되는 오버헤드 감소.
  • 객체마다 2 RTT 대신 전체 페이지에 대해 최소 2 RTT로 처리 가능.
  • 서버와 클라이언트의 자원 사용 감소.
• 단점:
  • 장시간 연결 유지로 인해 연결 타임아웃 설정이 필요.
  • 잘못된 연결로 인해 여러 요청이 실패할 가능성.

HTTP 메시지 포맷

보통 HTTP 요청 메시지의 형식은 다음과 같다.

GET /somedir/page.html HTTP/1.1
Host: www.someschool.edu
Connection: close
User-agent: Mozilla/5.0
Accept-language: fr

요청 라인(Request Line): HTTP 요청 메시지 내 첫번째 줄

• 메서드(보통 GET), url, http 버전으로 구성돼있음.

헤더 라인(Header Lines): HTTP 요청 메시지 내 요청 라인을 제외한 나머지

Web proxy caches 때문에 꼭 필요함.

• Host: 요청 객체가 위치한 서버의 호스트 이름 지정.
• Connection: 연결 유지 여부 (예: close는 비지속적 연결 요청).
• User-agent: 요청을 보낸 브라우저 정보
• Accept-language: 사용자 선호 언어 설정

오래된 Unix 파일 시스템

장점

• 단순함.

단점

• 낮은 성능
• 디스크를 RAM처럼 사용: 데이터를 임의의 위치에 저장하여 잦은 헤드 이동 발생
• 512바이트의 작은 블록 크기
  
• 단편화: 빈 공간 관리가 효율적이지 못해 디스크 공간이 조각나고, 파일이 여러 조각으로 나뉘어 저장.

이러한 데이트 블럭 영역에서 B와 D를 삭제하면

이런 상태가 된다.

데이터가 삭제되어도 연속된 청크가 아닌 두 블럭으로 단편화되어, 후 네 블럭으로 구성된 파일 E가 들어와도

이런 형태를 유지하기에, 파일 E를 읽을 때 포인터의 위치를 변경해줘야하는 번거로움을 겪는다.

FFS의 핵심 아이디어: 디스크에 대한 이해

• 디스크의 물리적인 특성을 고려하여 파일 시스템의 성능 개선.
• 기존 오래된 Unix 파일 시스템 인터페이스와 호환성을 유지함.

FFS의 주요 개선 사항

• 실린더 그룹
  • 디스크를 실린더 그룹으로 나누어 데이터와 메타데이터를 지역적으로 저장.
  • 동일한 디렉터리에 속한 파일을 가깝게 배치하여 디스크 헤드 이동 최소화.
• 관련 데이터의 근접 배치
  • 디렉터리와 해당 파일은 동일한 실린더 그룹에 배치.
  • 관련 없는 파일은 서로 다른 실린더 그룹에 배치.
• 슈퍼블록 복제
  • 각 실린더 그룹에 슈퍼블록 복제본을 저장하여 데이터 손실 방지.
• 비트맵 사용
  • 아이노드와 데이터 블록의 할당 상태를 추적하여 단편화 감소.
• 대용량 파일 예외 처리
  • 큰 파일을 여러 그룹에 분산 저장하여 지역성 유지 및 성능 저하 완화.
• 서브 블록
  • 작은 파일을 저장할 때 4KB 블록 전체를 낭비하지 않고 필요한 만큼의 서브 블록만 할당.
• 매개화된 배치
  • 디스크의 성능 매개변수를 검출하여 최적의 배치 간격을 결정하는 매개화 기법 사용.

FFS의 성능 원칙

• 지역성
  • 관련 데이터가 디스크 상에서 물리적으로 가까운 위치에 배치되어야 성능이 향상.
  • 디렉터리 트리 상의 파일 접근 패턴을 분석하여 지역성을 확인.
• 할당 정책의 합리성
  • 디렉터리 내 파일 접근의 지역성이 실제로 높음.
  • 디렉터리와 파일 간의 물리적 근접성이 성능에 기여.

페이징, 왜 느려질까?

운영체제에서 가상 메모리를 구현하는 대표적인 방식은 페이징(Paging) 이다.

페이징: 프로세스의 주소 공간을 일정 크기(페이지 단위)로 나누어 물리 메모리에 매핑하는 기법

문제점: 매번 가상 주소 → 물리 주소 변환 시 페이지 테이블을 참조해야 하고, 그때마다 메모리를 추가로 읽게 되므로 성능 저하가 발생

예) 모든 메모리 접근(load/store)마다 ‘페이지 테이블’을 찾아봐야 한다면? CPU 성능이 아무리 좋아도 속도가 크게 느려질 수밖에 없습니다.

TLB(Translation Lookaside Buffer)의 등장

이에, 느려지는 페이징 주소 변환 문제를 해결하기 위해 등장한 것이 바로 TLB다.

• TLB: CPU 내부에 있는 작은 하드웨어 캐시
  • 자주 참조되는 ‘가상 주소 ↔ 물리 주소 변환 정보’를 저장
  • 일종의 ‘주소 변환 캐시’ 역할
• TLB 히트: 원하는 변환 정보가 TLB에 이미 있다면, 페이지 테이블을 거치지 않아도 바로 물리 주소를 얻어낼 수 있어 빠른 접근이 가능
• TLB 미스: TLB에 변환 정보가 없으면(=미스), CPU나 운영체제가 페이지 테이블을 다시 참조하고 TLB에 정보를 추가(갱신)해야 하므로 느려짐

따라서 TLB가 자주 히트할수록 주소 변환 속도가 빨라지고, 페이징의 성능이 크게 향상된다.

예시: 배열 순차 접근

1. 연속된 배열이 가상 메모리 상에서 ‘한 페이지’에 여러 원소가 담겨 있음
2. 배열의 첫 원소를 참조할 때에는 TLB 미스가 발생 → 페이지 테이블 접근 후 TLB 갱신
3. 같은 페이지 안에 있는 나머지 원소들을 계속 참조하면 TLB 히트가 연이어 발생
   • 공간 지역성(spatial locality): 배열 원소들이 페이지 내에서 인접하므로, 한 번 주소 변환 정보를 TLB에 가져오면 그 페이지 안의 다음 번지는 빠르게 접근 가능

결과적으로, 배열 전체 접근 시 처음 몇 번만 미스가 발생하고 대부분은 히트를 기록하여 성능이 크게 개선됨.

TLB 미스 처리: 하드웨어 vs 소프트웨어

TLB 미스가 발생하면 처리하는 데 크게 하드웨어와 소프트웨어(운영체제) 방식이 있다.

1. 하드웨어 관리(예: CISC, x86 등)
   • CPU 내부에서 페이지 테이블 위치를 알고 있어, 미스 발생 시 직접 페이지 테이블을 참조해 TLB를 업데이트
   • 이후 명령어를 재실행해 TLB 히트를 유도
2. 소프트웨어 관리(예: RISC 계열, MIPS 등)
   • TLB 미스가 발생하면 ‘예외(Trap)’를 발생시켜 운영체제(커널 모드) 코드가 페이지 테이블을 확인 후 TLB를 갱신
   • TLB 업데이트가 끝나면 다시 해당 명령어를 재실행하여 TLB 히트를 발생시킴

어느 방식이든 최종 결과는 같지만, 하드웨어 관리 방식은 프로세서가 직접 처리하고, 소프트웨어 관리 방식은 운영체제 트랩 핸들러가 담당한다.

문맥 교환 (Context Switch) 과 TLB

멀티프로그램 환경에서 운영체제가 문맥 교환을 할 때도 TLB 문제가 발생한다.

• 다른 프로세스로 전환되면, 이전 프로세스의 가상 주소 ↔ 물리 주소 변환 정보가 더 이상 유효하지 않을 수 있음
• 해결 방법:
  1. 문맥 전환 시 TLB를 전부 비워(모든 valid 비트를 0으로) 새 프로세스가 TLB를 새로 채우도록 함
  2. ASID(Address Space ID)를 TLB 엔트리에 추가하여, 프로세스 식별자(혹은 유사한 ID)와 매핑 정보를 함께 저장. 이렇게 하면 프로세스 간 TLB 항목을 구분할 수 있음

TLB 교체 정책

TLB도 한정된 크기의 캐시이므로, 새 항목을 넣어야 할 때 어느 항목을 제거할지 결정해야 한다.

• LRU(Least Recently Used): 가장 오래 안 쓰인 항목을 제거
• Random: 무작위로 항목을 교체 (오히려 어떤 패턴에서는 더 좋은 경우가 있음)

목표는 TLB 미스를 최소화하여 성능을 높이는 것이며, 실제 구현에서는 하드웨어 복잡성이나 응용 프로그램 특성에 따라 달라진다.

마무리

• TLB는 가상 메모리 체계를 지원하는 현대 CPU 구조에서 필수적인 장치
• 페이징의 ‘추가 메모리 접근 비용’을 억제하여 가상 메모리를 사실상 “매우 빠른” 방식으로 사용할 수 있도록 해줌
• 프로그램 특성(지역성)과 TLB 정책이 잘 맞으면 페이징 성능이 비약적으로 향상
• 하지만 한 번에 너무 많은 페이지를 건드리거나(TLB 범위를 넘는 경우), 문맥 교환이 잦으면 TLB 미스 오버헤드가 늘어나므로 주의가 필요