-
KDB 트리 기본)
B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다.
검색 시에는 키에 따라 분기가 되는 게 아니라 루트 노드로 부터 전체 공간을 쪼개면서 검색을 진행한다.
KDB 트리는 두 종류의 노드로 구성된다.
- 영역 노드 트리의 차원에 따라 노드가 차지하는 공간을 표현하는 노드
- 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드
k 차원의 키를 사용하는 경우 영역은 다음과 같이 표현한다.
(<min0, max0>, <min1, max1>, ... , <mink-1, maxk-1>)
쉽게 배우는 알고리즘 KDB 트리 그림 5-26