10.다차원 공간 화일

 다차원 데이타 다차원 데이타는 단일 키 화일 구조로 처리 불가 다차원 데이타(multidimensional data) 전통적인 1차원 데이타 레코드가 아니라 CAD (computer aided design) 나 지리 정보 시스템(geographical information system) 에서의 선(line), 면(plane), 위치(location)와 같은 데이타 다차원 데이타를 나타내는 (x, y) 또는 (x, y, z)는 차원당 하나의 값 다차원 데이타는 단일 키 화일 구조로 처리 불가 다차원 데이타의 접근을 위해서는 다차원 인덱스 (multidimensional index) 구조가 필요

▶ 다차원 공간 화일이란 ? 여러 개의 필드(차원)를 동시에 키로 사용하는 화일 다차원 공간 화일을 트리로 표현 여러 개의 필드(차원)를 동시에 키로 사용하는 화일 다차원 공간 화일을 트리로 표현 k-d 트리(´75) k-d-B 트리(´81) 격자 화일(Grid File) (´84) 사분 트리(Quadtree) (´84) R-트리(´84), R+-트리(´87), R*-트리(´90)

▶ 다차원 인덱스(multidimensional index) 기법 PAM (Point Access Method) 다차원 점 데이타 (multidimensional point data)를 공간에서 저장, 검색하는 점 접근 방법 k-d 트리, k-d-B 트리, 격자 화일(grid file) SAM (Spatial Access Method) 선(line), 면(plane), 다각형(polygon), 다면체(polyhedron) 같은 다차원 공간 데이타(multidimensional spatial data)를 저장, 검색할 수 있는 공간 접근 방법 R-트리, R*-트리, R+-트리

 k-d 트리 k-d(k-dimensional) 트리 특징 k 차원의 점 데이타를 인덱스하는 구조 data structure for associative search 이원 탐색 트리를 다차원 공간 (multidimensional space)으로 확장한 것 다차원 이원 탐색 트리 (multidimensional binary search tree) 기본 구조와 알고리즘은 이원 탐색 트리와 유사 분기 조건은 < 이 아니라 ≤ 임 트리의 레벨을 내려가면서 차원의 필드 값을 차례로 번갈아 가며 비교 예) 3차원의 데이타(x,y,z)의 경우: x  y  z  x  y  z  ,,, 특징 메인 메모리상에서 동작하는 인덱스 구조 소규모의 다차원 점 데이타(multidimensional point data)를 인덱싱할 때 적합(PAM) 균형 트리가 아님

▶ k-d 트리에서의 데이타 삽입 다음과 같은 2차원 공간의 점(x,y) 데이타를 a, b, c, …j의 순서로 k-d 트리에 삽입하는 경우 점 위치 a (5, 4) b (2, 7) c (9, 5) d (3, 1) e (7, 2) f (9, 7) g (1, 4) h (4, 3) i (8, 2) j (4, 8)

▶ k-d 트리에서의 데이타 삽입 점 a(5,4)의 삽입 루트로 저장 a (5,4) 점 a가 삽입된 뒤의 2-d 트리 :x (0,0) (10,10) a (5,4) :x 점 a가 삽입된 뒤의 2-d 트리

▶ k-d 트리에서의 데이타 삽입 점 b(2,7)의 삽입 루트의 x 값과 비교, 작으므로 왼쪽 자식 노드에 삽입 a (5,4) (0,0) (10,10) a (5,4) b (2,7) :x :y

▶ k-d 트리에서의 데이타 삽입 점 c(9,5)의 삽입 루트의 x 값과 비교, 크므로 오른쪽 자식 노드에 삽입 a (5,4) b c (0,0) (10,10) a (5,4) b (2,7) c (9,5) :x :y

▶ k-d 트리에서의 데이타 삽입 점 d(3,1)의 삽입 루트의 x 값과 비교, 작으므로 왼쪽 자식 노드로 분기 점 b의 y값과 비교, 작으므로 왼쪽 자식 노드에 삽입 a b c d (10,10) (0, 0) a (5,4) b (2,7) c (9,5) d (3,1) :x :y :x

▶ k-d 트리에서의 데이타 삽입 삽입이 완료된 k-d 트리 a (5,4) b (2,7) c (9,5) d (3,1) e f h g j i (0,0) (10,10) a (5,4) :x b (2,7) c (9,5) :y d (3,1) j (4,8) e (7,2) f (8,7) :x g (1,4) h (4,3) i (8,2) :y

▶ k-d 트리에서의 데이타 검색 위치 (4,8)의 점은 무엇인가? 루트 a(5,4)에서 x값을 비교: 4 ≤ 5이므로 왼쪽 서브 트리로 분기 점 b에서 y값을 비교: 7 < 8이므로 오른쪽 서브 트리로 분기 점 j를 발견 . 검색 완료 a b c d e f h g j i (0,0) (10,10) a (5,4) :x b (2,7) c (9,5) :y d (3,1) j (4,8) e (7,2) f (8,7) :x g (1,4) h (4,3) i (8,2) :y

▶ k-d 트리에서의 데이타 검색 위치 (6,2)의 점을 검색하라 루트 a(5,4)에서 시작하여 점 c(9,5), 점 e(7,2)를 검사한 다음에 왼쪽 서브트리로 분기 시도. 그러나 분기 실패(널)로 해당 점 레코드가 없다는 것을 확인. k-d 트리의 높이가 h라 하면 최악의 검색 시간은 O(h)가 됨 k-d 트리에서의 삭제는 복잡 삭제된 노드의 서브트리들에 대한 재구성 요구 발생

▶ k-d 트리의 단점 균형 트리가 아니므로 데이타의 입력 순서나 분포에 따라 트리의 높이가 극단적으로 높아지면 검색 성능이 저하가능 예)  g, d, b, e, h, a, f, c, i, j 의 순서로 입력된 예 g (1,4) f (8,7) d (3,1) c (9,5) b (2,7) i (8,2) e (7,2) h (4,3) j (4,8) a (5,4) :x :y a b c d e f h g j i (0,0) (10,10)

 k-d-B(k-dimensional B-tree) 트리 디스크 기반으로 다차원 점 데이타를 효율적으로 검색, 저장하기 위한 구조 디스크 페이지 크기의 노드들로 구성된 다원 탐색 트리(multiway search tree) 균형 트리 루트에서 리프 노드까지의 탐색 경로 길이가 모두 동일 다중키 레코드 검색을 위한 인덱스 레코드 구조: (key0, key1, …, keyK-1, 주소) keyi 는 도메인i에 속하는 탐색 키 k는 차원(필드) 수 k-d-B 트리는 범위 질의(range query)를 지원 범위 질의는 각 탐색 키 값이 mini과 maxi로 명세됨 mini≤keyi≤maxi , 0≤i≤ k-1

▶ k-d-B 트리 점(point)는 카티션 프로덕트, (도메인0×도메인1×…도메인K-1)의 한 원소 영역(region)은 다음 C와 같은 성질을 만족하는 모든 점 xi, 0≤i≤(k-1) 들의 집합 C: mini≤xi≤maxi , 0≤i≤(k-1), mini, maxi 는 도메인i의 원소 점은 xi, 0≤i≤(k-1)만 저장 k 개의 필드 값을 가진 하나의 레코드 인스턴스에 해당 영역은 mini와 maxi, 0≤i≤(k-1)를 저장 k 개의 범위 조건을 만족하는 레코드의 집합

▶ k-d-B 트리 2개의 필드(차원)로 표현된 레코드의 예 키와 몸무게는 탐색을 위한 도메인 선수 키 몸무게 a 170 65 b 173 63 c 180 75 d 178 80 e 160 55 f 166 48 g 168 47 h 185 필드 1( 키 ) 165 180 70 60 2 ( 몸무게 영역은 ([165, 180], [60, 70])

▶ k-d-B 트리의 구조 k-d-B 트리는 루트 페이지와 자식 페이지로 구성 페이지는 영역 페이지와 점 페이지로 구분 영역 페이지(region page) : <영역, 페이지-id> 쌍의 엔트리들을 포함하는 노드 점 페이지(point page) : <점, 주소> 쌍의 엔트리들을 포함하는 단말 노드. 주소는 점 데이타 레코드가 저장되어있는 주소. 페이지 크기는 디스크 페이지 크기 엔트리 삽입으로 오버플로가 일어나면 분할 연산이 필요 엔트리 삭제로 언더플로가 일어나면 합병 연산이 필요

▶ k-d-B 트리의 특성 ① 각 페이지를 노드라하고, 영역의 페이지-id를 노드 포인터라 하면 k-d-B 트리는 root-id가 가리키는 다원 탐색 트리이다. 영역 페이지는 공백이거나 널 포인터를 포함할 수 없고 점 페이지는 <점, 주소> 쌍의 엔트리만 포함한다. ② 모든 단말 페이지까지의 경로 길이는 동일 ③ 영역 페이지는 소영역으로 완전 분리(disjoint) 분할할 수 있다. 이 소영역의 합은 그 부모 영역과 같다. ④ 루트 페이지가 영역 페이지이면, 이 페이지의 소영역들의 합은 화일 전체의 영역이 된다. ⑤ 자식 페이지가 점 페이지이면 이 점 페이지에 있는 모든 점들은 그 부모 영역에 속한다.

▶ 2-d-B 트리의 예 영역 페이지 점 페이지 root-id --- 페이지에 포함된 영역(흰색) 페이지에 포함되지 않은 영역 (회색) 점 root-id 영역 페이지 점 페이지

▶ k-d-B 트리의 연산 (검색) k-d-B 트리가 지원하는 범위 질의는 질의 영역(query region)으로 표현 1. 부분 범위 질의(partial range query) : 차원이 모두 범위로 명세 2. 부분 일치 질의(partial match query) : 차원의 일부가 점이고, 나머지는 범위로 명세 3. 완전 일치 질의(exact match query) : 모든 차원이 점으로 명세 질의 영역을 만족하는 모든 레코드(점)를 검색하는 알고리즘 ① root-id가 널이면 종료, 그렇지 않으면 변수 page는 루트 페이지를 가리키게 한다. ② 변수 page가 점 페이지를 가리키면 질의 영역에 속하는 <점, 주소>를 검사해서 그 주소에 해당하는 레코드를 검색 ③ 영역 페이지인 경우는 질의 영역과 중첩되거나 포함되는 모든 <영역, child-id>에 대해 차례로 변수 page가 이 페이지를 가리키게 하고 단계 ②를 다시 수행

▶ 2-d-B 트리의 질의 영역 검색 예 root-id 2 1 3 질의 영역 1.1 1.2 3.2 3.1 1.3 1.4 3.3

▶ k-d-B 트리의 연산 (삽입) 원소 값 xi에 따라 영역 Ix x Iy를 분할하는 방법 x’이 구간(interval) Ix에 포함되는 경우에 구간 Ix=[minx, maxx]는 영역 Ix x Iy를 다음과 같이 두 소영역으로 분할 ① [minx, x’] x Iy : 왼쪽 영역 ② [x’, maxx] x Iy : 오른쪽 영역 원소 값 xi에 따라 점 페이지 분할 방법 x’ 값에 따라 점 페이지를 오른쪽 점 페이지와 왼쪽 점 페이지로 분할 모든 <점, 주소> 쌍에 대해 x의 값과 x’의 값을 비교하여 오른쪽 또는 왼쪽 점 페이지로 이동하고 원래의 점 페이지는 삭제

▶ k-d-B 트리의 연산 (삽입) x’에 의한 점 페이지 분할 분할 전 분할 원소 분할 후 왼쪽 페이지 오른쪽 페이지

▶ k-d-B 트리의 연산 (삽입) 원소 값 xi에 따라 영역 페이지 분할 방법 영역의 엔트리들을 분할하는 방법 영역 페이지로 분할 모든 <영역, 페이지-id> 쌍 엔트리를 오른쪽 또는 왼쪽 페이지로 이동하고 원래의 페이지는 삭제 영역의 엔트리들을 분할하는 방법 원래 영역 페이지 내의 각 <영역, 페이지-id> 에 대해 ① 영역이 x’의 왼편에 있으면 <영역, 페이지-id>를 왼쪽 영역 페이지로 이동 ② 영역이 x’의 오른편에 있으면 <영역, 페이지-id>를 오른쪽 영역 페이지로 이동 ③ x’이 영역 중간을 가로지르면 그 영역을 x’ 값에 따라 두 개의 소영역으로 분할하고 각각 오른쪽 페이지와 왼쪽 페이지에 첨가한다.

▶ k-d-B 트리의 연산 (삽입) x’에 의한 영역 페이지 분할 분할 원소 전 * 표시된 부분이 분할된다 후

▶ k-d-B 트리의 연산(삽입) 인덱스 레코드 <점, 주소> 쌍을 삽입하는 알고리즘 ① root-id가 널(null)이면 점 페이지를 생성하고 <점, 주소> 엔트리를 저장. ② <점, 주소> 쌍이 삽입되어야 할 페이지를 완전 일치 질의 수행 방식으로 탐색. 페이지에 여유 공간이 있으면 <점, 주소> 쌍을 페이지에 삽입하고 종료. ③ 삽입하려는 점 페이지에 오버플로가 발생하면 엔트리들을 등분할 수 있는 적절한 도메인i의 원소 xi를 선택하여 페이지를 분할하고 엔트리들을 이동. ④ 분할된 페이지의 부모 영역 페이지에 있는 원래의 <영역, 페이지-id>를 새로운 <왼쪽 영역, 페이지-id>, <오른쪽 페이지, 페이지-id>로 대체한다. 이 엔트리의 증가로 페이지가 오버플로되면 이 영역 페이지를 분할 하고 단계 ④를 다시 실행한다. ⑤ 루트 페이지가 분할하게 되면 새로운 루트 페이지를 생성하여 조정한다. 이때 k-d-B 트리의 높이는 하나 증가된다.

▶ k-d-B 트리의 연산(삭제) 점 페이지에서 <점, 주소> 쌍을 완전 일치 질의로 검색 후 삭제 공간 이용률을 높이기 위해 재구성 합병 : 두 영역의 엔트리들을 하나의 큰 페이지로 통합 언더플로 : 두 형제 영역을 합병 또는 엔트리들의 재분배 두 영역의 합이 보다 큰 직사각형 형태의 영역을 구성하게 되면 합병 가능(joinable) 합병이 불가능한 경우 영역 A와 B 또는 A와 C

 격자 화일(Grid file) 격자 화일 특징 공간상의 점 데이타를 저장하는 다차원 인덱스 구조(multidimensional index structure) 전체 공간을 격자(grid)로 분할하여 격자 단위로 데이타를 저장 격자의 크기는 데이타의 삽입에 따라 분할되어 작은 격자로 변환 특징 디스크 기반 대용량의 다차원 데이타를 처리 해싱 기반 일반적으로 두 번의 디스크 접근으로 데이타 검색

▶ 격자 화일의 구성 K-차원 격자 화일 선형 눈금자(linear scale) 격자 배열(grid array) k개의 선형 눈금자 (linear scale)와 k-차원의 격자 배열 (grid array)로 구성된 격자 디렉터리(grid directory)로 관리 이 디렉터리가 해싱 역할을 수행 선형 눈금자(linear scale) 각 차원별 눈금 정보를 표현하며 메인 메모리에 유지 격자 배열(grid array) 선형 눈금자에 의해 분할된 격자 블록(grid block)으로 구성 각 격자 블록에는 데이타 페이지를 가리키는 페이지 번호 (page number)가 저장 격자 배열과 페이지는 디스크에 저장

▶ 격자 화일의 구성 격자 블록과 데이타 페이지 x 축과 y 축으로 표현되는 2차원 격자 화일 예 기본적으로 하나의 격자 블록당 하나의 데이타 페이지 두 개 이상의 격자 블록이 하나의 데이타 페이지를 공유 가능 x 축과 y 축으로 표현되는 2차원 격자 화일 예 x 축은 (0, 5, 10, 15, 20)의 선형 눈금자 y 축은 (0, 5, 10) 의 선형 눈금자 격자 배열은 각 축의 선형 눈금자에 따라 구성 각 데이타 페이지는 최대 3개의 점 데이타를 저장

▶ 격자 화일의 구성 선형 눈금자 격자 배열 데이타 페이지

▶ 격자 화일의 레코드 삽입 예 예제 데이타 데이타 위치 a (2, 4) b (4, 6) c (16, 2) d (7, 2) e 데이타  위치 a (2, 4) b (4, 6) c (16, 2) d (7, 2) e (18, 8) f (9, 4) g (8, 8) h (13, 9) i (6, 4)

▶ 격자 화일의 레코드 삽입 예 점 a(2,4), b(4,6), c(16,2)를 삽입 하나의 격자 블록을 통해 페이지 P1에 저장되고 P1은 만원 SY SX

▶ 격자 화일의 레코드 삽입 예 점 d(7,2)를 삽입 페이지 P1이 오버플로가 되어 격자를 분할 각 축(axis)을 순환적으로 분할 x=10으로 격자 블록을 분할하고 페이지 P2를 할당 분할된 두 페이지 P1과 P2를 트윈(twin)이라 함 x>10인 레코드들은 P2로 이동 SY SX

▶ 격자 화일의 레코드 삽입 예 점 e(18,8), f(9,4)를 삽입 f를 삽입 시 페이지 P1에 오버플로가 발생 y=5로 격자를 분할하고 페이지 P3을 할당 P1에 있는 y<5인 레코드들을 P3으로 이동 P2는 원하지 않게 분할된 두 격자가 공용 SY SX

▶ 격자 화일의 레코드 삽입 예 g(8,8), h(13,9), i(6,4)를 삽입 i를 삽입 시 P3에 오버플로가 발생 x=5로 격자를 분할하여 P4를 할당하고 레코드를 분할 SY SX

▶ 격자 화일의 질의 예 메모리에 선형 눈금자를 유지 x=7, y=2인 데이타의 검색 예 두 번의 디스크 접근으로 데이타 접근 선형 눈금자(SX, SY)를 검사 x=7: SX의 두 번째 범위 y=2: SY의 첫 번째 범위 격자 배열 인덱스 (2, 1)을 결정 디스크에 있는 격자 배열 G[2,1]을 접근 데이타 페이지 번호 P3을 검색 디스크 데이타 페이지 P3을 접근 페이지 P3에서 데이타 d를 검색 두 번의 디스크 접근으로 데이타 접근 격자 배열과 데이타 페이지를 각각 한 번 (7, 2) SY(0, 5, 10) SX(0, 5, 10, 20) 1 2 1 2 3 G 1 2 3 2 1 P3 d(7,2) f(9,4) i(6,4)

▶ 격자 화일의 레코드 삭제 예 점 i(6,4)의 삭제 트윈 P3과 P4는 하나의 페이지 P3으로 합병 가능 x=5에 의한 분할을 제거 격자 블록 합병하고 선형 눈금자를 수정 SY SX

 사분 트리 (Quadtree) (1) 사분 트리(Quadtree) 사분 트리의 구분 표현 대상 데이타 공간을 반복적으로 분해하는 성질을 가진 계층적 자료 구조(hierarchical data structure)를 표현하는데 사용 사분 트리의 구분 표현하고자 하는 데이타의 유형 공간 분해 방법 해상도(resolution) – 분해 레벨 정도를 고정 또는 가변 표현 대상 데이타 점(point), 영역(region), 곡선(curve), 표면(surface), 볼륨(volume) 데이타 곡선이나 표면과 같이 개체의 경계를 표현하는 경우와 영역이나 볼륨과 같이 개체의 내부를 표현하는 경우에 따라 상이한 자료구조를 사용

 사분 트리 (Quadtree) (2) 공간 분해 방법 가장 많이 사용되는 사분 트리 이미지 공간 계층(image space hierarchy) : 각 레벨마다 공간을 일정 크기의 동일한 소공간으로 분해 객체 공간 계층(object space hierarchy) : 입력 데이타 값에 따라 가변적 크기의 공간으로 분해 가장 많이 사용되는 사분 트리 영역 사분 트리(region quadtree): 2차원의 영역 데이타를 표현 점 사분 트리(point quadtree): 다차원 점 데이타를 표현

▶ 영역 사분 트리(region quadtree) (1) 2차원 영역 데이타 표현에 많이 사용 이미지를 표현하는 2진수의 배열을 동일한 크기의 사분면 (quadrant)으로 연속적으로 분할하는 방법에 기초 영역을 표현하는 배열이 전부 1이나 0으로 구성되지 않으면 계속 서브사분면(subquadrant)으로 분할 가변 해상도 자료 구조 영역 사분트리 예 표현하려는 이미지 또는 영역(a) 영역을 23 x 23 크기의 이진 배열(b)로 표현 1은 영역에 포함된 그림 원소(picture element), 즉 화소(pixel)를 표현하고 0은 영역에 포함되지 않은 화소를 표현 이진 배열을 블록으로 표현(c) 블록들을 사분 트리로 표현(d)

▶ 영역 사분 트리 (2) 영역 사분트리 예

▶ 영역 사분 트리 (3) 영역 사분 트리의 루트 노드는 이진 배열 전체에 대응 한 노드의 자식 노드들은 각각 그 부모 노드가 표현하는 영역의 한 사분면을 표현 NW, NE, SW, SE 순으로 레이블을 붙임 리프 노드는 분할이 필요 없는 블록에 해당 흑색 노드(black node): 블록이 완전히 영역의 내부에 포함되어 있다는 것을 표현 1로 표현된 서브사분면 백색 노드(white node): 블록이 완전히 영역의 외부에 있다는 것을 표현 0으로 표현된 서브사분면 회색 노드(gray node): 단말이 아닌 노드 0과 1로 표현된 블록을 모두 포함

▶ 점 사분 트리 (point quadtree) 점 데이타를 표현 공간을 동일하지 않은 4개의 소공간(subspace)으로 분할 2차원 점 데이타에 대한 인덱스로 활용 단말 노드는 버켓의 포인터를 저장하고 인덱스 역할 트리에는 비교하는 점 데이타만 저장하고 전체 레코드는 인덱스에 의해 참조되는 버켓에 저장 2차원 점 데이타 레코드는 데이타 필드, x 좌표, y 좌표, 4개(NW, NE, SW, SE )의 포인타 필드를 갖는 노드로 표현 다차원 데이타를 위한 이원 탐색 트리의 일반화

▶ 도시 데이타 레코드 도시명 X Y 기타 정보 대전 35 40 … 진주 50 10 속초 60 75 강릉 80 65 서울 5 45 전주 25 경주 85 15 부산 90

▶ 점 사분 트리의 표현 단말 노드가 버켓의 포인터를 가질 때 인덱스 역할 (예) 버켓 1 : 0≤x<5와 45≤y<100의 값을 갖는 점 데이타 레코드들

▶ 점 사분 트리 (삽입) 이원 탐색 트리에 대한 삽입과 유사한 방법 최적 점 사분 트리 구성 방법 삽입할 레코드의 위치를 x, y 좌표 값을 바탕으로 탐색 노드의 좌표 값과 삽입할 데이타의 좌표 값을 비교 이 과정을 반복한 후, 도착한 리프 노드에 레코드를 삽입할 버킷의 주소 점 사분트리의 삽입 과정 예(그림) 최적 점 사분 트리 구성 방법 모든 점 데이타를 미리 알 수 있는 경우에 최적화가 가능 어떤 노드의 서브트리도 전체 노드 수의 반 이상을 갖지 않는 트리로 정의. 이를 위해, 모든 점 데이타들을 하나의 좌표축(x) 값으로 정렬하고 다른 좌표축(y) 값은 보조 키로 사용. 루트는 정렬 화일의 중간 값을 갖게 하고, 나머지는 4개 그룹으로 나누어 루트의 네 서브트리가 되도록 함.

▶ 점 사분 트리의 삽입 예

▶ 점 사분 트리의 삽입 예

▶ 점 사분 트리 (검색) 탐색 공간을 좁혀 나가는 기법 범위 탐색이나 근접 탐색에도 적용 한 레벨 내려 갈수록 탐색 공간은 1/4로 감소 리프 노드가 가리키는 버킷에서 원하는 데이타 검사 (예) “(95, 8)에 위치한 도시를 검색하라” 대전(35, 40)의 SE, 진주(85, 15)의 SE, 부산(90, 5)의 NE에 속하므로 버킷 23을 조사 범위 탐색이나 근접 탐색에도 적용 (예) “좌표 값 (83, 10)에서 거리 8이내에 존재하는 모든 도시를 검색하라” 대전(35, 40)의 SE를 검색하고 진주 (50, 10)의 NE와 SE만 검색하면 됨

▶ 점 사분 트리 (삭제) 삭제는 매우 복잡 이상적인 삭제 방법 삭제할 노드를 루트로 하는 서브 트리에 있는 모든 노드들이 재삽입 되어야 함 이상적인 삭제 방법 삭제할 노드 A를 어떤 노드 B로 대치한 후 삭제 이때, 노드 B는 노드 A를 루트로 하는 서브트리의 노드들이 속해 있는 사분면에 영향을 주지 않아야 한다. 이런 B가 존재 않을 경우 가장 근접한 것으로 대체하고 영역에 존재하는 점 데이타들을 재삽입

 R-트리 R-트리 모양이 불규칙한 공간 데이타 객체를 저장하기 위하여 B-트리를 다차원으로 확장시킨 완전 균형 트리 점, 선, 면, 도형 등 다양한 다차원 공간 데이타 객체를 저장하고 검색하기 위한 다차원 인덱스 구조 SAM: spatial access method R means rectangle? 모양이 불규칙한 공간 데이타 객체를 저장하기 위하여 객체의 최소 경계 사각형 MBR (Minimum Bounding Rectangle)을 구하여 이 MBR을 인덱스 엔트리로 저장 MBR대신 MBB (Minimum Bounding Box)로 표현하기도 함

▶ MBR MBR에는 MBR은 (x1min, y1min), (x1max, y1max) 와 같이 두 개의 2차원 점 데이타로 표현할 수 있기 때문에 저장 관리가 용이. 객체 검색 시에는 검색 대상이 되는 객체 MBR이 해당 영역에 속하는지를 먼저 비교하여 탐색 공간을 빠르게 축소 시킬 수 있음.

▶ MBR 예 불규칙 데이타 (x2max, y2max) (x1max, y1max) (x2min, y2min)

▶ R-트리의 개념 B-트리를 다차원 구조로 확장 디스크 페이지 단위로 데이타를 저장, 검색할 수 있어서 대용량 데이타에 대한 인덱스 구조로 적당 인덱스 구조는 B-트리와 같이 높이 균형 트리(height balanced tree) 리프 노드의 엔트리는 객체 MBR과 이 객체가 저장된 주소(포인터)로 구성 중간 노드의 엔트리는 자식 노드의 모든 MBR을 포함하는 보다 큰 MBR과 자식 노드에 대한 포인터로 구성

▶ R-트리의 특성 특성 루트 노드가 아닌 노드는 최소 m, 최대 M개의 인덱스 엔트리와 자식 포인터를 포함한다. 루트 노드는 리프가 아닌 이상 최소 2개의 자식 노드를 갖는다. 모든 리프 노드는 최소 m, 최대 M개의 인덱스 엔트리를 포함한다 리프 노드에 있는 각 인덱스 엔트리는 객체 데이타를 실제 공간적으로 포함하고 있는 MBR과 이 공간 객체가 저장된 페이지 주소를 포함한다. 완전 균형 트리이다. 즉 모든 리프 노드는 같은 레벨에 있다.

▶ R-트리의 특성 점 데이타를 주로 처리하는 k-d-B 트리는 데이타 자체를 분할하는 것이 아니라 영역을 분할하기 때문에 중간 노드들의 영역이 중첩될 수 없음 R-트리는 데이타 객체들을 분할하고 이들을 포함(cover) 하는 영역을 MBR로 표현하는 것이기 때문에 MBR이 서로 겹칠 수 있고 또 전체 영역 중에는 어떤 MBR에도 포함되지 않는 영역이 있을 수 있다. 따라서 R-트리는 중간 노드들이 표현하는 MBR이 중첩될 수 있기 때문에 임의의 크기의 객체를 분할 저장하기가 쉽다.

▶ 데이타 예 2차원 공간 데이타 객체 y r1 r13 r12 r2 r10 r14 r11 r6 r4 r9 r5 r7 r3 r8 x 2차원 공간 데이타 객체

▶ 시각적 MBR 예 M=3, m=2 R1 r1 R3 R2 r13 r12 R5 r2 r10 r14 r11 r6 r4 R4 R6

▶ R-트리 구성 공간 데이타 객체를 M=3, m=2인 시각적 MBR로 표현 실선으로 표시된 사각형 r1, r2, …,r14는 실제 데이타에 대한 데이타 객체 MBR을 표현. 가는 점선으로 표시된 사각형 R3, R4, R5, R6, R7은 각 리프 노드들이 포함하는 데이타 MBR 그룹에 대한 MBR을 표현. 굵은 점선으로 표시된 사각형 R1과 R2는 각각 자식 노드 엔트리들이 나타내는 MBR 그룹에 대한 중간 노드 MBR을 표현.

▶ R-트리 구성 예 R-트리 표현 a R1 R2 b c R3 R4 R5 R6 R7 d e f g h r1 r13 r14 r4

▶ R-트리 표현 예 루트 노드 a에는 자식 노드 b와 c가 나타내는 영역에 대한 MBR R1과 R2, 그리고 이들에 대한 포인터가 저장 R-트리 노드는 디스크 페이지로 저장되므로 포인터는 디스크 페이지 번호가 됨 중간 노드에는 그 자식 노드가 나타내는 하위 MBR과 그 노드에 대한 포인터가 저장 R-트리 노드 구조 리프 노드 구조: ((oid, mbr),…,) oid는 데이타베이스에서 객체 참조를 위한 객체 식별자이고 mbr은 데이타 객체의 MBR이다. 중간 노드 구조: ((p, mbr),…,) p는 트리의 하위 노드에 대한 포인터이고 mbr은 그 하위 노드에 있는 엔트리들이 나타내는 MBR들을 모두 포함하는 MBR이다.

▶ R-트리의 연산 검색 영역 검색 질의 k-NN 질의 삽입 삭제

▶ 영역 검색 연산 주어진 영역에 포함된 객체의 검색 1. 질의 영역을 트리의 루트 노드에서부터 하위 노드들의 MBR과 비교하여 중첩(overlap)되는 MBR을 비교해 가며 리프 노드까지 탐색 2. 리프 노드에서는 모든 객체 MBR을 비교하여 최종 목표 객체를 출력

▶ 영역 검색 알고리즘 Search(Node node, Region S) {     if (node.level > 0) { // 리프 노드가 아닌 경우            for (i=0; i<node.NumOfEntry; i++) {            if (IsOverlap(node.entry[i].MBR, S)) {               Search(node.entry[i].child, S); // 하위 노드 검사            }        }     }else {   // 리프 노드인 경우        for (i=0; i<node.NumOfEntry; i++) {           if (IsOverlap(node.entry[i].MBR, S)) {              PrintResult(node.entry[i].child);  // 결과 발견           }        }     }  }

▶ 영역 검색 예 1 Q1 영역 검색 질의: Q1 영역과 중첩되는 모든 객체를 검색하라 영역 R1에만 포함 R1 r1 R3

▶ 영역 검색 예 1 a R1 R2 b c R3 R4 R5 R6 R7 d e f g h r1 r13 r14 r4 r6 r2

▶ 영역 검색 예 2 Q2 영역 검색 질의: Q2 영역과 중첩되는 객체를 검색하라 영역 R1과 R2에 중첩 R1 r1 R3

▶ 영역 검색 예 2 영역 검색 질의: Q2 영역과 중첩되는 객체를 검색하라 영역 R1과 R2에 중첩 a R1 R2 b c d e f g h r1 r13 r14 r4 r6 r2 r10 r12 r5 r7 r8 r3 r9 r11 r4만 최종결과로 출력

▶ k-NN(k-Nearest Neighbor) 질의 점 Q1에서부터 가장 가까운 3 개의 객체를 검색하라 R1 r1 R3 R2 r13 Q1 r12 R5 r2 r10 r14 r11 r6 r4 R4 R6 r9 r5 r7 r3 R7 r8

▶ k-NN 질의 실행 방법 우선순위 큐(priority queue)를 이용 우선순위 큐는 엔트리가 우선순위 순으로 정렬되도록 구현 큐 엔트리는 <p, d>, 즉 트리 노드의 포인터 p와 질의 점과 노드의 거리 d로 구성 우선순위는 질의 점과 노드의 거리 d가 가까운 것이 우선순위가 높음. 초기에 루트 노드를 삽입 우선순위 큐로부터 원소를 삭제하여 객체가 아닌 MBR인 경우에는 이 MBR에 포함된 엔트리를 모두 삽입한다. 삭제한 원소가 객체인 경우에는 결과로 포함시킨다. 결과에 k 개의 객체가 포함될 때까지 반복한다. k-NNSearch(root-node, point, k) 알고리즘

▶ k-NN 질의 수행 예 우선 순위 큐(우선순위로 정렬) 질의 결과 (a) Root (b) R1 R2 (c) R2 R4 R3 (d) R4 R5 R6 R3 R7 (e) r6 R5 r4 R6 R3 R7 (f) R5 r4 R6 R3 R7 r6 (g) r12 r4 R6 r10 R3 R7 r2 r6 (h) r4 R6 r10 R3 R7 r2 r6 r12 (i) R6 r10 R3 R7 r2 r6 r12 r4

▶ k-NN 질의 알고리즘 kNNSearch(Node Root, Point P, int k) { NumResult = 0;    PQ.clear(); // 우선순위 큐 초기화    distance = CaculateDistance(Root, P);    PQ.insert(distance, Root, NODE_TYPE);  // 우선순위 큐에 루트 삽입 while (NumResult<k, && !PQ.isEmpty()) {       node = PQ.delete();       if (IsNodeType(p)) {           // 노드일 경우 하위 엔트리를 우선순위 큐에 모두 추가             for (i=0; i<node.NumberOfEntry(); i++) {         distance = CaculateDistance(node.entry[i], P);          if (node.level==0) {                 // 리프노드의 엔트리는 데이타 객체                 PQ.insert(distance, node.entry[i], OBJECT_TYPE);           }else                 PQ.insert(distance, node.entry[i], NODE_TYPE);           }           }        }else { // 결과 발견          PrintResult(node);          NumResult ++;        }    } }

▶ R-트리에서의 삽입 데이타 객체를 삽입해야 될 리프 노드를 찾은 뒤 여유 공간이 있으면 바로 삽입. 만일 최대 엔트리 수 M 개의 엔트리가 저장되어 이미 만원이면 이 노드를 분할하고 엔트리들도 분할 저장. 분할된 노드에 대한 인덱스 엔트리를 부모 노드에 삽입. 부모 노드가 새로운 엔트리를 수용할 공간이 없으면 다시 분할하고 분할된 노드에 대한 인덱스 엔트리를 부모 노드에 저장.

▶ 삽입 알고리즘 리프 노드 선택 리프 노드에 데이타 저장 트리 재조정 트리 높이 증가 데이타를 삽입할 적절한 리프 노드 선택. chooseLeaf() 알고리즘을 사용 리프 노드에 데이타 저장 선택된 리프 노드에 빈 공간이 있으면 새로운 엔트리 E를 저장. 빈 공간이 없는 경우 노드를 분할하여 E를 저장하고 트리를 조정 트리 재조정 데이타가 삽입된 경로를 따라 새로운 데이타 삽입으로 변경된 MBR들을 조정. 노드가 분할된 경우에는 새로운 MBR을 결정하고 그 부모 노드들을 따라가며 분할 된 노드에 대한 엔트리를 삽입. 이때 중간 노드에 자유 공간이 없으면 다시 분할이 계속될 수 있음 트리 높이 증가 만일 루트 노드가 분할되어야 하면 루트 노드를 분할하고 분할 된 두 노드에 대한 엔트리를 새로운 루트 노드를 만들어 저장. 이 경우 트리의 높이가 1 증가한다.

▶ 삽입 알고리즘 - 리프 노드 선택 chooseLeaf() 알고리즘 ① 루트 노드 T를 N으로 설정 ② N이 리프 노드이면 N을 반환 ③ N이 리프 노드가 아니면 N의 엔트리 가운데 E가 삽입되었을 때 MBR의 크기가 최소로 증가하는 엔트리를 F로 선택. 만일 증가하는 크기가 같으면 MBR의 크기가 작은 엔트리를 F로 선택 (면적 최소) ④ 선택된 엔트리 F가 가리키는 노드를 N으로 하여 알고리즘 ②부터 반복 수행 MBR이 크면 질의 영역과 중첩되는 MBR이 많아질 수 있으므로 검사 시간이 많이 걸린다. MBR이 작으면 질의 영역과 중첩되는 MBR이 적게될 수 있으므로 검사 시간이 적게 걸린다 데이타 삽입은 리프 노드 선택이나 노드 분할 방법에 따라 R-트리의 성능에 영향을 준다.

▶ 삽입으로 인한 노드 분할 방법 분할 된 두 노드 MBR의 합이 최소가 되도록 분할  검색 시 불필요한 노드 탐색을 줄여 질의 성능을 높일 수 있음 4개의 데이타 객체(a)를 2개의 노드에 2개씩 분할 저장하는 방법 예 r2 r3 r2 r3 r2 r3 r2 r3 r1 r4 r1 r4 r1 r4 r1 r4 (a) (b) {r1,r2},{r3,r4} (c) {r1,r3},{r2,r4} (d) {r1,r4},{r2,r3}

▶ R-트리에서의 삽입 예 r15를 삽입하는 경우 R1 R3 r1 R2 r13 r12 R5 r2 r15 r14 r10 r6

▶ 삽입 전 R-트리 a R1 R2 b c R3 R4 R5 R6 R7 d e f g h r1 r13 r14 r4 r6 r2

▶ R-트리의 데이타 (객체 r15) 삽입 예 ① 리프 노드 선택 : ② 리프 노드 h에 데이타 저장 : ③ 트리 재조정 : 객체 r15 MBR을 R7 MBR에 삽입할 때 MBR의 크기가 가장 작게 증가되므로 리프 노드 h를 선택. ② 리프 노드 h에 데이타 저장 : 노드 h는 만원이 되어 MBR R8과 R9로 분할하여 노드 h와 i로 저장. 객체 r15는 노드 i에 저장 ③ 트리 재조정 : 부모 노드에 저장되어있는 노드 h의 MBR R7을 새로운 MBR R8로 변경하고 새로 분할된 노드 i에 대한 엔트리를 추가. 노드 c역시 여유 공간이 없으므로 다시 R5와 R6을 포함하는 노드 c와 R8과 R9를 포함하는 노드 j로 분할. 다시 트리를 재조정하면 결국 마지막으로 분할된 노드 c의 부모인 루트 노드 a에 노드 c의 MBR을 R10으로 변경하고, 빈 공간에 노드 j의 MBR인 R11을 삽입하면 트리의 조정이 모두 끝나게 된다.

▶ 객체 r15 삽입 결과 R1 r1 R3 R10 r13 R11 r12 R5 r2 r15 r10 r14 r11 r6 r4 R4

▶ 객체 r15 삽입 결과 a R1 R10 R11 b c j R3 R4 R5 R6 R8 R9 d e f g h i r1 r13

▶ R-트리에서의 데이타 삭제 리프 노드 탐색: 삭제할 데이타 객체를 포함하고 있는 리프 노드를 탐색. 해당 데이타 삭제: 리프 노드에서 해당 데이타 객체를 삭제. 언더플로 처리: 리프 노드의 엔트리 수가 m보다 작게 되면 언더플로가 발생하게 된다. 언더플로가 발생한 노드를 삭제하고 그 노드의 모든 엔트리들을 트리에 다시 삽입 삭제로 인한 언더플로는 트리의 루트 방향으로 파급될 수 있음. m개 이하의 엔트리를 갖는 중간 노드 역시 노드를 삭제하고 트리에 다시 삽입. 중간 노드를 재 삽입할 경우 이 노드는 원래의 레벨에 삽입되어야 함. 이때 MBR이 변하게 될 경우 트리의 루트까지 경로를 따라 MBR을 조정. 트리가 모두 조정된 뒤에 트리의 루트가 단지 하나의 자식만을 갖게 될 경우 루트의 자식 노드를 새로운 루트 노드로 만들고 기존의 루트 노드를 삭제. 이 경우 트리의 높이가 1 낮아짐.

▶ R-트리의 분석 k 차원의 데이타를 처리하기 위한 B-트리의 확장으로서 중간 노드와 리프 노드로 구성된 높이 균형 트리 리프 노드 : 공간 데이타에 대한 인덱스 엔트리를 저장 중간 노드 : 하위 노드의 엔트리들이 표현하는 MBR들을 완전히 포함하는 상위 MBR 엔트리들을 저장 탐색 연산: 포함과 중첩 관계가 중요 포함(coverage)과 중첩(overlap) 관계가 최소일 때 가장 효율적임 최소 포함은 죽은 공간(dead space) 즉, 빈 공간의 양을 감소시킴 중첩 : 높이 h, 레벨 h-i에서 k개의 노드가 중첩되면, 최악은 리프 노드에 대해 k 개의 경로를 접근해야 됨. 따라서 i에서 ik 페이지 접근이 필요. N개의 인덱스를 갖는 R-트리의 높이는 최대 logmN  -1 왜냐하면 각 노드의 분기율이 적어도 m이 되기 때문 루트를 제외한 모든 노드에서 최악의 공간 활용도 (space utilization)는 m/M 트리의 높이를 감소시키면 공간 활용도는 증가

R-트리의 변형 트리 성능 향상이나 다양한 응용 지원을 위한 여러 가지 R-트리의 변형 트리들이 있음 k-d-B 트리의 특징을 접목 R*-트리 R-트리의 삽입, 삭제 알고리즘을 개선

▶ R+-트리 여러 MBR과 중첩되는 데이타는 여러 노드에 중복 저장 R-트리와의 차이점 데이타를 저장할 때는 데이타 일부가 아니라 데이타 객체 전체를 저장 R-트리와의 차이점 ① R+-트리의 노드는 적어도 1/2이상의 엔트리가 채워진다는 것을 보장을 하지 않음. ② R+-트리의 중간 노드들의 MBR은 중첩되지 않음. ③ R+-트리의 데이타 객체는 분할될 수 있으나 이 경우 그 데이타 객체 전체가 둘 이상의 리프 노드에 중복 저장될 수 있음.

▶ R+-트리의 예 데이타 객체 r4와 r11이 분할되게 MBR 설정 R1 r1 R3 R2 r13 R7 r12 r2 r10

▶ R+-트리의 예 데이타 r4, r11이 MBR 설정 시 분할된 경우 중복저장 a R1 R2 b c R3 R4 R5 R6 d e f g h i r1 r13 r4 r6 r14 r4 r5 r8 r4 r7 r12 r2 r10 r11 r3 r9 r11 중복저장

▶ R+-트리의 검색 예 • Q1 점 Q1을 포함하고 있는 객체를 검색하라 R1 r1 R3 R2 r13 R7 r12 r2

▶ R+-트리의 검색 예 3개의 노드 방문 점 Q1을 포함하고 있는 객체를 검색하라 a R1 R2 b c R3 R4 R5 R6 e d f g h i r1 r13 r4 r6 r14 r4 r5 r8 r4 r7 r12 r2 r10 r11 r3 r9 r11 3개의 노드 방문

▶ R+-트리의 삽입, 삭제 연산 일반적으로 R-트리보다 복잡 데이타 삽입 데이타 삭제 하나의 데이타 객체가 여러 리프 노드에 중복될 수 있기 때문 데이타 삽입 데이타 객체를 삽입해야 될 모든 리프 노드를 찾음. 삽입하는 데이타 객체의 MBR이 중간 노드의 MBR과 중첩되면 중첩되는 MBR을 통하는 경로로 도달하는 모든 리프 노드에 중복 저장. 삽입하는 데이타 객체의 MBR이 기존의 중간 노드 MBR에 포함되지 않으면 기존 MBR을 조정. 리프 노드에 삽입할 때 만원이면 노드를 분할. 데이타 삭제 해당 객체가 하나 이상의 리프 노드에 저장될 수 있으므로 해당하는 모든 리프 노드에서 해당 객체를 삭제해야 함. 삭제가 많이 발생한 뒤에는 공간 활용도가 매우 나빠질 수 있음. 이런 경우에는 성능을 고려하여 주기적으로 서브트리들을 재구성해야 함.

▶ R+-트리의 장단점 장점 단점 MBR이 중첩될 때의 문제점을 해결 불필요한 노드 탐색을 줄임  노드의 공간 활용도가 나빠짐 리프 노드에 중복되어 저장되는 데이타의 수는 데이타의 분포나 데이타 개수의 영향을 받으므로 데이타의 분포나 데이타의 개수에 따라 R+-트리의 성능이 저하될 수 있음.

▶ R*-트리 기본적인 구조와 연산은 R-트리와 동일 삽입, 삭제 시 부모 노드의 MBR이 효율적으로 확장될 수 있도록 알고리즘을 개선 R-트리 질의 처리 성능 향상을 위한 고려 사항 ① MBR의 면적(covered area)을 최소화 ② MBR 간의 중첩 영역(overlap)을 최소화 ③ 둘레 길이(margin) 최소화: 정사각형에 가까운 모양의 MBR이 좋음 ④ 저장공간 이용률(storage utilization)의 최적화 : 트리의 노드 수를 줄이고, 트리의 높이를 낮게 유지함

▶ R*-트리의 개선 사항 chooseLeaf() 알고리즘 개선 노드 분할 알고리즘 변경: 2단계 heuristic을 사용 중간 노드 선택 시에는 최소 면적이 최소인 MBR을 우선 리프 노드 선택 시에는 중첩 영역의 증가가 최소가 되는 MBR을 우선 노드 분할 알고리즘 변경: 2단계 heuristic을 사용 분할 축(split axis) 선택: 분할된 두 MBR의 둘레 길이 합이 최소가 되게 하는 축 분할 인덱스(split index) 선택 : 엔트리들을 분할할 때 중첩 영역 증가 최소화 (같을 경우 면적 합이 최소화)

▶ R*-트리의 개선 사항 노드 분할 전에 강제 재삽입 전략 R*-트리의 장점 오버플로 발생시 노드의 M+1개의 데이타 중 트리의 중심에서 멀리 떨어진 p개(보통 30%)를 강제로 트리에 재 삽입 이점 ① 중첩 영역이 감소 ② 분할 비용이 감소 ③ MBR 모양이 정사각형에 근사 R*-트리의 장점 R-트리의 기본 구조나 연산을 그대로 유지하고 있으므로 구현이 비교적 간단 삽입, 삭제 알고리즘 개선으로 질의 성능이 우수