제 11 장 다원 탐색 트리

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

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

m-원 탐색 트리에서의 탐색 m-원 탐색 트리에서 키 x를 가진 원소를 탐색 (E0.K = -∞, En+1.K = +∞ 라고 가정) 트리의 루트에서 시작 Ei.K≤x<Ei+1.K를 만족하는 i를 찾는다. x = Ei.K이면 탐색 완료 x ≠Ei.K이고 x가 존재한다면 x는 서브트리 Ai에 있을 것이므로 서브 트리의 루트로 가서 탐색 반복 // m-원 탐색 트리에서 키가 x인 원소를 찾는다. // 원소를 찾으면 그 원소를 반환한다. 그렇지 않으면 NULL을 반환한다. E0.K = -MAXKEY; for(*p = root; p; p = Ai) { p의 형식이 n, A0, (E1, A1), ..., (En, An)이라 하자; En+1.K = MAXKEY; Ei.K≤x<Ei+1.K와 같은 i를 결정; if(x == Ei.K) return Ei; } // x는 트리에 없다. return NULL;

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

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

2-3 트리 2-3 트리 : 차수가 3인 B-트리 각 노드는 2개의 원소를 가질 수 있다. A 40 B C 10 20 80 2-3 트리의 예

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

B-트리의 원소 수 모든 외부 노드의 레벨이 l+1인 차수가 m인 B-트리 최대 ml-1개의 키를 갖음 최소 원소 수 N은? 트리에 있는 키들을 K1,K2,…,KN (Ki<Ki+1, 1≤i<N)이라 할 때 외부 노드의 수는 N+1개 N+1 = 외부 노드의 수 = (l+1) 레벨에서의 노드 수 ≥ 2 따라서, N ≥ 2 -1, l ≥ 1

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

B-트리로의 삽입 (2) 2-3트리로의 삽입 (1) A A 40 20 40 B C B D C 10 20 70 80 10 30

B-트리로의 삽입 (3) 2-3트리로의 삽입 (2) G 40 A F 20 70 B D C E 10 30 60 80 2-3 트리에 60을 삽입

B-트리로의 삽입 (4) - 분석 B-트리가 디스크에 상주한다고 가정 B-트리 높이가 h일 때 평균 분할 횟수 Savg 분할 노드가 루트이면 3개의 노드를 디스크에 기록 분할 노드가 루트가 아니면 2개의 노드를 디스크에 기록 삽입을 위한 디스크 최대 접근 횟수 h(하향과정) + 2(h-1)(루트가 아닌 노드 분할) + 3(루트 분할) = 3h+1 평균 분할 횟수 Savg Savg = (총 분할 횟수)/N ≤ (p-2)/{1+( - 1)(p-1)} < 1/( - 1) 삽입 과정에 디스크 접근 수 h + 2s -1 (s : 삽입 동안 분할되는 노드 수) 평균 디스크 접근 수 h+2Savg+1 < h+101/99 ≈ h + 1

차수가 2인 B-트리 20 10, 30 10 25, 30 (a) p = 1, s = 0 (b) p = 3, s = 1 20, 28 10 25 30 (c) p = 4, s = 2

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

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

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의 왼쪽 자식이다.

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의 중간 자식이다.

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의 오른쪽 자식이다.

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

2-3 트리에서의 삭제 (1) A 50 80 B C D A 10 20 60 90 95 50 80 B C D (b) 70이 삭제됨 10 20 60 70 90 95 A 50 80 (a) 2-3트리의 초기 상태 B C D 20 60 90 95 (c) 10이 삭제됨

2-3 트리에서의 삭제 (2) A A 50 90 50 B C D B C 20 80 95 20 80 90 (d) 60이 삭제됨 (e) 95가 삭제됨 A 50 B 50 80 B C 20 80 (g) 20이 삭제됨 (f) 90이 삭제됨

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

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

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

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

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

B+-트리(6) - 삽입 (2) (a) 14를 삽입 (b) 86을 삽입 A 20 40 B C D 10 16 30 70 80 2 12 14 16 18 20 25 32 36 40 50 60 71 72 80 82 84 G 40 (b) 86을 삽입 A F 20 80 B C D E 10 16 30 70 84 2 4 6 12 14 16 18 20 25 32 36 40 50 60 71 72 80 82 84 86

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

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

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

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