z-ordering Tree

z-ordering tree

z-ordering tree는 linear quadtree처럼 MBR을 사용하지 않음

z-odering tree는 최대 degree인 d를 설정하고 시작함

d=3이므로 4^3 = 64의 격자로 쪼개짐

 

위와 같이 degree=3 이므로 최대 3개의 digit을 갖는 index로 표현할 수 있음

단, 03처럼 030,031,032, 033이 모두 포함되면 그냥 03으로 표기함

그 다음 object가 겹치는 index의 집합을 구성함

**  linear quadtree 와 z-ordering 차이를 알기!

단점. 여전히 duplication이 많이 발생함

 

 

z-order tree에서의 rectangle  찾기

파란점 = 012, 빨간점 121

 

indexing을 하면 012(파랑)부터 시작해서 121(빨강)사이의 모든 것을 다 가져옴

{c, d, f}

 

{c, d, f} 중 window와 겹치는 {c,c,c,f,f,f, f}가 질의에 해당하는 최종 result임

→ 중복을 제거하고 unique한것 만 가져온 것임

I/O에 대한 정리

위의 예제에서 k=3

z-order tree의 단점: 

- B+ tree depth가 더 큼( linear quad tree보다 entry수가 더 많음)

- 더 작은 격자무늬를 사용할 수록 더 정확한 위치파악으 할 수 있으나

  index의 수가 더 많이 늘어남

  (leaf level에서 duplication이 더 많이 발생함)