제 11 장 다원 탐색 트리

제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University

m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다. 구조 : n, 0, (E 1, 1 ), (E 2, 2 ),..., (E n, n ) E i 는원소를의미 각원소 E i 는 E i.k 키를가지고있음 (2) E i.k < E i+1.k (1 i<n) (3) E 0.K = -, E n+1.k = 이다. (0 i<n<m) E i.k < 서브트리 i 의모든키 < E n+1.k (0 i<n) (4) 0 i<n 에대하여서브트리 i 역시 m- 원탐색트리이다. Copyright 07 DBLB, Seoul National University 2

m- 원탐색트리의정의와성질 (2) b T 10, 15 c e, 25, 30 28 a d 45, 50 node a b c d e schematic format 2, b, (, c), (, d) 2, 0, (10, 0), (15, 0) 2, 0, (25, e), (30, 0) 2, 0, (45, 0), (50, 0) 1, 0, (28, 0) 3- 원탐색트리의예 차수가 m 이고높이가 h 인트리에서최대노드수 i m 0 i h 1 ( m h 1) /( m 1) 주어진원소의수가 n 개일때최적의 m- 원탐색트리의성능을얻으려면탐색트리가반드시균형이어야함 Copyright 07 DBLB, Seoul National University 3

m- 원탐색트리에서의탐색 m- 원탐색트리에서키 x 를가진원소를탐색 (E 0.K = -, E n+1.k = + 라고가정 ) 트리의루트에서시작 E i.k x<e i+1.k 를만족하는 i 를찾는다. x = E i.k 이면탐색완료 x E i.k 이고 x 가존재한다면 x 는서브트리 i 에있을것이므로서브트리의루트로가서탐색반복 // m- 원탐색트리에서키가 x 인원소를찾는다. // 원소를찾으면그원소를반환한다. 그렇지않으면 NULL 을반환한다. E 0.K = -MXKEY; for(*p = root; p; p = i) { p 의형식이 n, 0, (E 1, 1 ),..., (E n, n ) 이라하자 ; E n+1.k = MXKEY; E i.k x<e i+1.k 와같은 i 를결정 ; if(x == E i.k) return E i ; } // x 는트리에없다. return NULL; Copyright 07 DBLB, Seoul National University 4

B- 트리의정의와성질 (1) 외부노드 (external node) 탐색중에트리에서찾고자하는원소를검색하지못했을때도달하는노드 차수가 m 인 B- 트리 (B-tree of order m) 공백이거나다음성질들을만족 (1) 루트노드는적어도두개의자식노드를갖는다. (2) 루트노드와외부노드를제외한모든노드는적어도 m / 2 개의자식노드를갖는다. (3) 모든외부노드들은갖은레벨에있다. Copyright 07 DBLB, Seoul National University 5

B- 트리의정의와성질 (2) 모든 n 0 과 m>2 에대해키가 n 개이고차수가 m 인 B- 트리는항상존재 차수가 2 인모든 B- 트리 포화이진트리 키값의수가어떤 k 값에대하여 2 k -1 일때만존재 Copyright 07 DBLB, Seoul National University 6

2-3 트리 2-3 트리 : 차수가 3 인 B- 트리 각노드는 2 개의원소를가질수있다. B C 10 80 2-3 트리의예 Copyright 07 DBLB, Seoul National University 7

2-3-4 트리 2-3-4 트리 : 차수가 4 인 B- 트리 각노드는 3 개의원소를가질수있다. 50 10 70 80 5 7 9 30 60 75 85 90 92 2-3-4 트리의예 Copyright 07 DBLB, Seoul National University 8

B- 트리의원소수 모든외부노드의레벨이 l+1 인차수가 m 인 B- 트리 최대 m l -1개의키를갖음 최소원소수 N은? l 레벨 l에서의노드수는최소 2 m / 2 2 개 내부노드들 트리에있는키들을 K 1,K 2,,K N (K i <K i+1, 1 i<n) 이라할때외부노드의수는 N+1개 N+1 = 외부노드의수 = (l+1) 레벨에서의노드수 l 2 m / 2 2 l 2 따라서, N 2 m / 2-1, l 1 Copyright 07 DBLB, Seoul National University 9

B- 트리로의삽입 (1) B- 트리로의삽입알고리즘 새로운키가삽입될리프노드 p 를정하기위한탐색 삽입의결과 p 가 m 개의키를가지게되면, p 를분할 그렇지않으면, 새로운 p 가디스크에기록되고삽입종료 p 의분할 새로운원소삽입후 p 의형식 m, 0,(E 1, 1 ),...,(E m, m ) ( 단, E i <E i+1, l i<m) 분할된두개의노드 p, q의형식 노드 p: m / 2-1, 0, (E 1, 1 ),..., ( E m / 2 1, m / 2 1) 노드 q: m- m / 2, m / 2,( E m/ 2 1, m / 2 1),..., ( Em, m ) 나머지원소인 E m / 2 와새로운노드에대한포인터 q는하나의투플 E m/, q 을형성하여 p의부모에삽입 ( 2 ) 분할과정은루트에도달할때까지계속될수있음 루트가분할되면새로운루트생성되고 B- 트리높이가하나증가함 Copyright 07 DBLB, Seoul National University 10

B- 트리로의삽입 (2) 2-3 트리로의삽입 (1) B C B D C 10 70 80 10 30 70 80 (a) 70 삽입 (b) 30 삽입 Copyright 07 DBLB, Seoul National University 11

B- 트리로의삽입 (3) 2-3 트리로의삽입 (2) G F 70 B D C E 10 30 60 80 2-3 트리에 60 을삽입 Copyright 07 DBLB, Seoul National University 12

B- 트리로의삽입 (4) - 분석 B- 트리가디스크에상주한다고가정 B- 트리높이가 h 일때 하향탐색동안 h 번의디스크접근필요 최악의경우, h 개의노드가상향분할과정동안계속분할 분할노드가루트이면 3 개의노드를디스크에기록 분할노드가루트가아니면 2 개의노드를디스크에기록 삽입을위한디스크최대접근횟수 h( 하향과정 ) + 2(h-1)( 루트가아닌노드분할 ) + 3( 루트분할 ) = 3h+1 평균분할횟수 S avg S avg = ( 총분할횟수 )/N (p-2)/{1+( / 2-1)(p-1)} < 1/( m / 2-1) m 삽입과정에디스크접근수 h + 2s -1 (s : 삽입동안분할되는노드수 ) 평균디스크접근수 h+2s avg +1 < h+101/99 h + 1 Copyright 07 DBLB, Seoul National University 13

차수가 2 인 B- 트리 10, 30 10 25, 30 (a) p = 1, s = 0 (b) p = 3, s = 1, 28 10 25 30 (c) p = 4, s = 2 Copyright 07 DBLB, Seoul National University 14

B- 트리에서의삭제 (1) 키가 x 인원소를삭제하기위해 x 에대해탐색 x 를찾지못하면삭제할원소없는것 x 가리프가아닌노드 z 에서발견되면 z 에서 x 가차지하던자리는리프노드로부터적당한키로대체 리프노드가아닌노드로부터의삭제가리프노드로부터의삭제로변환됨 x 가리프노드에서발견되면리프노드로부터의삭제수행 Copyright 07 DBLB, Seoul National University 15

B- 트리에서의삭제 (2) 리프노드 p에서의삭제 p가루트인경우 삭제후루트에원소가남아있을경우변경된루트를디스크에기록하고완료 그렇지않으면삭제후 B-트리는공백이된다. p 가루트가아닌경우 삭제후 p 가적어도 m / 2-1 개의원소를가지고있는경우 수정된리프노드가디스크에기록되고완료 / 2 m / 2 p가 -2개, 인접한형제노드 q가최소개의원소를가진경우 m 회전수행 : q 의원소수하나감소시키고 p 의원소수를하나증가시킴 p가 / 2-2개, 가장가까운형제노드 q가 m / 2-1개의원소를가진경우 m 결합수행 : p, q, 부모노드중간에있는원소를하나의노드로결합 부모노드 r의키수를하나감소시킴 원소부족현상을없애기위해 r의가장가까운형제노드중하나에대하여회전시도 회전불가능하면결합은완료된것결합된노드 : ( m / 2-2)+( m / 2-1)+1=2 m / 2-2 m-1개의원소를가짐 Copyright 07 DBLB, Seoul National University 16

2-3 트리회전의세가지경우 (1) r r x? y? p q p q y z x z a b c d a b c d (a) p 는 r 의왼쪽자식이다. Copyright 07 DBLB, Seoul National University 17

2-3 트리회전의세가지경우 (2) r r z? y? p q p q x y x z a b c d a b c d (b) p 는 r 의중간자식이다. Copyright 07 DBLB, Seoul National University 18

2-3 트리회전의세가지경우 (3) r r w z w y a a q p q p x y x z b c d e b c d e (c) p 는 r 의오른쪽자식이다. Copyright 07 DBLB, Seoul National University 19

Copyright 07 DBLB, Seoul National University 2-3 트리에서의결합 x y a b c r p x y b a c r q p (a) z x y a b c r p x z y b a c r q p (b) d d 2-3 트리에서 p 가 r 의왼쪽자식일경우의결합

2-3 트리에서의삭제 (1) 50 80 50 80 B 10 C 60 D 90 95 B 10 C 60 70 D 90 95 (b) 70 이삭제됨 50 80 (a) 2-3 트리의초기상태 B C 60 D 90 95 (c) 10 이삭제됨 Copyright 07 DBLB, Seoul National University 21

2-3 트리에서의삭제 (2) 50 90 50 B C 80 95 D B C 80 90 (d) 60 이삭제됨 50 (e) 95 가삭제됨 B 50 80 B C 80 (g) 이삭제됨 (f) 90 이삭제됨 Copyright 07 DBLB, Seoul National University 22

B + - 트리 (1) B- 트리와비슷한계통 B- 트리와의차이점 (1) 인덱스 (index) 노드와데이타 (data) 노드 인덱스노드 : B- 트리에서의내부노드와일치, 키와포인터를저장 데이타노드 : B- 트리에서의외부노드와일치, 키와함께원소를저장 (2) 데이타노드는왼쪽에서오른쪽순서대로서로링크되어있고이중연결리스트를형성 Copyright 07 DBLB, Seoul National University 23

B + - 트리 (2) - 차수 3 인 B + - 트리의예 B C D 10 30 70 80 2 4 6 12 16 18 25 32 36 50 60 71 72 80 82 84 데이터노드 ( 회색 ) 인덱스노드들은높이 2인 2-3 트리를형성하고있음 데이터노드크기와인덱스노드크기는똑같지않아도된다. Copyright 07 DBLB, Seoul National University 24

B + - 트리 (3) - 정의 차수가 m 인 B + - 트리 (B + -tree of order m) 공백이거나다음성질들을만족 (1) 모든데이타노드는같은레벨에위치해있고, 리프노드이다. 데이타노드는원소만포함함. (2) 인덱스노드는차수가 m 인 B- 트리를정의함. 각인덱스노드는키를갖고있지만원소를갖고있지는않다. (3) 인덱스노드의형식 : n, i,(k 1, 1 ),(K 2, 2 ),...,(K n, n ) - i (0 i n<m) 가서브트리에대한포인터, K i (1 i<n<m) 는키임 - K 0 =-, K n+1 = - 서브트리 i 의모든원소는 0 i<n 일때, K i+1 보다작고 K i 보다크거나같은키를가진다. Copyright 07 DBLB, Seoul National University 25

B + - 트리 (4) - 탐색 두가지종류의탐색지원 정확히일치하는값에대한검색 범위검색 // B + - 트리에서 x 키를갖고있는원소를탐색한다. // 찾으면원소를반환한다. 그렇지않으면 NULL 을반환한다. if the tree is empty return NULL; K 0 = -MXKEY; for(*p = root; p is an index node; p = i) { } p 가다음과같은형식을갖고있다. : n, 0, (K 1, 1 ),...,(K n, n ); K n+1 = MXKEY; K i <= x < K i+1 ; // p 데이타노드를탐색한다. x 인키를가지고있는원소 E 에대한 p 를탐색한다 ; if 이러한원소를찾으면 E 를 return else return NULL; B + - 트리에서의탐색알고리즘 Copyright 07 DBLB, Seoul National University 26

B + - 트리 (5) - 삽입 (1) B- 트리에서의삽입과는분할된데이타노드를처리하는방법에차이가있음 데이타노드가완전히차면가장큰키들을가지고있는 원소의절반을새로운노드로옮김 이중가장작은원소의키를새로생성된데이타노드에 대한포인터와같이 B- 트리삽입과정을따라서부모 인덱스노드에삽입 인덱스노드분할은 B- 트리에서의내부노드분할과같음 Copyright 07 DBLB, Seoul National University 27

B + - 트리 (6) - 삽입 (2) (a) 14 를삽입 B C D 10 16 30 70 80 2 4 6 12 14 16 18 25 32 36 50 60 71 72 80 82 84 G (b) 86 을삽입 F 80 B C D E 10 16 30 70 84 2 4 6 12 14 16 18 25 32 36 50 60 71 72 80 82 84 86 Copyright 07 DBLB, Seoul National University 28

B + - 트리 (7) - 삭제 (1) 원소들은리프에만저장 리프에서의삭제만주의 최소원소수가부족하게되는경우 인덱스노드 : B-트리를형성하므로루트가아닌인덱스노드는 m / 2-1개보다키가적을때, 루트인덱스노드는키를갖고있지않을때 데이타노드 : 루트가아닌데이타노드는원소수가 c / 2 개보다적을때, 루트노드는공백일때 (c : 데이타노드가가질수있는원소수 ) 원소를삭제한후 데이타노드의최소원소수가부족하지않은경우 변경된데이타노드는디스크에기록되고, 인덱스노드는변경되지않음 데이타노드의최소원소수가부족한경우 최소원소수보다많은원소를보유한가장가까운형제노드에게원소를빌려오며그에따른부모노드 ( 인덱스노드 ) 의해당키값을변경한다. Copyright 07 DBLB, Seoul National University 29

B + - 트리 (8) - 삭제 (2) B C D 10 30 70 82 2 4 6 12 16 18 25 32 36 50 60 72 80 82 84 (a) 그림 11.11 에서 71 이삭제됨 B C D 10 30 70 2 4 6 12 16 18 25 32 36 50 60 72 82 84 (b) (a) 에서 80 이삭제됨 Copyright 07 DBLB, Seoul National University 30

B + - 트리 (9) - 삭제 (3) G 80 F 2 4 6 B C D E 10 16 30 70 84 12 14 16 18 25 36 50 60 71 72 80 82 84 86 G (a) C 의원소가부족함 16 80 F 2 4 6 B C D E 10 70 84 12 14 16 18 32 36 50 60 Copyright 07 DBLB, Seoul National University 31 71 72 80 82 84 86 (b) B 에서빌려온뒤

B + - 트리 (10) - 삭제 (4) G 80 F 2 4 6 B C D E 10 16 30 70 12 14 16 18 25 32 36 50 60 71 72 80 82 84 G (a) E 의원소가부족하게됨 F 2 4 6 B C D 10 16 30 70 80 12 14 16 18 25 32 36 50 60 Copyright 07 DBLB, Seoul National University 32 71 72 80 82 84 (b) F 의원소가부족하게됨