그리드 파일

컴퓨터 과학에서 그리드 파일이나 버킷 그리드는 그리드의 하나 이상의 셀이 작은 점 집합을 참조하는 비주기적 그리드로 공간을 분할하는 점 접근 방법이다.그리드 파일(대칭 데이터 구조)은 이러한 인덱스를 디스크에 저장하여 복잡한 데이터 검색을 수행하는 효율적인 방법을 제공한다.

n은 단일 점을 참조하기 위해 사용할 수 있는 키 수를 나타내는 n-dimension 격자를 제공한다.

그리드 파일은 데이터 자체를 포함하지 않고 대신 올바른 버킷에 대한 참조를 포함하고 있다.

사용하다

그리드 파일은 일반적으로 단일 값을 여러 키로 참조할 수 있는 경우에 사용된다.

그리드 파일이 사용되기 시작한 것은 "예: 반전된 파일과 같이 레코드에 대한 다중키 액세스를 제공하는 전통적인 파일 구조가 원래 단일키 액세스를 위해 설계된 파일 구조의 확장자이기 때문이다.특히 동적 파일에 대한 멀티키 액세스에 대한 여러 가지 결함을 나타낸다."^[1]

전통적인 단일 차원 데이터 구조(예: 해시)에서 단일 기준에 대한 검색은 일반적으로 매우 단순하지만 두 번째 기준을 찾는 것은 훨씬 더 복잡할 수 있다.

그리드 파일은 전통적인 해시가 그리드 디렉토리로 대체되는 해싱의 특별한 종류를 나타낸다.

예

인구조사 데이터베이스^[2][3]

인구 조사 데이터를 포함하는 데이터베이스를 고려하십시오.한 개의 레코드는 한 가구를 나타내며, 모든 레코드는 버킷으로 그룹화된다.양동이의 모든 기록은 그들의 도시(양동이의 모든 기록에 대해 동일함)와 이름이 같은 문자로 시작하는 그 도시의 거리에 의해 색인화될 수 있다.

그리드 파일은 이 구조에 대한 효율적인 지수를 제공하기 위해 사용될 수 있다. 여기서 기록은 26개의 그룹으로 분류되며, 각각은 알파벳 문자 중 하나로 시작하는 도시의 거리 이름과 관련된다.이 구조는 우리가 x축과 y축이라고 부르는 2차원의 배열, 테이블 또는 격자로 생각할 수 있다.

X축은 도시, Y축은 알파벳의 각 글자 또는 각 거리의 첫 글자로 간주할 수 있다.

이 구조에서 각각의 기록은 셀로 알려져 있다.각 셀에는 실제 데이터가 저장되는 데이터베이스의 해당 버킷에 대한 포인터가 포함될 것이다.도시의 이름을 저장하기 위해 여분의 셀 또는 기록 헤더가 필요할 수 있다.첫 번째 셀은 "A"로 시작하는 거리 이름, 두 번째 셀은 "B"로 시작하는 거리 이름 등에 해당하므로 이 셀과 함께 그룹화된 다른 셀은 각각의 버킷에 대한 포인터만 포함하면 된다.

이 데이터베이스는 인구조사를 다른 대륙으로 확대하기 위한 대륙 영역을 포함하도록 더 확장될 수 있다.이것은 같은 양동이의 기록들이 같은 대륙의 같은 편지로 시작하는 거리의 가정들에 해당하게 할 것이다.

그리드 파일의 셀은 도시 헤더로 구성되며, 동일한 대륙의 동일한 도시, 동일한 대륙에서 동일한 출발 문자로 거리에 관련된 26개의 셀로 구성된 6개의 그룹(각 대륙당 1개, 남극 대륙을 포함하지 않음)으로 구성되며, 현재 3차원 배열로 생각할 수 있다.

이점

그리드 파일의 단일 항목에는 지정된 키로 인덱싱된 모든 레코드에 대한 포인터가 포함되므로:^[4]

• 특별한 계산이 필요하지 않다.
• 올바른 레코드만 검색됨
• 단일 검색 키 쿼리에 사용할 수도 있음
• 검색 키 n개에 대한 쿼리로 쉽게 확장
• 다중 키 쿼리의 처리 시간 대폭 단축
• 데이터 액세스를 위한 2-디스크 액세스 상한이 있음.^[1]

단점들

그러나, 그리드 파일의 특성 때문에 다음과 같은 단점도 있다.^[4]

• 공간 오버헤드 부과
• 삽입 및 삭제 시 성능 오버헤드

관련 데이터 구조

• 다중 계층 그리드 파일
• 트윈 그리드 파일
• BANG 파일

참고 항목

• 격자 그래프
• 그리드(공간 지수)
• 인덱스(데이터베이스), 쿼드트리, Kd-트리, UB-트리, R-트리, 범위 트리 등의 대체 트리.

참조