Chapter 14. Indexing

한 줄 핵심: 인덱스(index)는 책 뒤의 “찾아보기”처럼 원하는 데이터를 빨리 찾기 위한 (search-key, pointer) 보조 구조이며, 정렬 기반의 ordered index(완성형 = B⁺-tree)와 해시 함수 기반의 hash index 두 갈래로 나뉜다. B⁺-tree는 모든 leaf가 같은 깊이인 균형 트리로, $K$ 개 키에 대해 높이를 $⌈ lo g_{⌈ n /2 ⌉} (K)⌉$ 이하로 보장해 디스크 환경에서 압도적이다.

이 챕터가 답하는 핵심 질문

Q1. 인덱스란 무엇이고 어떻게 평가하는가?

Q2. Ordered index의 종류(clustering/secondary, dense/sparse, multilevel)는 어떻게 나뉘는가?

Q3. 인덱스는 삽입·삭제 때 어떻게 갱신되는가?

Q4. 왜 B⁺-tree인가, 그리고 그 정의·구조는?

Q5. B⁺-tree에서 탐색(find)은 어떻게 하고 왜 디스크에 강한가?

Q6. B⁺-tree 삽입(split)은 어떻게 동작하는가?

Q7. B⁺-tree 삭제(merge/redistribute)는 어떻게 동작하는가?

Q8. B⁺-tree로 파일 자체를 조직하면(B⁺-tree File Organization) 무엇이 다른가?

Q9. B-tree는 B⁺-tree와 무엇이 다르고 왜 덜 쓰이는가?

Q10. Hashing은 어떻게 동작하고 ordered index와 비교해 언제 쓰는가?

Q11. 복수 키(multiple-key) 질의는 어떻게 처리하는가?

Q12. 인덱스는 언제 생성되고 SQL로 어떻게 정의하는가?

Q1. 인덱스란 무엇이고 어떻게 평가하는가? ✅

A. 인덱스는 (search-key, pointer) 엔트리로 이루어진, 데이터 접근을 빠르게 하는 보조 파일이다. 책 전체를 넘기는 대신 뒤의 찾아보기에서 단어→페이지로 바로 가는 것과 같다.

Search Key(탐색 키): 파일에서 레코드를 찾을 때 기준이 되는 속성(또는 속성들). 테이블의 primary key와는 별개 개념 — “무엇으로 찾을 것인가”일 뿐.
Index file: index entry들의 모음.
- 각 엔트리는 | search-key | pointer | 형태.
- 원본 파일보다 훨씬 작다(찾아보기가 본문보다 얇음).
두 가지 기본 종류:

종류	원리
Ordered index	search key를 정렬된 순서로 저장
Hash index	search key를 hash function으로 “bucket”들에 균등 분배

"정렬된 순서로 저장" / "hash로 분배"가 정확히 무슨 뜻?
인덱스는 (search-key, pointer) 엔트리들을 담은 별도의 작은 파일이다. 두 종류는 그 엔트리들을 인덱스 파일 안에 어떻게 배치하느냐가 다르다 (원본 데이터 파일 얘기가 아님).

Ordered index — 엔트리를 키 값이 원래 가진 대소 순서대로 줄 세워 저장. 순서를 인위적으로 “부여”하는 게 아니라, 숫자면 10 < 20 < 30, 문자면 'Adams' < 'Brandt' < 'Crick' 처럼 값 자체의 크기/사전 순서를 그대로 따른다. 사전처럼 정렬돼 있으니:

특정 값 찾기(point) → 이분 탐색으로 빠름

범위 찾기(range, 예: 30~50) → 시작점만 찾으면 그 뒤로 줄줄이 읽으면 됨 ✅
Ordered index (키 순 정렬):
 [10|→][20|→][30|→][40|→][50|→] ...   ← 값 크기 순서대로
Hash index — 순서는 버린다. 대신 h(키) = 버킷 번호 를 계산해 그 버킷에 엔트리를 던져 넣는다. 찾을 땐 h(찾는 값)을 다시 계산해 해당 버킷으로 곧장 점프.

특정 값 찾기(point/등호) → 계산 한 번으로 한 방에 ✅ (보통 ordered보다 빠름)

범위 찾기 → 불가 ❌ : 11과 12처럼 인접한 값도 h가 전혀 다른 버킷으로 흩뿌리므로 “근처를 줄줄이 읽기”가 안 됨.
Hash index (h(키)=버킷):
 버킷0:[30|→]   버킷1:[11|→][51|→]   버킷2:[20|→]  ...  ← 값 크기와 무관, 흩어짐
한 줄 정리: Ordered = 사전(정렬, 범위 강함), Hash = 사물함 번호표(흩뿌림, 등호 한 방·범위 불가). (Hash는 Q9에서 자세히)

Index Evaluation Metrics(평가 기준) — 좋은 인덱스를 판단하는 5가지:

효율적으로 지원하는 접근 유형(access types): 특정 값(point query), 특정 범위(range query)
Access time(검색)
Insertion time(삽입)
Deletion time(삭제)
Space overhead(공간)

Q2. Ordered index의 종류는 어떻게 나뉘는가?

A. Ordered index에서는 index entry가 search key 값으로 정렬되어 저장되며, ① clustering vs secondary, ② dense vs sparse, ③ multilevel의 세 축으로 나뉜다.

"세 축으로 나뉜다"가 무슨 뜻?

인덱스를 분류하는 서로 독립된 질문 3개라는 뜻이다. 하나의 인덱스는 세 질문에 각각 답을 하나씩 갖는다(택일이 아니라 조합). 즉 “이 인덱스는 (clustering) + (sparse) + (2-level)” 식으로 세 좌표가 정해진다.

축 핵심 질문 (기준) 두 갈래
① clustering vs secondary 인덱스 순서 = 파일의 물리적 정렬 순서인가? 일치=clustering / 불일치=secondary
② dense vs sparse search-key 값마다 entry를 두나, 일부만 두나? 전부=dense / 일부=sparse
③ multilevel 인덱스가 너무 커서 그 위에 또 인덱스를 얹나? 1단계 / 인덱스의 인덱스(여러 단계)

예: instructor를 ID로 정렬·저장하고 ID 인덱스를 블록당 한 entry로 두면 → clustering + sparse + (작으면)1-level. 같은 파일에 salary 인덱스를 추가로 두면 정렬과 무관하므로 → secondary + dense.

축	핵심 질문 (기준)	두 갈래
① clustering vs secondary	인덱스 순서 = 파일의 물리적 정렬 순서인가?	일치=clustering / 불일치=secondary
② dense vs sparse	search-key 값마다 entry를 두나, 일부만 두나?	전부=dense / 일부=sparse
③ multilevel	인덱스가 너무 커서 그 위에 또 인덱스를 얹나?	1단계 / 인덱스의 인덱스(여러 단계)

아래 설명은 공통 예시를 사용한다. instructor 파일이 ID 기준으로 정렬되어 디스크에 저장돼 있고, 한 블록에 레코드 2개씩 들어간다고 하자.

[블록1] 10101 Srinivasan | 12121 Wu
[블록2] 15151 Mozart     | 22222 Einstein
[블록3] 32343 El Said    | 33456 Gold

① Clustering vs Secondary — “인덱스 순서가 파일의 물리적 순서와 같은가?”

핵심 질문: 인덱스가 줄 세운 순서 = 실제 파일이 디스크에 저장된 순서, 인가?

Clustering index (= primary index): 그렇다. 인덱스가 정렬한 키 순서대로 파일도 물리적으로 정렬돼 있다. 위 예시에서 ID 인덱스가 그렇다 — 인덱스도 ID 순, 파일도 ID 순. 그래서 어떤 ID를 찾으면 그 레코드와 그 다음 레코드들도 바로 옆 블록에 줄줄이 있다 → 범위 검색에 강함.
Secondary index (= nonclustering): 아니다. 파일은 ID 순으로 저장돼 있는데 salary 같은 다른 키로 인덱스를 만들면, 인덱스는 salary 순으로 정렬되지만 파일은 그 순서가 아니다. salary가 비슷한 레코드들이 디스크 여기저기 흩어져 있어, 인덱스 포인터가 블록을 이리저리 점프해야 한다.

구분	Clustering (primary)	Secondary (nonclustering)
파일 물리 순서와	일치 (예: ID 인덱스)	불일치 (예: salary 인덱스)
비유	사전: 단어 자체가 가나다순으로 책에 배치	책 뒤 찾아보기: 단어→페이지, 본문 순서와 무관
한 파일에 개수	최대 1개 (물리 순서는 하나뿐이니까)	여러 개 가능
dense/sparse	둘 다 가능	반드시 dense (이유는 ②에서)

Index-sequential file: 위 예시처럼 search key로 정렬된 순차 파일 + 그 위의 clustering index.

② Dense vs Sparse — “키 값마다 entry를 두나, 일부만 두나?”

가장 헷갈리는 축. “모든 search-key마다 entry” 는 *파일에 등장하는 각각의 키 값 하나하나에 대해 인덱스 줄(entry)을 만든다*는 뜻이다. 위 예시로 직접 보자.

Dense index — 키 값마다 한 줄 (레코드 수만큼):

10101 →(블록1 Srinivasan)
12121 →(블록1 Wu)
15151 →(블록2 Mozart)
22222 →(블록2 Einstein)
32343 →(블록3 El Said)
33456 →(블록3 Gold)

→ 파일에 ID가 6개 있으면 인덱스 줄도 6개. “모든 값마다 entry”가 바로 이것. 찾는 값이 인덱스에 항상 있으니 한 번에 포인터를 얻어 빠르다. 대신 줄이 많아 공간을 더 쓴다.

Sparse index — 블록마다 한 줄 (블록 수만큼):

10101 →(블록1)      ← 블록1의 첫(최소) ID만
15151 →(블록2)      ← 블록2의 첫 ID만
32343 →(블록3)      ← 블록3의 첫 ID만

→ 모든 값이 아니라 각 블록의 대표값(보통 첫 키) 하나씩만 둔다. 줄이 3개로 적어 공간을 아낀다.

Sparse로 22222 찾기 (인덱스에 22222가 없을 때):

22222보다 작거나 같은 값 중 가장 큰 entry = 15151 →블록2.
블록2로 가서 거기부터 순차로 읽어 22222 발견.
(사전 페이지 모서리에 “가·나·다”만 적혀 있어도, ‘나’로 점프한 뒤 눈으로 훑어 원하는 단어를 찾는 것과 같다.)

구분	Dense	Sparse
entry 개수	키 값마다 1개 (≈ 레코드 수)	블록마다 1개 (≈ 블록 수)
적용 조건	항상 가능	파일이 그 키로 정렬돼 있어야 (안 그러면 “근처 순차 탐색”이 불가)
공간	큼	작음
검색	빠름(바로 포인터)	약간 느림(점프 후 순차)

왜 secondary는 반드시 dense인가?

sparse가 성립하려면 “대표값으로 점프 → 거기서부터 순차로 훑기”가 돼야 하는데, 이건 파일이 그 키로 정렬돼 있을 때만 가능하다. secondary index는 파일이 그 키 순서가 아니므로(①), 점프해도 근처에 원하는 값들이 모여 있지 않다 → 모든 값에 entry를 둘 수밖에 없다(= dense).

③ Multilevel Index — “인덱스가 너무 커서 그 위에 또 인덱스를 얹나?”

문제: 파일이 거대하면 dense index도 덩달아 커져, 인덱스조차 메모리에 다 못 올린다. 그러면 인덱스를 뒤지는 것도 디스크 I/O가 들어 느려진다.
해결: 큰 인덱스(inner index)를 그냥 또 하나의 정렬된 파일로 보고, 그 위에 sparse index(outer index)를 한 겹 더 얹는다. outer는 inner의 블록마다 한 줄만 두면 되니 작아서 메모리에 올라간다.

outer index(작음, 메모리)   →  inner index(큼, 디스크)   →  실제 데이터 파일
  블록 대표값만                 키마다 entry                 레코드

찾기: 작은 outer를 메모리에서 보고 → inner의 어느 블록인지 알아내 그 블록만 디스크에서 읽고 → 데이터로. 디스크 접근이 확 줄어든다 (인덱스의 인덱스 = “목차의 목차”).
outer조차 크면 한 단계 더 얹어 **여러 단계(multilevel)**로. 단점: 삽입·삭제 시 모든 레벨을 갱신해야 함. (이 부담을 자동으로 푸는 게 Q4의 B⁺-tree)

Q3. 인덱스는 삽입·삭제 때 어떻게 갱신되는가?

A. 인덱스는 검색엔 큰 이득이지만 변경엔 오버헤드를 부과한다 — 레코드 삽입/삭제 시 그 릴레이션의 모든 인덱스를, 속성 수정 시 그 속성의 인덱스를 갱신해야 한다.

Deletion(삭제) — 삭제된 레코드가 그 search-key 값의 유일한 레코드였다면 인덱스에서도 그 키를 삭제:

Dense: 파일 레코드 삭제와 유사.
Sparse: 그 키의 entry가 있으면 (search-key 순) 다음 값으로 교체. 다음 값이 이미 entry를 가지면 교체 대신 삭제.

Insertion(삽입) — 삽입할 레코드의 키로 먼저 lookup:

Dense: 키가 인덱스에 없으면 삽입(순차 파일이라 공간 확보 필요, overflow block 가능).
Sparse: 블록당 한 entry 방식이면 새 블록이 생기지 않는 한 변경 불필요. 새 블록이 생기면 그 블록의 첫 키를 삽입.
Multilevel: single-level 알고리즘의 단순 확장.

Q4. 왜 B⁺-tree인가, 그리고 그 정의·구조는?

A. Indexed-sequential file은 커질수록 overflow block이 쌓여 성능이 저하되고 주기적 전체 재조직이 필요한데, B⁺-tree는 작고 국소적인 split·merge만으로 스스로 균형을 유지해 전체 재조직이 필요 없다.

B⁺-tree의 (사소한) 단점: 삽입·삭제 시 추가 오버헤드, 공간 오버헤드. 그러나 장점이 압도해 광범위하게 사용된다.

Recall) BST와의 차이

이진 탐색 트리는 삽입 순서에 따라 한쪽으로 길어질 수 있다. B⁺-tree는 모든 leaf 깊이가 같은 균형 트리이고 한 노드가 자식을 수십~수백 개 갖는(fanout 큼) 덕에 디스크에서 훨씬 얕다.

B⁺-tree 정의 (order $n$ ) — 다음을 만족하는 rooted tree:

root→leaf 모든 경로 길이가 같다(완벽한 균형).
내부 노드(root·leaf 아님): $⌈ n /2 ⌉ \sim n$ 개 자식.
leaf 노드: $⌈(n - 1) /2 ⌉ \sim n - 1$ 개 값.
특수: root가 leaf 아니면 자식 최소 2개; root가 leaf면 $0 \sim n - 1$ 개 값.

직관: “각 노드는 절반 이상 차 있어야 한다”가 트리가 헐렁해지는 것을 막는다. 예 $n = 6$ : leaf 3~~5개 값, 내부 3~~6개 자식, root 최소 2자식.

그림으로 보는 B⁺-tree 한 장 ( $n = 4$ 예시)
$n = 4$ 면 내부 노드는 포인터 최대 4·키 최대 3개, leaf는 값 최대 3개. 아래는 키 A B C D E F G H를 담은 완성된 트리 모습이다.
                   ┌─────────────┐
     (root, 내부)  │ · C · E · I·│        ← 키 = "이 값 미만은 왼쪽, 이상은 오른쪽" 칸막이
                   └─┬───┬───┬───┘
         ┌──────────┘   │   └──────────┐
         ▼              ▼               ▼
     ┌───────┐     ┌───────┐       ┌───────┐
leaf │A·B·  ·│ ──▶ │C·D·  ·│ ──▶  │E·F·G·│ ──▶ ...   ← leaf끼리 옆으로 연결(연결 리스트)
     └─┬─┬───┘     └─┬─┬───┘       └─┬─┬─┬─┘
       ▼ ▼           ▼ ▼             ▼ ▼ ▼
     실제 레코드     실제 레코드      실제 레코드
내부 노드 키 = 칸막이(길 안내판): “C 미만이면 왼쪽 자식, C~E면 가운데…” 처럼 어디로 내려갈지만 알려줄 뿐, 데이터를 직접 안 가리킨다.

leaf 키 = 진짜 데이터 위치: 모든 실제 키는 leaf에 있고, leaf의 포인터가 레코드를 가리킨다.

leaf 옆 화살표(→): 마지막 포인터 $P_{n}$ 이 다음 leaf를 가리켜 “정렬된 일렬 줄”을 만든다 → 범위 검색 시 줄줄이 읽기.

노드 구조: $P_{1} ∣ K_{1} ∣ P_{2} ∣ \dots ∣ P_{n - 1} ∣ K_{n - 1} ∣ P_{n}$ — $K_{i}$ 는 노드 안에서 정렬( $K_{1} < \dots < K_{n - 1}$ ).

Leaf 성질: $P_{i}$ 는 $K_{i}$ 값을 가진 레코드(또는 bucket)를 가리킴. leaf끼리도 전역 정렬되며, 마지막 포인터 $P_{n}$ 은 다음 leaf를 가리켜 leaf들이 연결 리스트를 이룬다 → 범위 검색·순차 스캔이 쉬움.
Non-leaf 성질: leaf 위의 multi-level sparse index. 포인터 $n$ 개 노드에서 $P_{1}$ 서브트리 < $K_{1}$ , $P_{i}$ 서브트리는 $K_{i - 1} \leq key < K_{i}$ , $P_{n}$ 서브트리 ≥ $K_{n - 1}$ . (내부 노드 = “층 안내판”, leaf = 실제 책장)
높이 보장: $K$ 개 키면 높이 ≤ $⌈ lo g_{⌈ n /2 ⌉} (K)⌉$ .

Q5. B⁺-tree에서 탐색(find)은 어떻게 하고 왜 디스크에 강한가?

A. 내부 노드에서 “V가 어느 칸막이 사이인가”를 보고 자식으로 내려가다 leaf에서 V의 존재를 확인하며, $K$ 개 키에 대해 단 $⌈ lo g_{⌈ n /2 ⌉} (K)⌉$ 번의 노드(=디스크) 접근만으로 끝난다.

function find(V)
1. C = root
2. while (C가 leaf가 아닌 동안)
   1. V ≤ K_i 인 가장 작은 i를 찾는다
   2. 그런 i가 없으면 → C = 마지막 non-null 포인터(가장 오른쪽 자식)
   3. else if (V = C.K_i) → C = P_{i+1}
   4. else (V < C.K_i)   → C = C.P_i
3. leaf 도착: 어떤 i에 대해 K_i = V 면 → C.P_i 반환
4. else → null (V 가진 레코드 없음)

같으면 오른쪽( $P_{i + 1}$ )으로 가는 이유: 내부 규칙상 $K_{i - 1} \leq key < K_{i}$ 이므로 $K_{i}$ 와 같은 값들은 $P_{i + 1}$ 서브트리에 있다.

왜 디스크에 강한가:

노드 크기 = 디스크 블록 크기(전형적으로 4 KB), entry당 40 bytes 가정 시 $n \approx 100$ .
100만 키, $n = 100$ 이면 최대 $lo g_{50} (1 0^{6}) = 4$ 개 노드만 접근하면 root→leaf 완료.
비교: 균형 이진 트리는 100만 키에 약 20개 접근( $⌈ lo g_{2} (1 0^{6})⌉$ ). 노드 접근 1회 ≈ 디스크 I/O 1회(≈20 ms) 이므로 4 vs 20의 체감 차이가 결정적.

Q6. B⁺-tree 삽입(split)은 어떻게 동작하는가?

A. find로 들어갈 leaf를 찾아 자리가 있으면 넣고, 가득 차 있으면 노드를 분할(split)해 분리 키를 부모로 올려보내며, 부모도 가득 차면 위로 전파한다 — 최악의 경우 root 분할로 트리 높이가 1 증가한다.

( $p r$ =레코드 포인터, $v$ =search-key 값)

Leaf 분할:

삽입할 것 포함 $n$ 개 쌍을 정렬해 모은다.
앞쪽 $⌈ n /2 ⌉$ 개는 원래 노드에, 나머지는 새 노드로.
새 노드 $p$ 의 최소 키 $k$ 에 대해 $(k, p)$ 를 부모에 삽입.
부모도 가득 차면 분할해 위로 전파. (최악: root 분할 → 높이 +1)

Non-leaf(내부) 분할 — 가득 찬 $N$ 에 $(k, p)$ 삽입:

$N$ 을 포인터 $n + 1$ ·키 $n$ 개 담을 영역 $M$ 으로 복사, $(k, p)$ 삽입.
$P_{1} \dots P_{⌈(n + 1) /2 ⌉}$ 를 $N$ 으로, $P_{⌈(n + 1) /2 ⌉ + 1} \dots P_{n + 1}$ 를 새 노드 $N^{'}$ 으로.
$(K_{⌈(n + 1) /2 ⌉}, N^{'})$ 을 부모에 삽입.

Leaf 분할 vs 내부 분할의 결정적 차이

Leaf: 가운데 키가 새 노드에 남으면서 그 복사본이 부모로 올라감(레코드 포인터를 잃으면 안 되므로).

내부: 가운데 키 $K_{⌈(n + 1) /2 ⌉}$ 는 부모로 올라가기만 하고 두 노드 어디에도 안 남음(내부 키는 길 안내용 칸막이일 뿐).
예: $M$ =[Califieri,Einstein,Gold,Kim] → $N$ =[Califieri,Einstein], $N^{'}$ =[Kim], Gold가 부모로 상승.

연속 삽입 종합 예시 — A E I B F J C G D H ( $n = 4$ ):

단계	삽입	결과
1	A,E,I	leaf `[A,E,I]` (root=leaf)
2	B	분할 `[A,B]`,`[E,I]`, root `[E]` 생성(높이+1)
3	F	`[E,I]`→`[E,F,I]`
4	J	분할 `[E,F]`/`[I,J]`, root `[E,I]`
5	C	`[A,B]`→`[A,B,C]`
6	G	`[E,F]`→`[E,F,G]`
7	D	분할 `[A,B]`/`[C,D]`, root `[C,E,I]`
8	H	분할 `[E,F]`/`[G,H]`, root에 G 삽입→root도 가득→root 분할 내부`[C,E]`/`[I]`, 새 root `[G]`(높이 2)

한 스텝씩 그림으로 보는 split (위 표 중 핵심 3장면)

장면 1 — 단계 2(B 삽입): 가득 찬 leaf를 쪼개 root가 처음 생김.

삽입 전:  leaf [A·E·I]  ← 꽉 참(n=4면 leaf 값 최대 3개)
B를 넣으려면 [A·B·E·I] = 4개 → 넘침! → 절반으로 split
          앞 ⌈4/2⌉=2개 / 나머지 2개

삽입 후:        ┌─────┐
               │ · E·│        ← 오른쪽 노드의 최소키 E를 부모로 "복사해 올림"
               └─┬─┬─┘
           ┌────┘ └────┐
         ▼            ▼
       [A·B·]       [E·I·]    ← E는 leaf에도 그대로 남음(레코드 포인터 필요)

장면 2 — 단계 7(D 삽입): leaf split이 부모로 키 하나 올림(부모는 아직 여유 있음).

[A·B] 가득 → C,D 들어오며 [A·B·C·D] split → [A·B]/[C·D], 최소키 C를 부모로
root [E·I] → [C·E·I] (자리 있어 그냥 삽입, 전파 끝)

장면 3 — 단계 8(H 삽입): 내부 노드까지 가득 차 root가 분할되며 높이 +1.

[E·F] split → [E·F]/[G·H], 최소키 G를 부모 root[C·E·I]에 삽입 시도
  → [C·E·G·I] = 키 4개 → 내부 노드도 넘침! → 내부 split
  내부는 가운데 키가 "올라가기만 하고 사라진다"(칸막이일 뿐):
     [C·E·G·I] → 왼쪽[C·E] / 오른쪽[I],  가운데 G가 새 root로 상승

           ┌───┐
           │·G·│          ← 새 root, 높이 2로 증가
           └┬─┬┘
       ┌───┘ └───┐
     [C·E]      [I]       ← G는 여기 어디에도 안 남음 (leaf split과의 결정적 차이!)

핵심 대비: leaf split → 가운데 키 “복사”해서 올림(아래에도 남음), 내부 split → 가운데 키 “이동”해서 올림(아래에서 사라짐).

Q7. B⁺-tree 삭제(merge/redistribute)는 어떻게 동작하는가?

A. leaf에서 엔트리를 지운 뒤 노드가 최소치 미만(underfull)이 되면 형제와 합칠 수 있으면 병합(merge), 못 합치면 형제에게서 빌려오는 재분배(redistribute)를 하며, 변경이 위로 연쇄될 수 있다 — root에 포인터가 1개만 남으면 root를 삭제해 높이가 1 감소한다.

삽입의 split과 정반대 대칭: “넘치면 쪼개고, 모자라면 합치거나 빌린다.”

합칠까(merge) vs 빌릴까(redistribute) — 한 문장 판단법
underfull 노드와 형제를 한 노드에 다 합쳐서 들어가면 → merge(합치기), 합치면 넘쳐서 안 들어가면 → redistribute(빌려오기). 즉 “둘이 합쳐 한 칸에 다 들어가나?”만 보면 된다.
[빌려오기 redistribute]  형제가 넉넉할 때 — 한 칸씩 빌려 둘 다 최소치 채움
          부모 …│Mozart│…                  부모 …│Kim│…   ← 칸막이 값도 갱신!
                ╱      ╲                          ╱    ╲
    [Gold·Katz·Kim]  [Mozart]    ──▶    [Gold·Katz]  [Kim·Mozart]
         (넉넉)      (모자람)              Kim을 오른쪽으로 빌려줌

[합치기 merge]  둘 다 빠듯할 때 — 한 칸에 몰고 빈 노드는 삭제
          부모 …│Wu│…                     부모 …(Wu 칸막이 제거)…
                ╱   ╲                              │
    [Mozart·Singh]  [Wu]      ──▶        [Mozart·Singh·Wu]   ← 부모도 줄어듦
       (빠듯)      (모자람)                빈 노드 삭제 → 부모 underfull이면 위로 연쇄
직관: 빌려오기는 부모 칸막이 값만 살짝 바꾸고 끝, 합치기는 부모에서 칸막이 하나가 통째로 빠져 부모까지 모자라질 수 있어 위로 번진다. root 자식이 1개만 남으면 root를 없애 높이가 줄어든다(split의 “root 분할로 높이+1”의 정반대).

leaf에서 $(P r, V)$ 제거.
underfull이 되면:
- Case A — 병합(merge): 형제와 합쳐 한 노드에 다 들어가면 병합. 두 노드 키를 왼쪽 노드에 몰고 다른 노드 삭제. 삭제된 노드를 가리키던 $(K_{i - 1}, P_{i})$ 를 부모에서 제거 → 부모가 underfull이면 재귀.
- Case B — 재분배(redistribute): 합쳐서 안 들어가면 형제에게서 엔트리를 빌려와 둘 다 최소치 이상으로. 부모의 해당 search-key 값을 갱신.
노드 삭제는 $⌈ n /2 ⌉$ 이상 포인터를 가진 노드를 만날 때까지 위로 연쇄(cascade).
root에 포인터 1개만 남으면 root 삭제, 유일 자식이 새 root(높이 −1).

예시 모음:

“Srinivasan” 삭제(병합→내부 연쇄): leaf [Srinivasan,Wu]→[Wu] underfull → 형제 [Mozart,Singh]과 병합 [Mozart,Singh,Wu] → 부모 underfull로 내부 레벨도 병합·재구성.
“Singh”,“Wu” 삭제(재분배=빌려오기): [Mozart,Singh,Wu]→[Mozart] underfull → 왼쪽 형제 [Gold,Katz,Kim]에서 Kim을 빌림 → [Gold,Katz]/[Kim,Mozart], 부모 키가 [Mozart]→[Kim]으로 변경.
“Gold” 삭제(병합 연쇄로 높이 감소): [Gold,Katz]→[Katz] underfull → 형제 [Kim,Mozart]와 병합. 내부 노드 병합 시 부모의 분리 키가 아래로 내려온다(pulled down): [Califieri,Einstein]+(Gold↓)+[Kim] → [Califieri,Einstein,Gold]. root에 자식 1개만 남아 root 삭제, 높이 −1.

연속 삭제 종합 예시 ( $n = 4$ , Q6의 트리에서):

삭제	처리
E	`[E,F]`→`[F]` underfull → 병합 `[C,D,F]`, 내부 `[C,E]`→`[C]`
H	`[G,H]`→`[G]` underfull → 재분배: 후속 형제 `[I,J,K]`에서 I 빌림 → `[G,I]`/`[J,K]`, 부모 키 `[I]`→`[J]`
K	`[J,K]`→`[J]` underfull → 병합 `[G,I,J]` → 내부 underfull 연쇄 → root 삭제, 높이 감소

갱신 복잡도: 엔트리 1개 삽입/삭제 비용(I/O)은 트리 높이에 비례 → 최악 $O (lo g_{⌈ n /2 ⌉} (K))$ . 실제로는 내부 노드가 버퍼 상주하고 split/merge가 드물어 대부분 leaf 하나만 건드림. 평균 점유율: 랜덤 삽입 ≈ 2/3, 정렬 삽입 ≈ 1/2.

Q8. B⁺-tree로 파일 자체를 조직하면 무엇이 다른가?

A. B⁺-tree File Organization은 leaf에 포인터 대신 실제 레코드를 저장해, 삽입·삭제·갱신이 일어나도 데이터가 계속 클러스터링(정렬·군집) 상태로 유지되게 한다.

leaf는 여전히 절반 이상 차 있어야 함. 레코드가 포인터보다 커서 leaf 저장 가능 레코드 수 < 내부 노드 포인터 수.
삽입·삭제 처리는 인덱스 엔트리의 그것과 동일.
공간 활용(space utilization) 이 중요(레코드가 공간을 많이 씀): split/merge 시 더 많은 형제를 재분배에 참여시켜 활용도를 높임. 형제 2개를 참여시키면 각 노드 최소 $⌊ 2 n /3 ⌋$ 엔트리.

Q9. B-tree는 B⁺-tree와 무엇이 다르고 왜 덜 쓰이는가?

A. B-tree는 search-key 값이 트리 전체에서 단 한 번만 등장(중복 저장 제거)하지만, 그 대가로 내부 노드마다 레코드 포인터 필드가 붙어 fan-out이 줄고 트리가 깊어진다 — 일반적으로 장점이 단점을 상회하지 못해 실무는 B⁺-tree를 쓴다.

내부 노드 키가 leaf에 다시 안 나타나므로, 내부 노드의 각 키마다 추가 포인터 $B_{i}$ (그 키의 레코드/bucket 포인터)가 필요.
노드 구조: leaf는 B⁺-tree와 동일 형태 / nonleaf는 $P_{1} ∣ B_{1} ∣ K_{1} ∣ P_{2} ∣ B_{2} ∣ K_{2} ∣ \dots ∣ P_{m}$ .

B-tree 장점	B-tree 단점
대응 B⁺-tree보다 노드 수가 적을 수 있음	전체 키 중 소수만 leaf 도달 전에 일찍 발견
leaf 도달 전에 키를 찾을 수도 있음	내부 노드가 커져 fan-out↓ → 트리가 더 깊어짐
	삽입·삭제·구현이 B⁺-tree보다 복잡·어려움

Q10. Hashing은 어떻게 동작하고 ordered index와 비교해 언제 쓰는가?

A. Hash function이 search-key를 bucket 주소로 직접 매핑해 등호 검색에 강하지만 범위 검색엔 약하다 — static hashing은 DB 크기 변화에 취약하므로 bucket 수를 동적으로 늘리는 dynamic(extendable) hashing이 등장한다.

Static Hashing

Bucket: 엔트리를 담는 저장 단위(보통 디스크 블록 1개).
Hash function $h$ : 모든 search-key 집합 $K$ → 모든 bucket 주소 집합 $B$ . 검색뿐 아니라 삽입·삭제에도 사용. (우체국 분류함 비유)
서로 다른 키가 같은 bucket에 매핑될 수 있어 → 찾을 땐 그 bucket 전체를 순차 탐색.
두 사용 형태: Hash index(bucket에 포인터 저장) vs Hash file-organization(bucket에 레코드 자체 저장).
예) instructor를 dept_name으로 해싱(bucket 8개): $h (Music) = (13 + 21 + 19 + 9 + 3) %8 = 1$ , $h (Physics) = 3$ , $h (Elec.Eng.) = 3$ → 다른 키가 같은 bucket 3에 충돌.

해시가 실제로 키를 버킷에 던져 넣는 모습
각 글자를 알파벳 번호로 바꿔 더한 뒤 %8(버킷 8개)을 한다고 하자. 계산값이 곧 들어갈 사물함(버킷) 번호다.
 dept_name      h(키) = 합 % 8     →  들어갈 버킷
 ─────────      ──────────────        ──────────
 Music          (…)%8 = 1          →  버킷 1
 History        (…)%8 = 2          →  버킷 2
 Physics        (…)%8 = 3          →  버킷 3 ┐ 두 키가
 Elec.Eng.      (…)%8 = 3          →  버킷 3 ┘ 같은 곳에 충돌(collision)!
 Finance        (…)%8 = 5          →  버킷 5

 버킷 배열:
  0 [    ]  1 [Music]  2 [History]  3 [Physics│Elec.Eng.]  4 [   ]
  5 [Finance]  6 [   ]  7 [   ]
찾기: dept_name='Physics' 조회 → h('Physics')=3 한 번 계산 → 버킷 3으로 직행 → 그 버킷 안만 훑어 일치 항목 확인. (충돌해도 한 버킷 내부만 보면 되니 보통 한 방.)

버킷이 꽉 차면: 아래 Bucket Overflow처럼 추가 버킷을 사슬로 매단다.

Overflow chaining = 사물함이 꽉 차면 보조 사물함을 매다는 것
 버킷 3 [Physics│Elec.Eng.] ──▶ overflow [Civil.Eng.│…] ──▶ overflow […]
        (꽉 참)                   (넘친 것 보관)            (또 넘치면 계속)
같은 버킷에 들어갈 키가 버킷 용량보다 많으면, 빈 다른 버킷을 찾는 게 아니라(open addressing — DB엔 부적합) 그 버킷 뒤에 overflow 버킷을 연결 리스트로 줄줄이 매단다. 단점: 사슬이 길어지면 그 버킷 검색이 “직행 한 방”이 아니라 사슬을 끝까지 따라가는 선형 탐색이 되어 느려진다 → 그래서 분포가 한쪽으로 쏠리면(skew) 해싱이 약해진다.

Bucket Overflow

원인: ① bucket 수 부족, ② 분포 skew(같은 키 값 다수 / 해시 함수가 비균등).
overflow 확률은 줄여도 없앨 수 없음 → overflow chaining: overflow bucket들을 연결 리스트로 사슬화(= closed addressing/hashing). 대안 open addressing(빈자리를 찾음)은 DB 응용에 부적합.

Static의 결함과 Dynamic Hashing

Static은 $h$ 가 고정 bucket 집합에 매핑 → 파일이 커지면 overflow 과다(성능↓), 미리 크게 잡으면 공간 낭비, 축소 시도 낭비.
주기적 재조직은 비싸고 운영을 방해 → bucket 수를 동적으로 변경 = dynamic hashing.
Extendable hashing: 어느 시점이든 해시 값의 접두사(prefix)만으로 bucket address table을 인덱싱하고, 필요해지면 테이블을 2배(doubling) 로 늘리며 넘친 bucket만 분할.

Ordered Indexing vs Hashing

고려 요소	판단
예상 쿼리 유형	등호 검색 위주 → hashing 유리. range query 흔하면 → ordered index 선호
삽입·삭제 빈도	함께 고려
평균 vs 최악 접근 시간	평균을 최적화하며 최악을 희생할 것인가

실무: PostgreSQL(hash index 지원하나 비권장), Oracle(static hash organization은 O, hash index는 X), SQL Server(B⁺-tree만).

Q11. 복수 키(multiple-key) 질의는 어떻게 처리하는가?

A. 단일 속성 인덱스 여러 개로 처리하거나(특히 포인터 집합의 교집합), 여러 속성을 묶은 composite search key 인덱스를 쓴다 — 단 composite는 lexicographic 정렬이라 “첫 속성 등호 + 둘째 범위”까지만 효율적이다.

예: select ID from instructor where dept_name="Finance" and salary=80000

단일 인덱스 전략 3가지:

dept_name 인덱스로 Finance 교수 찾고 각각 salary=80000 검사.
salary 인덱스로 80000 교수 찾고 각각 dept_name 검사.
두 인덱스로 각각 포인터 집합을 얻어 교집합(intersection).

Composite search key: 둘 이상 속성의 search key(예 (dept_name, salary)). 값은 사전식(lexicographic) 정렬 — $(a_{1}, a_{2}) < (b_{1}, b_{2})$ ⟺ $a_{1} < b_{1}$ , 또는 $a_{1} = b_{1} \land a_{2} < b_{2}$ . (John,12121)<(John,13514)<(Peter,11223). 첫 속성만으로도, 전체로도 질의 가능.

Composite index가 잘 먹히는 조건과 안 먹히는 조건

(dept_name, salary) 인덱스는 전화번호부가 (성, 이름) 순서로 정렬된 것과 같다.

dept_name='Finance' and salary between 70000 and 90000 → Finance 구간으로 들어간 뒤 salary 범위를 연속으로 읽으면 되므로 좋다.

salary between 70000 and 90000만 있음 → 첫 정렬 기준인 dept_name이 없어서 Finance, Music, Physics 구간을 모두 뒤져야 한다.

한 줄 판단: composite index는 왼쪽부터 연속으로 조건이 잡힐 때 강하다. 첫 속성을 건너뛰면 정렬의 이점을 거의 못 쓴다.

(dept_name, salary) 인덱스가 처리하는 쿼리:

where 절	처리
`dept_name="Finance" and salary=80000`	✅ 두 조건 만족 레코드만 정확히 fetch
`dept_name="Finance" and salary<80000`	✅ 효율적(첫 등호 + 둘째 범위)
`dept_name<"Finance" and balance=80000`	❌ 비효율 — 첫 조건만 맞고 둘째는 틀린 레코드 다수 fetch

직관: 사전식이라 “첫 속성 고정” 시에만 둘째 속성이 인덱스에서 연속 구간을 이룬다. 첫 속성이 범위면 둘째 값이 흩어져 인덱스가 무의미.

Q12. 인덱스는 언제 생성되고 SQL로 어떻게 정의하는가?

A. 대부분 DBMS가 primary key에 인덱스를 자동 생성하며(무결성 검사 가속), create index ... on ...으로 명시 생성할 수 있다 — 단 인덱스는 조회를 가속하는 대신 갱신에 비용을 부과한다.

Primary key 인덱스 자동 생성: 삽입마다 중복/무결성 검사가 필요한데 인덱스가 있어야 그 검사가 빠름.
일부 DBMS는 foreign key에도 인덱스 생성. 예: $t ak es ⋈ σ_{nam e =^{'} s hanka r^{'}} (s t u d e n t)$ — shankar의 ID로 takes를 찾을 때 takes의 FK(ID) 인덱스가 유용.
인덱스는 lookup을 크게 가속하지만 갱신 비용 부과 → 여러 DBMS가 워크로드 기반 index tuning assistant/wizard 제공.

create index <index-name> on <relation-name> (<attribute-list>)
create index b-index on branch(branch_name)   -- 예
drop index <index-name>                        -- 삭제

Juhyeon's Blog

탐색기

Ch14_Indexing

Chapter 14. Indexing

Q1. 인덱스란 무엇이고 어떻게 평가하는가? ✅

Q2. Ordered index의 종류는 어떻게 나뉘는가?

① Clustering vs Secondary — “인덱스 순서가 파일의 물리적 순서와 같은가?”

② Dense vs Sparse — “키 값마다 entry를 두나, 일부만 두나?”

③ Multilevel Index — “인덱스가 너무 커서 그 위에 또 인덱스를 얹나?”

Q3. 인덱스는 삽입·삭제 때 어떻게 갱신되는가?

Q4. 왜 B⁺-tree인가, 그리고 그 정의·구조는?

Q5. B⁺-tree에서 탐색(find)은 어떻게 하고 왜 디스크에 강한가?

Q6. B⁺-tree 삽입(split)은 어떻게 동작하는가?

Q7. B⁺-tree 삭제(merge/redistribute)는 어떻게 동작하는가?

Q8. B⁺-tree로 파일 자체를 조직하면 무엇이 다른가?

Q9. B-tree는 B⁺-tree와 무엇이 다르고 왜 덜 쓰이는가?

Q10. Hashing은 어떻게 동작하고 ordered index와 비교해 언제 쓰는가?

Static Hashing

Bucket Overflow

Static의 결함과 Dynamic Hashing

Ordered Indexing vs Hashing

Q11. 복수 키(multiple-key) 질의는 어떻게 처리하는가?

Q12. 인덱스는 언제 생성되고 SQL로 어떻게 정의하는가?

그래프 뷰

목차

Properties