[Database] Index structures (single-level ordered)

인덱스는 레코드를 검색할 때 속도를 높여주는 보조 역할을 한다.

 

기존 레코드들의 물리적 위치와 관계없이 작동한다.

 

크게 두 가지 방식으로 나뉜다.

 

1. single-level ordered indexes
2. multilevel indexes

이번 포스팅에서는 1번 single-level ordered indexes에 대해서 공부해보려 한다.

 

single-level ordered indexes는 세 가지 방식으로 나뉜다.

 

1. primary index
2. clustering index
3. secondary index

primary index

두 개의 필드를 갖는 고정 길이 형식이다.

<K(i), P(i)>        K(i) : 정렬 키 필드 P(i) : 디스크 블록의 포인터

index entry는 한 블록당 하나를 갖는다.

 

각각 블록의 첫 번째 레코드를 Anchor record라고 부른다.

 

 

primary index는 블록 당 검색을 하므로 sparse(non-dense) index 이다.

 

정렬된 파일에는 200000개의 레코드가 있고 블록의 크기는 2048Bytes이고 레코드의 크기는 100Bytes이다.
블록의 개수를 구하려면 먼저 bfr(블록에 들어갈 수 있는 레코드의 개수)를 구한다.
2048/100을 하고 소수점을 버리면 20이다. 즉 한 블록에는 20개의 레코드가 들어갈 수 있다.
블록의 개수는 레코드의 개수를 bfr로 나누면 된다.
즉 10000개의 블록이 있다.
정렬되어 있으니까 이진 탐색을 한다면 평균 14개의 블록 탐색을 해야한다.

이제 여기서 primary index를 사용한다면 얼마나 줄어들까?
index entry의 크기를 15이라고 가정하자.
먼저 bfri(블록에 들어갈 수 있는 인덱스 엔트리의 개수)를 구한다.
2048/15를 하고 소수점을 버리면 136이다. 즉 한 블록에는 136개의 index entry가 들어갈 수 있다.
총 index entry의 개수는 블록의 개수와 동일하다.
위 문제에서 구한 블록의 개수는 10000개이므로 index entry의 개수는 10000개이다.
인덱스 블록의 개수는 index entry의 개수를 bfri로 나누면 된다.
10000/136을 하고 소수점을 올리면 74개이다.
정렬되어 있으니까 이진 탐색을 한다면 평균 7개의 인덱스 블록 탐색을 해야한다.
그런데 인덱스 블록 탐색을 하고 데이터 블록 탐색도 해야하므로 총 탐색 횟수는 7+1=8이다.

이렇게 primary index를 사용하면 시간을 많이 단축할 수 있다.

 

그런데 이러한 방식은 삽입, 삭제할 때 큰 문제가 될 수 있다.

 

레코드 전체를 움직이고 인덱스 또한 움직여야하기 때문이다.

 

그래서 트랜잭션 파일이나 deletion mark를 사용한다.

 

clustering index

primary index처럼 정렬이 되어있지만 다른점은 nonkey field이기 때문에 중복값이 존재한다는 점이다.

 

우리는 블록당 연결된 인덱스 엔트리를 하나로 유지하고 싶다. 이를 위해 같은 값을 갖는 필드끼리 묶는 방법이 있다.

 

이렇게 같은 값들을 묶는다.

 

블록에서 오버플로가 나타난다면 연결 리스트로 처리한다.

 

secondary index

위에서 본 primary index와 clustering index는 정렬이 되어있다는 것이 공통점이고 키냐 아니냐에 따라 나뉜다.

 

secondary index는 정렬이 되어있지 않고 키 일수도있고 아닐수도 있다.

 

블록당 엔트리가 존재하는 것이 아닌 레코드당 엔트리가 존재하므로 dense-index이다.

 

nonkey field일 경우 더욱 복잡해지는데 해결 방법은 3가지가 있다.

 

1. 같은 키를 갖는 여러 개의 index entry 생성
2. 엔트리의 P(i)가 여러 개가 될 수 있는 가변 길이 엔트리 생성
3. 레벨을 늘려서 중간 단계에 포인터들의 집합 생성

 

다음 포스팅에서는 single-level이 아닌 multi-level을 공부할 예정이다.