[10장] 인덱스 (Index)

1. 인덱스의 개념

・튜플에 빨리 접근하기 위한 <키, 포인터> 쌍

・인덱스가 없으면 모든 데이터를 다 뒤지는 TABLE SCAN이 발생.

2. m-원 검색 트리(m-Way Search Tree)

・한 노드가 1개의 키 값과 2개의 서브 노드를 갖는 이진 검색 트리를 일반화 한 트리.

・한 노드가 최대 m-1개의 키 값과 최대 m개의 서브 노드를 갖는다.

・이진 검색 트리보다 분기율이 향상되어 트리 깊이가 낮아져 특정 노드에 대한 검색 시간이 감소한다.

・키의 삽입, 삭제 시 트리의 균형을 유지하기 위하여 복잡한 연산이 수반되어야 한다는 단점이 있음.

3. B-트리

・인덱스를 구성하는 방법으로 많이 사용되는 균형된 m-원 검색 트리이다.

・키 값과 레코드를 가리키는 포인터들이 트리 노드에 오름차순으로 저장된다.

・키의 삽입과 삭제 시 노드의 분열과 합병이 발생할 수 있다.

・차수가 m인 B-트리의 특징

― 모든 노드는 최대 m개의 서브 노드를 가진다.

― 루트(Root) 노드와 단말 노드를 제외한 모든 노드는 최소 m/2개, 최대 m개의 서브 노드를 가진다.

― 루트 노드는 단말 노드가 아닌 이상 적어도 2개의 서브 노드를 가진다.

― 단말 노드가 아닌 노드에 있는 키 값의 수는 그 노드의 서브 노드 수보다 하나 적다.

― 모든 단말 노드는 같은 레벨에 있다. (루트로부터 같은 거리에 있다.)

― 한 노드 안에 있는 키 값들은 오름차순을 유지한다.

4. B*-트리

・B*-트리는 B-트리의 문제점인 빈번한 노드의 분할을 줄이는 목적으로 제시된 B-트리의 변형이다.

・B*-트리에서는 각 노드가 가능한 한 최소 2/3가 채워지도록 한 것이 특징이다.

・차수가 m인 B*-트리의 특징

― 루트 노드를 제외한 모든 노드는 최소 (2m-2)/3개, 최대 m개의 서브 노드를 가진다.

― 루트 노드는 그 자체가 단말 노드가 아닌 경우 적어도 2개의 서브 노드를 가진다.

― 단말 노드가 아닌 노드에 있는 키 값의 수는 그 노드의 서브 노드 수 보다 하나 적다.

― 모든 단말 노드는 같은 레벨에 있다. (루트로부터 같은 거리에 있다.)

― 한 노드 안에 있는 키 값들은 오름차순을 유지한다.

5. B+-트리

・B+-트리는 B-트리의 변형으로 단말 노드가 아닌 노드로 구성된 인덱스 세트(Index Set)와 단말 노드로만 구성된 순차 세트로 구분된다.

・인덱스 세트에 있는 노드들은 단말 노드에 있는 키 값을 찾아갈 수 있는 경로만 제공되며, 순차 세트에 있는 단말 노드가 해당 데이터 레코드의 주소를 가리킨다.

・인덱스 세트에 있는 모든 키 값이 단말 노드에 다시 나타나므로 단말 노드만을 이용한 순차 처리가 가능하다.

・B+-트리에서의 직접 접근에는 인덱스 세트가 사용되고, 순차 접근에는 순차 세트가 사용된다.

・차수가 m인 B+-트리의 특징

― 루트 노드와 단말 노드를 제외한 모든 노드는 최소 m/2개, 최대 m개의 서브 노드를 가진다.

― 루트 노드는 0 또는 2에서 m개 사이의 서브 노드를 가진다.

― 단말 노드가 아닌 노드에 있는 키 값의 수는 그 노드의 서브 노드 수보다 하나 적다.

― 모든 단말 노드는 같은 레벨에 있다. (루트로부터 같은 거리에 있다.)

― 한 노드 안에 있는 키 값들은 오름차순을 유지한다.

― 순차 세트 내의 단말 노드들은 모두 링크로 연결되어 있다.