10. 다차원공간화일 DBLAB, SNU v 다차원데이타 u 다차원데이타 (multidimensional data) 전통적인 1차원데이타레코드가아니라 CAD (computer aided design) 나지리정보시스템 (geographical information sys

Transcription

1 10. 다차원공간화일 v 다차원데이타 u 다차원데이타 (multidimensionl dt) 전통적인 1차원데이타레코드가아니라 CAD (computer ided design) 나지리정보시스템 (geogrphicl informtion system) 에서의선 (line), 면 (plne), 위치 (loction) 와같은데이타 다차원데이타를나타내는 (x, y) 또는 (x, y, z) 는차원당하나의값 u 다차원데이타는단일키화일구조로처리불가 u 다차원데이타의접근을위해서는다차원인덱스 (multidimensionl index) 구조가필요 2

2 다차원공간화일이란? u 여러개의필드 ( 차원 ) 를동시에키로사용하는화일 u 다차원공간화일을트리로표현 k-d 트리 ( 75) k-d-b 트리 ( 81) 격자화일 (Grid File) ( 84) 사분트리 (Qudtree) ( 84) R- 트리 ( 84), R + - 트리 ( 87), R * - 트리 ( 90) 3 다차원인덱스 인덱스 (multidimensionl index) 기법 (multidimensionl index) 기법 1. PAM (Point Access Method) 다차원점데이타 (multidimensionl point dt) 를공간에서저장, 검색하는점접근방법 k-d 트리, k-d-b 트리, 격자화일 (grid file) 2. SAM (Sptil Access Method) 선 (line), 면 (plne), 다각형 (polygon), 다면체 (polyhedron) 같은다차원공간데이타 (multidimensionl sptil dt) 를저장, 검색할수있는공간접근방법 R-트리, R * -트리, R + -트리 4

3 v k-d 트리 u k-d(k-dimensionl) 트리 k 차원의점데이타를인덱스하는구조 dt structure for ssocitive serch 이원탐색트리를다차원공간 (multidimensionl spce) 으로확장한것 다차원이원탐색트리 (multidimensionl binry serch tree) 기본구조와알고리즘은이원탐색트리와유사 분기조건은 < 이아니라 임 트리의레벨을내려가면서차원의필드값을차례로번갈아가며비교 예 ) 3차원의데이타 (x,y,z) 의경우 : x à y à z à x à y à z à,,, u 특징 메인메모리상에서동작하는인덱스구조 소규모의다차원점데이타 (multidimensionl point dt) 를인덱싱할때적합 (PAM) 균형트리가아님 5 k-d 트리에서의데이타삽입 u 다음과같은 2차원공간의점 (x,y) 데이타를, b, c, j의순서로 k-d 트리에삽입하는경우 점 b c 위치 (5, 4) (2, 7) (9, 5) b j f (10,10) d e f g h i (3, 1) (7, 2) (9, 7) (1, 4) (4, 3) (8, 2) g d h e i c j (4, 8) (0,0) 6

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

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

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

7 k-d 트리에서의데이타검색 u 위치 (6,2) 의점을검색하라 루트 (5,4) 에서시작하여점 c(9,5), 점 e(7,2) 를검사한다음에왼쪽서브트리로분기시도. 그러나분기실패 ( 널 ) 로해당점레코드가없다는것을확인. u k-d 트리의높이가 h라하면최악의검색시간은 O(h) 가됨 u k-d 트리에서의삭제는복잡 삭제된노드의서브트리들에대한재구성요구발생 13 k-d 트리의단점 u 균형트리가아니므로데이타의입력순서나분포에따라트리의높이가극단적으로높아지면검색성능이저하가능 예 ) g, d, b, e, h,, f, c, i, j 의순서로입력된예 g (1,4) :x (10,10) d (3,1) b (2,7) :y :x b j f e (7,2) i (8,2) h (4,3) :y :x g c j (4,8) (5,4) :y h e i f (8,7) :x d c (9,5) :y (0,0) 14

8 v k-d-b(k-dimensionl B-tree) 트리 u k-d 트리와 B-트리의특성을결합 디스크기반으로다차원점데이타를효율적으로검색, 저장하기위한구조 디스크페이지크기의노드들로구성된다원탐색트리 (multiwy serch tree) 균형트리 루트에서리프노드까지의탐색경로길이가모두동일 u 다중키레코드검색을위한인덱스레코드구조 : (key 0, key 1,, key K-1, 주소 ) key i 는도메인i에속하는탐색키 k는차원 ( 필드 ) 수 u k-d-b 트리는범위질의 (rnge query) 를지원 범위질의는각탐색키값이 min i 과 mx i 로명세됨 min i key i mx i, 0 i k-1 15 k-d-b 트리 u 점 (point) 는카티션프로덕트, ( 도메인 0 도메인 1 도메인 K-1 ) 의한원소 u 영역 (region) 은다음 C와같은성질을만족하는모든점 x i, 0 i (k-1) 들의집합 C: min i x i mx i, 0 i (k-1), min i, mx i 는도메인i의원소 u 점은 x i, 0 i (k-1) 만저장 k 개의필드값을가진하나의레코드인스턴스에해당 u 영역은 min i 와 mx i, 0 i (k-1) 를저장 k 개의범위조건을만족하는레코드의집합 16

9 k-d-b 트리 u 2 개의필드 ( 차원 ) 로표현된레코드의예 키와몸무게는탐색을위한도메인 선수 키 170 몸무게 65 필드 2 ( 몸무게 ) b c d e f g h 필드 1( 키 ) 영역은 ([165, 180], [60, 70]) 17 k-d-b 트리의구조 u k-d-b 트리는루트페이지와자식페이지로구성 u 페이지는영역페이지와점페이지로구분 영역페이지 (region pge) : < 영역, 페이지-id> 쌍의엔트리들을포함하는노드 점페이지 (point pge) : < 점, 주소 > 쌍의엔트리들을포함하는단말노드. 주소는점데이타레코드가저장되어있는주소. u 페이지크기는디스크페이지크기 엔트리삽입으로오버플로가일어나면분할연산이필요 엔트리삭제로언더플로가일어나면합병연산이필요 18

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

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

12 k-d-b 트리의연산 ( 삽입 ) u 원소값 x i 에따라영역 I x x I y 를분할하는방법 x 이구간 (intervl) I x 에포함되는경우에구간 I x =[min x, mx x ] 는영역 I x x I y 를다음과같이두소영역으로분할 1 [min x, x ] x I y : 왼쪽영역 2 [x, mx x ] x I y : 오른쪽영역 u 원소값 x i 에따라점페이지분할방법 x 값에따라점페이지를오른쪽점페이지와왼쪽점페이지로분할 모든 < 점, 주소 > 쌍에대해 x의값과 x 의값을비교하여오른쪽또는왼쪽점페이지로이동하고원래의점페이지는삭제 23 k-d-b 트리의연산 ( 삽입 ) x 에의한점페이지분할 분할원소 분할전 분할후 왼쪽페이지 오른쪽페이지 24

13 k-d-b 트리의연산 ( 삽입 ) u 원소값 x i 에따라영역페이지분할방법 x 값에따라영역페이지를오른쪽영역페이지와왼쪽영역페이지로분할 모든 < 영역, 페이지-id> 쌍엔트리를오른쪽또는왼쪽페이지로이동하고원래의페이지는삭제 u 영역의엔트리들을분할하는방법 원래영역페이지내의각 < 영역, 페이지 -id> 에대해 1 영역이 x 의왼편에있으면 < 영역, 페이지 -id> 를왼쪽영역페이지로이동 2 영역이 x 의오른편에있으면 < 영역, 페이지 -id> 를오른쪽영역페이지로이동 3 x 이영역중간을가로지르면그영역을 x 값에따라두개의소영역으로분할하고각각오른쪽페이지와왼쪽페이지에첨가한다. 25 k-d-b 트리의연산 ( 삽입 ) x 에의한영역페이지분할 분할원소 * * 분할전 * 표시된부분이분할된다 분할후 26

14 k-d-b 트리의연산 ( 삽입 ) u 인덱스레코드 < 점, 주소 > 쌍을삽입하는알고리즘 1 root-id 가널 (null) 이면점페이지를생성하고 < 점, 주소 > 엔트리를저장. 2 < 점, 주소 > 쌍이삽입되어야할페이지를완전일치질의수행방식으로탐색. 페이지에여유공간이있으면 < 점, 주소 > 쌍을페이지에삽입하고종료. 3 삽입하려는점페이지에오버플로가발생하면엔트리들을등분할수있는적절한도메인 i의원소 x i 를선택하여페이지를분할하고엔트리들을이동. 4 분할된페이지의부모영역페이지에있는원래의 < 영역, 페이지 -id> 를새로운 < 왼쪽영역, 페이지 -id>, < 오른쪽페이지, 페이지 -id> 로대체한다. 이엔트리의증가로페이지가오버플로되면이영역페이지를분할하고단계 4를다시실행한다. 5 루트페이지가분할하게되면새로운루트페이지를생성하여조정한다. 이때 k-d-b 트리의높이는하나증가된다. 27 k-d-b 트리의연산 ( 삭제 ) u 점페이지에서 < 점, 주소 > 쌍을완전일치질의로검색후삭제 u 공간이용률을높이기위해재구성 합병 : 두영역의엔트리들을하나의큰페이지로통합 언더플로 : 두형제영역을합병또는엔트리들의재분배 u 두영역의합이보다큰직사각형형태의영역을구성하게되면합병가능 (joinble) u 합병이불가능한경우 영역 A 와 B 또는 A 와 C B A C 28

15 v 격자화일 (Grid file) u 격자화일 공간상의점데이타를저장하는다차원인덱스구조 (multidimensionl index structure) 전체공간을격자 (grid) 로분할하여격자단위로데이타를저장 격자의크기는데이타의삽입에따라분할되어작은격자로변환 u 특징 디스크기반 대용량의다차원데이타를처리 해싱기반 일반적으로두번의디스크접근으로데이타검색 29 격자화일의구성 u K-차원격자화일 k개의선형눈금자 (liner scle) 와 k-차원의격자배열 (grid rry) 로구성된격자디렉터리 (grid directory) 로관리 이디렉터리가해싱역할을수행 u 선형눈금자 (liner scle) 각차원별눈금정보를표현하며메인메모리에유지 u 격자배열 (grid rry) 선형눈금자에의해분할된격자블록 (grid block) 으로구성 각격자블록에는데이타페이지를가리키는페이지번호 (pge number) 가저장 격자배열과페이지는디스크에저장 30

16 격자화일의구성 u 격자블록과데이타페이지 기본적으로하나의격자블록당하나의데이타페이지 두개이상의격자블록이하나의데이타페이지를공유가능 u x 축과 y 축으로표현되는 2차원격자화일예 x 축은 (0, 5, 10, 15, 20) 의선형눈금자 y 축은 (0, 5, 10) 의선형눈금자 격자배열은각축의선형눈금자에따라구성 각데이타페이지는최대 3개의점데이타를저장 31 격자화일의구성 10 5 b i g f h c e P1 b(4,6) g(8,8) P2 c(16,2) e(18,8) h(13,9) P3 d(7,2) f(9,4) i(6,4) 0 d (2,4) P 선형눈금자격자배열데이타페이지 32

17 격자화일의레코드삽입예 u 예제데이타 데이타 위치 (2, 4) b (4, 6) c d e (16, 2) (7, 2) (18, 8) b g h e f (9, 4) g h i (8, 8) (13, 9) (6, 4) i d f c 33 격자화일의레코드삽입예 u 점 (2,4), b(4,6), c(16,2) 를삽입 하나의격자블록을통해페이지 P1에저장되고 P1은만원 10 (2,4) b(4,6) P1 c(16,2) SY b c SX 34

18 격자화일의레코드삽입예 u 점 d(7,2) 를삽입 페이지 P1 이오버플로가되어격자를분할 각축 (xis) 을순환적으로분할 x=10 으로격자블록을분할하고페이지 P2 를할당 분할된두페이지 P1 과 P2 를트윈 (twin) 이라함 x>10 인레코드들은 P2 로이동 10 (2,4) b(4,6) d(7,2) P1 SY b c(16,2) P2 c 0 d SX 35 격자화일의레코드삽입예 u 점 e(18,8), f(9,4) 를삽입 f를삽입시페이지 P1에오버플로가발생 y=5로격자를분할하고페이지 P3을할당 P1에있는 y<5인레코드들을 P3으로이동 P2는원하지않게분할된두격자가공용 10 b(4,6) P1 SY 5 b f c e P2 c(16,2) e(18,8) P3 (2,4) d(7,2) f(9,4) 0 d SX 36

19 격자화일의레코드삽입예 u g(8,8), h(13,9), i(6,4) 를삽입 i를삽입시 P3에오버플로가발생 x=5로격자를분할하여 P4를할당하고레코드를분할 SY 10 5 b i g f h c e P1 b(4,6) g(8,8) P2 c(16,2) e(18,8) h(13,9) P3 d(7,2) f(9,4) i(6,4) 0 d (2,4) P SX 37 격자화일의질의예 u 메모리에선형눈금자를유지 u x=7, y=2 인데이타의검색예 선형눈금자 (SX, SY) 를검사 x=7: SX 의두번째범위 y=2: SY 의첫번째범위 격자배열인덱스 (2, 1) 을결정 디스크에있는격자배열 G[2,1] 을접근 데이타페이지번호 P3 을검색 디스크데이타페이지 P3 을접근 페이지 P3 에서데이타 d 를검색 u 두번의디스크접근으로데이타접근 격자배열과데이타페이지를각각한번 (7, 2) SY(0, 5, 10) SX(0, 5, 10, 20) P3 G d(7,2) f(9,4) i(6,4) 38

20 격자화일의레코드삭제예 u 점 i(6,4) 의삭제 트윈 P3과 P4는하나의페이지 P3으로합병가능 P3의트윈 P1은합병된격자블록만사용 x=5에의한분할을제거 격자블록합병하고선형눈금자를수정 SY 10 5 b g f h c e P1 b(4,6) g(8,8) P2 c(16,2) e(18,8) h(13,9) P3 d(7,2) f(9,4) (2,4) 0 d SX 39 v 사분트리 (Qudtree) (1) u 사분트리 (Qudtree) 공간을반복적으로분해하는성질을가진계층적자료구조 (hierrchicl dt structure) 를표현하는데사용 u 사분트리의구분 표현하고자하는데이타의유형 공간분해방법 해상도 (resolution) 분해레벨정도를고정또는가변 u 표현대상데이타 점 (point), 영역 (region), 곡선 (curve), 표면 (surfce), 볼륨 (volume) 데이타 곡선이나표면과같이개체의경계를표현하는경우와영역이나볼륨과같이개체의내부를표현하는경우에따라상이한자료구조를사용 40

21 v 사분트리 (Qudtree) (2) u 공간분해방법 이미지공간계층 (imge spce hierrchy) : 각레벨마다공간을일정크기의동일한소공간으로분해 객체공간계층 (object spce hierrchy) : 입력데이타값에따라가변적크기의공간으로분해 u 가장많이사용되는사분트리 영역사분트리 (region qudtree): 2차원의영역데이타를표현 점사분트리 (point qudtree): 다차원점데이타를표현 41 영역사분트리 (region qudtree) (1) u 2차원영역데이타표현에많이사용 u 이미지를표현하는 2진수의배열을동일한크기의사분면 (qudrnt) 으로연속적으로분할하는방법에기초 영역을표현하는배열이전부 1이나 0으로구성되지않으면계속서브사분면 (subqudrnt) 으로분할 가변해상도자료구조 u 영역사분트리예 표현하려는이미지또는영역 () 영역을 2 3 x 2 3 크기의이진배열 (b) 로표현 1은영역에포함된그림원소 (picture element), 즉화소 (pixel) 를표현하고 0은영역에포함되지않은화소를표현 이진배열을블록으로표현 (c) 블록들을사분트리로표현 (d) 42

22 영역사분트리 (2) 영역사분트리예 () (b) (c) 레벨 3 A NW NE SW SE 레벨 2 1 B C E 레벨 D F 19 레벨 (d) 43 영역사분트리 (3) u 영역사분트리의루트노드는이진배열전체에대응 한노드의자식노드들은각각그부모노드가표현하는영역의한사분면을표현 NW, NE, SW, SE 순으로레이블을붙임 리프노드는분할이필요없는블록에해당 흑색노드 (blck node): 블록이완전히영역의내부에포함되어있다는것을표현 1로표현된서브사분면 백색노드 (white node): 블록이완전히영역의외부에있다는것을표현 0으로표현된서브사분면 회색노드 (gry node): 단말이아닌노드 0과 1로표현된블록을모두포함 44

23 점사분트리 (point qudtree) u 점데이타를표현 u 공간을동일하지않은 4개의소공간 (subspce) 으로분할 u 2차원점데이타에대한인덱스로활용 단말노드는버켓의포인터를저장하고인덱스역할 트리에는비교하는점데이타만저장하고전체레코드는인덱스에의해참조되는버켓에저장 u 2차원점데이타레코드는 데이타필드, x 좌표, y 좌표, 4개 (NW, NE, SW, SE ) 의포인타필드를갖는노드로표현 u 다차원데이타를위한이원탐색트리의일반화 45 도시데이타레코드 도시명 X Y 기타정보 대전 진주 속초 강릉 서울 전주 경주 부산

24 점사분트리의표현 (0,100) (60,75) 속초 (100,100) (5,45) 서울 (35,40) 대전 (80,65) 강릉 (25,35) 전주 (50,10) 진주 (85,15) 경주 Y (0,0) X (90,5) 부산 (100,0) 대전 서울 속초 전주 진주 (1) (2) (3) (4) (5) (6) (7) 강릉 (12) (13) (14) (15) (16) 경주 (21) 부산 (8) (9)(10)(11) (17)(18)(19)(20) (22)(23)(24)(25) 단말노드가버켓의포인터를가질때인덱스역할 ( 예 ) 버켓 1 : 0 x<5 와 45 y<100 의값을갖는점데이타레코드들 47 점사분트리 ( 삽입 ) u 이원탐색트리에대한삽입과유사한방법 삽입할레코드의위치를 x, y 좌표값을바탕으로탐색 노드의좌표값과삽입할데이타의좌표값을비교 이과정을반복한후, 도착한리프노드에레코드를삽입할버킷의주소 점사분트리의삽입과정예 ( 그림 ) u 최적점사분트리구성방법 모든점데이타를미리알수있는경우에최적화가가능 어떤노드의서브트리도전체노드수의반이상을갖지않는트리로정의. 이를위해, 모든점데이타들을하나의좌표축 (x) 값으로정렬하고다른좌표축 (y) 값은보조키로사용. 루트는정렬화일의중간값을갖게하고, 나머지는 4개그룹으로나누어루트의네서브트리가되도록함. 48

25 점사분트리의삽입예 (0,100) (100,100) 대전 () (35,40) 대전 Y (0,0) (0,100) X (100,0) (100,100) 대전 SE (b) (35,40) 대전 진주 (50,10) 진주 Y (0,0) X (100,0) 49 점사분트리의삽입예 (0,100) (60,75) 속초 (100,100) 대전 (c) (35,40) 대전 속초 진주 (50,10) 진주 Y (0,0) X (100,0) (0,100) (60,75) 속초 (100,100) 대전 (d) (35,40) 대전 (80,65) 강릉 속초 진주 (50,10) 진주 강릉 Y (0,0) X (100,0) 50

26 점사분트리 ( 검색 ) u 탐색공간을좁혀나가는기법 한레벨내려갈수록탐색공간은 1/4로감소 리프노드가가리키는버킷에서원하는데이타검사 ( 예 ) (95, 8) 에위치한도시를검색하라 대전 (35, 40) 의 SE, 진주 (85, 15) 의 SE, 부산 (90, 5) 의 NE에속하므로버킷 23을조사 u 범위탐색이나근접탐색에도적용 ( 예 ) 좌표값 (83, 10) 에서거리 8 이내에존재하는모든도시를검색하라 대전 (35, 40) 의 SE 를검색하고 진주 (50, 10) 의 NE 와 SE 만검색하면됨 51 점사분트리 ( 삭제 ) u 삭제는매우복잡 삭제할노드를루트로하는서브트리에있는모든노드들이재삽입되어야함 u 이상적인삭제방법 삭제할노드 A를어떤노드 B로대치한후삭제 이때, 노드 B 는노드 A 를루트로하는서브트리의노드들이속해있는사분면에영향을주지않아야한다. 이런 B 가존재않을경우가장근접한것으로대체하고영역에존재하는점데이타들을재삽입 52

27 v R-트리 u R-트리 B-트리를다차원으로확장시킨완전균형트리 점, 선, 면, 도형등다양한다차원공간데이타객체를저장하고검색하기위한다차원인덱스구조 SAM: sptil ccess method R mens rectngle? u 모양이불규칙한공간데이타객체를저장하기위하여객체의최소경계사각형 MBR (Minimum Bounding Rectngle) 을구하여이 MBR 을인덱스엔트리로저장 u MBR 대신 MBB (Minimum Bounding Box) 로표현하기도함 53 MBR u MBR 에는 1. 객체자체를나타내는객체 MBR 2. 몇개의객체 MBR 그룹을나타내는리프노드 MBR 3. 몇개의 MBR 그룹을나타내는중간노드 MBR u MBR 은 (x1 min, y1 min ), (x1 mx, y1 mx ) 와같이두개의 2차원점데이타로표현할수있기때문에저장관리가용이. u 객체검색시에는검색대상이되는객체 MBR 이해당영역에속하는지를먼저비교하여탐색공간을빠르게축소시킬수있음. 54

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

29 R-트리의특성 u 특성 M: 한노드가저장할수있는최대엔트리수 m(<=m/2): 한노드가저장해야되는최소엔트리수 1. 루트노드가아닌노드는최소 m, 최대 M개의인덱스엔트리와자식포인터를포함한다. 2. 루트노드는리프가아닌이상최소 2개의자식노드를갖는다. 3. 모든리프노드는최소 m, 최대 M개의인덱스엔트리를포함한다 4. 리프노드에있는각인덱스엔트리는객체데이타를실제공간적으로포함하고있는 MBR과이공간객체가저장된페이지주소를포함한다. 5. 완전균형트리이다. 즉모든리프노드는같은레벨에있다. 57 R-트리의특성 u 점데이타를주로처리하는 k-d-b 트리는데이타자체를분할하는것이아니라영역을분할하기때문에중간노드들의영역이중첩될수없음 u u R- 트리는데이타객체들을분할하고이들을포함 (cover) 하는영역을 MBR 로표현하는것이기때문에 MBR 이서로겹칠수있고또전체영역중에는어떤 MBR 에도포함되지않는영역이있을수있다. 따라서 R- 트리는중간노드들이표현하는 MBR 이중첩될수있기때문에임의의크기의객체를분할저장하기가쉽다. 58

30 데이타예 y r1 r13 r12 r2 r14 r6 r10 r5 r4 r9 r11 r8 r7 2 차원공간데이타객체 r3 x 59 시각적 MBR 예 R1 r1 R3 R2 r13 r12 R5 r2 r14 r6 r10 R4 r5 r4 R6 r9 r11 r8 r7 r3 R7 M=3, m=2 60

31 R-트리구성 u 공간데이타객체를 M=3, m=2 인시각적 MBR 로표현 실선으로표시된사각형 r1, r2,,r14는실제데이타에대한데이타객체 MBR을표현. 가는점선으로표시된사각형 R3, R4, R5, R6, R7은각리프노드들이포함하는데이타 MBR 그룹에대한 MBR을표현. 굵은점선으로표시된사각형 R1과 R2는각각자식노드엔트리들이나타내는 MBR 그룹에대한중간노드 MBR을표현. 61 R-트리구성예 R- 트리표현 R1 R2 b R3 R4 c R5 R6 R7 d e f g h r1 r13 r14 r4 r6 r2 r10 r12 r5 r7 r8 r3 r9 r11 62

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

33 영역검색연산 u 주어진영역에포함된객체의검색 1. 질의영역을트리의루트노드에서부터하위노드들의 MBR 과비교하여중첩 (overlp) 되는 MBR 을비교해가며리프노드까지탐색 2. 리프노드에서는모든객체 MBR 을비교하여최종목표객체를출력 65 영역검색알고리즘 Serch(Node node, Region S) { if (node.level > 0) { // 리프노드가아닌경우 for (i=0; i<node.numofentry; i++) { if (IsOverlp(node.entry[i].MBR, S)) { Serch(node.entry[i].child, S); // 하위노드검사 } } }else { // 리프노드인경우 for (i=0; i<node.numofentry; i++) { if (IsOverlp(node.entry[i].MBR, S)) { PrintResult(node.entry[i].child); // 결과발견 } } } } 66

34 영역검색예 1 R1 영역검색질의 : Q1 영역과중첩되는모든객체를검색하라 영역 R1 에만포함 r1 R3 r13 Q1 r12 R5 r2 R2 r14 r6 r10 R4 r5 r4 R6 r9 r11 r8 r7 r3 R7 67 영역검색예 1 R1 R2 b c R3 R4 R5 R6 R7 d e f g h r1 r13 r14 r4 r6 r2 r10 r12 r5 r7 r8 r3 r9 r11 r13 을최종결과로출력 68

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

36 k-nn(k-nerestnerest Neighbor) 질의 u 질의점으로부터가장가까운 k개의객체를검색하는질의 u 3-NN 질의예 점 Q1에서부터가장가까운 3 개의객체를검색하라 R1 r1 R3 R2 r13 Q1 r12 R5 r2 r14 r6 r10 R4 r5 r4 R6 r9 r11 r8 r7 r3 R7 71 k-nn 질의실행방법 u 우선순위큐 (priority queue) 를이용 우선순위큐는엔트리가우선순위순으로정렬되도록구현 큐엔트리는 <p, d>, 즉트리노드의포인터 p와질의점과노드의거리 d로구성 우선순위는질의점과노드의거리 d가가까운것이우선순위가높음. 초기에루트노드를삽입 우선순위큐로부터원소를삭제하여객체가아닌 MBR인경우에는이 MBR에포함된엔트리를모두삽입한다. 삭제한원소가객체인경우에는결과로포함시킨다. 결과에 k 개의객체가포함될때까지반복한다. u k-nnserch(root-node,, point, k) 알고리즘 72

37 k-nn 질의수행예 우선순위큐 ( 우선순위로정렬 ) 질의결과 () (b) Root R1 R2 (c) (d) R2 R4 R3 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 73 k-nn 질의알고리즘 knnserch(node Root, Point P, int k) { NumResult = 0; PQ.cler(); // 우선순위큐초기화 distnce = CculteDistnce(Root, P); PQ.insert(distnce, Root, NODE_TYPE); // 우선순위큐에루트삽입 while (NumResult<k, &&!PQ.isEmpty()) { node = PQ.delete(); if (IsNodeType(p)) { // 노드일경우하위엔트리를우선순위큐에모두추가 for (i=0; i<node.numberofentry(); i++) { distnce = CculteDistnce(node.entry[i], P); if (node.level==0) { // 리프노드의엔트리는데이타객체 PQ.insert(distnce, node.entry[i], OBJECT_TYPE); }else PQ.insert(distnce, node.entry[i], NODE_TYPE); } } }else { // 결과발견 PrintResult(node); NumResult ++; } } } 74

38 R-트리에서의삽입 u 데이타객체를삽입해야될리프노드를찾은뒤여유공간이있으면바로삽입. u 만일최대엔트리수 M 개의엔트리가저장되어이미만원이면이노드를분할하고엔트리들도분할저장. u 분할된노드에대한인덱스엔트리를부모노드에삽입. u 부모노드가새로운엔트리를수용할공간이없으면다시분할하고분할된노드에대한인덱스엔트리를부모노드에저장. 75 삽입알고리즘 리프노드선택 데이타를삽입할적절한리프노드선택. chooselef() 알고리즘을사용 리프노드에데이타저장 선택된리프노드에빈공간이있으면새로운엔트리 E 를저장. 빈공간이없는경우노드를분할하여 E 를저장하고트리를조정 트리재조정 데이타가삽입된경로를따라새로운데이타삽입으로변경된 MBR 들을조정. 노드가분할된경우에는새로운 MBR 을결정하고그부모노드들을따라가며분할된노드에대한엔트리를삽입. 이때중간노드에자유공간이없으면다시분할이계속될수있음 트리높이증가 만일루트노드가분할되어야하면루트노드를분할하고분할된두노드에대한엔트리를새로운루트노드를만들어저장. 이경우트리의높이가 1 증가한다. 76

39 삽입알고리즘 - 리프노드선택 u chooselef() 알고리즘 1 루트노드 T를 N으로설정 2 N이리프노드이면 N을반환 3 N이리프노드가아니면 N의엔트리가운데 E가삽입되었을때 MBR의크기가최소로증가하는엔트리를 F로선택. 만일증가하는크기가같으면 MBR의크기가작은엔트리를 F로선택 ( 면적최소 ) 4 선택된엔트리 F가가리키는노드를 N으로하여알고리즘 2부터반복수행 u MBR 이크면질의영역과중첩되는 MBR 이많아질수있으므로검사시간이많이걸린다. u MBR 이작으면질의영역과중첩되는 MBR 이적게될수있으므로검사시간이적게걸린다 u 데이타삽입은리프노드선택이나노드분할방법에따라 R-트리의성능에영향을준다. 77 삽입으로인한노드분할방법 u 분할된두노드 MBR 의합이최소가되도록분할 à 검색시불필요한노드탐색을줄여질의성능을높일수있음 u 4개의데이타객체 () 를 2개의노드에 2개씩분할저장하는방법예 r1 r4 r1 r4 r1 r4 r1 r4 r2 r3 r2 r3 r2 r3 r2 r3 () (b) {r1,r2},{r3,r4} (c) {r1,r3},{r2,r4} (d) {r1,r4},{r2,r3} 78

40 R-트리에서의삽입예 r15 를삽입하는경우 R1 r1 R3 R2 r13 r12 R5 r2 r14 r6 r10 r15 R4 r5 r4 R6 r9 r11 r8 r7 r3 R7 79 삽입전 R-트리 R1 R2 b R3 R4 c R5 R6 R7 d e f g h r1 r13 r14 r4 r6 r2 r10 r12 r5 r7 r8 r3 r9 r11 80

41 R-트리의데이타 ( 객체 r15) 삽입예 1 리프노드선택 : 객체 r15 MBR 을 R7 MBR 에삽입할때 MBR 의크기가가장작게증가되므로리프노드 h 를선택. 2 리프노드 h에데이타저장 : 노드 h 는만원이되어 MBR R8 과 R9 로분할하여노드 h 와 i 로저장. 객체 r15 는노드 i 에저장 3 트리재조정 : 부모노드에저장되어있는노드 h 의 MBR R7 을새로운 MBR R8 로변경하고새로분할된노드 i 에대한엔트리를추가. 노드 c 역시여유공간이없으므로다시 R5 와 R6 을포함하는노드 c 와 R8 과 R9 를포함하는노드 j 로분할. 다시트리를재조정하면결국마지막으로분할된노드 c 의부모인루트노드 에노드 c 의 MBR 을 R10 으로변경하고, 빈공간에노드 j 의 MBR 인 R11 을삽입하면트리의조정이모두끝나게된다. 81 객체 r15 삽입결과 R1 r1 R3 R10 r13 r12 R5 r2 R11 r14 r6 r10 r15 R4 r5 r4 R6 r9 r11 r8 r7 r3 R8 R9 82

42 객체 r15 삽입결과 R1 R10R11 b R3 R4 R5 R6 c R8 R9 j d e f g r1 r13 r14 r4 r6 r2 r10 r12 r5 r7 r8 h r3 r9 r11 r15 i 83 R-트리에서의데이타삭제 1 리프노드탐색 : 삭제할데이타객체를포함하고있는리프노드를탐색. 2 해당데이타삭제 : 리프노드에서해당데이타객체를삭제. 3 언더플로처리 : 리프노드의엔트리수가 m보다작게되면언더플로가발생하게된다. 언더플로가발생한노드를삭제하고그노드의모든엔트리들을트리에다시삽입 삭제로인한언더플로는트리의루트방향으로파급될수있음. m 개이하의엔트리를갖는중간노드역시노드를삭제하고트리에다시삽입. 중간노드를재삽입할경우이노드는원래의레벨에삽입되어야함. 이때 MBR 이변하게될경우트리의루트까지경로를따라 MBR 을조정. 트리가모두조정된뒤에트리의루트가단지하나의자식만을갖게될경우루트의자식노드를새로운루트노드로만들고기존의루트노드를삭제. 이경우트리의높이가 1 낮아짐. 84

43 R-트리의분석 u k 차원의데이타를처리하기위한 B-트리의확장으로서중간노드와리프노드로구성된높이균형트리 리프노드 : 공간데이타에대한인덱스엔트리를저장 중간노드 : 하위노드의엔트리들이표현하는 MBR 들을완전히포함하는상위 MBR 엔트리들을저장 u 탐색연산 : 포함과중첩관계가중요 포함 (coverge) 과중첩 (overlp) 관계가최소일때가장효율적임 최소포함은죽은공간 (ded spce) 즉, 빈공간의양을감소시킴 중첩 : 높이 h, 레벨 h-i 에서 k 개의노드가중첩되면, 최악은리프노드에대해 k 개의경로를접근해야됨. 따라서 i 에서 ik 페이지접근이필요. u N개의인덱스를갖는 R-트리의높이는최대 élog m N ù -1 왜냐하면각노드의분기율이적어도 m이되기때문 u 루트를제외한모든노드에서최악의공간활용도 (spce utiliztion) 는 m/m 트리의높이를감소시키면공간활용도는증가 85 R-트리의변형트리 u 성능향상이나다양한응용지원을위한여러가지 R-트리의변형트리들이있음 u 대표적 R-트리변형트리 R + - 트리 R- 트리에서노드간의중첩영역을없앰 k-d-b 트리의특징을접목 R * - 트리 R- 트리의삽입, 삭제알고리즘을개선 86

44 R + -트리 u 여러 MBR 과중첩되는데이타는여러노드에중복저장 à데이타가분할되게 MBR을설정할수있음 à중간노드 MBR들은중첩이필요없음 à데이타를저장할때는데이타일부가아니라데이타객체전체를저장 u R-트리와의차이점 1 R + -트리의노드는적어도 1/2이상의엔트리가채워진다는것을보장을하지않음. 2 R + -트리의중간노드들의 MBR은중첩되지않음. 3 R + -트리의데이타객체는분할될수있으나이경우그데이타객체전체가둘이상의리프노드에중복저장될수있음. 87 R + -트리의예 R1 r1 R3 R2 r13 r12 R7 r2 r14 R4 r6 r5 r4 R6 r10 r9 r11 R5 r8 r7 r3 R8 데이타객체 r4 와 r11 이분할되게 MBR 설정 88

45 R + -트리의예 데이타 r4, r11 이 MBR 설정시분할된경우 R1 R2 b R3 R4 R5 c R6 R7 R8 d e f g h i r1 r13 r4 r6 r14 r4 r5 r8 r4 r7 r12 r2 r10 r11 r3 r9 r11 중복저장 89 R + -트리의검색예 R1 점 Q1 을포함하고있는객체를검색하라 r1 R3 R2 r13 r12 R7 r2 r14 R4 Q1 r6 r5 R5 r8 r4 r7 R6 r10 r3 r9 R8 r11 90

46 R + -트리의검색예 점 Q1 을포함하고있는객체를검색하라 R1 R2 b R3 R4 R5 c R6 R7 R8 d e f g h i r1 r13 r4 r6 r14 r4 r5 r8 r4 r7 r12 r2 r10 r11 r3 r9 r11 3 개의노드방문 91 R + -트리의삽입, 삭제연산 u 일반적으로 R-트리보다복잡 하나의데이타객체가여러리프노드에중복될수있기때문 u 데이타삽입 데이타객체를삽입해야될모든리프노드를찾음. 삽입하는데이타객체의 MBR 이중간노드의 MBR 과중첩되면중첩되는 MBR 을통하는경로로도달하는모든리프노드에중복저장. 삽입하는데이타객체의 MBR 이기존의중간노드 MBR 에포함되지않으면기존 MBR 을조정. 리프노드에삽입할때만원이면노드를분할. u 데이타삭제 해당객체가하나이상의리프노드에저장될수있으므로해당하는모든리프노드에서해당객체를삭제해야함. 삭제가많이발생한뒤에는공간활용도가매우나빠질수있음. 이런경우에는성능을고려하여주기적으로서브트리들을재구성해야함. 92

47 R + -트리의장단점 u 장점 MBR이중첩될때의문제점을해결 불필요한노드탐색을줄임 u 단점 R + -트리의경우노드의분할이상위노드뿐만아니라다시하위노드로파급될수있음. 즉중간노드의분할은하위노드전체를분할하게될수도있음. à 노드의공간활용도가나빠짐 리프노드에중복되어저장되는데이타의수는데이타의분포나데이타개수의영향을받으므로데이타의분포나데이타의개수에따라 R + - 트리의성능이저하될수있음. 93 R * -트리 u 기본적인구조와연산은 R-트리와동일 u 삽입, 삭제시부모노드의 MBR 이효율적으로확장될수있도록알고리즘을개선 u R-트리질의처리성능향상을위한고려사항 1 MBR 의면적 (covered re) 을최소화 2 MBR 간의중첩영역 (overlp) 을최소화 3 둘레길이 (mrgin) 최소화 : 정사각형에가까운모양의 MBR 이좋음 4 저장공간이용률 (storge utiliztion) 의최적화 : 트리의노드수를줄이고, 트리의높이를낮게유지함 94

48 R * -트리의개선사항 u chooselef() 알고리즘개선 중간노드선택시에는최소면적이최소인 MBR을우선 리프노드선택시에는중첩영역의증가가최소가되는 MBR을우선 u 노드분할알고리즘변경 : 2 단계 heuristic 을사용 분할축 (split xis) 선택 : 분할된두 MBR의둘레길이합이최소가되게하는축 분할인덱스 (split index) 선택 : 엔트리들을분할할때중첩영역증가최소화 ( 같을경우면적합이최소화 ) 95 R * -트리의개선사항 u 노드분할전에강제재삽입전략 오버플로발생시노드의 M+1개의데이타중트리의중심에서멀리떨어진 p개 ( 보통 30%) 를강제로트리에재삽입 이점 1 중첩영역이감소 2 분할비용이감소 3 MBR 모양이정사각형에근사 u R * -트리의장점 R-트리의기본구조나연산을그대로유지하고있으므로구현이비교적간단 삽입, 삭제알고리즘개선으로질의성능이우수 96