쉽게배우는알고리즘 5 장. 검색트리 htt://academy.hanb.co.k 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 - 2 - 한빛미디어 1
학습목표 검색에서레코드와키의역할을구분한다. 이진검색트리에서의검색 삽입 삭제작업의원리를이해한다. 이진검색트리의균형이작업의효율성에미치는영향을이해하고, 레드블랙트리의삽입 삭제작업의원리를이해한다. B- 트리의도입동기를이해하고검색 삽입 삭제작업의원리를이해한다. 검색트리관련작업의점근적수행시간을이해한다. 일차원검색의기본원리와다차원검색의연관성을이해한다. - 3 - 한빛미디어 레코드, 키, 검색트리 레코드 ecod 개체에대해수집된모든정보를포함하고있는저장단위 e.g., 사람의레코드 주민번호, 이름, 집주소, 집전화번호, 직장전화번호, 휴대폰번호, 최종학력, 연소득, 가족상황등의정보포함 필드 field 레코드에서각각의정보를나타내는부분 e.g., 위사람의레코드에서각각의정보를나타내는부분 검색키 each key 또는키 key 다른레코드와중복되지않도록각레코드를대표할수있는필드 키는하나의필드로이루어질수도있고, 두개이상의필드로이루어질수도있다 검색트리 each tee 각노드가규칙에맞도록하나씩의키를갖고있다 이를통해해당레코드가저장된위치를알수있다 2
Binay Seach Tee (BST) 각노드는하나씩의키값을갖는다. 각노드의키값은다르다. 최상위레벨에루트노드가있고, 각노드는최대두개의자식을갖는다. 임의의노드의키값은자신의왼쪽자식노드의키값보다크고, 오른쪽자식의키값보다작다. BST 의예 40 45 20 40 20 35 10 25 35 45 10 25 (a) (b) 3
서브트리의예 20 40 10 25 35 45 (a) 20 40 10 25 35 45 (b) 노드 의왼쪽서브트리 (c) 노드 의오른쪽서브트리 BST 에서의검색 teeseach(t, ) t: 트리의루트노드 : 검색하고자하는키 // 성공하면해당노드를리턴, 실패하면 NIL 을리턴 { if (t=nil o key[t]=) then etun t; if ( < key[t]) then etun teeseach(left[t], ); ele etun teeseach(ight[t], ); } 4
BST 검색에서의재귀적관점 t left[t] ight[t] BST 검색에서실패 / 성공하는경우 성공 검색이 leaf 노드까지가지않고, 중간에어떤노드 의키값이 와같아지는순간 을리턴하고종료 실패 검색이루트노드에서 leaf 노드까지진행된다. leaf 노드는자식이없으므로 teeseach(nil, ) 가되어 NIL 을리턴하고종료. 그림 5-4 참조. 교재 P 132 5
BST 에서의삽입의예 1:, 20, 25, 40, 10, 35 순으로삽입됨 20 20 20 40 25 25 (a) (b) (c) (d) 20 40 20 40 10 25 (e) 10 25 35 (f) BST 에서의삽입의예 2: 10, 20, 25,, 40, 45 순으로삽입됨 10 20 25 35 40 (f) 6
BST 에서의삽입개요 // 같은키값이트리내에없다고가정 teeinet(t, ) t: 트리의루트노드 : 삽입하고자하는키 // 작업완료후루트노드의포인터를리턴한다. { if (t=nil) then { // 검색에실패했음. Leaf까지내려옴. key[] ; : 새노드 etun ; } if ( < key(t)) then {left[t] teeinet(left[t], ); etun t;} ele {ight[t] teeinet(ight[t], ); etun t;} } BST 에서의삽입상세버전 // 같은키값이트리내에없다고가정 teeinet(t, ) t: 트리의루트노드 : 삽입하고자하는키 // 작업완료후루트노드의포인터를리턴한다. { if (t=nil) then { // 검색에실패했음. Leaf까지내려옴. key[] ; left[] NIL; left[] NIL; : 새노드 etun ; } if ( < key(t)) then {left[t] teeinet(left[t], ); etun t;} ele {ight[t] teeinet(ight[t], ); etun t;} } 7
BST 에서의삭제 3 가지경우에따라다르게처리한다. Cae 1 : 이리프노드인경우 Cae 2 : 의자식노드가하나인경우 Cae 3 : 의자식노드가두개인경우 t: 트리의루트노드 : 삭제하고자하는노드 BST 에서의삭제개요 Sketch-TeeDelete(t, ) // t: 트리의루트노드 // : 삭제하고자하는노드 { if ( 이리프노드 ) then Cae 1 그냥 을버린다 ; ele if ( 의자식이하나만있음 ) then Cae 2 의부모가 의자식을직접가리키도록한다 ; ele Cae 3 의오른쪽서브트리의최소원소노드 를삭제하고, 를 자리에놓는다 ; } 8
삭제의예 : Cae 1 55 55 15 15 8 28 90 8 28 90 3 18 3 38 48 50 은리프노드이므로지우고, 단지 의부모노드에서 을가리키고있던포인터를 NIL 로만바꿔주면됨 38 48 50 33 33 32 36 (a) 의자식이없음 32 36 (b) 단순히 을제거한다 삭제의예 : Cae 2 55 55 55 15 15 15 8 28 90 8 28 90 8 28 90 3 18 3 18 3 18 48 38 48 50 38 48 50 의부모노드에서 을가리키고있던포인터를 의자식을가리키도록바꿔주면됨 33 38 50 33 33 32 36 32 36 32 36 (a) 의자식이하나뿐임 (b) 을제거 (c) 자리에 의자식을놓는다 9
삭제의예 : Cae 3 3 8 55 15 28 18 45 41 38 33 32 36 90 48 50 3 8 15 18 32 33 41 55 38 36 45 48 50 90 자리에옮겨놓아도 BST 의성질을전혀깨뜨리지않는원소는무엇일까? 왼쪽서브트리원소들보다크고, 오른쪽서브트리의원소들보다작아야함. 트리전체에딱두개가존재!!! ü 의왼쪽서브트리에서가장큰원소 ü 의오른쪽서브트리에서가장작은원소 (a) 의직후원소 를찾는다 (b) 을없앤다 55 55 15 15 8 90 8 90 ü 의왼쪽서브트리에서가장큰원소 의직전원소임 오른자식존재불가 ü 의오른쪽서브트리에서가장작은원소 의직후원소임 왼쪽자식존재불가 3 18 45 41 38 33 48 50 3 18 38 33 32 36 41 45 48 50 32 36 (c) 를 자리로옮긴다 (d) 가있던자리에 의자식을놓는다 10
teedelete(t,, ) { if ( = t) then oot deletenode(t); ele if ( = left[]) then left[] deletenode(); ele ight[] deletenode(); BST 에서의삭제상세버전 이루트노드인경우 이루트가아닌경우 이 의왼쪽자식 이 의오른쪽자식 } deletenode() // 의부모노드에매달릴노드를리턴함 { if (left[] = ight[] = NIL) then etun NIL; Cae 1 ele if (left[] = NIL and ight[] NIL) then etun ight[]; Cae 2-1 ele if (left[] NIL and ight[] = NIL) then etun left[]; Cae 2-2 ele { Cae 3 ight[]; while (left[] NIL) {aent ; left[];} key[] key[]; if ( = ight[]) then ight[] ight[]; ele left[aent] ight[]; etun ; } } t: 트리의루트노드 : 삭제하고자하는노드 : 의부모노드 Red-Black Tee (RB Tee) BST 의모든노드에블랙또는레드의색을칠하되다음의레드블랙특성을만족해야한다 1 2 3 4 루트는블랙이다모든리프는블랙이다노드가레드이면그노드의자식은반드시블랙이다루트노드에서임의의리프노드에이르는경로에서만나는블랙노드의수는모두같다 ü 여기서리프노드는일반적인의미의리프노드와다르다. 모든 NIL 포인터가 NIL 이라는리프노드를가리킨다고가정한다. 11
BST 를 RB Tee 로만든예 NIL NIL NIL NIL NIL NIL NIL NIL NIL (a) BST 의한예 (b) (a) 를 RB Tee 로만든예 NIL (c) 실제구현시의 NIL 노드처리방법 RB Tee 에서의삽입 BST 에서의삽입과같다. 다만삽입후삽입된노드를레드로칠한다. ( 이노드를 라하자 ) 만일 의부모노드 의색상이 블랙이면아무문제없다. 레드이면레드블랙특성 3 이깨진다. 그러므로 가레드인경우만고려하면된다 12
RB Tee 에서의삽입 주어진조건 : i ed 2 는반드시블랙이고, 의형제노드도반드시블랙이다 의형제노드인 는레드 / 블랙이모두가능하므로 의색상에따라두가지로나눈다 Cae 1: 가레드 Cae 2: 가블랙 2? Cae 1: 가레드 와 의색상을 ed à black 으로, 2 의색상은 black à ed 2 가루트면 2 의색상을다시 black 을바꾸고끝. 2 가루트가아니면 2 의부모색상을확인해야함. ü 2 의부모색상이 black: RB 트리속성만족됨! ü 2 의부모색상이 ed: 지금과똑같은경우이므로 ecuion 돌면됨. Cae 1 2 2 : 색상이바뀐노드 ü 2 에서방금과같은문제가발생할수있다 : ecuive oblem! 13
Cae 2-1: 가블랙이고, 가 의오른쪽자식 를중심으로왼쪽으로회전한다. 여전히레드블랙특성 ƒ 을위반한다. Cae 2-2 로간다. Cae 2-1 2 Cae 2-2로! 2 y y 2 1 2 1 Cae 2-2: 가블랙이고, 가 의왼쪽자식 2 를중심으로오른쪽으로회전하고, 와 2 의색상을맞바꾼다. : 색상이바뀐노드 Cae 2-2 2 2 y y ü 삽입완료! 14
RB Tee 에서의삭제 삭제노드의자식이없거나 1개만을가진노드로제한해도된다 텍스트의.146의첫문단참조 삭제노드를 m이라하자 삭제노드가레드이면아무문제없다 삭제노드가블랙이라도 ( 유일한 ) 자식 가레드이면문제없다 삭제후 의색상을블랙으로바꾸면됨. m m m 이블랙이면 m 의부모색상은상관없게됨. 이제까다로운경우는 m 과 의색상이모두블랙일때이다. 이때 m 이삭제되면 는 m 의부모 의자식이되고, 레드블랙특성 4 가깨진다.? m -1 옆의 -1은루트에서 를통해리프에이르는경로에서블랙노드의수가하나모자람을의미한다. -1 l??? 의주변상황에따라처리방법이달라진다 m 삭제후문제발생 ( 레드블랙특성 4 위반 ) 15
경우의수나누기 i ed i black -1-1 Cae 1 - 가레드면 는반드시블랙임. Cae 2 - 가블랙이면 는블랙, 레드모두가능. Cae 1-1 -1 l Cae 1-2 -1 l Cae 1-3 -1 l Cae 2-1 -1 l Cae 2-2 -1 l Cae 2-3 -1 l Cae 2-4 -1 l 의색상만다른데 의색상이처리방법에영향을미치지않으므로통합처리할수있음 16
Cae 1-1 -1 l Cae *-2-1 l Cae *-3-1 l Cae 2-1 -1 l ü 최종적으로 5 가지경우로나뉜다 Cae 2-4 -1 l 각경우에따른처리 ü Cae 1-1 단순히 와 의색상을맞바꾼다. 에이르는경로상에블랙노드가 1 개늘었으므로 OK 에이르는경로상의블랙노드개수는변화없으므로 OK Cae 1-1 -1 l l 17
ü Cae *-2 를중심으로왼쪽으로회전하고, 와 의색상을맞바꾸고, 의색상을레드에서블랙으로바꿈 Ø 에이르는경로상에블랙노드가 1 개늘었으므로 OK Ø 1,2,3 으로표시된이르는서브트리까지경로상의블랙노드개수는변화없으므로 OK Cae *-2-1 1 2 3 1 2 3 ü Cae *-3 를오른쪽으로회전하고, l 과 의색상을맞바꾼다. 이제 Cae *-2 와같은모양이되었으므로 Cae *-2 로이동하여마무리처리한다. Cae *-3-1 l Cae *-2 로 -1 1 l 1 2 2 18
ü Cae 2-1 ü 단순히 의색상을블랙에서레드로바꾼다. ü 이제 를지나는경로에서도블랙노드가 1 개부족 è 를지나가는경로전체에서블랙노드가하나부족함 ü Recuive oblem. 를문제발생노드로하여재귀적으로다시시작한다. Cae 2-1 -1 l l -1 ü Cae 2-4 를중심으로왼쪽으로회전하고, 와 의색상을맞바꾼다. l 과 을경유하는경로는문제가없다. 다만문제가발생한 의부모노드의색상이블랙에서레드로바뀌었음 è Cae 1 에해당 v 색상조합을따져 Cae 1-1, Cae 1-2, Cae 1-3 중의하나로이동한다. Cae 2-4 -1 l Cae 1-1, Cae 1-2, Cae 1-3 중의하나로 -1 l 19
B-Tee 검색트리가방대하면검색트리를메모리에모두올려놓고사용할수없을수있음 검색트리를디스크에저장해두고사용해야함 ( 외부검색트리형태 ) 디스크의접근단위는블록 ( 페이지 ) 디스크에한번접근하는시간은수십만명령어의처리시간과맞먹는다 검색트리가디스크에저장되어있다면트리의높이를최소화하는것이유리 예 ) 10 억개내외의키를관리해야한다면? BST 가균형이잘맞았다고해도트리깊이가 레벨정도됨. 이럴때한노드에자식이두개가아닌여러개가붙을수있다면? 한노드에 256 개의자식이붙을수있으면깊이가 5 정도될것임. B- 트리는다진검색트리가균형을유지하도록하여최악의경우디스크접근횟수를줄인것 B- 트리 == 외부다진검색트리 다진검색트리 key 0 key 1 key 2 key k-1 T 0 T 1 T 2 T 3 T k key i-1 < T i < key i 20
B-Tee B-Tee 는균형잡힌다진검색트리로다음의성질을만족 루트를제외한모든노드는 ~ k 개의키를갖는다. 분기수를최대한늘리되균형을위해최대허용량의반이상은채우자는의미 모든리프노드는같은깊이를가진다. B- 트리의노드구조 부모노드의페이지 <key 0, 0 > <key 1, 1 > <key k-1, k-1 > 21
B- 트리를통해 Recod 에접근하는과정 <key 0, 0 > <key i, i > 키 key i 를가진 ecod 페이지 i B-Tee 에서의검색 노드의여러키중일치하는것이있는지확인해야함. key i-1 < < key i 인두키를찾아그사이에있는따라내려가며찾아야함. 22
B-Tee 에서의삽입개요 BTeeInet(t, ) { 를삽입할리프노드 을찾는다 ; 를 에삽입한다 ; t : 트리의루트노드 : 삽입하고자하는키 if (에오버플로우발생 ) then cleaoveflow(); } cleaoveflow() { if (의형제노드중여유가있는노드가있음 ) then {의남는키를넘긴다 }; ele { 을둘로분할하고가운데키를부모노드로넘긴다 ; if ( 부모노드 에오버플로우발생 ) then cleaoveflow(); } } B-Tee 에서삽입의예 (k=5 일때 ) (a) 7 13 25 34 1 2 3 4 6 8 10 15 17 19 20 27 28 33 37 38 40 41 45 9, 31 삽입 (b) 7 13 25 34 1 2 3 4 6 8 9 10 15 17 19 20 27 28 31 33 37 38 40 41 45 5 삽입 23
(c) 7 13 25 34 1 2 3 4 5 6 8 9 10 15 17 19 20 27 28 31 33 37 38 40 41 45 오버플로우! 바로오른쪽형제노드에공간여유가있으니키를하나넘긴다 ( 재분배 : editibution). 맨오른쪽의 6 을형제노드에바로넘기면 B- 트리성질이훼손됨. 부모노드에있는 7 을넘기고그자리에 6 을놓는다. 6 13 25 34 1 2 3 4 5 7 8 9 10 15 17 19 20 27 28 31 33 37 38 40 41 45 39 삽입 (d) 39 삽입 6 13 25 34 오버플로우! 1 2 3 4 5 7 8 9 10 15 17 19 20 27 28 31 33 37 38 39 40 41 45 바로옆형제노드에공간여유가없음 è 분할해야함 맨가운데키 40 을부모노드로넘기고나머지를분할함 노드가늘어났으므로부모노드에분기를위한키가하나더필요하기때문 6 13 25 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 27 28 31 33 37 38 39 41 45 23, 35, 36 삽입 분할! 24
(e) 23, 35, 36 삽입 6 13 25 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 31 33 35 36 37 38 39 41 45 32 삽입 (f) 6 13 25 34 40 32 삽입 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 31 32 33 35 36 37 38 39 41 45 오버플로우! 오버플로우! 6 13 25 31 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 32 33 35 36 37 38 39 41 45 31 분할! 분할! 6 13 25 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 32 33 35 36 37 38 39 41 45 25
B-Tee 에서의삭제 BTeeDelete(t,, v) t : 트리의루트노드 { : 삭제하고자하는키 if (v가리프노드아님 ) then { v : 를갖고있는노드 의직후원소 y를가진리프노드를찾는다 ; 와 y를맞바꾼다 ; } 리프노드에서 를제거하고이리프노드를 이라한다 ; if (에서언더플로우발생 ) then cleaundeflow(); } cleaundeflow() { if ( 의형제노드중키를하나내놓을수있는여분을가진노드가있음 ) then { 이키를넘겨받는다 ;} ele { 의형제노드와 을합병한다 ; if ( 부모노드 에언더플로우발생 ) then cleaundeflow(); } } (a) B-Tee 에서삭제의예 15 4 8 19 22 1 2 3 5 6 7 9 10 16 18 20 21 24 25 26 7 삭제 (b) 15 4 8 19 22 1 2 3 5 6 9 10 16 18 20 21 24 25 26 4 삭제 26
(c) 4, 5 교환 15 5 8 19 22 1 2 3 4 6 9 10 16 18 20 21 24 25 26 4 제거 5 8 15 19 22 1 2 3 6 9 10 16 18 20 21 24 25 26 언더플로우! 형제노드중여분의키를내놓을수있는지본다 왼쪽노드가여분이있으므로키 3 을가져온다. 키 3 을바로 6 옆에놓을수없으므로부노노드에있는 5 를끌어내리고그자리에 3 을놓는다. (c) 계속 재분배 15 3 8 19 22 1 2 5 6 9 10 16 18 20 21 24 25 26 9 삭제 (d) 15 3 8 언더플로우! 19 22 1 2 5 6 10 16 18 20 21 24 25 26 형제노드가여분의키가없으므로병합한다. 형제노드의내용과부모노드의키하나를내려받아행함 27
언더플로우! 3 15 병합! 19 22 1 2 5 6 8 10 16 18 20 21 24 25 26 병합에키하나 (8) 를내준부모노드에서다시언더플로우발생 앞서발생한언더플로우와같은문제이므로재귀적으로처리한다. 부모노드가루트노드이고키가하나밖에없으므로루트노드는키를넘겨주고없어진다. 3 15 19 22 병합! 1 2 5 6 8 10 16 18 20 21 24 25 26 다차원검색트리 검색키가두개이상의필드로이루어진검색 복수개의필드를그대로검색에사용하는트리 3 개의다차원검색트리와하나의다차원저장 / 검색방법소개 KD- 트리 KDB- 트리 R- 트리 그리드파일 - 56 - 한빛미디어 28
KD-Tee 각레벨에서필드를번갈아가며검색에사용한다. 트리의한레벨에서는하나의필드만사용한다. 레벨 0( 루트노드 ) 에서는필드 0 만으로분기 레벨 i 에서는필드 i(mod k) 만으로분기 총 k 개의필드를사용하는검색이라면, k 개의레벨을내려가면검색에사용하는필드가일치한다. - 57 - 한빛미디어 레벨 0 a 0 a 1 a k-1 KD-Tee 레벨 1 b 0 b 1 b k-1 c 0 c 1 c k-1 레벨 2 d 0 d 1 d 2 e 0 e 1 e 2 레벨 k-1 레벨 k 0 1 k-1 0 1 k-1 29
KD-Tee 에서의삽입예 삽입순서 : A(50, 50), B(10, 70), C(80, 85), D(25, 20), E(40, 85), F(70, 85), G(10, ) 키가두개이므로레벨별로번갈아사용하여삽입한다. A 50 50 B 10 70 C 80 85 D 25 20 E 40 85 F 70 85 G 10 KD-Tee 상의각노드는다차원공간의한점에해당 한노드에서필드 를사용해분기하는것 è 그노드가속한다차원공간에대해공간을둘로분할하는효과 검색을통해내려간다는것 è 다차원공간에서이렇게나누어진결과에대해공간의범위를점점좁혀나가는것 A 50 50 E(40,85) F(70,85) C(80,85) B(10,70) B 10 70 C 80 85 G(10,) D 25 20 E 40 85 F 70 85 A(50,50) G 10 D(25,20)
KD-Tee 에서의검색과삽입 이진탐색트리에서의검색 / 삽입방법을단순확장 KD-Tee 에서의삭제 이진탐색트리에서의삭제를신중하게확장해야함. 삭제노드 이몇개의자식을갖느냐에따라 자식이없는경우 BST 와마찬가지로노드 만제거하면됨 자식이하나뿐인경우 BST 처럼노드 의부모가노드 의자식을가리키게하면, 노드 의자식서브트리들의레벨이하나씩올라가므로각레벨에서사용하는키가달라져문제가발생 è 자식이둘인경우와같은방법으로삭제해야함. 자식이둘인경우 노드 의오른쪽서브트리중노드 에서분기에사용한필드값이가장작은노드를찾아삭제하고, 그노드를노드 자리로이동한다. A 50 50 루트노드 A 를삭제하고자한다. 키값을 (, y) 라하자. B 55 C 55 70 D 40 85 E 65 20 F 85 G 61 H 70 I 65 80 J 75 55 K 70 75 L 68 72 M 76 78 31
A 50 50 A 의오른쪽서브트리에서 값이가장작은노드를찾는다. 노드 C 의 값이가장작다. B 55 C 55 70 D 40 85 E 65 20 F 85 G 61 H 70 I 65 80 J 75 55 K 70 75 L 68 72 M 76 78 B 55 C 55 70 A 50 50 노드 A 에노드 C 를옮겨놓는다. 이제노드 C 를삭제해야한다. è 재귀적으로처리할수있음. D 40 85 E 65 20 F 85 G 61 H 70 I 65 80 J 75 55 K 70 75 L 68 72 M 76 78 32
C 55 70 C 가있는레벨은분기를위해 y 값을사용 C 의오른쪽서브트리에서 y 값이가장작은노드를찾으면노드 L 이다. B 55 D 40 85 E 65 20 F 85 G 61 H 70 I 65 80 J 75 55 K 70 75 L 68 72 M 76 78 C 55 70 L 을 C 의빈자리로옮긴다. B 55 L 68 72 D 40 85 E 65 20 F 85 G 61 H 70 I 65 80 J 75 55 K 70 75 M 76 78 33
C 55 70 L 은리프노드였으므로 L 이위로옮겨감으로써영향을받는자식이없다. L 에대한부모노드의연결만 NIL 로바꾼다. B 55 L 68 72 D 40 85 E 65 20 F 85 G 61 H 70 I 65 80 J 75 55 K 70 75 M 76 78 B 55 D KD-Tee 에서 또는 y 값이가장작은노드찾기 여러키를사용하므로 BST 같이쉽지는않다. 예 ) A 의오른쪽서브트리에서 값이가장작은노드찾는과정 AàC 로오면 : C 의서브트리는모두다내려가봐야함 노드 C 는 y 값에의해분기했으므로 C 의후손들의 값을짐작할수없기때문 40 85 A 50 50 C 55 70 E 65 20 F 85 E 의오른쪽서브트리는 E 의 값보다큰 값을가지므로볼필요가없다. E 의왼쪽서브트리를확인한다음, 55 보다더작은 값노드가없으므로 F 로간다. F 의오른쪽서브트리도볼필요가없다. G 61 H 70 I 65 80 J 75 55 K 70 75 L 68 72 M 76 78 34
KDB-Tee KD-Tee 와 B-Tee 의특성결합 KD-Tee 의특성 다차원 key B-Tee 의특성 디스크의한페이지가한노드와일치 Balanced tee 각레코드는 k 차원공간에서하나의점에해당 자신이속한공간을담당하는색인 node 들을따라감 KDB-Tee 의 Node 들 Intenal node 하나는 k 차원공간에서한영역을담당한다 루트노드는 k 차원공간전체를커버 이하의노드들은 k 차원공간의부분영역을담당 같은 level 에있는모든노드들은서로겹치는영역이없다 같은 level 에있는모든노드들의담당영역을합하면 k 차원공간전체가됨 Intenal node 는따라서영역노드라고할수있다. 리프노드는데이터페이지정보를저장 따라서모든리프노드는키노드라고할수있다. 35
공간은 3 개로나누어져 3 개의페이지가각각커버한다. 각페이지는다시복수개로나누어져자식페이지들이나누어커버한다. 맨아래리프노드들은각각한영역을커버하는데, 해당영역에속하는키들의정보가들어있다. : 제외된영역 : 점 ( 하나의레코드포인트 ) Dik 의한페이지 36
KDB-Tee 에서의검색 루트노드부터시작해해당키가포함되는영역을따라리프노드까지내려간다. 키는 ( 0, 1,, k-1 ) 로표현됨 각노드의영역들은서로겹치는부분이없으므로키에의해도달하는리프는유일함. 리프노드에해당키의 ( 키, 페이지번호 ) 정보가있으면해당페이지로가서레코드를가져옴. 도달한리프에해당키의 ( 키, 페이지번호 ) 정보가없으면검색실패 영역검색도가능 키는 (<min 0, ma 0 >, < min 1, ma 1 >,, < min k-1, ma k-1 >) 로표현됨. KDB-Tee 에서의삽입 삽입과정 삽입할키가속하는리프노드를찾는다. 해당리프노드가키를더수용할수있는공간이있으면, ( 키, 페이지번호 ) 쌍을삽입하고끝냄. 그렇지않으면, 형제노드와재분배할수있으면재분배함. 재분배불가능시리프노드를분할하여두개로만듦 이에따라부모노드에있는한영역이두개로나누어지므로 ( 영역, 페이지번호 ) 쌍이하나늘어난다. 부모노드가 ( 영역, 페이지번호 ) 를하나더수용할수있으면삽입은끝. 그렇지않으면부모노드를분할해야함. 37
(a) 분할전 의자식노드에서분할 이분할이노드 에서오버플로우를유발하면노드 도분할해야함. 분할시자식노드에서분할을위해사용된차원의분할선을노드 전체에적용하여자른다. 의부모노드에서 를가리키던 ( 영역, 페이지번호 ) 를두개로나누어야함. (b) 노드 분할후 KDB-Tee 에서의삭제 삭제과정 : B- 트리와유사 언더플로우가생기지않으면삭제완료 언더플로우가생기면, 이웃영역과경계를재조정해서재분배 재분배가불가능하면병합을시도 병합은부모노드에서 ( 영역, 페이지번호 ) 쌍두개가하나로통합된다. 이로인해부모노드에서또언더플로우가생기면재귀적으로처리한다. 38
R-Tee 다차원검색을다룰수있도록 B- 트리를확장한것 균형잡힌검색트리 R-Tee 의성질 루트를제외한모든내부노드는 ~ k개의영역을갖는다. 모든리프노드는같은깊이를가진다. 모든레코드는리프노드에서만가리킴 다차원도형의저장가능 점, 선, 면, 폐공간, 각종도형 MBR(Minimum Bounding Rectangle) 로근사 R- 트리로구성하고자하는레코드들의이차원키예 이름 Key1 Key2 A 8 100 B 4 10 C 6 35 D 1 10 E 6 40 F 5 45 G 7 85 H 3 20 I 10 70 J 2 K 8 50 L 4 50 39
이차원키들의레코드를이차원공간에표시한예 120 110 100 90 A 80 70 G I 50 40 J L F E C K 20 10 D H B 1 2 3 4 5 6 7 8 9 10 11 12 R1 R2 R3 R4 R5 R6 R7 A I C G E K D H B F J L 120 110 100 90 80 70 R1 R4 G A R3 I k=5, 즉루트를제외한모든노드는 2 개 ~ 5 개의영역을가지는 R-Tee 임. 검색 R-Tee 는한노드에있는영역들이서로겹칠수있음 검색의경로가유일하지않을수있음. 예 ) 레코드 E 는 R4 와 R5 에동시에속한다. 50 40 20 10 R2 D R7 J R6 H L B F E C K R5 1 2 3 4 5 6 7 8 9 10 11 12 40
R1 R2 R3 R4 R5 R6 R7 120 110 100 90 80 70 50 40 20 10 A I C G E K D H B F J L R2 D R7 J R6 H N L B F M R1 R4 G E C K A R5 R3 I 레코드삽입과정 레코드 M 은 R7 에속하는데문제없이삽입됨. 역시 R7 에속하는 N 을삽입하려하면오버플로우발생 M N 1 2 3 4 5 6 7 8 9 10 11 12 R1 R2 R3 R4 R5 R6 R7 120 110 100 90 80 70 50 40 20 10 A I C G E K D H B M J N L F R2 R6 D R7 J H N L B F M R1 R4 G E C K A R5 R3 I 레코드삽입과정 ( 계속 ) R6 과 R7 의영역을조정함으로써두리프에속하는키들을재분배 노드에서 R6 와 R7 은같은이름으로표현되었지만실제영역의내용은바뀌었다. 1 2 3 4 5 6 7 8 9 10 11 12 41
R1 R2 R3 R4 R5 R6 R7 y 120 110 100 90 80 70 50 40 20 10 A I C G E K D H B M P J N L F R2 R6 P D R7 J O H Q L N B F M R1 R4 G E C K A R5 R3 I Q 레코드삽입과정 ( 계속 ) R7 에속하는레코드 O 와 R6 에속하는레코드 P 는별문제없이삽입성공 여기세 R6 에속하는레코드 Q 를또삽입하면오버플로우발생 재분배를시도했으나형제노드에빈공간이없다. O 1 2 3 4 5 6 7 8 9 10 11 12 R1 R2 R3 R4 R5 R6 R7 R8 D H P Q J N L F O B M 120 110 100 90 80 70 R1 R4 G A R3 I 레코드삽입과정 ( 계속 ) 재분배불가이어서영역 R6 를둘로분할하여 R6 와 R8 로나누었다. 만약부모노드에서도오버플로우가발생했다면재귀적으로처리한다. 50 40 20 10 R2 R7 J O R6 P H D Q L F N R8 M B E C K R5 1 2 3 4 5 6 7 8 9 10 11 12 42
Gid File 검색트리가아닌일종의저장시스템 키의내용에따라레코드가저장된곳을 단번에 알아낼수있도록설계된다차원저장 / 검색수단 a(10, 50) f(, 45) k(55, 45) e(, 40) d(85, 45) i(65, 35) h(80, 35) l(25, 25) 0 j(40, 15) b(10, 10) c(80, 10) g(55, 5) 0 100 (a) P1 a b c a(10, 50) b(10, 10) c(80, 10) 0 (b) 0 100 a b P1 a(10, 50) d(85, 45) c d P2 b(10, 10) c(80, 10) 0 43
(c) a b P1 a(10, 50) e(, 40) d(85, 45) c d e P2 b(10, 10) c(80, 10) 0 0 50 100 (d) a b f P1 a(10, 50) f(, 45) e(, 40) d(85, 45) c d e P2 b(10, 10) c(80, 10) 0 (e) a b f P1 a(10, 50) f(, 45) e(, 40) d(85, 45) P2 e d 0 b(10, 10) c(80, 10) g(55, 5) c g P3 0 50 100 (f) a b f P1 a(10, 50) f(, 45) e(, 40) d(85, 45) h(80, 35) P2 e d h 0 b(10, 10) c(80, 10) g(55, 5) P3 c g 44
(g) a b f P1 a(10, 50) f(, 45) e(, 40) d(85, 45) e i P2 i(65, 35) h(80, 35) P4 d h 0 b(10, 10) c(80, 10) g(55, 5) c g P3 0 50 75 100 P1 (h) a(10, 50) f(, 45) e(, 40) d(85, 45) a b f j P5 P2 i(65, 35) h(80, 35) e i P4 0 j(40, 15) b(10, 10) c(80, 10) g(55, 5) d c h g P3 (i) a(10, 50) f(, 45) k(55, 45) e(, 40) d(85, 45) a b f j l P1 P5 P2 l(25, 25) i(65, 35) h(80, 35) e i k P4 0 j(40, 15) b(10, 10) c(80, 10) g(55, 5) d c h g P3 0 50 75 100 45
Gid Configuation 일차스케일링배열 50 75 그리드배열 1 2 5 3 4 3 Thank you - 92 - 한빛미디어 46