Ch 16. 파일 인덱싱 기법 및 B트리와 B+트리

인덱스(색인)

• 보조 접근 구조
• 검색 속도를 높여주기 위한 방법
• 두번째 접근 경로로 제공댐
• 인덱싱 필드로 레코드를 효율적으로 검색함

 

인덱스 종료

단일 단계 순서 인덱스(primary, secondary, clustering, ISAM)

다단계 인덱스(B트리, B+트리)

 

 

1. 단일 단계 순서 인덱스(Single-level ordered indexes)

Primary index(기본 인덱스) - 정렬된 키(중복X) 필드로 구성된 레코드들의 순서 파일

Clustering index - 정렬된 키가 아닌 필드로 구성된 레코드들의 순서 파일인데, nonkey이므로 중복을 허용함

그래서 파일은 primary index 혹은 clustering index 둘 중 하나임

Secondary index - 정렬되지 않은 파일, primary index에  추가적인 기능 목적으로 사용함

 

Primary Index(기본 인덱스)

두 개의 필드로 구성된 고정 길이 레코드들의 순서 파일임 <K(i), P(i)>

K(i)는 정렬된 키 필드로 primary key임

P(i)는 디스크 블록의 주소를 나타내는 포인터임

인덱스 엔트리는 각각의 데이터 블록마다 하나씩 존재함

 

한 블록에서 대표하는 레코드를 Anchor record, block anchor라고 부름(주로 첫번째 레코드)

 

모든 엔트리에 대해서 인덱스를 가지고 있으면 dense index이고, 일부 인덱스만 가지고 있으면 sparse(non-dense) index임. 그러니까 인덱스 수가 레코드 수보다 적으면 희소 인덱스임

(항상 primary index는 sparse index이고, secondary index가 dense index임)

 

sparse index

만약 찾는 값이 key라면 dense index는 K(i) <= key < K(i+1)임. 여기에 이제 secondary index를 사용하여 정확한 주소를 구하면 끝남

 

 

ex1) r = 300,000개의 레코드, B = 4,096 bytes(한 블록의 크기), R = 100bytes(레코드의 길이)

한 블록에 담을 수 있는 레코드의 개수(bfr) = 4096 / 100 (내림) = 40개 저장가능(bfr = 40)

필요한 블록의 수(b) = 300000 / 40 (올림) = 7500개의 블록이 필요(b= 7500)

이진 탐색으로 데이터 파일을 탐색시 log2(b) = log2(7500) (올림) = 13개의 블록 접근이 필요함

- 만약 primary index가 있다면?

V = 9bytes ( 키 필드의 크기)

P = 6bytes ( 포인터 필드의 크기)

R_i = (9 + 6) = 15bytes(인덱스 엔트리의 크기)

bfr_i = B/R_i(내림) = (4096 / 15) (내림) = 블록당 273개의 엔트리가 들어갈 수 있음

전체 인덱스 엔트리의 수는 블록당 1개 있으니 r_i = 7500개가 있음

전체 인덱스를 저장하는데 필요한 블록의 수 b_i = (r_i / bfr_i) (올림) = (7500 / 273) (올림) = 28블록이 필요함

★그래서 primary index로 이진 탐색을 하면 log2(28) (올림) = 5번의 접근으로 블록의 위치를 구하고, 데이터 블록을 1번 접근하므로 (5+1) = 6번의 블록 접근이 필요함

 

새로운 레코드 삽입시 순차 파일이므로 새로운 공간을 위해 레코드 전부가 움직여야하고, 기본 인덱스도 같이 움직여야함 => 너무 비효율적이라 오버플로우 파일을 사용(overflow file + linked list로 연결)

삭제시 deletion markers만 해두고 데이터 이동을 하지 않음

 

 

Clustering Index(클러스터링 인덱스)

ex) 부서 번호가 맨 앞에 나오게 employee테이블을 만들면 key값은 부서 번호인데, 부서 번호의 중복이 일어남

문제점: 블록 포인터를 잡기 어려워짐

해결: index file의 블록 포인터는 해당 key값이 처음 나오는 위치를 가리키고, 순차적으로 살펴보면 블록의 마지막은 널 포인터가 나오게 함(블록 크기를 넘게 되면 블록 포인터로 다음 블록의 위치를 가리키게함(key=3처럼))

ex2) r = 300,000개의 레코드의 수, B = 4096 bytes인 한 블록의 크기, Zipcode(1000개의 종류 = index file 엔트리 수)로 평균 300개의 레코드가 저장되어 있음

이때 index를 사용하여 블록의 평균 접근 횟수를 구하기

 

V = 5 bytes(key)

P = 6 bytes(block pointer)

로 11bytes 크기로 1000개의 인덱스 엔트리들을 가짐

그래서 bfr_i = (4096 / 11) (내림) = 376개의 엔트리를 블록에 넣을 수 있음

따라서 인덱스 블록의 개수 b_i = (r_i / bfr_i) (올림) = (1000/372) (올림) = 3개의 블록이 필요함

인덱스 파일의 이진탐색은 log2(3) (올림) = 2 블록 접근  + 한 번의 데이터 블록 접근이 일어나야하므로 총 (2 + 1)번의 블록 접근이 일어남

 

Secondary Index(보조 인덱스)

검색을 더 빨리하기 위해서 만들어줌

레코드당 하나의 엔트리가 생겨서 굉장히 많은 엔트리인 dense index임. 대신 굉장히 효율적으로 빠르게 구할 수 있음

만약 보조 인덱스가 nonkey 필드라면 중복을 허용한다는 뜻이므로 해당되는 하나의 키값에 대해 여러개의 값이 생김(그래서 중간에 하나의 파일을 더 만들어서 포인터를 가리키게 함)

 

 

ex3) r = 300,000, R = 100bytes, B = 4096 bytes, V = 9bytes, P = 6bytes

secondary index 없이 비정렬 파일을 검색하면 정렬되어 있지 않으므로 순차 탐색을 사용하여 7500 / 2 (올림) = 3750번의 블록 접근이 필요함

secindary index를 사용하여 접근

R_i = V + P = 15bytes

bfr_i = 273개의 엔트리가 한 개의 블록에 있음

★보조 인덱스의 인덱스 엔트리의 수는 레코드당 하나의 엔트리가 있으므로 r_i = r = 300,000임

b_i = (r_i / bfr_i) (올림) = 1099개의 블록이 필요함

이진 탐색을 하면 log2(b_i) (올림) = 11개의 블록 접근이 필요 + 데이터 블록에 접근해야하므로 총 (11 + 1)번 블록의 접근이 필요함

 

정리

인덱스 유형들의 특성

첫 번째 단계 인덱스 엔트리의 개수

• 기본 인덱스: 데이터 블록의 개수(앵커 파일이 무조건 있음)
• 클러스터링 인덱스: zipcode처럼 문제에 나온 데이터 블록의 개수 ★ (앵커 파일이 있을 수도 있고 없을 수도 있음)
• 보조 인덱스(key): 레코드 개수(앵커 파일이 없음)
• 보조 인덱스(nonkey) : 레코드 개수 혹은 본문에서 언급한 인덱스 필드 값들의 개수(앵커 파일 없음)

 

 

 

 

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

bfr_i = 다단계 인덱스의 분기율(fan-out) = fo(n진탐색일 때 bfr_i = n)

bfr_i만큼에 인덱스 파일을 하나씩 추가하여 속도를 더 빠르게 함

log_fo(b_i)번의 블록 접근이 필요함

13개의 레코드가 있을 때 한 데이터 블록당 4개씩 넣으면 4개의 데이터 블록이 필요함

log4(13) (올림) = 2 + 데이터 블록 접근으로 총 (2+1) = 3번의 데이터 블록 접근으로 원하는 레코드를 찾을 수 있음

 

 

ex4) r = 300,000 개의 레코드 수, R = 100bytes, B = 4096 bytes로 ex3에 있던 보조 인덱스 파일 대신 다단계 인덱스로 바꿨을 경우의 변화

bfr_i = B / R_i (내림) = 4096 / 15 (내림) = 273개의 엔트리가 하나의 블록에 들어가 있음(fo = 273)

첫번째 단계의 인덱스 블록 b1 = 1099블록

두번째 단계의 인덱스 블록 b2 = (b1 / fo) (올림) = 5블록

세번째 단계의 인덱스 블록 b3 = (b2 / fo) (올림) = 1블록

이제 더 이상 최상위 인덱스 단계를 만들 수 없으므로 인덱스 (단계의 수) + (데이터 블록 접근) = 3 + 1 = 4개의 블록 접근을 통해 원하는 레코드를 얻을 수 있음

 

 

 

 

3. B 트리

트리의 모양이 한쪽으로 쏠릴 수 있는데, 한쪽으로 쏠릴 수 없게 계속 밸런스를 맞춰주는 트리를 B트리라고 부름

 

트리 모양의 구조는 트리노드 포인터(다음 트리로 넘어가는 포인터), 데이터 포인터(바로 데이터로 접근하는 포인터), 널 트리 포인터(아무것도 없다는 뜻)

 

차수가 p인 B-트리의 특성

• 루트와 리프를 제외한 노드의 서브트리 수는 : p/2(올림) <= 개수 <= p (적어도 노드의 반은 채워야함)
• 루트의 서브트리의 수 > 2 (루트 노드부터 분기)
• 모든 리프는 같은 레벨에 속해있음(균형트리)
• 키값의 수
  • 리프 : p/2 (이상) - 1에서 p-1까지의 사이에 존재(노드내의 키 수)
  • 리프가 아닌 노드: 서브트리수 - 1
• 한 노드 내의 키 값은 오름차순으로 정렬(p-원 탐색트리)

 

B-트리의 연산

• 직접 탐색 - 키 값에 의존한 분기
• 순차 탐색 - 중위 순회
• 삽입, 삭제 - 트리의 균형 유지
  • 분할 : 높이 증가
  • 합병 : 높이 감소

 

 

B 트리의 검색

• 블록 내에서는 순차 탐색을 함
• 검색 방식은 쉬우니까 생략

B 트리의 삽입

• 리프노드에서 삽입이 일어남
• 그래서 리프노드에 빈공간이 있으면 바로 삽입
• 빈공간이 없으면(overflow) 분할(split)을 해줌
  •  p/2 (올림) 번째의 키 값을 부모 노드로 이동
  • 나머지 키 값들은 반씩 나눔

B 트리의 삭제

• 삭제 키가 리프 노드가 아닌 곳에 있을 경우, 후행 키 값(오른쪽 서브트리의 가장 왼쪽)과 자리 교환 후 리프 노드에서 삭제
  • 후행키가 아닌 선행키로도 바꿀 수 있음
• 삭제할 때 리프 노드에서 언더플로(underflow)가 발생하면
  • 언더플로 조건: 키의 수 < (p/2) 올림 - 1
  • 재분배 또는 합병

재분배 - 최소 키 수 이상을 포함한 형제 노드에서 이동(형제 노드의 키 -> 부모노드 -> 언더플로 노드)

합병 - 재분배가 불가능할 떄(형제 노드 + 부모 노드의 키 + 언더플로 노드 -> 하나의 노드)

 

키 값은 tree pointer - 1개가 존재

ex5) nonordering key field, B-tree p=23, 69% full

각 노드의 평균 포인터 접근은 p * 0.69 = 23 * 0.69 = 16pointers가 존재

따라서 평균 fan-out fo = 16

 

 

 

4. B+ 트리

데이터 포인터가 리프노드에만 저장됨(중간 노드는 분기만 해주는 구조)

그래서 리프노드까지 가야함

 

B+ 트리의 구조

• 인덱스 세트 - 내부 노드, 리프에 있는 키에 대한 경로 정보만 제공
• 순차 세트 - 리프 노드, 모든 키 값들을 포함, 순차 세트는 순차적으로 연결 -> 직접 또는 순차 접근, 내부 노드와 다른 구조
• 리프노드엔 다음 리프 노드를 가리키는 연결리스트로 구성되어 있음

분기가 있으면 X <= K_i 혹은 K_i-1 < X <= K_i 혹은 X > K_i를 뜻함

 

B+ 트리의 특성

• 루트의 서브트리: 0, 2, (p/2) (올림) ~ p
• 노드의 서브트리(루프, 리프 제외): (p/2) (올림) ~ p
• 모든 리프는 동일 레벨
• 리프가 아닌 노드의 킷값 수: 서브트리 - 1
• 리프노드: 데이터 파일의 순차세트(리스트로 연결)

 

B+ 트리의 연산

• 탐색
  • B+트리의 인덱스세트(=p원 탐색트리)
  • 리프 노드에서 검색
• 삽입
  • B-트리와 유사
  • 오버플로우시 분열 -> 부모노드, 분열노드 모두에 키 값 존재
• 삽입
  • 리프에서만 삭제(재분배, 합병  없는 경우)
  • 합병: 인덱스의 키 값도 삭제
  • 재분배: 트리 구조 유지