14.1 인덱스 개요 (Index)
인덱스는 "찾기"를 빠르게 해 주는 대신, "고치기"에 비용을 더한다.
핵심 용어
- Search key (탐색 키)
- 인덱스가 정렬·검색의 기준으로 삼는 하나 이상의 속성(attribute) 값. 예:
ID,salary. - Index entry (인덱스 항목)
[search-key | pointer]형태의 레코드. pointer는 실제 데이터 레코드(또는 블록)를 가리킨다.- Index file (인덱스 파일)
- 인덱스 항목들의 모음. 보통 원본 데이터 파일보다 작다(키 + 포인터만 저장).
인덱스의 두 종류
- Ordered index (정렬 인덱스)
- 탐색 키 순서로 정렬된 값을 저장. 범위 검색에 유리. 대표 구조: B+-Tree.
- Hash index (해시 인덱스)
- 해시 함수로 키를 bucket에 균등 분산. 정확히 일치하는 점 검색에 유리.
하나의 파일에 여러 인덱스를 둘 수 있다(서로 다른 search key별).
인덱스 항목(index entry) 구조
인덱스 평가 지표 (Evaluation metrics)
| 지표 | 의미 |
|---|---|
| Point query (점 질의) | key == value — 특정 값과 정확히 일치하는 레코드 검색 |
| Range query (범위 질의) | low < key < high — 어떤 범위 안의 레코드 검색 |
| Access time | 검색에 걸리는 시간 |
| Insertion time | 삽입 시간(인덱스 갱신 포함) |
| Deletion time | 삭제 시간(인덱스 갱신 포함) |
| Space overhead | 인덱스가 추가로 차지하는 공간 |
인덱스는 검색 속도를 크게 올리지만, 데이터가 바뀔 때 모든 인덱스를 함께 갱신해야 하므로 삽입/삭제/수정 부담이 커진다. 무조건 많이 만드는 것이 좋은 것은 아니다.
14.2 Ordered 인덱스 (정렬 인덱스)
파일 정렬 순서와 인덱스 키 순서가 같은가, 다른가로 갈린다.
Clustered index (= Primary index)
인덱스 키의 순서 = 데이터 파일의 정렬 순서. 파일은 한 가지 순서로만 물리적으로 정렬될 수 있으므로 테이블당 1개만 가능.
- 예: 데이터 파일이
ID순으로 정렬 →ID위의 인덱스가 clustered. - 범위 스캔이 매우 효율적(연속 블록을 순차 읽기).
Secondary index (= Non-clustered index)
인덱스 키 순서가 파일 정렬 순서와 불일치. 같은 search-key 값을 가진 모든 레코드 포인터를 모으기 위해 bucket을 경유한다.
- 예:
ID로 정렬된 파일 위에salary(40000~95000) secondary index. - 한 테이블에 여러 개 가능.
Secondary index는 파일 정렬과 순서가 다르기 때문에 일부 키만 저장하는 sparse 방식이 불가능하다. 따라서 모든 search-key 값마다 항목이 존재(dense)해야 한다.
스캔 비용 비교
| 스캔 | 비용 | 이유 |
|---|---|---|
| Clustered index 스캔 | 효율적 | 인덱스 순서대로 읽으면 데이터도 정렬되어 있어 연속 블록 순차 접근 |
| Secondary index 스캔 | 비쌈 | 인덱스 순서와 데이터 순서가 달라, HDD에서 레코드마다 다른 블록을 fetch(블록당 5~10ms) |
▶ Dense/Sparse 인덱스의 정의·트레이드오프와 Multilevel index는 바로 아래 §14.3에서 자세히 다룬다.
14.3 Dense vs Sparse 인덱스 · Multilevel 보충
"모든 키를 적느냐, 블록 대표 키만 적느냐" — 공간과 검색 속도의 맞교환.
이 절은 강의 슬라이드에 압축되어 있던 내용을 표준 교재(Silberschatz)에 맞춰 정의·트레이드오프·갱신·다단계 구성까지 완전히 보강한 것이다.
Dense index (밀집 인덱스)
파일에 등장하는 모든 search-key 값마다 인덱스 항목을 둔다. (clustered 파일에서는 각 값마다 1개, secondary 인덱스에서는 같은 값을 가진 레코드들을 bucket으로 모은다.)
- 장점: 인덱스만 보고 키 존재 여부를 즉시 판정. 데이터 블록을 더듬을 필요가 없다.
- 단점: 항목 수 = 키 수 → 인덱스가 크다(공간·갱신 부담↑).
- secondary index는 반드시 dense여야 한다(아래 핵심).
Sparse index (희소 인덱스)
일부 키에 대해서만 — 보통 각 데이터 블록의 첫(최소) 키마다 — 항목을 둔다. 데이터가 그 키 순서로 정렬되어 있어야 하므로 clustered index에서만 가능하다.
- 장점: 항목 수 = 블록 수 → 인덱스가 작다. 메모리에 올리기 쉽다.
- 단점: 찾는 키 K에 항목이 없으면, K 이하 중 가장 큰 항목으로 점프한 뒤 해당 블록을 순차 탐색해야 한다(검색이 느려질 수 있다).
그림 — 정렬 파일 위의 Dense vs Sparse
같은 정렬 데이터 파일(레코드 10, 20, 30 / 40, 50 / 60, 70, 80; 슬래시는 블록 경계)에 대해 두 인덱스를 비교한다.
Dense (모든 키)
40→■ · 50→■
60→■ · 70→■ · 80→■
항목 8개 = 키 8개. ■ = 레코드 포인터.
Sparse (블록당 첫 키)
40→[블록2: 40,50]
60→[블록3: 60,70,80]
항목 3개 = 블록 3개. 50 검색 → 40 항목으로 점프 → 블록2 안에서 50을 순차 탐색.
트레이드오프 요약
| 기준 | Dense | Sparse |
|---|---|---|
| 공간(항목 수) | 키 수 — 큼 | 블록 수 — 작음 |
| 점 검색 속도 | 빠름(인덱스만으로 판정) | 블록 내 추가 순차 탐색 |
| 갱신 비용 | 큼(모든 키 반영) | 작음(블록 대표 키만) |
| 적용 가능 | clustered + secondary | clustered만 |
Sparse index는 "블록 첫 키로 점프 → 블록 안 순차 탐색"이 성립하려면 데이터가 그 키로 정렬되어 있어야 한다. 따라서 파일 정렬과 순서가 다른 secondary index는 sparse가 될 수 없고 반드시 dense다.
Multilevel index (다단계 인덱스)
인덱스 자체가 커져 메모리에 다 들어가지 않으면, 인덱스를 디스크에 두고 검색할 때마다 인덱스 안에서 또 이진 탐색(블록마다 random I/O)을 해야 한다 — 느리다. 해결책은 인덱스 위에 다시 인덱스를 만드는 것이다.
- Inner index(1차): 데이터 파일에 대한 (보통 dense하거나 블록당 1개) 기본 인덱스. 디스크에 저장.
- Outer index(2차): inner index의 각 블록 첫 키만 모은 sparse index. 작아서 메모리에 올라간다.
(메모리) (디스크) (디스크)
인덱스가 더 커지면 outer 위에 또 한 단계를 둘 수 있다 — 즉 인덱스를 트리로 일반화한 것이다.
Multilevel index는 정적이라 삽입/삭제 시 재구성이 번거롭다. B+-Tree는 이 다단계 sparse index를 동적으로 일반화한 것이다: 내부 노드 = sparse index 계층, leaf = 가장 아래 단계, 그리고 split/coalesce로 단계 수(=높이)를 자동 조절한다. (아래 §14.4 내부 노드 설명에서 "= multi-level sparse index 역할"이라 한 이유.)
인덱스 갱신 (Index update)
삽입 Insertion
- Dense: 키가 없던 값이면 항목을 추가; 이미 있으면(중복) 포인터를 bucket에 추가.
- Sparse: 보통 새 블록이 생길 때만 항목 추가. 새 키가 어떤 블록의 새 첫 키가 되면 해당 항목 키를 갱신.
삭제 Deletion
- Dense: 그 값을 가진 레코드가 모두 사라지면 항목 제거(중복은 포인터만 제거).
- Sparse: 삭제된 키가 어떤 블록의 첫 키였다면, 그 블록의 새 첫 키로 항목을 갱신; 블록이 비면 항목 제거.
14.4 B+-Tree
모든 root→leaf 경로 길이가 같은 균형 트리. 거의 모든 RDBMS의 기본 인덱스.
B+-Tree는 balanced tree다. 즉 root에서 모든 leaf까지의 경로 길이가 동일하다. 디스크 블록 하나를 노드 하나로 매핑해 적은 디스크 접근으로 검색을 끝낸다.
노드 구조 (order n)
Leaf node (리프 노드)
- Pᵢ → key Kᵢ를 가진 레코드(또는 bucket)를 가리킴.
- 마지막 포인터 Pₙ → 다음 leaf 노드(범위 검색용 연결 리스트).
Non-leaf node (내부 노드)
= multi-level sparse index 역할
- P₁ subtree: 모든 key < K₁
- Pᵢ subtree: Kᵢ₋₁ ≤ key < Kᵢ
- Pₙ subtree: 모든 key ≥ Kₙ₋₁
• Non-root, non-leaf 노드: ⌈n/2⌉ ~ n 개의 children
• Leaf 노드: ⌈(n−1)/2⌉ ~ n−1 개의 value
• Root(non-leaf): 최소 2 children
• Root(leaf, 트리 전체가 한 노드): 0 ~ n−1 value
예제 — n = 6
n = 6이면 leaf는 3~5개 value(⌈5/2⌉=3 ~ 5), non-leaf는 3~6개 children(⌈6/2⌉=3 ~ 6), root는 최소 2 children.
| 레벨 | 노드 내용 |
|---|---|
| Root (non-leaf) | [ El Said | Mozart ] |
| Leaf 1 | [ Brandt | Califieri | Crick | Einstein ] |
| Leaf 2 | [ El Said | Gold | Katz | Kim ] |
| Leaf 3 | [ Mozart | Singh | Srinivasan | Wu ] |
트리 높이 (height) 공식
K개의 search key가 있을 때, B+-Tree의 높이(= 검색 시 최대 노드 접근 수)는 다음으로 상한이 정해진다.
height ≤ ⌈ log⌈n/2⌉(K) ⌉ = 검색 비용(최대 노드 접근 수)
성능 예제 — 왜 B+-Tree인가
노드 1개 = 블록 1개(4KB), 항목 약 40B → 노드당 약 n ≈ 100개 항목. 키 100만 개(K = 1,000,000)라면:
반면 균형 이진 탐색 트리(balanced BST)는 키 100만 개에 약 log₂(1,000,000) ≈ 20개 노드를 거쳐야 한다. BST 노드는 키 1개짜리 작은 노드여서 블록 지역성이 거의 없어 각 단계가 사실상 독립적인 random seek가 되므로, 교재 예제 기준 약 4000ms가 걸린다. B+-Tree가 약 50배 빠르다.
검색 알고리즘 — find(v)
find(v): C = root while C is not a leaf node: i = least i such that v ≤ Kᵢ # 가장 작은 i if no such i: C = last non-null pointer (Pₙ) else if v == Kᵢ: C = Pᵢ₊₁ else: C = Pᵢ # v < Kᵢ # C는 이제 leaf if some Kᵢ in C equals v: return Pᵢ # 레코드 포인터 else: return null # 없음
B+-Tree를 인덱스가 아니라 실제 레코드 저장 구조로 쓸 수도 있다(B+-tree file organization). indexed-sequential 파일과 달리, 삽입/삭제 시 전체 파일을 재구성하지 않고 작은 국소 변경(split·redistribute)으로 자동 재구성된다. 대가는 약간의 공간/부담이다.
14.5 B+-Tree 삽입 / 삭제 알고리즘 보충
분할(split)과 병합(coalesce)으로 항상 균형을 유지한다.
아래 삽입·삭제 절차는 강의 슬라이드에 명시되지 않은 표준 교재(Silberschatz) 내용으로, 시뮬레이터(위 §14.4)와 동작이 일치한다. 직접 따라 그려보거나 시뮬레이터로 검증해 보라.
삽입 Insertion
- ① leaf에 공간 있음: find(v)로 leaf를 찾아 정렬 위치에 삽입하고 끝.
- ② leaf full(키가 n개가 됨): split — n개를 둘로 나눠 첫 노드에 ⌈n/2⌉개, 둘째 노드에 나머지. 둘째 leaf의 첫 키를 부모로 copy-up하고, leaf 연결 리스트(next 포인터)를 갱신한다.
- ③ internal full: 재귀 split — 가운데 키를 부모로 push-up. leaf와 달리 올라간 키는 원래 내부 노드에서 제거된다(라우팅 키일 뿐).
- ④ root까지 전파: 새 root를 만들고 올라온 키 1개와 두 자식을 둔다 → 높이 +1.
삭제 Deletion
- ① 단순 제거: find(v)로 leaf에서 키를 지운다. underflow가 아니면 끝.
- ② underflow(value 수 <
⌈(n−1)/2⌉): 인접 형제가 여유 있으면 redistribute(빌려오기) — 한 개를 옮기고 부모 분리 키를 갱신. 여유 없으면 coalesce/merge — 두 노드를 합치고 부모에서 분리 키 제거 → 부모도 underflow면 재귀. - ③ root에 포인터 1개만 남음: root를 제거하고 그 유일한 자식을 새 root로 → 높이 −1.
Leaf split → copy-up: 분리 키가 leaf에도 남고 부모에도 복사된다(leaf는 실제 값을 모두 보관해야 하므로).
Internal split → push-up: 가운데 키는 leaf에 없는 라우팅 키이므로 위로 올라가고 원래 노드에서는 사라진다.
Worked Example — 삽입 (n = 4: 노드당 최대 3 key, leaf split 시 좌 2 / 우 2)
n = 4이면 leaf는 최대 n−1 = 3개 키. 4번째 키가 들어와 4개가 되는 순간 split(좌 ⌈4/2⌉=2, 우 2). 키 5, 13, 18, 21, 24, 2를 차례로 삽입한다.
| 단계 | 삽입 | 트리 상태 | 설명 |
|---|---|---|---|
| 1 | 5 | [5] | 빈 leaf(=root)에 삽입. |
| 2 | 13 | [5 13] | 공간 있음. |
| 3 | 18 | [5 13 18] | 3개 = 최대치, 아직 split 아님. |
| 4 | 21 | [18 21] ←root[18]→ [5 13] | leaf full → split. {5,13,18,21}을 좌[5,13]/우[18,21]로. 둘째 첫 키 18을 copy-up → 새 root[18]. 높이 1→2. |
| 5 | 24 | root[18] → [5 13] · [18 21 24] | 24는 18 이상 → 오른쪽 leaf에 삽입(공간 있음). |
| 6 | 2 | root[18] → [2 5 13] · [18 21 24] | 2는 왼쪽 leaf에 삽입(3개, 아직 full 아님). |
분할은 정확히 4번째 삽입(21)에서 한 번 발생했고, copy-up으로 새 root가 생겨 높이가 2가 되었다. (만약 6번째에 왼쪽 leaf가 이미 3개였다면 다시 leaf split이 일어나 root가 [?,18]처럼 자랐을 것이다.)
Worked Example — 삭제 (n = 4: leaf 최소 ⌈(n−1)/2⌉ = 2 key)
위 결과 트리 root[18] → 좌[2 5 13] · 우[18 21 24]에서 삭제한다.
| 단계 | 삭제 | 트리 상태 | 설명 |
|---|---|---|---|
| 1 | 24 | root[18] → [2 5 13] · [18 21] | 우 leaf에 2개 남음 = 최소치, underflow 아님. |
| 2 | 21 | root[5] → [2] · [5 13 18] | 우 leaf가 1개([18])로 underflow. 좌 형제[2,5,13]는 3개로 여유 → redistribute: 13을 빌려 우=[13,18], 부모 키 18→13... 실제 시뮬레이터 구현은 왼쪽에서 빌려와 우=[13,18], 부모[13]로 갱신. (또는 coalesce 선택 가능 — 구현 정책에 따라 다름.) |
| 3 | 13 | [2 5 18] (root=leaf) | 한쪽이 최소 미만 → 두 leaf coalesce, 부모 분리 키 제거. root에 자식 1개만 남아 root 제거, 높이 2→1. |
▶ 위 §14.4 시뮬레이터에 같은 순서로 입력하면 redistribute/coalesce 동작과 높이 감소를 눈으로 확인할 수 있다(분리 키 선택 등 세부는 구현 정책에 따라 표와 약간 다를 수 있다).
복잡도 · 중복 키 · Bulk loading
복잡도 (N개 키)
트리 높이에 비례. 각 단계는 디스크 노드 1개 접근(+ split/merge 시 형제·부모 추가 접근, 상수배).
중복 키 처리
- Unique-fy: search-key에 레코드 식별자를 덧붙여
(key, rid)로 유일화. - Bucket: 같은 키의 모든 포인터를 별도 overflow bucket(또는 포인터 리스트)에 모은다.
대량 데이터로 인덱스를 처음 만들 때 한 건씩 삽입(top-down split 반복)하면 매우 느리다. 대신 키를 먼저 정렬한 뒤 leaf를 순서대로 채워 bottom-up으로 한 번에 구성한다(bulk loading) — split이 거의 없어 빠르다. 이때 leaf를 꽉 채우지 않고 fill factor(예 2/3)만큼만 채워 두면 이후 삽입 시 split 빈도를 낮출 수 있다.
B+-Tree vs B-Tree
| 항목 | B+-Tree | B-Tree |
|---|---|---|
| 레코드 포인터 위치 | leaf에만 | 내부 노드에도 레코드 포인터 보유 |
| 키 중복 | 라우팅 키가 leaf에도 등장(중복) | 각 키 1번만 등장(중복 없음) |
| leaf 연결 | 있음(연결 리스트 → 범위 스캔 쉬움) | 없음(범위 스캔 시 트리 순회 필요) |
| 내부 노드 fan-out | 키만 저장 → 더 많은 자식 → 낮은 높이 | 포인터까지 저장 → 자식 수 적음 |
| 운 좋은 빠른 검색 | 항상 leaf까지 내려감 | 상위 노드에서 바로 찾을 수도 있음 |
정리: B-Tree는 키 중복이 없고 운 좋으면 일찍 끝나지만, 내부 노드가 무거워 fan-out이 낮고 범위 스캔이 불리하다. 디스크 DBMS는 거의 항상 B+-Tree를 쓴다.
14.6 해싱 (Hashing)
키를 해시 함수로 bucket에 흩뿌려 평균 O(1) 검색을 노린다.
Hash table: 순서 없는 연관 배열(unordered associative array). 해시 함수로 키를 offset(bucket 번호)으로 변환한다. 공간 O(n), 시간 평균 O(1) / 최악 O(n).
Static hashing (정적 해싱)
- Hash index
- bucket에 레코드를 가리키는 포인터를 저장.
- Hash file org.
- bucket에 레코드 자체를 저장.
Overflow (오버플로우)
한 bucket에 들어갈 항목이 용량을 넘으면 overflow가 발생한다.
- 원인: bucket 수 부족, 또는 skew(편중) — 같은 키가 많거나 해시가 균등하지 않아 특정 bucket에 몰림.
- Overflow chaining (= closed addressing): overflow bucket을 연결 리스트로 매단다.
- Open addressing (linear probing): overflow bucket을 쓰지 않고 다음 빈 슬롯으로 이동(probe).
버킷 용량 = 2. 가득 찬 버킷에 더 넣으면 overflow bucket이 체인으로 연결됩니다.
Put 11→b1, Put 0→b0, Put 21→b1(11,21), Put 31·41→b1 가득 → overflow bucket(31,41), Put 39→b9.
Get 51 → b1 체인 스캔(11,21,31,41) → 일치 없음 → ❌ 없음.
Static hashing의 결함
- bucket 수 N이 고정: 작으면 overflow로 성능↓, 크게 잡으면 공간 낭비.
- 데이터가 줄어도 bucket이 남아 낭비. 크기 변경하려면 전체 rehashing이 필요해 비싸다.
Dynamic hashing (동적 해싱)
Extendible hashing
여러 해시 값이 하나의 bucket을 공유하다가, 가득 차면 디렉터리 항목 수를 2배로 늘려 bucket을 분리한다. → 아래 §14.7.
Linear hashing
디렉터리 없이 bucket을 점진적으로(한 번에 하나씩) rehash하며 확장한다. 주기적 rehashing으로 부하를 분산.
14.7 Extendible Hashing (확장성 해싱) 보충
디렉터리를 2배로 늘려, rehashing 없이 동적으로 bucket을 분리한다.
강의에서는 개념만 언급된 동적 해싱을 global/local depth 규칙과 worked example까지 완전히 보강한다.
구성 요소
- Hash 함수 h(K)
- 키를 b비트(예 32비트) 값으로 변환. 그중 앞 i비트(또는 뒤 i비트)만 사용한다.
- Global depth i (전역 깊이)
- 현재 디렉터리 인덱싱에 쓰는 비트 수. 디렉터리 크기 = 2i 엔트리.
- Bucket address table (디렉터리)
- 2i개 엔트리의 배열. 각 엔트리는 bucket을 가리키는 포인터. 여러 엔트리가 같은 bucket을 공유할 수 있다.
- Local depth ij (지역 깊이)
- bucket j 안의 모든 키가 공유하는 상위 ij비트의 수. 이 bucket을 가리키는 디렉터리 엔트리 수 = 2(i − ij).
삽입 알고리즘
- h(K)의 앞 i비트로 디렉터리 엔트리를 찾고, 그 bucket에 빈자리가 있으면 삽입하고 끝.
- bucket overflow 시 두 경우로 나뉜다 — 분리할 bucket의 local depth ij와 global depth i를 비교:
- ① ij < i (디렉터리는 그대로): 이 bucket을 둘로 split, 두 새 bucket의 local depth를 ij+1로. 이 bucket을 가리키던 디렉터리 엔트리들을 새 두 bucket으로 재분배하고 키를 재배치. 디렉터리는 두 배로 늘지 않는다.
- ② ij == i (디렉터리 꽉 참): 먼저 디렉터리를 2배(global depth i +1)로 늘려 각 엔트리를 복제한 뒤, ①처럼 bucket을 split한다.
overflow 발생 시 ij < i면 bucket만 split(디렉터리 그대로), ij == i면 디렉터리 2배(i+1) 후 split. local depth가 증가한 bucket을 가리키는 디렉터리 엔트리 수는 분리될 때마다 절반이 된다.
삭제 / 축소
키 삭제 후 bucket이 비거나, 같은 local depth를 가진 형제(buddy) bucket과 합쳐도 한 bucket에 들어가면 coalesce하고 local depth를 1 줄인다. 모든 bucket의 local depth가 global depth보다 작아지면 디렉터리를 절반으로 줄여(global depth −1) 공간을 회수할 수 있다(실무에서는 자주 생략).
Worked Example — 디렉터리가 2배 되는 과정 (bucket 용량 2, 앞 i비트 사용)
처음 i=1, 디렉터리 2엔트리. 키의 해시 앞 비트를 직접 쓴다고 가정(예시용). 키를 삽입하며 변화를 추적한다.
| 단계 | 삽입(앞 비트) | i (global) | 디렉터리 → bucket | 설명 |
|---|---|---|---|---|
| 1 | A(0..), B(0..) | 1 | 0→[A,B] · 1→[ ] | bucket A에 2개(꽉 참). local depth 모두 1. |
| 2 | C(0..) | 2 | 00→[A,..] · 01→[B,C..] · 10→[ ] · 11→[ ] | overflow & ij(=1)==i(=1) → 디렉터리 2배(i=2) 후 split. 앞 2비트로 A류(00)와 B,C류(01)를 분리, 두 bucket local depth=2. |
| 3 | D(10..) | 2 | … 10→[D] … | 10 엔트리의 bucket(local depth 1, 처음 빈 것)에 삽입. 디렉터리 안 늘어남. |
| 4 | E(01..) overflow | 2 | 01 bucket split(local 1→2 …) | 이때 만약 그 bucket의 ij < i이면 bucket만 split(디렉터리 그대로). ij==i였다면 다시 디렉터리 2배(i=3). |
핵심 그림: 여러 디렉터리 엔트리(00,01)가 한 bucket을 공유하다가, 그 bucket이 넘치면 local depth를 올려 분리한다. local depth가 global depth와 같을 때만 디렉터리 전체가 2배로 커진다.
hash(key) = key의 하위 8비트, 그중 상위 i비트로 디렉터리 인덱싱. bucket이 넘치면 local depth < global depth → bucket만 split, 같으면 디렉터리 2배.
Linear hashing은 디렉터리가 없다. 대신 split pointer가 가리키는 bucket을 overflow 발생과 무관하게 순서대로 하나씩 둘로 나누며 점진적으로 확장한다. 디렉터리 메모리가 없어 가볍지만, split이 overflow와 동기화되지 않아 overflow chain이 일시적으로 길어질 수 있다. extendible은 디렉터리 한 번 참조로 정확히 해당 bucket을 찾는 대신 디렉터리 공간/2배 비용이 든다.
14.8 Bitmap Index (비트맵 인덱스) 보충
값마다 비트 벡터 하나. 여러 조건을 비트 AND/OR로 한 번에 처리한다.
분석/OLAP 질의에 강한 비트맵 인덱스를 정의·다중 조건·압축·존재 비트맵까지 보강한다.
정의
레코드가 0..N−1로 순서 번호(record number)를 갖는다고 하자. 어떤 속성의 가능한 값마다 길이 N의 비트맵을 둔다. 레코드 r이 그 값이면 비트맵의 r번째 비트 = 1, 아니면 0.
- 적합: low-cardinality(값 종류가 적은) 속성 — 성별(gender), 소득 구간(income_level), 상태 플래그 등.
- 값 종류가 많으면 비트맵 수가 너무 많아져 비효율 → B+-tree가 나음.
예시 테이블 (레코드 0~5)
데이터
| # | gender | income_level |
|---|---|---|
| 0 | m | L1 |
| 1 | f | L2 |
| 2 | f | L1 |
| 3 | m | L2 |
| 4 | m | L1 |
| 5 | f | L2 |
비트맵 (비트 순서 = 레코드 0→5)
gender = f : 0 1 1 0 0 1
income = L1: 1 0 1 0 1 0
income = L2: 0 1 0 1 0 1
다중 조건 = 비트 연산
"gender = m AND income = L1" (conjunctive selection)은 두 비트맵을 AND:
AND L1 1 0 1 0 1 0
─────────────────
= 1 0 0 0 1 0 → 레코드 #0, #4
"... OR ..." (disjunctive)는 OR, "NOT 조건"은 비트 보수(존재 비트맵과 AND). 결과 비트맵의 1인 위치가 곧 결과 레코드 번호이며, 비트 연산은 CPU 워드 단위로 매우 빠르다.
여러 selection 조건을 각 값의 비트맵을 AND(교집합)/OR(합집합) 하여 한 번에 평가한다. low-cardinality 속성의 conjunctive 질의에서 특히 강력하다.
존재 비트맵 · 압축 · 결합
- Existence bitmap: 삭제되거나 NULL인 레코드를 표시하는 비트맵. 결과를 이것과 AND 해서 삭제/널 레코드를 제외한다(NOT 연산에도 사용).
- 압축: 1이 드문 비트맵은 0이 길게 이어지므로 run-length encoding 등으로 크게 압축된다.
- B+-tree와 결합: 비트맵으로 후보 집합을 빠르게 좁힌 뒤 다른 인덱스/스캔과 조합하기도 한다.
14.9 Ordered vs Hashing 비교
"무엇을 자주 묻는가"가 인덱스 선택을 결정한다.
| 질의 유형 | Ordered (B+-Tree) | Hashing | 승자 |
|---|---|---|---|
Point query (key == v) | O(log n) 노드 접근 | 평균 O(1) | Hashing |
Range query (low<key<high) | 정렬+leaf 연결로 효율적 | 불리(순서 없음) | Ordered |
| 정렬 출력 / 최소·최대 | 지원 | 불리 | Ordered |
Point query → Hashing, Range query → Ordered(B+-Tree). 범위 질의가 흔한 실무에서는 Ordered가 선호된다.
PostgreSQL: hash index를 지원하지만 일반적으로 성능이 좋지 않다(대부분 B+-Tree 사용).
SQL Server: (디스크 인덱스로) B+-Tree만 제공한다.
14.10 LSM Tree (Log-Structured Merge Tree)
쓰기에 최적화된 구조. B+-Tree의 쓰기 약점을 해결한다.
B+-Tree는 write-intensive 워크로드에 약하다. 삽입마다 leaf 블록에 직접 쓰기(in-place)가 필요해 HDD에서는 초당 100건 미만, SSD에서도 삽입마다 page overwrite(쓰기 증폭)가 발생한다.
해결책이 LSM Tree(1996 제안, Google BigTable 2006에서 대중화)다. 쓰기를 제자리에 하지 않고(out-of-place) 누적·병합한다. RocksDB, LevelDB, Elasticsearch 등이 사용한다.
구성 요소
- MemTable
- 메모리 안의 정렬된 쓰기 버퍼. 새 쓰기는 먼저 여기에 담긴다.
- SSTable
- MemTable이 가득 차면 디스크로 flush한 Sorted String Table — 정렬·불변(immutable)·인덱스 포함.
- Levels (L0…Lₙ)
- SSTable을 레벨로 그룹화. L0는 키 범위가 겹칠 수 있고, L0 외의 각 레벨은 서로 겹치지 않는다(non-overlapping).
- Compaction
- 레벨이 임계치에 도달하면 SSTable들을 병합해 다음 레벨로 내리고, 균일한 크기를 유지한다.
읽기 경로 (Read path)
각 SSTable에 Bloom filter(확률적 자료구조)를 붙인다. "있을 수도 있음(might exist)" 또는 "확실히 없음(definitely not exist)"만 답한다. 검색 전에 먼저 물어, 키가 없는 SSTable은 읽지 않아 디스크 I/O를 크게 줄인다.
14.11 인덱스 정의 (SQL) · 실무 보충
인덱스는 표준 SQL에 없지만 모든 DBMS가 지원하는 사실상의 표준 구문이다.
인덱스 생성/삭제 구문, 복합·커버링 인덱스, 그리고 "언제 만드나"의 실무 기준을 보강한다.
기본 구문
-- 인덱스 생성 (중복 허용) CREATE INDEX idx_instructor_dept ON instructor (dept_name); -- 유일 인덱스: 중복 값 금지 (제약 + 인덱스) CREATE UNIQUE INDEX idx_student_email ON student (email); -- 복합(composite) 인덱스: 컬럼 순서가 중요 CREATE INDEX idx_takes ON takes (ID, course_id); -- 인덱스 삭제 DROP INDEX idx_instructor_dept;
복합(composite) 인덱스 — 컬럼 순서
인덱스 (A, B)는 (A로 먼저 정렬, 같으면 B로) 정렬된 것과 같다. 따라서:
WHERE A = ?또는WHERE A = ? AND B = ?→ 인덱스 사용(좌측 접두사 규칙, leftmost prefix).WHERE B = ?(A 조건 없음) → 대부분 인덱스 못 씀. A가 선행 컬럼이기 때문.- 선택도(selectivity)가 높은(=값이 다양한) 컬럼을 보통 앞에 둔다.
Covering index (커버링 인덱스)
질의가 필요로 하는 모든 컬럼이 인덱스 안에 들어 있으면, 테이블(heap) 레코드를 읽지 않고 인덱스만으로 응답한다(index-only scan). 예: (ID, course_id) 인덱스로 SELECT course_id FROM takes WHERE ID = ?를 처리.
① WHERE/JOIN/ORDER BY에 자주 쓰이고 ② 선택도가 높은(소수 행만 골라내는) 컬럼에 만든다. 단, 인덱스마다 쓰기(INSERT/UPDATE/DELETE) 비용이 증가하고 공간을 더 쓰므로 과다 생성은 금물. 거의 안 쓰이는 인덱스, 쓰기 위주 테이블의 인덱스는 오히려 손해다.
모든 인덱스는 데이터가 바뀔 때 함께 갱신되어야 한다. 인덱스가 많을수록 쓰기마다 갱신 대상이 늘어 쓰기 처리량이 떨어지고 저장 공간이 늘어난다. (§14.1 트레이드오프와 동일한 원리.)
14.12 핵심 정리
구조 제약 · 공식
- 인덱스 항목 =
[search-key | pointer], 원본보다 작다. - B+-Tree non-leaf:
⌈n/2⌉~nchildren, leaf:⌈(n−1)/2⌉~n−1values, root non-leaf ≥2 children. - 높이 =
⌈log⌈n/2⌉(K)⌉= 검색 비용. - n=100, K=1M → height 4 → 80ms (BST ≈ 4000ms).
선택 기준
- Clustered=Primary(파일 순서=인덱스 순서), Secondary=Non-clustered는 dense 필수. Sparse는 clustered 전용.
- Multilevel sparse index를 동적으로 일반화한 것이 B+-Tree.
- Point query → Hashing, Range query → Ordered(B+-Tree).
- Static hashing은 N 고정이 결함 → Dynamic: extendible(디렉터리 2배)/linear hashing.
- Low-cardinality 분석 질의 → Bitmap index(조건을 AND/OR).
- 쓰기 집중 → LSM Tree(MemTable→SSTable, compaction, Bloom filter).
① ⌈n/2⌉ children / ⌈(n−1)/2⌉ values 제약 · ② 높이 공식과 n=6 예제(leaf 3~5, non-leaf 3~6 children) · ③ Secondary index는 dense, sparse는 clustered 전용 · ④ point→hash / range→ordered · ⑤ overflow chaining(closed) vs open addressing · ⑥ B+-Tree 삽입 copy-up(leaf) vs push-up(internal) · ⑦ Extendible: ij<i면 bucket split, ij==i면 디렉터리 2배 · ⑧ Bitmap AND/OR · ⑨ B+-Tree vs B-Tree(내부 포인터·leaf 연결).