KD Tree / KDB Tree

K-D Tree(K = 숫자, D = Demension, 차원)

k-d tree는 다차원의 점 data를 index할 수 있는 가장 간단하면서도 기본적인 data 구조이다.

k-d tree는 일반적으로 disk의 저장을 고려하지 않고 주 기억장치 상에서 동작하는 index 구조이다.

따라서 대용량의 data에 대해서는 적당하지 않고 소규모의 다차원 점 data를 index할 때 적당하다.

즉 Binary Search Tree를 다차원 공간으로 확장한것, 기본 구조와 알고리즘은 BST와 유사하지만 

Tree의 level차원을 번갈아 가며 비교한다는게 차이점이다.

특징

주 기억장치에서 동작

소규모의 다차원 점 data를 인덱싱할때 적합(PAM)

balanace tree가 아님

삽입

삽입하려는 data key value가 tree의 기존 node의 data key value 보다 

작거나 같으면 left subtree에 save

크면 right subtree에 저장

삭제

node 삭제로 인해 삭제된 node 아래 있는 subtree를 재 구성해야하기 때문에 연산이 복잡하다.

KDB Tree(KD Tree + B Tree)

다원 탐색 트리 : disk page size와 같은 일정 size의 node들로 구성

완전 균형 tree 구조

입출력을 효율적으로 하기위해 각 node는 page에 저장

탐색공간(Search space)분할 : 한 field의 domain값을 비교한 결과에 따라 탐색공간을 두개의 subspace로 분할

참고

https://algs4.tistory.com/68

https://3dmpengines.tistory.com/1352

10장.pptx