UB트리

UB-tree
2차원 Z-오더

루돌프 바이어와 볼커 마클이 제안한 UB 트리는 다차원 데이터를 저장하고 효율적으로 검색하기 위한 균형잡힌 트리다.기본적으로 Z순서에 따라 기록이 저장되어 있는 B+나무(잎에만 있는 정보)로, 모튼순서라고도 한다.Z 순서는 단순히 키를 비트로 교차시켜 계산한다.

삽입, 삭제, 포인트 조회는 일반 B+ 나무와 같이 한다.그러나 다차원 지점 데이터에서 범위 검색을 수행하려면 다차원 검색 범위에 있는 다음 Z-값을 데이터 베이스에서 만나는 지점에서 계산하기 위한 알고리즘이 제공되어야 한다.

이 핵심 문제를 해결하기 위한 원래 알고리즘은 차원성에 기하급수적이어서 실현[1] 가능하지 않았다("GetNextZ-address").z 주소 비트 길이를 가진 이 "UB 트리 범위 쿼리의 기준 부분"에 대한 해결책은 나중에 설명되었다.[2]이 방법은 이미 검색 트리와 함께 Z 오더를 사용하는 것이 먼저 제안된 이전 논문에서[3] 설명되었다.

참조

  1. ^ Markl, V. (1999). "MISTRAL: Processing Relational Queries using a Multidimensional Access Technique". CiteSeerX 10.1.1.32.6487. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  2. ^ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (September 10–14, 2000). Integrating the UB-tree into a Database System Kernel (PDF). 26th International Conference on Very Large Data Bases. pp. 263–272.
  3. ^ Tropf, H.; Herzog, H. "Multidimensional Range Search in Dynamically Balanced Trees" (PDF). Angewandte Informatik (Applied Informatics) (2/1981): 71–77. ISSN 0013-5704.


Stub icon

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