GiST

GiST

컴퓨팅에서 GiST(Generalized Search Tree)는 다양한 디스크 기반 검색 트리를 구축하는 데 사용할 수 있는 데이터 구조 및 API입니다.GiST는 B+ 트리의 일반화로 저장되는 데이터 유형이나 서비스되는 쿼리에 대한 가정을 하지 않고 동시에 복구 가능한 높이 균형 검색 트리 인프라를 제공합니다.GiST를 사용하면 B+ 트리, R-tree, hB-tree, RD-tree 등 다양한 알려진 인덱스를 쉽게 구현할 수 있습니다.또, 새로운 데이터 타입의 전용 인덱스를 간단하게 개발할 수도 있습니다.쿼드 트리나 프리픽스트리(트리) 등 높이 밸런싱이 불가능한 트리를 구현하기 위해 직접 사용할 수 없지만 프리픽스트리와 마찬가지로 손실 압축을 포함한 압축을 지원합니다.GiST는 슈퍼셋 계층으로 자연스럽게 정렬할 수 있는 모든 데이터 유형에 사용할 수 있습니다.데이터 유형 지원 및 트리 레이아웃 측면에서 확장이 가능할 뿐만 아니라 확장자가 선택한 쿼리 술어를 지원할 수 있습니다.

GiST는 데이터베이스 시스템의 맥락에서 소프트웨어 확장성의 한 예입니다.새로운 트리 기반 인덱스를 지원하기 위해 데이터베이스 시스템을 쉽게 발전시킬 수 있습니다.다양한 인덱스 설계의 애플리케이션별 측면을 캡처하기에 충분한 좁은 API에서 핵심 시스템 인프라를 배제함으로써 이를 달성합니다.GiST 인프라스트럭처 코드는 디스크의 인덱스 페이지 레이아웃, 인덱스를 검색하고 인덱스에서 삭제하는 알고리즘 및 높은 동시성을 위한 페이지 수준 잠금, 크래시 복구를 위한 미리 쓰기 로그와 같은 복잡한 트랜잭션 세부 정보를 관리합니다.이를 통해 새로운 트리 기반 인덱스의 작성자는 데이터베이스 시스템 내부 전문가가 되지 않고도 새로운 인덱스 유형의 새로운 기능(예를 들어 데이터의 서브셋을 검색용으로 기술해야 하는 방법)을 구현하는 데 집중할 수 있습니다.

원래 부울 선택 쿼리에 응답하도록 설계되었지만 GiST는 가장 가까운 네이버 검색 및 대규모 데이터 세트에 대한 다양한 형태의 통계 근사도 지원할 수 있습니다.

실장

가장 널리 사용되는 GiST 실장은 Postgre에 있습니다.SQL 관계형 데이터베이스. Informix Universal Server 및 독립 실행형 라이브러리로 libgist에도 구현되었습니다.

포스트그레스Ql

포스트그레SQL GiST 구현에는 가변 길이 키, 복합 키, 동시성 제어 및 복구 지원이 포함됩니다.이러한 기능은 모든 GiST 확장에 상속됩니다.GiST를 사용하여 개발되어 Postgre와 함께 배포된 여러 모듈이 있습니다.SQL. 예:

  • rtree_gist, btree_gist - R 트리 및 B 트리의 GiST 구현
  • intarray - int4의 1차원 배열에 대한 인덱스 지원
  • tsearch2 - 색인화된 액세스를 가진 검색 가능(전체 텍스트) 데이터 유형
  • ltree - 데이터 유형, 색인화된 접근 방법 및 트리와 같은 구조로 구성된 데이터에 대한 쿼리
  • hstore - (키, 값) 데이터를 위한 스토리지
  • 큐브 - 데이터 유형, 다차원 큐브를 나타냅니다.

포스트그레SQL GiST 구현은 PostGIS(지리적 정보 시스템) 및 BioPostgres 바이오 인포매틱스 시스템의 인덱싱을 지원합니다.

레퍼런스

외부 링크