Grid File
그리드 파일
- Key의 내용으로 Record가 저장된 곳을 "단번에" 알아낼 수 있도록 한
Multi-Dimensional Store/Search 자료구조이다.
- Key가 곧, Record의 저장 위치값이기 때문에, Grid File구조에서는 범위 검색이 가능하다.
- 대표적인 자료구조 중 하나인 Hash Table (URL)은 저장 위치를 Hashing하여 Key로 산출해내는 구조이다.
(즉, 그리드 파일과 달리, 해시 테이블에서는 저장 위치를 "변형"하여 Key로 만든다.)
Mechanism (원리)
- 메모리 공간을 배타적인 Grid(격자) 영역으로 나눈 다음,
해당 영역에 속하는 Record를 한 Page에 모아서 저장한다.
- 즉, 임의의 레코드들에 특정 좌표값(=Key)이 지정되어, 상수시간에 저장과 검색이 이루어진다.
Linear Scaling Array (일차 스케일링 배열)
- 각 Grid들의 경계값을 저장하고 있는 배열이다.
Grid Array (그리드 배열)
- Linear Scaling Array를 기반으로, 각 영역이 저장되어 있는 Page 번호를 저장하고 있는 배열이다.
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
Reference: Grid File
(Wikipedia, 2021, URL)
