[File System] ::Grid File

★ 다차원 데이터 : 선, 면, 위치와 같은 데이터로 이러한 다차원 데이터는 단일 키 파일구조로 처리가 불가능하고 다차원 인덱스구조가 필요

다차원 공간 파일은 여러개의 필드를 동시에 키로 사용하며 이것을 트리로 표현한건 아래의 종류가 있음

1) K-D

2) K-D-B

3) GRID FILE

4) QUAD TREE

5) R-TREE,R+-TREE,R*-TREE

최근의 비 정형화된 데이터베이스의 파일 처리에서는

1) 기본키,보조 키를 구분하지 않고 이들을 대칭적으로 취급하여 같은 수준의 검색을 요구

2) 기본키 자체가 복수의 애트리뷰트로 구성되는 경우가 빈번

여러개의 애트리뷰트를 동시에 키로 사용할 수 있는 다차원 파일 구조 및 검색 기법을 알아보자

격자 파일(Grid File)

- 다중키 파일 구조 , 삽입삭제가 빈번,자주일어나지 않는 두 가지 경우 모두 잘 적용함

- 공간상의 점 데이터를 저장하는 다차원 인덱스 구조

- 전체 공간을 격자단위로 분할해서 그 단위로 데이터 저장

특징

-디스크 기반 : 대용량 다차원 데이터 처리

- 해싱 기반 : 일반적으로 두번의 디스크 접근으로 데이터 검색

1) 완전 일치 질의(exact match query) : 모든 검색 키에 대한 값이 명세 된 경우

ex ) 은행 고객 파일에서 계좌번호와 성명이 검색키로 되어 있을 때 쿼리가 " 계좌번호 1234567890인 위지원의 잔액은? "

2) 범위 질의(range query) : 특정 검색 키값으로 범위 수식이 명세 된 경우

ex ) 잔액이 100~200사이인 고객을 검색

3) 부분 일치 질의(partial match query) : 몇개의 검색키에 대한 값이 조건으로 명세 된 경우

ex ) 고객 위지원의 계좌번호와 잔액을 검색

아래의 파일은 X - Y 평면상에 존재하는 점들을 나타내는 것이다.

인덱스 엔트리 =( 키값의 범위, 페이지 번호 )

위에서부터 차례대로 삽입시키면서 이해하자. 이때 데이터 페이지는 최대 3개의 레코드를 저장할 수 있다고 가정

(...)

먼저 가장 위에 있는 E1을 넣고 나서 그 다음에 있는 M1,Z1을 그대로 넣어도 되지만 그러면 다음에 있는 E2를 넣을 수 없는 오버플로 상태가 된다.

그래서 키 값의 범위를 분할점을 선택(여기서는L9)하여 적절히 분할한다.

이런식으로 오버플로가 일어나지 않도록 적절하게 분할하면서 값을 넣어야한다.

이런 상황에서 만약에 K1,E2를 삭제하면 해당 페이지의 적재율이 낮아진다. 이러한 경우 효율성을 위해 합병을 할 수 있따

격자 파일(Grid File)은 이런 인덱스 구조를 K차원으로 확장시킨 것이다.(K=검색 키로 참가하는 필드수)

이제 앞의 구조와 다르게 격자 배열의 정의는 다음과 같다.

1) 키 값의 범위 = 선형 눈금자(liner scale)

-메인 메모리에 유지

2) 페이지 번호 = 격자 배열(grid array)

- 가장 작은 공간 = 격자 블록(grid block)

-데이터 페이지를 가리키는 page number가 저장

- 격자배열과 페이지는 디스크에 저장

- 기본적으로 하나의 격자블록당 하나의 페이지 공유

- 두개이상의 격자 블록이 하나의 데이터 페이지 공유 ( 데이터 페이지의 적재율이 낮아지는 것을 방지하기 위해 )

3) 선형눈금자+격자배열 = 격자 디렉토리(grid directory)

-해싱 역할을 수행

격자파일에서 어떻게 되는지 알아보자

앞서 본것과 같이 E1,M1,Z1까지는 블로킹 인수가 3이기 때문에 잘 들어가지만 그 다음인 E2를 삽입하려고할때면 P1에서 오버플로우가 발생한다.

그럼 이제 분할을 해야합니다. 1차원과 달리 분할기준을 잘 선정해야하는데,,, 아래의 순서로 분할을 합니다.

특정 축의 범위를 선정하여 그 범위를 이분(二分)하면서 전체공간을 분할하는 겁니다.

그래서 이 방법을 적용하여 레코드 공간을 분할시키어서 한다.

그렇게 계속 분할하게 되면 아래와 같이 된다. 여기서도 알 수 있지만 분할된 구역 ≠ 페이지 이다. (너무 뻔한가..)

이때 분할 된 친구들끼리를 트윈(twin)이라고 한다. 아래의 그림에서는

p4:p3

(p4,p3):p1

((p4,p4),p1):p2

가 트윈이다.

격자배열이 2차원 배열G로 구성되어 잇고 선형 눈금자 X,Y가 1차원배열 SX,SY로 구성되었다고 가정하자.

SX,SY는 크기가 작아서 주기억 장치에 저장할 수 있지만

G는 크기가 크므로 디스크에 저장해야한다.

완전 질의가 "X=7 Y=2인 PID를 구하여라" 이면 SX를 이용하여 X가 첫번째 범위에 있고 SY를 이용하여 Y가 첫번째 범위에 있다는 것을 알 수 있다.

이렇게 되면 SX,SY는 주기억 장치에 있어서 디스크접근이 필요없고 대신

디스크에 저장 되어있는 G배열에 접근할때 한번

G배열에 있는 페이지번호를 따라서 한번 더 접근할때 두번

으로 총 디스크에 두번 접근한다.

한번 더 해보자 이번 질문은 범위 질위이다. 5<X<9인 경우에는 다음과 같이 접근을 하게 된다. Y에 대해서는 언급이 없기때문에 모두 접근한다.

삭제인 경우에는 적제율이 낮은 페이지들을 합병을 할 수 있다. 이때 보통 트윈인 경우만 합병 시킬 수 있다. (그렇다고 트윈이 아닌친구들을 합병할 수 없다는 건 아니고, 트윈 합병이 비용도 적게들고 간단하기 때문이다)

예를 들어 아래의 그림에서 p3에 있는 Z2를 삭제하면 아래와 같이 합병이 될 수 있다.

일반적으로 격자 파일은 인덱스 키 개수가 작을경우(대개 10개미만)에 효율적이고 키들이 가질 수 있는 값의 범위가 크고 균등하게 분포되어 있을때 효율적이다.