[Algorithm] 인덱스 구조란 무엇인가?

인덱스의 개념

인덱스는 데이터 레코드를 빠르게 접근하기 위해서 구성하는 것으로 다음과 같은 특징이 있다.

1. 인덱스는 데이터가 저장된 물리적 구조와 밀접한 관계가 있다.

2. 인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공한다.

3. 인덱스를 통해서 파일의 레코드에 대한 액세스를 빠르게 수행할 수 있다.

4. 레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소로 하는것이 효율적이다.

트라이 색인은 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조이다.

키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 떄 적합하다.

1. 가변 길이의 키 값을 효율적으로 나타낼 수 있다.

2. 삽입 및 삭제 시 노드의 분열과 병합이 없다.

3. 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수(Radix)에 의해 결정된다.

4. 키 값의 푼포를 미리 예측할 수 있다면 기억장소를 절약할 수 있다.

5. 트라이의 크기는 나타내려고 하는 키 값의 기수와 키 필드 길이에 의해 결정된다.