방송대 데이터베이스시스템 - 10강. 인덱싱
1. 인덱스의 이해
인덱스의 필요성
DBMS는 실질적으로 데이터를 디스크에 영구적으로 저장하고, 사용자가 어떤 데이터를 요청하게 되면 내부적으로 디스크와 메모리를 처리해서 그 결과를 제공함.
'COM12'의 과목명을 물어보면
- 디스크에 있는 정보가 곧바로 사용자에게 전달 (X)
- 실제 'COM12'에 대한 그 레코드가 메모리 위로 올라와야 함.
→ 이를 통해서 CPU '메모리 12'에 대한 '과목 코드 12'에 대한 '과목명'은 인터넷과 정보 사회라고 대답하는 형태의 처리 과정
데이터 양이 수천개 정도로 많아질 때,
이런 식의 처리과정은 굉장히 많은 디스크와 메모리 사이에 데이터 입출력이 동반될 수밖에 없는 그런 구조적 특징이 있음.
하나씩 입출력하는 I/O를 동반하면 성능을 악화시킴.
→ 디스크와 메모리의 I/O(입출력)를 최소화 해야함.
인덱스의 개념
데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 시작됨.
인덱스 : DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조
인덱싱 : 인덱스를 구성하고 생성하는 작업
인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재
탐색키 : 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합
인덱스의 종류
· 순서 인덱스 : 특정 값에 대해 정렬된 순서 구조
· 해시 인덱스 : 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정
인덱스의 평가기준
· 접근시간(access time) : 데이터를 찾는 데 걸리는 시간
· 유지 비용(maintenance cost) : 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
· 공간 비용(space cost) : 인덱스 구조에 의해 사용되는 부가적인 공간 비용
2. 순서 인덱스
순서 인덱스
모든 인덱스의 탐색키 값들이 순차적으로 정렬되어 있음.
탐색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스
탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통하여 인덱스 생성
ex. 영어사전 - d로 시작하는 'database'를 찾으려고 하면 'd'를 찾아서 그곳에서부터 시작해서 원하는 단어를 찾음.
순서 인덱스의 종류
| 밀집 인덱스 | 모든 레코드에 대해 탐색키 값, 포인터 쌍을 유지 · 장점 : 인덱스만으로도 레코드의 블럭 내 위치를 정확하게 찾을 수 있어서 검색 속도가 빠름. · 단점 : 많은 공간을 사용하여 비효율적임. |
| 희소 인덱스 | 인덱스의 엔트리가 일부의 탐색키 값만을 유지 찾고자 하는 탐색키보다 작거나 같은 값 중 가장 큰 값을 찾음. · 장점 : 인덱스 크기가 작아 저장 공간을 적게 차지하며 적은 저장장치 접근 횟수로도 사용할 수 있음. · 단점 : 블럭 내부에서 레코드에 대한 작은 규모의 검색을 다시 해야 함. |
| 다단계 인덱스 | 밀집 인덱스와 희소 인덱스가 결합된 구조 외부 인덱스에 대해서는 희소 인덱스, 내부 인덱스에 대해서는 밀집 인덱스 방식으로 블럭을 읽어들임. · 외부 인덱스 : 내부 인덱스를 가리키는 인덱스 엔트리의 집합 · 내부 인덱스 : 레코드를 직접 가리키는 인덱스 엔트리의 집합 |
순차 파일
테이블이 '과목코드'를 탐색키로 지정되어서 정렬됨.
순차파일들은 연속된 레코드의 접근을 빠르게 하기 위해서 각각의 레코드 끝에 다음 레코드에 위치하는 포인터를 가짐으로써 특정 레코드의 다음 레코드는 무엇인지 곧바로 빠르게 접근할 수 있는 구조를 제공하고 있음.
순서인덱스는 위와 같은 순차 파일처럼 저장된 데이터 레코드를 대상으로 만든 인덱스임.
인덱스된 순차 파일은 순차파일과 순서 인덱스로 구성됨.
· 순차파일 : 레코드 집합 전체에 대한 순차 접근을 지원하는 데 사용됨.
· 순서 인덱스 : 어느 한 특정 레코드에 대한 직접 접근을 위해 사용됨.
클러스터드 인덱스 vs 논클러스터드 인덱스
| 클러스터드 인덱스 (clustered index) |
테이블의 실제 데이터를 정렬된 형태로 저장 인덱스 키 값에 따라 데이터를 물리적으로 정렬함. 데이터의 물리적인 저장 순서와 인덱스 순서가 일치함. |
| 논클러스터드 인덱스 (non-clustered index) |
테이블의 실제 데이터를 정렬된 형태로 저장하지 않음. 인덱스 키 값과 해당 키 값에 대한 데이터의 위치를 매핑하여 인덱스를 생성함. 테이블의 레코드를 정렬된 순서로 유지하지 않기 때문에 테이블에 여러 개의 논클러스터드 인덱스를 생성할 수 있음. |
인덱스 엔트리
인덱스 엔트리 : 각각의 레코드에 대한 빠른 접근을 할 수 있는 아주 작은 형태의 어떤 별도의 레이블 또는 태그
 |
• 탐색키 값 : 인덱스 엔트리가 어떤 레코드를 대상으로 만들어졌는지 알려줌. • 포인터 - 블럭 ID : 레코드가 어느 디스크 블럭에 저장되어 있는지 가리키는 식별자 - 오프셋 : 블럭 내부에서 해당되는 레코드가 어느 정도 내부에 위치되어 있는지 그 내부에서의 위치를 가리키기 위한 것 |
 |
김영희 학생은 두번째 블럭, 즉 B2 블럭에서 오프셋이 하나의 블럭에 대해서 30바이트 뒤에 김영희 학생 레코드가 있다 |
| 밀집 인덱스 | 희소 인덱스 |
| 모든 레코드에 대해 {탐색키 값, 포인터} 쌍을 유지 | 인덱스의 엔트리가 일부의 탐색키 값만을 유지 |
 |
 |
| · 장점 : 인덱스만으로도 레코드의 블럭 내 위치를 정확하게 찾을 수 있어서 검색 속도가 빠름. · 단점 : 많은 공간을 사용하여 비효율적임. 인덱스의 엔트리가 일부의 탐색키 값만을 유지 찾고자 하는 탐색키보다 작거나 같은 값 중 가장 큰 값을 찾음. |
· 장점 : 인덱스 크기가 작아 저장 공간을 적게 차지하며 적은 저장장치 접근 횟수로도 사용할 수 있음. · 단점 : 블럭 내부에서 레코드에 대한 작은 규모의 검색을 다시 해야 함. |
다단계 인덱스
다단계 인덱스의 필요
4KB 크기의 한 블럭에 100개의 엔트리가 삽십될 때, 100,000,000 개의 레코드에 대한 순서 인덱스
1,000,000개의 블럭 = 4GB의 공간 필요
인덱스 크기에 따른 검색 성능
· 인덱스 크기 < 메모리 크기 : 디스크 I/O이 줄어 탐색 시간이 축소
· 인덱스 크기 > 메모리 크기 : 저장된 블럭을 여러번 나누어 읽어야 하기 때문에 디스크 I/O 비용이 증가하여 탐색 시간이 증가
→ 다단계 인덱스를 구성
다단계 인덱스
내부 인덱스와 외부 인덱스로 구성
외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블럭을 지칭
포인터가 가리키는 블럭을 스캔하여 원하는 레코드보다 작거나 같은 탐색키 값 중에 가장 큰 값을 가지는 레코드를 탐색
전체 인덱스 구조가 일종의 트리 형태로 만들어짐
내부 인덱스는 1,000,000개의 블럭을 갖는 반면, 외부 인덱스는 100개의 블럭만 사용하여 작은 크기의 외부 인덱스로 메모리에 적재 가능
내부 인덱스 블럭은 곧바로 이렇게 레코드가 있는 블럭에 연결시킴
외부 인덱스는 사용자의 요청이 이루어진 그 조건에 만족하는 레코드가 어디 있는지 범위적으로 알려줄 수 있음
가장 먼저 작은 양의 외부 인덱스 하나만을 메모리에 적재시켜서 처리하고 그렇게 해서 점점 범위를 구체화해감으로써 특정 레코드가 저장돼 있는 블럭을 메모리에 적재할 수 있는 힌트를 얻어내는 구조
3. B+-트리 인덱스
B+-트리의 구조
루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
이진탐색 트리를 다단계 인덱스와 결합시켜서 만들어 놓은 구조
순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
상용 DBMS에서도 널리 사용되는 대표적인 순서 인덱스
하나의 노드에 여러 개의 탐색키가 들어가고, 그 하부에는 여러 개의 자식노드를 가짐.
전체적으로 트리 형태의 구조를 가짐.
가장 큰 특징은 맨 밑에 있는 노드가 서로 가리키고 있는 연결리스트 형태로 되어 있는 것임.
B+-트리의 노드 구조
| 탐색키값 | n-1개 (K1, K2, K3, ... Kn-1) 노드 내에서 키를 찾는 데 사용되는 값 노드 내에서 탐색 키 값보다 작은 값은 왼쪽 포인터를 통해 탐색하고, 탐색 키 값보다 큰 값은 오른쪽 포인터를 통해 탐색함. 정렬된 순서로 유지되어 있음. |
| 포인터 | n개 (P1, P2, P3, ...., Pn) 포인터는 자식 노드나 레코드의 저장 위치를 가리킴. 한 노드에 저장되는 최대 포인터 개수는 B+-트리의 차수에 의해 결정됨. |
| 차수(degree) | 한 노드가 가질 수 있는 최대 자식 수 한 노드는 (차수-1)개의 탐색키값과 (차수)개의 포인터를 가짐. |
| 팬아웃(fanout) | 어떤 노드에 하위노드가 몇 개인지를 나타냄. |
| 자식 노드 | 한 노드가 가질 수 있는 자식 노드의 개수 m ⌈ 차수 / 2 ⌉ ≤ m ≤ 차수 ex. 차수 3인 B+-트리의 자식 노드 ⌈ 3 / 2 ⌉ ≤ m ≤ 3, 2 ≤ m ≤ 3 → 최소 2개 혹은 3개의 자식 노드를 가짐. |
B+-트리의 구성 요소
B+-트리는 인덱스 세트와 순차 세트 두 부분으로 구성되어 있음.
| 인덱스 세트 | 순차 세트 |
| 루트노드와 중간노드로 구성 단말노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용 - 실제 탐색키에 대한 레코드가 어디 있는지 위치정보 (X) - 그 데이터가 어디 있는지 범위를 알려줌 (O) ⌈𝑛/2⌉ ~ n 사이의 개수를 자식 노드(포인터)로 소유 (루트 노드는 ⌈𝑛/2⌉보다 적은 수의 포인터 가질 수 있음) |
단말노드로 구성 모든 노드가 순차적으로 서로 연결 단말 노드는 적어도 ⌈(𝑛-1)/2⌉개의 탐색키를 포함 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공 |
 |
 |
| 실제 레코드를 가리키는 포인터 (X) 또 다른 하위 노드를 가리키는 포인터 (O) |
포인터는 실제 디스크 내부에 어떤 블럭에 몇 번째 오프셋에 따라서 저장되는지 값을 가지고 있는 것들임 |
단말노드만이 실제 레코드를 가리키는 포인터를 제공함.
사용자가 'COM44'의 과목명은 무엇이냐고 질문을 올려서 요청함.
| 탐색 대상, 현재의 노드 : N (루트노드부터 시작) 찾고자 하는 탐색키값(예시에서는 'COM44') : V 하나의 노드에 존재하는 포인터 개수 : m |
1) B+트리에서는 루트 노드부터 값을 찾기 시작함.
'COM44'와 같거나, 이것보다 큰 것 중에서 가장 작은 값을 찾음.
'COM34'보다 크니까 오른쪽 포인터로 따라가서 자식 노드로 감.
| V보다 큰 탐색키가 없는 경우, 노드 내의 NULL이 아닌 마지막 포인터가 가리키는 노드를 N으로 결정 |
2) 'ECE24'와 'ECE31'은 모두 'COM44'보다 큰 값임.( C → E)
둘 중 더 작은 ECE24와 찾는 값인 'COM44'를 비교하는데, 찾는 값이 더 작은 값이므로 왼쪽 포인터 따라감.
| Ki > V인 경우, Pi가 가리키는 노드를 N으로 결정 |
3) 자식노드에는 'COM44'가 있으니 COM44의 왼쪽 포인터를 따라가서 실제 COM44 레코드에 접근함.
| Ki = V일 경우, 포인터 Pi+1이 가리키는 노드를 N으로 결정 |
→ B+-트리의 루트노드부터 시작하여 중간 노드에 있는 인덱스 블럭을 메모리로 올려서 요청하는 'COM44'의 위치를 찾아보고 실제로 'COM44'가 저장된 레코드 블럭을 메모리에 올려서 사용자한테 제공함.
바람직한 인덱스 구성
- 무분별하게 많은 형태의 인덱스 구성 (X)
- 자주 사용되는 탐색키값, 조건을 가지고 인덱스를 구성 (O)
B+-트리 상에서의 삽입, 삭제
레코드 삽입, 삭제 시 B+-트리 수정
| 레코드 삽입 | 노드에서 유지해야 할 탐색키와 포인터 수 증가로 인해 노드를 분할해야 하는 경우가 발생 |
| 검색과 같은 방법을 사용하여 삽입되는 레코드의 탐색키 값이 속할 단말 노드를 탐색 · 해당 단말 노드에 <탐색키, 포인터> 쌍을 삽입 · 삽입 시 탐색키가 순서를 유지 |
|
| 레코드 삭제 | 노드에서 유지해야 할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분배 또는 병합해야 하는 경우가 발생 |
| 삭제될 레코드의 탐색키를 통해 삭제될 탐색키와 포인터를 포함한 단말 노드를 탐색 · 같은 탐색키 값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말노드에서 제거 · 단말 노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동 |
|
| 높이 균형 유지 | 노드가 분할되거나 병합되면서 높이의 균형이 맞지않은 경우가 발생 |
노드가 분할되는 삽입
| 'COM24' 삽입 전 | → | 'COM24' 삽입 후 |
 |
 |
'COM12'에서 'COM24'를 찾아가려고 하니까 값이 존재하지 않음.
→ 가장 오른쪽에 있는 포인터를 따라감.
 |
삽입 대상 노드에 추가적인 저장 공간 부족: 노드 분할 · COM12를 하나의 단말 노드로 구성 · COM24와 COM31이 하나의 단말 노드로 구성 포인터를 따라 왔는데 문제는 'COM24'가 들어갈 공간이 없음. |
 |
공간이 부족해서 두 개의 노드로 분할함. COM24를 삽입함. |
 |
노드가 분할되었으므로 새롭게 생성된 노드에 대해서 가리킬 수 있는 포인터 값들도 필요함. 부모 노드에 탐색키를 조정하고, 추가된 노드에 대한 포인터를 삽입함. |
만약 부모노드에서 새로운 키값과 포인터를 추가할 공간이 없다면
→ 단말 노드에서 수행한 분할 작업을 다시 부모 노드 레벨에서 수행함.
탐색키가 재분배되지 않는 삭제
| 'COM44' 삭제 전 | → | 'COM44' 삭제 후 |
 |
 |
삭제할 레코드의 탐색키를 통해 삭제될 탐색키와 포인터를 포함하는 단말노드를 찾고, 해당 탐색키와 포인터를 삭제한다.
이때 탐색키와 탐색키에 해당하는 레코드도 같이 삭제한다.
단말 노드에서 제거된 엔트리의 오른쪽에 있는 모든 엔트리들은 빈 공간이 발생하지 않도록 왼쪽으로 이동시킨다.
위 예시에서 노드를 찾아 'COM34'를 제거하고 오른쪽에 위치한 모든 엔트리를 왼쪽으로 이동시킨다.
탐색키가 재분배되는 삭제
| 'COM12' 삭제 전 | → | 'COM12' 삭제 후 |
 |
 |
 |
 |
'COM12'가 있는 단말노드를 검색하고 탐색키를 삭제
· 해당 단말 노드는 삭제 후 탐색키가 존재하지 않음
· 노드가 공백상태를 유지하거나 ⌈ (n - 1) / 2 ⌉개보다 탐색키가 적으므로 다른 노드와 별도의 재구조화 작업이 필요
| 예시의 경우 차수가 3이라서 탐색키가 1개보다 적어지게 됨. 'COM12'를 삭제하자마자 이 노드에는 어떠한 탐색키값도 없어지게 됨. 이런 탐색키 값이 하나도 없는 노드를 B+트리가 유지할 필요가 없음. |
• 다음 이웃 단말 노드의 키를 재분배 :
다음 이웃 노드가 ⌈ (n - 1) / 2 ⌉개보다 많은 키를 가지고 있는 경우
• 다음 이웃 단말 노드와의 병함 :
키 재분배 후, 다음 이웃 노드도 ⌈ (n - 1) / 2 ⌉개보다 적은 키값을 갖게 되는 경우
| 예시의 경우 다음 이웃 노드가 2개 있는 상태에서 재분배하면 키를 1개 가지므로 재분배만 하면 됨. 만약 'COM24'와 'COM31'이 있는 노드가 'COM24'만 있었다면 병합이 필요함. COM12이 저장된 노드의 오른쪽 노드의 형제노드와 키를 재분배함. |
키에 대한 재분배가 발생하면 이 둘을 가리키는 부모노드에 대한 탐색키 재분배 또는 재수정도 동반되어야 함.
| 예시의 경우 'COM12'가 있던 노드의 부모노드의 탐색키 'COM12'를 삭제, 'COM31'을 삽입함. |
