X-트리

X-tree
이 글은 데이터를 다차원으로 저장하기 위한 트리 데이터 구조에 관한 것이다.XTree 파일 관리자에 대해서는 XTree를 참조하십시오.

컴퓨터 과학에서 X-트리(eXtended node tree의[1] 경우)는 데이터를 여러 차원으로 저장하는 데 사용되는 R-트리를 기반으로 한 인덱스 트리 구조다.1996년에 등장하였으며,[2] 경계상자의 중복방지를 강조하기 때문에 R-tree(1984), R+tree(1987), R*-tree(1990)와 차이가 있어, 고차원에서 점점 문제가 되고 있다.중복을 방지하지 않고 노드를 분할할 수 없는 경우에는 노드 분할이 지연되어 슈퍼노드가 발생하게 된다.극단적인 경우 트리는 선형화되므로 일부 다른 데이터 구조에서 관찰되는 최악의 경우에 대비할 수 있다.

구조

X 트리는 데이터 노드, 일반 디렉터리 노드, 슈퍼노드 등 세 가지 유형의 노드로 구성된다.X 트리의 데이터 노드에는 실제 데이터 개체에 대한 포인터와 함께 직선으로 된 최소 경계 직사각형(MBR)이 포함되며, 디렉토리 노드에는 하위 MBR에 대한 포인터가 함께 MBR이 포함되어 있다.슈퍼노드는 가변 크기(일반 블록 크기의 배수)의 대형 디렉토리 노드다.슈퍼노드의 기본 목표는 디렉토리 구조가 비효율적인 결과를 초래하는 디렉토리의 분할을 피하는 것이다.

참조

  1. ^ Selçuk Candan, K.; Luisa Sapino, Maria (31 May 2010). Cambridge University Press (ed.). Data Management for Multimedia Retrieval. ISBN 9781139489584.
  2. ^ Berchtold, Stefan; Keim, Daniel A.; Kriegel, Hans-Peter (1996). "The X-tree: An Index Structure for High-Dimensional Data". Proceedings of the 22nd VLDB Conference. Mumbai, India: 28–39.


Stub icon

이 알고리즘이나 데이터 구조와 관련된 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.