데이터베이스 설계 6)-2 물리적 저장구조와 인덱스

 

 

 

 

 

 

 

 

 

1. B+ tree 인덱스

: 관계형 데이터베이스에서 가장 널리 사용되는 인덱스 구조이다.

 

 

 

 

1) 차수가 n인 B+tree

차수 : 한 노드에서 하위 자식 노드를 가리키는 주소의 개수이다.

 

중간 노드 구조

 

P1 ~ Pn : 자식 노드를 가리키는 포인터

Key1 ~ Keyn-1 : 검색 키

Pi+1이 가리키는 하위 노드의 모든 검색 키는 Keyi 보다 크고 Keyi+1보다 작거나 같다.

 

 

 

 

 

 

 

 

2) B+tree 의 특징(차수가 n이라고 가정)

: 단말 노드에 레코드의 주소를 저장한다.

- 레코드의 검색 키 값에 따라 인덱스 엔트리들이 정렬된 형태이다.

- 단말 노드들이 검색 키 순서에 따라 연결된다.(다음 노드의 주소를 포함)

 

: 루트 노드에서 단말 노드까지의 모든 경로의 길이가 같다. (balanced tree)

: 루트 노드는 최소 2개, 최대 n개의 자식 노드를 가진다.

: 루트와 단말 노드를 제외한 중간 노드들은 최소 [n/2] (올림기호), 최대 n개의 자식 노드를 가진다.

 

K개의 검색 키 값을 포함하는 B+tree의 높이 = [lognK]

 

 

 

 

 

3) B+tree 의 성능

: 차수가 10이고 검색 키의 값이 10,000개 이면 B+tree의 높이는 4를 넘지 않는다.

 

 

 

 

 

 

 

 

 

2. 복합 인덱스

: 두 개 이상의 필드에 대해 정의되는 인덱스이다.

 

 

- 인덱스 엔트리들은 검색키의 값은 순서대로 정렬된다.

- 효율적인 검색을 위해 B+ tree 구성이 가능하다.

 

 

 

1) 복합 인덱스 정렬 방법

: 검색 키 값이 숫자인 경우 크기로 정렬 가능하다.

: 문자열인 경우 사전식 순서에 따라 정렬한다.

: 문자열 / 숫자가 아닌 경우, 엔트리들 간에 대소 관계 정의가 필요하다.

 

 

 

 

 

 

 

 

 

 

 

2) 복합 인덱스의 효과

: 복합키 필드들에 대한 동등 조건을 포함하는 질의 처리 성능을 향상시킨다.

 

SELECT *
FROM TAKES
WHERE STU_ID = '1292001' AND CLASS_ID = 'C101-01';

 

: 복합 인덱스가 정의된 필드만을 이용하는 질의는 테이블 조회 없이 복합 인덱스 조회만으로 처리 가능하다.

 

 

 

 

 

 

3) 복합 인덱스 주의사항

: 관련 필드의 순서에 따라 인덱스의 효과가 달라진다.