인덱스(INDEX)
인덱스(INDEX)
- 수많은 데이터 중에서 원하는 자료를 빠르고 효율적으로 검색하기 위해서 사용하는 방법을 말한다.
- 기본적으로 데이터의 위치(주소)를 관리/기억하는 인덱스 파일(Index File)과 실제 데이터를 기억하는 데이터 파일(Data File)로 구성된다.
- 데이터를 검색할 때는 먼저 인덱스 파일에서 데이터의 주소를 찾는다. 이어서 데이터 파일에서 인덱스 파일에서 찾은 주소의 데이터를 검색하게 된다.
- 인덱스 파일(Index File)은 [키 값, 주소]의 두 가지 정보로 구성된다.
키 값 : 인덱스를 만들 때 사용된 속성의 값.
주소 : 실제로 자료가 저장된 위치.
인덱스 구조
1) B-트리(Balanced Tree)
- 검색의 효율을 높이기위해 자료의 구조를 균형 있는 트리 구조로 나타내는 방법이다.
- 하나의 노드에는 여러 개의 자료를 기억할 수 있다.
B-트리의 노드
| P1 | data1 | P2 | data2 | P3 | ... |
- 한 노드의 데이터들은 오름차순 정렬되어 있다.
- P1 : data1보다 작은 값을 갖는 하위 노드의 주소.
- P2 : data1과 data2의 중간 값을 갖는 하위 노드의 주소.
- P3 : data2보다 큰 값을 갖는 하위 노드 주소.
- B-트리의 특징
- 차수가 m일 때, 루트(Root) 노드와 리트(Leaf) 노드를 제외한 모든 노드는 최소 m/2개, 최대 m개의 서브트리를 갖는다.
즉, 한 노드에는 반절 이상의 자료가 채워져야 한다.
차수 : 노드의 가짓수.
루트 노드 : 트리에서 최상위 노드.
리프(단말) 노드 : 하위노드가 없는 노드.
- 모든 리프(단말) 노드는 같은 레벨에 있다.
- 루트 노드는 리프 노드가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
- 한 노드 안에 있는 키 값들은 오름차순으로 구성된다.
- 검색은 루트 노드에서부터 시작한다.
- 한 노드의 키 값은 반 이상 채워져 있으며, 오름차순 정렬되어 있다.
탐색 트리 : 루트 값과 비교하여 루트보다 작은 값은 좌측 서브트리로 이동하고, 루트보다 큰 값은 우측 서브트리로 이동하면서 검색하도록 만든 트리.
2) B+-트리
- B트리의 변형으로 인덱스 세트와 순차 세트로 구성된다.
- 인덱스 세트는 단말 노드를 찾기 위한 인덱스를 제공하고, 순차 세트는 단말 노드로만 구성되어 있다.
- 순차 세트의 단말 노드에는 모든 키 값이 다시 나타나도록 하여 단말 노드만으로도 순차 검색이 가능하다.
인덱스 기타 유형
1) 클러스터드 인덱스(Clustered Index)
- 테이블에서 하나의 속성을 기준으로 정렬시킨 후 테이블을 재구성하여 인덱스를 만드는 방법을 말한다.
- 테이블의 물리적 순서(실제 순서)와 인덱스 순서가 동일하다.
- 하나의 테이블에는 하나의 인덱스만 만들 수 있다.
- 일정한 범위를 가지고 찾는 경우 속도 향상에 도움이 된다.
- 삽입, 수정의 경우 변경된 내용을 인덱스에 반역하고 재정렬해야 하므로 넌 클러스터드 인덱스보다 불리하다.
2) 넌 클러스터드 인덱스(Non Clustered Index)
- 테이블을 재구성하지 않고, 데이터 주소를 이용하여 인덱스를 만들어 주소값을 이용하여 검색하는 방법이다.
- 하나의 테이블에 여러 개의 인덱스를 만들 수 있다.
- 인덱스 구조보다 다소 복잡해질 수 있다.
- 한 개의 특정 값을 찾거나, 많은 양의 데이터 중에서 작은 범위를 찾을 때 유용하다.