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

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

- 인덱스 순차 파일의 단점 :

  파일 크기 증가 => 오버플로우 블록 증가

  오버플로우 블록은 이진 탐색이 아닌 순차 탐색 => 성능저하(재구성 필요)

- 재구성 자동 수행

- 삽입, 삭제시 성능, 공간 부담(반영 구단 적음)

- 삽입, 삭제에 대응하기 위하여 여유 공간 확보 => 트리 노드의 약 절반이 비어있을 수 있음

- 파일 변경이 많은 경우 파일 재구성 비용 피함

- 각각의 노드마다 disk하고 I/O 발생 => 헤드 움직임

- 각각의 노드는 하나의 block

- 공간 요구 (빈 공간 + 인덱스 키 값을 담을 공간)

- 루트 노드부터 모든 단말 노드들까지의 거리가 동일 : 균형 트리

- 한 곳에 치우치지 않음 => 트리의 높이가 낮음(지나가는 레벨 수(노드 수) 적어 속도 빠름)

- 트리에서 높이를 낮추는 방법(노드 수 가능한 한 줄임) => 1. 균형 2. 자식 많이 둠

- 내부 노드 키 값들 중복

- 포인터 2개 가짐(작은, 실제 레코드)

- 키의 개수 줄어듦 => 높이 높아짐 => I/O 많아짐

 

 

# B+ 트리 인덱스 특징

1. 내부 노드

- 자식 수 : [n/2] ~ n 노드 (포인터를 [n/2] ~ n 개 가짐)

- 검색키 값 수 : [(n–1)/2] ~ n–1 개

 

2. 단말노드(외부 노드)

- 데이터 레코드에 대한 포인터를 가짐

- 검색키 값 수 : [(n–1)/2] ~ n–1 개

 

3. 루트 노드

- 단말 노드가 아닌 경우 : 적어도 2개 이상의 자식 노드를 가져야 함

- 단말 노드인 경우 : 0 ~ n-1 개 검색 키를 가짐(노드 한 개 가짐. 250개)

 

 

# B+ 트리 노드 구조

P1

K1

P2

...

Pn-1

Kn-1

Pn

1. Ki : 검색키 값 (n-1개)

- 순서화 : K1 < K2 < K3 < . . . < Kn–1

 

2. Pi : 포인터 (n개)

- 비단말노드인 경우 : 자식 노드를 향한 포인터

- 단말노드인 경우 : 데이터 레코드에 대한 포인터

 

 

# 단말노드 특징 : 외부노드

- [(n–1)/2] ~ n–1 개 검색키 값

- B+ 트리 인덱스가 밀집 인덱스인 경우 : 모든 검색키 값들은 단말노드에 등장

- Pn :

  각 단말노드는 검색키 값을 기준으로 순서화

  단말노드 Li, Lj에 대하여 i < j 인 경우 Li에 있는 모든 검색키 값들은 Lj에 있는 모든 검색키 값보다 작거나 같음

- Pn은 단말 노드를 검색키 순서로 서로 연결

- 범위 검색 등에 효과적으로 사용(연속적인 처리)

 

 

# 비단말노드 특징 : 내부노드

- 단말노드 상에서 다단계 희소 인덱스 형성

- [n/2] ~ n 개의 포인터

- 팬 아웃(Fanout) : 한 노드의 포인터 수

- m개 포인터를 가지고 있는 비단말노드에 대하여

   2 <= i <= m – 1 일 때 Pi는 Ki보다 작고 Ki-1보다 크거나 같은 검색키 값을 가지는 하위 트리를 가리킴

   Pm : 맨 뒤 포인터

          Km-1 보다 크거나 같은 검색키 값을 포함하고 있는 하위 트리를 가리킴

   P1 : 맨 앞 포인터

         K1보다 작은 검색키 값을 포함하는 하위트리를 가리킴

 

 

# B+ 트리에서의 질의

- 검색 키 값 V를 가지는 모든 레코드 찾기

- V값보다 큰 검색 키 Ki를 만족하는 가장 작은 I값 찾음

- Ki == V 이면 Pi+1가 현재 노드 가리킴

- Ki > V 이면 Pi가 현재 노드 가리킴

- Ki 발견하지 못하면 V > Km-1이고 Pm은 노드에서 널이 아닌 마지막 포인터 됨

- Pm이 현재 노드 가리킴

- 단말 노드에 도달할 때 까지 반복

- V == Ki 이면 단말노드 L과 인덱스 I 반환

- V 발견 못하면 null 값 반환

- 루트부터 단말까지의 경로 길이: [logn/2(N)] (N : 레코드 수, n : 자식 수)

  => 트리가 가장 높아지는 상황, 반 정도밖에 안 채워짐

- 디스크 블록의 크기 : 4킬로바이트

- 하나의 노드는 디스크 블록과 동일한 크기

- 검색 키 크기 커질 수로 자식 수 줄어듦

 

 

# 이진트리와 B+ 트리 차이

- 이진 트리 : 각 노드는 작음. 많아야 2개의 포인터 가짐(가늘고 김)

- B+ 트리 : 각 노드는 큼. 디스크 블록 크기이면 많은 수의 포인터 가짐(굵고 짧음)

- 균형 이진트리는 경로의 길이가 [log2(N)]