데이터베이스 파일에 대한 인덱스 구조
데이터베이스에서 데이터를 보다 더 효과적으로 찾기 위해 사용하는 인덱스 구조에 대해 알아보겠습니다.
인덱스(Index)란?
: 데이터베이스 테이블에서 데이터 검색을 빠르게 하기 위해 사용하는 자료구조
책의 목차와 비슷하다고 생각하면 된다. 즉, 원하는 페이지(레코드)를 바로 찾아갈 수 있다.
1. 인덱스 파일 - 접근 경로(Access Path)
단일 단계 인덱스란, 데이터 파일 내의 레코드를 효과적으로 찾도록 도와주는 보조 파일을 말한다.
- 인덱스는 보통 파일 내의 한 필드에 대해 정의된다. (여러 필드에 대해서도 ok)
- 인덱스는 <필드값, 레코드에 대한 키값 주소>로 구성된 엔트리들을 저장한 파일이다.
- 인덱스는 파일에 대한 접근 경로(access path)라고 불린다. (파일을 찾으러 가는 경로)
- 인덱스 엔트리는 실제 레코드 크기보다 훨씬 작기 때문에, 인덱스 파일은 데이터 파일보다 훨씬 적은 디스크 블록을 차지한다.
- 인덱스에 대한 이진 탐색으로 (original)데이터 파일의 해당 레코드에 대한 주소를 얻을 수 있다.
- 인덱스는 밀집 또는 희소 인덱스가 될 수 있다.
- 밀집 인덱스(dense): 데이터 파일 내의 모든 탐색 키 값(즉, 모든 레코드)에 대한 인덱스 엔트리를 갖는 index
- => 모든 것이 키, 주소, 키, 주소 다 있는 것
- 희소(비밀집, sparse) 인덱스: 탐색 값의 일부에 대해서만 인덱스 엔트리를 갖는 index
- 밀집 인덱스(dense): 데이터 파일 내의 모든 탐색 키 값(즉, 모든 레코드)에 대한 인덱스 엔트리를 갖는 index
!! 데이터파일과 인덱스 파일은 완전히 별개로 다른 곳에 존재한다!!
키를 찾은 다음, 거기에 주소가 있어야 데이터 파일로 이동 가능
⭐️ Q. 특정 레코드를 찾기 위해 평균적으로 몇 개의 디스크 블록을 읽어야 하는가?
1) 한 블럭당 몇 개의 레코드를 저장할 수 있는지 구하기
• 블럭인수(Blocking Factor, Bfr) = 블록 크기 / 한 레코드의 길이 = Bfr 레코드/블럭
2) 파일의 블럭 수 구하기
• 레코드 개수 / 블럭인수 = b : Bfr개를 다 집어 넣으려면 블럭 b개 필요
[SSN 필드에 대해 인덱스를 사용하는 경우]
필드 크기 V, 레코드 포인터 크기 P
인덱스 엔트리 크기 R = (V + P)
인덱스 블럭킹 인수 Bfr = B / R
인덱스 블록 수 b = r / Bfr (인덱스 구축에 필요한 총 블록)
- 이진 탐색 시 접근할 블록 수: log₂b
- 평균 선형 탐색 비용: b/2
인덱스 파일을 이용하는 경우, 데이터 파일에 접근하기 위해 읽어야 하는 디스크 블록의 개수를 구하려면
인덱스 파일에 접근하기 위해 읽는 블록 수 + 데이터 파일 접근 횟수(1)
로 구해야 한다.
2. 단일 단계 인덱스(One-Level Index)의 3가지 유형
⭐️ 1) 기본 인덱스 (Primary Index)
- 정렬된 순서파일의 기본 키(Primary Key)에 대해 정의할 수 있는 인덱스
- Primary Key에 대한 인덱스
- 이 데이터 파일은 키 필드 순으로 정렬돼 있어야 한다.
- 인덱스의 각 엔트리는 하나의 블록을 대표하는 "앵커 레코드"의 키 값을 가지고 있다.
- 데이터 파일의 각 블록에 대해 하나의 엔트리를 가지며, 블록 앵커라 불리는 각 블록의 첫번째 레코드에 대한 키 필드 값을 엔트리로 갖는다.
- 각 블록의 마지막 레코드를 블록 앵커로 사용하는 방식을 이용할 수도 있다.
- 전체 탐색 값이 아니라 데이터 파일의 각 블록에 대해 하나의 엔트리(즉, 블록의 앵커 레코드에 대한 키값)을 가지므로, 기본 인덱스는 비밀집(희소) 인덱스(sparse index)이다.
📌 핵심 특징
| 항목 | 설명 |
| 대상 필드 | Primary Key |
| 정렬 여부 | 정렬된 순서 파일만 가능 |
| 인덱스 밀도 | 희소 인덱스 (block 단위로 하나씩) |
| 엔트리 내용 | 각 블록의 첫(또는 마지막) 레코드 키 + 블록 포인터 |
📚 쉬운 비유
- 도서관의 책장이 번호 순으로 정리돼 있고, 각 구역의 첫 번째 책 이름만 인덱스로 적어 둔 목록
2) 클러스터링 인덱스 (클러스터형 인덱스, Clustered Index)
- 정렬된 순서 파일이지만, 인덱싱 대상은 키가 아닌 필드 (즉, 중복값이 허용되는 속성)
- Primary key가 아닌 속성에 대한 인덱스 => 중복값 가짐
- 순서 파일에 대해 정의할 수 있다. (키가 아니어도 정렬되어 있으면 순서파일에 대해 정의 가능)
- 데이터 파일은 각 레코드에 대해 구별된 값을 갖지 않는 필드(즉, 키가 아닌 필드)에 따라 정렬된다.
- 클러스터링 필드의 각 고유값마다 첫 번째 레코드의 위치를 저장한다.
- 해당 필드에 올 수 있는 각 값의 종류별(each distinct value)로 하나의 인덱스 엔트리를 포함하여, 이 엔트리에는 그 필드 값을 가진 레코드들이 저장된 첫번째 블록에 대한 주소를 포함한다.
- 클러스터링 인덱스는 삽입과 삭제가 상대적으로 간단한 희소 인덱스의 한 예이다.
- 같은 필드 값을 가진 레코드들이 물리적으로 가까운 위치에 모여 있게 저장된다.
- 같은 필드값을 갖는 레코드들의 각 그룹을 위해, 별도의 블록 클러스터를 가지는 클러스터링 인덱스도 있다. 이것은 물리적으로 구분시켜놓는 방법으로, direct로 접근해서 원하는 값만 모든 값을 한 번에 가져올 수 있다.
📌 핵심 특징
| 항목 | 설명 |
| 대상 필드 | 키가 아닌 속성 |
| 정렬 여부 | 정렬된 순서파일 필요 |
| 인덱스 밀도 | 희소 인덱스 |
| 엔트리 내용 | 필드값 + 해당 값을 가진 첫 레코드의 포인터 |
📚 쉬운 비유
- 음식 코너에서 "과일", "채소", "육류" 순서로 정렬되어 있고, 각 항목의 첫 위치만 알려주는 목록
3) 보조 인덱스 (Secondary Index, 역인덱스 포함)
보조 인덱스는 기존 인덱스 외에 추가되는 인덱스라는 뜻으로, 기본 인덱스가 이미 존재하는 파일을 접근하는 보조 수단이다.
- 정렬되지 않은 필드에 대해 인덱스를 정의한다.
- 보조 인덱스는 모든 레코드에 대해 인덱스 엔트리를 가진다. → 밀집 인덱스(dense index)
- ex. 10개의 속성이 있다면, 10개 모두에 인덱스를 다 걸 수 있음. → 인덱스 파일이 데이터 파일 크기의 2배가 됨
- 중복 허용/불허 모두 가능
- 보조 인덱스는 두 개의 필드로 구성된 순서 파일이다.
- 1) 첫번째 필드: 인덱스 필드인 데이터 파일의 비순서 필드와 같은 데이터타입
- 2) 두번째 필드: 블록 포인터 or 레코드 포인터. 같은 파일에 여러 개의 보조 인덱스가 존재 가능
- (블록은 로지컬 단위이기 때문에 훨씬 가볍다.)
📌 핵심 특징
| 항목 | 설명 |
| 대상 필드 | 후보키, 일반 속성 등 |
| 정렬 여부 | 정렬 불필요 |
| 인덱스 밀도 | 밀집 인덱스 |
| 엔트리 내용 | 필드값 + 레코드 포인터 |
📚 쉬운 비유
- 친구 목록이 이름순이 아닌데, 이름별로 정리한 별도 검색 노트를 만드는 것
[ 정리 ]
| 인덱스 종류 | 밀집/희소 | 특징 |
| 기본 인덱스 | 희소 | - 기본키에 대한 인덱스(중복값X) - 순서파일 |
| 클러스터링 인덱스 | 희소 | - 기본키가 아니어도 괜찮음(중복값OK) - 순서파일 |
| 보조 인덱스 | 밀집 | - 이미 인덱스가 있는 파일에 접근하는 보조수단 - 중복이든 아니든 모든 속성에 대해 만들 수 있음. |
Q1. 다음 설명에 해당하는 인덱스의 종류는?
정렬된 순서파일에 대해, 기본 키가 아닌 중복값을 가질 수 있는 필드를 기준으로 정의된 인덱스. 해당 필드 값마다 레코드의 첫 번째 위치만 저장한다.
① 기본 인덱스
② 클러스터링 인덱스
③ 보조 인덱스
④ 역인덱스
정답: ② 클러스터링 인덱스
Q2. 보조 인덱스가 밀집 인덱스인 이유를 설명하시오.
답변 예시:
보조 인덱스는 정렬되지 않은 파일에 대해 정의되며, 특정 필드 값으로 원하는 레코드를 바로 찾기 위해 모든 레코드에 대해 인덱스 엔트리를 만들어야 하므로 밀집 인덱스이다.
3. 다단계 인덱스 (Multilevel Index)
단일 인덱스는 한 단계 인덱스인데 순서파일이므로, 인덱스 파일도 커지면 그 인덱스 파일에 인덱스를 또 만들 수 있다.
이처럼 인덱스를 인덱싱한 구조가 다단계 인덱스이다.
이 경우, 원래 인덱스 파일은 '첫번째 단계 인덱스'라 부르고, 그 인덱스에 대한 인덱스는 '두번째 단계 인덱스'라 부른다.
위와 같은 과정을 반복하면 모든 상위로 갈수록 요약 정보를 담게 된다.
최종적으로 엔트리를 한 블록에 저장할 수 있는 단계가 생기고, 이 단계의 블록을 최상위 단계 블록이라고 한다.
- 인덱스 계층 구조의 최상단은 보통 한 블록에 모두 저장 가능할 때까지 올라간다.
- 다단계 인덱스는 첫번째 단계 인덱스가 어떤 인덱스 유형이든지 사용할 수 있다.
- 구조적으로 탐색 트리(Search Tree) 형태를 갖는다.
- 탐색 트리의 한 노드는 서브 트리에 대한 포인터를 갖는다.
- 이 노드들은 key들 사이의 크기를 비교하여 탐색을 위한 포인터를 선택한다.
🧐 왜 필요할까?
단일 인덱스도 커지면 탐색이 느려진다.
따라서 "인덱스를 위한 인덱스"를 도입하여, 탐색 성능을 대폭 향상시키기 위함이다.
단점
인덱스의 모든 단계가 순서파일이기 때문에,
새로운 인덱스 엔트리에 대한 삽입과 삭제가 매우 복잡하다는 문제점이 있다. (정렬 유지 필요, 비효율적)
그래서 등장한 것이 B-트리, B+트리
B+: 가이드만. 블럭에 대한 포인터가 밑(리프노드)에 있다.
4. B-트리 & B+트리 (동적 다단계 인덱스)
- 삽입과 삭제 문제 때문에, 대부분의 다단계 인덱스는 B-tree나 B+tree 자료 구조를 사용한다.
- → 각 트리 노드(디스크 블록)에 새로운 인덱스 엔트리를 저장할 약간의 여유 공간을 남겨둔다.
- 새로운 탐색 키의 삽입과 삭제를 효율적으로 처리할 수 있는, 탐색 트리의 변형이다.
- B-tree와 B+tree 자료 구조에서, 각 노드는, 노드별로 하나의 디스크 블록(disk block)을 할당받아 저장한다. (할당받았다고 가정하고 저장함)
- “각 노드가 최소한 절반 이상 차 있다고 보장하는 방식”이므로, 디스크 저장 효율을 높일 수 있는 방식이다.
- [삽입] 어떤 노드에 key가 완전히 차 있지 않은 여유 있는 노드에 새로운 key를 삽입하는 건 간단
- 노드가 완전치 차 있으면, → 먼저 두 노드로 분할(divide) → 삽입
- 노드 분할은 트리의 레벨 변화(propagation)를 일으킬 수 있다.
- [삭제] 삭제 후에도 key가 아직 절반 이상 차 있는 노드는 간단하게 처리될 수 있다.
- 삭제 시 노드에서 key가 노드의 절반 이하로 차게 되면, 이 노드를 이웃 노드들과 합병해야 함.
- 삽입은 divide&propagation, 삭제는 merge&merge
📌 공통 특징
| 항목 | 설명 |
| 목적 | 삽입/삭제가 효율적인 다단계 인덱스 구조 |
| 구조 | 탐색 트리 계열, 균형 잡힌 트리 |
| 노드 저장 단위 | 각 노드는 디스크 블록 단위 |
| 디스크 효율 | 각 노드가 최소 절반 이상 차 있어야 함 |
| 핵심 연산 | 삽입 = divide & propagation, 삭제 = merge & merge |
⭐️B-트리와 B+트리의 차이점
🔹 B-트리 (Balanced Tree)
- 모든 노드(내부 노드 포함)가 데이터 포인터를 갖는다.
- 탐색 도중 내부 노드에서 바로 레코드로 접근 가능.
📚 비유
- 지하철 노선도에서 환승역에서도 목적지로 직접 가는 출구가 있음.
🔸 B+트리 (B Plus Tree)
- 내부 노드는 검색 가이드 역할만 함 (데이터 없음)
- 리프 노드에만 실제 데이터 포인터 존재
- 리프 노드들끼리 연결 리스트처럼 연결되어 있어서 범위 탐색에 매우 효율적
- 대응하는 B-트리보다 더 적은 레벨을 갖는다.
📚 비유
- 지하철 노선도에서 환승역은 방향만 알려주고, 실제 출구는 마지막역에만 있음
- 출구들(리프 노드들)이 쭉 연결되어 있어서 정렬된 순서로 방문 가능
📌 B-트리 vs B+트리 요약
| 항목 | B-트리 | B+트리 |
| 데이터 위치 | 모든 노드에 존재 가능 | 리프 노드에만 존재 |
| 탐색 성능 | 트리 높이 작지만 범위 탐색은 비효율 | 범위 탐색 효율적 |
| 리프노드 연결 | 없음 | 연결되어 있음 (Linked List) |
| 디스크 접근 | 상대적 비효율 | 디스크 트랙과 잘 맞아 현실적 |
B+ 트리 구조
- q-1개의 탐색 값을 갖는 내부 노드(Internal Node)(메인메모리에)
- q-1의 탐색값과 q-1의 데이터 포인터를 가지는 B+트리의 리프 노드(하드디스크에)
- 키가 중복돼서 있고 포인터가 있다. linear함.
- B+트리는 현존하는 가장 좋은 트리이다. 디스크의 트랙을 그대로 따라갈 수 있는 가장 현실적인 트리이기 때문.
- 리프노드에만 데이터 포인터가 있는 것이 특징이다.
- 하드디스크에 넣을 수 있다는 특징
- 리프노드들은 연결되어 있다.
| 구조 | 특징 | 삽입 | 삭제 |
| B- Tree | - 모든 단계의 노드들이 레코드 포인터를 가짐 | 간단. 노드가 완전히 차 있으면 노드 분할해서 중간 값을 위로 올리고 삽입 (노드 분할은 레벨 변화 일으킬 수 O) |
간단. 삭제 시 노드에서 key가 노드의 절반 이하로 차게 되면, 이 노드를 이웃 노드들과 합병 |
| B+ Tree | - 리프 노드들만 레코드 포인터를 가짐 - 리프노드들끼리 연결되어 있음(선형으로). - 하드디스크에 넣을 수 있음. - B-트리보다 더 적은 레벨 |
✅ 연습문제
Q1. 다음 중 다단계 인덱스의 특징으로 옳지 않은 것은? (객관식)
① 상위 단계 인덱스일수록 요약 정보를 담는다.
② 다단계 인덱스는 탐색 트리의 형태를 갖는다.
③ 삽입과 삭제가 간단하다.
④ 모든 단계가 순서파일이다.
정답: ③ 삽입과 삭제가 간단하다 ❌ (복잡하다!)
Q2. B+트리에 대한 설명으로 옳은 것을 모두 고르시오. (객관식, 복수 선택)
A. 리프 노드에만 실제 데이터에 대한 포인터가 존재한다.
B. 내부 노드는 탐색 가이드 역할만 한다.
C. 범위 질의(RANGE QUERY)에 비효율적이다.
D. 리프 노드들은 서로 연결되어 있다.
정답: ✅ A, B, D
Q3. (서술형) B-트리보다 B+트리가 인덱스로 더 많이 사용되는 이유를 서술하시오.
예시 답변
B+트리는 리프 노드에만 데이터 포인터가 존재하고, 리프 노드가 서로 연결되어 있기 때문에 범위 탐색이 효율적이다. 또한, 내부 노드는 검색 경로 가이드 역할만 하므로 구조가 단순하고 디스크 접근에 적합하다. 따라서 대용량 데이터를 다루는 인덱스에 많이 사용된다.
4. 다중 키 인덱스
- 속성들의 어떤 조합이 자주 사용되는 경우
- 이런 속성들의 조합으로 key를 만들어 index를 구축하면 효율적인 데이터 접근 가능
- 좋은 접근 경로를 구축한 것으로 성능상 유용함 (복합적으로 데이터를 찾아낼 수 O)
- 다중 속성에 대한, 순서화 된 인덱스
- 인덱스가 <A1, A2, …, An>의 속성에서 생성되었다면 탐색키 값은 n개의 키 값 <V1, V2, …, Vn>을 갖는다.
- 상기 키 값(value)은 사전적 순서를 갖는다. (사전적 순서를 이용하는 경우가 많음.)
그리드파일
- EMPLOYEE 파일을 격자 파일(X, Y 행렬 같은)로 구성. 이것 자체가 인덱스
- 이 방법은 선형 눈금을 따라, 여러 값의 그룹에 대응되는, 셀들의 집합으로 사상되는 “범위 질의(Range Query)”에 특히 유용하다.
[장점]
- 다중 키 접근에 걸리는 시간을 줄일 수 있는 효율적인 방법 (영역으로 인덱스를 만들어놔서)
[단점]
- 그리드 배열 구조를 위해 많은 공간을 필요로 함
- 동적 파일에서는 파일을 자주 재조직해야 하므로 유지보수 비용이 많이 증가함.
마무리
| 인덱스 종류 | 밀집/희소 | 특징 |
| 기본 인덱스 | 희소 | - 기본키에 대한 인덱스(중복값X) - 순서파일 |
| 클러스터링 인덱스 | 희소 | - 기본키가 아니어도 괜찮음(중복값OK) - 순서파일 |
| 보조 인덱스 | 밀집 | - 이미 인덱스가 있는 파일에 접근하는 보조수단 - 중복이든 아니든 모든 속성에 대해 만들 수 있음. |
| 구조 | 특징 | 삽입 | 삭제 |
| B- Tree | - 모든 단계의 노드들이 레코드 포인터를 가짐 | 간단. 노드가 완전히 차 있으면 노드 분할해서 중간 값을 위로 올리고 삽입 (노드 분할은 레벨 변화 일으킬 수 O) |
간단. 삭제 시 노드에서 key가 노드의 절반 이하로 차게 되면, 이 노드를 이웃 노드들과 합병 |
| B+ Tree | - 리프 노드들만 레코드 포인터를 가짐 - 리프노드들끼리 연결되어 있음(선형으로). - 하드디스크에 넣을 수 있음. - B-트리보다 더 적은 레벨 |