데이터(레코드)들은 블록 단위로 디스크에 저장되어 있다. 블록 채 찾아와 buffer에 놓고 필요한 데이터를 꺼내 사용한다.
이 블록들은 인덱스(접근 경로)가 있는데, 블록와 인덱스의 정보를 저장해놓는 인덱스 파일이 존재한다.
(레코드들 중 대표하는 값과 해당 블록의 주소 쌍으로 지정)
무순서, 순서, 해시 화일에서 데이터를 찾을 때, 순서키, 해시키 등을 이용하는데 데이터를 더 빨리 찾기 위해서 해당 주소를 이용한다. 주소와 해당 값을 담고 있는 것을 인덱스(접근 경로)라고 한다. (인덱스 화일로 관리한다)
인덱스 종류
-
단일 단계 인덱스 : 선형 형태로 되어있다. 이진 탐색 가능
-
기본 인덱스 :
- 기본키를 기준으로 정렬된 순서 파일의 인덱스
- 블록당 하나의 데이터에 대해서만 엔트리를 가지면 된다.
- 인덱스가 듬성듬성하므로 희소 인덱스라고 부른다.
-
클러스터링 인덱스 :
- 기본키가 아닌 필드를 기준으로 정렬된 파일의 인덱스이다.
- 인덱스 당 맡고 있는 데이터가 하나 이상이다.
- 인덱스로 여러 데이터를 한번에 불러올 수 있다.
- 데이터 파일은 실제로 인덱스가 같은 것끼리 블록으로 묶여있고, 블록이 모자라면 연결 리스트로 새로운 블록과 연결시켜 놓았다.
-
보조 인덱스 :
-
기본 인덱스나 클러스터링 인덱스를 이미 가지고 있고, 추가로 보조적으로 사용하는 인덱스
-
비순서 파일에서
-
키를 보조 인덱스로 할 때 :
- 모든 레코드에 대해서 보조 인덱스를 가지고 있어야 한다.
- 인덱스당 하나의 레코드를 맡고 있다.
- 밀집 인덱스가 된다. -
키가 아닌(중복된 값) 것이 보조 인덱스일 때 :
- 한 인덱스가 가리키는 데이터가 여러군데 퍼져있기 때문에 인덱스 파일과 데이터 파일의 중간 다리 역할을 하는 "posting file"을 둔다.
-
-
-
( * 기본 인덱스와 클러스터링 인덱스를 모두 클러스터링 인덱스로 부르는 교재도 있다)
-
다단계 인덱스 : 인덱스의 인덱스 파일을 계속 만들어 탐색 트리 형태를 이루는 것
-
B-트리와 그것을 확장한 B+-트리가 있다
-
인덱스 파일이 커질 경우, 더 빨리 찾기위해 인덱스의 인덱스를 둘 수 있다.
-
기존 인덱스는 기본키처럼 유일한 값을 가지고 있기 때문에 "기본 인덱스"의 형식과 똑같은 인덱스 파일이 된다.
-
각 노드는 하나의 블록을 가리킨다.
-
장점 1 : 블록당 50% 이상의 저장 공간을 사용하게 함으로서 저장 공간의 낭비를 줄인다.
-
장점 2 : 모든 leaf node가 같은 레벨에 위치하게 하고 삽입할 때는 데이터를 위로 올림으로서 균형이 맞게한다.
-
B+-트리 :
- 일반 B-트리는 범위탐색이 어렵기 때문에 이를 확장한 B+-트리를 사용한다.
- leaf node에 모든 데이터가 다 들어가게 하고, 그 윗 계층부터는 B-트리 형태로 포인터를 만든다.
- leaf node는 순차적으로 연결 리스트로 이어져 있어 범위 탐색에 유용하다.
- B+-트리의 B-트리에는 데이터 포인터는 없고, 데이터 값과 child 포인터만 있다.
- 데이터 포인터가 생략되기 때문에 더 많은 키 값을 넣을 수 있고, B-트리만 있는 것보다 트리 높이가 작아질 수 있다.
-
- 다중키 인덱스 : 여러개의 열로 인덱스를 만드는 것
- 분할 해싱 : 각 키에 대해 해싱한 값을 조합해 인덱스로 지정
