[Data Structures] Grid File | 그리드 파일

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)