HG-트리 색인 구조 및 그의 삽입, 삭제, 검색 방법

Abstract

본 발명은 멀티미디어 데이터베이스나 지리 정보 시스템과 같이 다차원 공간상의 데이터를 위한 검색 및 갱신 효율을 극대화하기 위한 새로운 HG-트리 색인 구조 및 그의 삽입, 삭제, 검색 방법에 관한 것이다.상세하게는 본 발명의 HG-트리(Hibert Grid- tree) 색인 구조는 힐버트 곡선을 사용하여 n-차원 공간상의 모든 위치를 1 차원 선분상의 위치로 사상(mapping)시키고, 색인 구조의 디렉토리 부분이 나타내는 영역이 가능한 한 실제로 데이터가 점유하는 부분을 최소로 나타내도록 최소경계간격(minimum bounding interval : MBI) 개념을 도입하여 색인 노드가 커버(cover)하는 데이터 영역을 가능한 한 줄임으로써 검색 성능을 높인 것이다.또한 새로운 데이터 객체를 삽입하는 경우 색인 구조의 노드(node)에서 범람(overflow)이 발생하여 노드를 분리해야 하는 경우에 인접한 노드에 여유가 있는지 검사한 후에, 여유가 있으면 범람 노드를 분리시키지 않고 데이터를 인접한 노드로 재분배 함으로써 노드 분리를 막고, 노드 분리가 불가피한 경우에는 인접한 노드 중 하나와 함께 두 개의 노드를 세 개로 분리하여 저장 효율을 높인 것이다.