KDB-Tree

KDB-Tree

• KD-Tree와 B-Tree의 특성 결합
  • KD-Tree의 특성
    • 다차원 key
  • B-Tree의 특성
    • 디스크의 한 페이지가 한 노드와 일치
    • Balanced tree : 모든 리프노드들의 레벨이 같다.

• 각 레코드는 k차원 공간에서 하나의 점에 해당한다.
• Internal node하나는 k차원 공간에서 한 영역을 담당한다.
• 루트노드는 k차원 공간 전체를 커버하고 이하의 노드들은 k차원 공간의 부분영역을 담당한다.
• 같은 level에 있는 모든 노드들은 서로 겹치는 영역이 없다
• 같은 level에 있는 모든 노드들의 담당 영역을 합하면 k차원 공간 전체가 된다.
• 리프노드는 데이터 페이지 정보를 저장한다.

영역노드

- 복수개의 (영역, 페이지 번호) pair로 구성된다.

- 영역노드에서의 페이지 번호란, 자식 노드가 위치한 페이지 번호를 의미한다.

- KDB-Tree의 모든 Internal Node는 영역노드이다.

 

키노드

- 복수 개의 (키, 페이지 번호) pair로 구성된다.

- 키 노드에서의 페이지 번호란, 실질적인 레코드(정보)가 위치한 페이지 번호를 의미한다.

- KDB-Tree의 모든 leaf node는 키 노드이다.

 

삽입연산

삽입연산은 B-Tree에서의 삽입연산과 같은 원리로 작동한다.

- 삽입할 key가 속할 리프노드를 찾은 후, 해당 리프노드가 삽입한 키를 수용할 수 있으면 삽입한다.

- 해당 리프노드가 삽입할 키를 수용할 수 없다면, 인접한 시블링 노드와 재분배한 후 삽입한다.

- 인접한 형제노드와 재분배조차 불가능하다면, 리프노드를 두개로 분할한 후, 한쪽에 삽입한다. 이때 하나였던 리프노드를 두개로 분할했으므로, 이 들의 부모 노드의 영역도 분리되어야한다. (재귀적 처리가 필요하다)