M원 탐색트리.

Presentation on theme: "M원 탐색트리."— Presentation transcript:

1 M원 탐색트리

2 M원탐색트리 한 개의 노드에 (m-1)개의 키와 m개의 종속트리를 가짐 2원탐색트리에 비하여 높이 감소 탐색시간 단축
삽입, 삭제의 어려움

3 M원탐색트리의 구조 n P1 K1 P2 K2 … Pm-1 Km Pm n=# of sub tree
Pi =sub tree에 대한 포인터 Ki = Key Key값은 반드시 오름차순 Pi 가 지시하는 서브트리내의 키값 < Ki Pi+1 가 지시하는 서브트리내의 키값 < Ki

4 B-Tree

5 B-Tree 정의 트리에 있는 각 노드는 최대 m개, 최소 ┏ m/2┐개의 종속 트리를 가져야 한다(루트와 leaf 노드는 제외. 루트는 성질2 참조. leaf노드는 종속트리가 없음) 루트노드는 최소한 두개의 종속트리를 가져야 한다 (단, 트리가 루트만 있는 경우에는 종속트리가 없음) 모든 leaf노드는 같은 level에 있어야 한다 (즉 모든 leaf노드는 루트로부터 같은 거리에 있음) 노드에 있는 키값 갯수는 종속트리의 갯수보다 하나 적으며 최소 ┏ m/2┐-1개, 최대 m-1개이다(루트노드 제외)

6 B-tree에서의 탐색(search) 특정 key값 탐색 순찬탐색 : 중위 순회 = B+ Tree
ㆍ 80 a ㆍ 19 b 43 ㆍ 126 c 138 ㆍ 16 d ㆍ 26 e 40 ㆍ 60 f ㆍ 100 g ㆍ 132 h ㆍ 145 i 7 15 j 18 k 29 l 30 36 m 42 n 50 58 o 62 65 p 96 q 110 120 r 130 s 136 t 140 u 150 v 차수3의 B-Tree B-tree에서의 탐색(search) 특정 key값 탐색 순찬탐색 : 중위 순회 = B+ Tree (방문의 중복으로 순차 file보다는 성능이 떨어짐)

7 차수5인 B-Tree의 생성 과정 a) 삽입 a, g, f, b b) 삽입 k b) 삽입 d, h, m e) 삽입 j
ㆍ f ㆍ ㆍ f ㆍ a b g k a b d g h k m a) 삽입 a, g, f, b b) 삽입 k b) 삽입 d, h, m ㆍ f ㆍ j ㆍ ㆍ f ㆍ j ㆍ a b d g h k m a b d e g h i k m r s e) 삽입 j f) 삽입 e, s, I, r 차수5인 B-Tree의 생성 과정

8 차수5인 B-Tree의 생성 과정 f) 삽입 x g) 삽입 c, l, m, t, u ㆍ f ㆍ j ㆍ r ㆍ a b d e g
h i k m s x f) 삽입 x ㆍ c ㆍ f ㆍ j ㆍ r ㆍ a b d e g h i k l m n s t u x g) 삽입 c, l, m, t, u 차수5인 B-Tree의 생성 과정

9 overflow : split(기존 Key값, 새로운 Key값) 中 Median값([m/2]번째값) : Parent node로
ㆍ j ㆍ ㆍ c ㆍ f ㆍ ㆍ m ㆍ r ㆍ a b d e g h i k l n p s t u x h) 삽입 p 차수5인 B-Tree의 생성 과정 삽입 Algorithm 빈공간이 있는 경우 : 단순 삽입 overflow : split(기존 Key값, 새로운 Key값) 中 Median값([m/2]번째값) : Parent node로 나머지 반씩 두 node로

10 B* Tree

11 B*-Tree (Knuth 제안) B-Tree의 단점 B*-Tree의 기본 Idea
분열, 재분배, 합병 연산이 빈번 -> node 수 증가 각 node는 절반 정도가 Key값으로 채워짐 B*-Tree의 기본 Idea Overflow 발생시 Split 대신 형제 node로 재분배 형재 node가 모두 Overflow이면 두 node를 세 node로 분할 => 각 node는 2/3 정도가 채워짐

12 삽입Overflow 차수 M의 B-트리구조 C = ┗ m+n/2 ┘ B-트리를 재배치한 결과 …… …… …… …… …… ……
ㆍ km(j) ㆍ …… ㆍ k(1) ㆍ k(2) ㆍ …… ㆍ k(m-1) ㆍ ㆍ k’(1) …… k’(n) p(1) p(2) p(m-1) p’(1) p’(2) p’(n) 삽입Overflow 차수 M의 B-트리구조 C = ┗ m+n/2 ┘ …… ㆍ k(c+1) ㆍ …… ㆍ k’(1) ㆍ k’(2) ㆍ …… ㆍ k(c) ㆍ ㆍ k(c+2) ㆍ …… ㆍ k(m) ㆍ k’(j) ㆍ k’(l) ㆍ …… ㆍ k’(n) ㆍ p(1) p(2) p(c) p(c+1) p’(h) p’(0) p’(1) p’(c) B-트리를 재배치한 결과

13 B-Tree의 경우 24를 삽입 => Overflow 재분배 Example ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ c ㆍ ㆍ
33 ㆍ B-Tree의 경우 ㆍ 22 ㆍ 33 ㆍ ㆍ 18 ㆍ 20 ㆍ 22 ㆍ 26 ㆍ ㆍ 35 ㆍ 24를 삽입 => Overflow 18 20 24 26 35 18 20 22 24 26 33 35 c 재분배 ㆍ 24 ㆍ ㆍ 18 ㆍ 20 ㆍ 22 ㆍ ㆍ 26 ㆍ 33 ㆍ 35 ㆍ

14 2m-2 3 2(2m-2) +1 β = α = 여기서 두 형재 node가 가득찬 경우 …… …… …… …… …… ㆍ
k(α+1) ㆍ k(β+1) ㆍ …… p(0) k(1) p(1) …… k(α) p(α) p(α+1) k(α+1) …… k(β) p(β) p(β+1) k(β+1) …… k(2m) p(2m) 2m-2 3 2(2m-2) +1 β = α = 여기서

15 24를 삽입 => Overflow 재분배 Example ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ α β 33 18 20
22 ㆍ 26 ㆍ ㆍ 35 ㆍ 41 ㆍ 43 ㆍ 48 ㆍ 24를 삽입 => Overflow 18 20 22 24 26 33 35 41 43 48 α β 재분배 ㆍ 22 ㆍ 35 ㆍ ㆍ 18 ㆍ 20 ㆍ ㆍ 24 ㆍ 26 ㆍ 33 ㆍ ㆍ 41 ㆍ 43 ㆍ 48 ㆍ

16 B+ Tree

17 B+-Tree (Knuth 제안) Index Part와 Sequnce Set로 구성
Index Part : Leaf node에 대한 경로 정보 Leaf node에 다시 나타남 Key 값만 수록 (주소는 없음) Sequence Set : Leaf node로 구성 Key값과 주소쌍으로 구성 -> 순차, 직접 access가 모두가능 삽입, 삭제는 B-Tree와 거의 유사

18 B+ 트리의 예 a b c e g j m n o p t v q u s d f h l k w r 인 덱 스 부 분
순차 데이타 부분 ㆍ 80 a b 20 43 110 c e 30 40 100 g 7 16 j 24 m n 42 o 50 58 p t 130 v 62 q 120 128 u 70 s d 18 f h l k 132 134 w r B+ 트리의 예

19 차수 3의 B+트리에서의 삽입 과정 예 l m n ㆍ ㆍ (a) 삽입 16, 23 (b) 삽입 4 (c) 삽입 47 ㆍ ㆍ ㆍ
8 ㆍ ㆍ 8 16 4 8 l 16 m 23 47 n ㆍ 6 ㆍ 16 (d) 삽입 8 4 6 8 16 23 47 (d) 삽입 6 차수 3의 B+트리에서의 삽입 과정 예

20 차수 5의 B+트리에서의 삭제 과정 예 ㆍ ㆍ (a) (b) 62의 삭제연산 결과 ㆍ ㆍ (c) 17의 삭제연산(배치) 결과
15 ㆍ 62 107 210 15 ㆍ 62 107 210 17 31 62 68 73 80 17 31 68 73 80 (a) (b) 62의 삭제연산 결과 15 ㆍ 68 107 210 15 ㆍ 107 210 31 68 73 80 31 68 80 (c) 17의 삭제연산(배치) 결과 (d) 73의 삭제연산(합병) 결과 차수 5의 B+트리에서의 삭제 과정 예