8. 파일 인덱스: 탐색트리 (Search Tree) 파일 구성론 8. 파일 인덱스: 탐색트리 (Search Tree) 컴퓨터멀티미디어학부 김 여자 컴퓨터멀티미디어학과 김여자

순서 이진탐색 트리 높이 균형 이진 트리 m 원 탐색 트리 B 트리 B* 트리 B+ 트리 컴퓨터멀티미디어학과 김여자

Linked list 자료와 다음 노드 지시 포인트 부분 연산 삽입(Insert) 삭제(Delete) 선형 탐색(linear search) 10 20 40 90 100 ^ 30 컴퓨터멀티미디어학과 김여자

Linear List 특성 연속된 공간 다음 노드 포인트 없음 삽입, 삭제 연산 복잡 변경, 검색 연산 시간 단축 30 50 60 65 70 90 30 50 60 65 70 90 컴퓨터멀티미디어학과 김여자

Binary Search Tree 자료와 두개의 포인트(왼쪽, 오른 쪽) 현 노드 값 보다 작은 값 갖는 서브 트리 지시 현 노드 값 보다 큰 값 갖는 서브 트리 지시 이진 트리 순회(binary tree traversing) Pre-order : Root => Left => Right In-order : Left => Root => Right Post-order : Left => Right => Root Data left subtree right subtree 컴퓨터멀티미디어학과 김여자

이진 탐색 트리(계속) 용어 root,부모(parent),형제(sibling),단말(leaf, terminal),조상(ancestor),후손(descendant) 루트,조상 50 레벨1 노드 차수 2 30 80 레벨2 20 ^ ^ 40 ^ ^ 60 ^ 90 레벨3 ^ 10 ^ ^ 70 ^ ^ 100 ^ 4 노드 차수 1 컴퓨터멀티미디어학과 김여자

이진탐색트리 트리의 노드 수(N)와 높이(h) 이진트리의 균형유지, 트리의 높이 최소화 관계식 : N = 2h – 1 h  log(N+1) 균형 트리는 높이가 주어진 노드들에 대해 최소값으로 주어지는 트리 균형 이진트리의 검색회수 : log N 컴퓨터멀티미디어학과 김여자

높이균형 이진트리 – AVL트리 특성 균형 트리의 조건 1962년 Adelson Velskii & Landis (AVL) 효율적인 탐색, 완전 균형에 가깝게 유지 삽입, 삭제시 균형이 깨어지면 균형 조정 균형 트리의 조건 1. TL은 T의 왼쪽 서브트리의 루트 2. TR은 T의 오른쪽 서비트리의 루트 3. TL과 TR의 높이는 균형 유지 4. hL과 TL의 높이 / 5. hR은 TR의 높이 6. | hL – hR|  1 컴퓨터멀티미디어학과 김여자

사향트리(Skewed tree) ^ 10 ^ 20 ^ 30 ^ 40 ^ 50 ^ 100 ^ 컴퓨터멀티미디어학과 김여자

AVL 트리의 재균형 RR회전 1 ^ 10 20 30 a b R a->rightchild = b->leftchild; b->leftchild = a; if ( f == NULL) b_is_the_new_root_of_theTree(); else f->rightchild = b; ^ 10 20 30 a b 컴퓨터멀티미디어학과 김여자

AVL 트리의 재균형 RR회전 2 40 ^ 50 30 10 20 b a f ^ 30 40 50 10 20 a b R f 컴퓨터멀티미디어학과 김여자

AVL 트리의 재균형 40 ^ 50 30 10 20 b a f 70 40 ^ 50 20 10 30 b a f 70 컴퓨터멀티미디어학과 김여자

AVL 트리의 재균형 RL회전 ^ 50 70 60 a b R L c f b->leftchild = c->rightchild; a->rightchild = c->leftchild; c->rightchild = b; c->leftchild = a; if ( f == NULL) c_is_the_new_root_of_theTree(); else f->rightchild = c; ^ 50 60 70 a c b 컴퓨터멀티미디어학과 김여자

AVL 트리의 재균형 LL회전 (RR 회전대칭) f a 30 ^ L b 20 ^ a->leftchild = b->rightchild; b->rightchild = a; if ( f == NULL) b_is_the_new_root_of_theTree(); else f->rightchild = b; L ^ 10 ^ b 20 a ^ 10 ^ ^ 30 ^ 컴퓨터멀티미디어학과 김여자

AVL 트리의 재균형 LR회전 (RL회전 대칭) 70 ^ 50 60 a b R L c f b->rihgtchild = c->leftchild; a->leftchild = c->rightchild; c->leftchild = b; c->rightchild = a; if ( f == NULL) c_is_the_new_root_of_theTree(); else f->rightchild = c; ^ 50 60 70 b c a 컴퓨터멀티미디어학과 김여자

AVL 트리 AVL트리가 완전균형 이진트리보다 같은 수의 노드를 가질 때 45% 이상 크지 않음을 증명 h 1.4404(log (N+2)) – 0.328 혹은 O(1.4[log N]) AVL트리가 파일의 키를 포함할 때 인덱스로서 디스크에 저장됨 컴퓨터멀티미디어학과 김여자

개념, B-tree, B*-tree, B+-tree m-way Search Tree 개념, B-tree, B*-tree, B+-tree 컴퓨터멀티미디어학과 김여자

개념 n S0 (K1,A1,S1) (K2,A2,S2) ... (Kn, An, Sn) Node 모든 노드의 차수가 m 이하, 0~m 개까지 다른 노드 포인트 가짐 특징 1. 트리 T에 있는 각 노드의 정보 (그림) 2. 키 값 수 n, 1  n < m 3. Ki(1  i  n)는 키 값, Ki<Ki+1 for 1  i<n=1 4. S0 : K1보다 작은 키 값을 갖는 subtree 포인터 5. Si(1  i  n) : Ki와 Ki+1 사이 키 값 갖는 subtree 포인터 6. Sn : Kn보다 큰 키 값 갖는 subtree 포인터 7. Si(0  i  n) : m원 탐색트리에 대한 포인터 8. Ai(0  i  n) : 화일에서 Ki를 키로 하는 레코드 주소 n S0 (K1,A1,S1) (K2,A2,S2) ... (Kn, An, Sn) Node 컴퓨터멀티미디어학과 김여자

개념 30 70 10 20 40 50 80 90 60 100 a b c d e f 위의 m원 트리의 각 노드를 기술하시오. 30 70 10 20 40 50 80 90 60 100 a b c d e f 위의 m원 트리의 각 노드를 기술하시오. a 2, b, (30, A[30], c), (70, A[70], d) b 2, 0, (10, A[10], 0). (20. A[20], 0) c 2, 0, (40, A[40], 0), (50, A[50], e) d 2, 0, (80, A[80], 0), (90, A[90], f) e 1, 0, (60, A[60], 0) F 1, 0, (100, A[100], 0) 컴퓨터멀티미디어학과 김여자

B-Tree 제안자 : Bayer & McCreight 정의 예 특성 1. B트리는 노드가 없거나 1이상의 높이를 갖는 m원 탐색트리 2. 루트 노드는 최소한 2개의 자식 노드, 적어도 한 개의 값을 갖음 3. 루트 노드를 제외하고 터미널 노드가 아닌, 즉 Si  0인 노드들은 최소한 m/2 개의 자식 노드를 가지고 m/2 -1 개의 값을 갖음. 4. 모든 터미널 노드 즉 Si = 0을 만족하는 노드는 같은 레벨에 있음 예 차수가 3인 B 트리는 최소한 (높이 1, 루트노드는 자식 노드 2, 한 개의 값)을 갖음. 특성 B트리는 가장 효율적인 파일의 색인 형태 컴퓨터멀티미디어학과 김여자

B-Tree : Insertion 삽입 다이아그램 : p310 ~ 315 프로그램 : p316~321 [알고리즘 8.2] 50 30 40 80 10 20 90 100 60 70 a b c d e f g 컴퓨터멀티미디어학과 김여자

B tree 파일은 상대파일 활용 인덱스(B tree) 파일과 자료파일 <RecSize 32B, Index File> <RecSize 128B, Data File> n s0 [K1,A1,S1] [K2,A2,S2] 학번 이름 전공 전화 1 1 50 홍길동 활빈당 332 1 128 40 흑길서 활쏘기 451 a 1 32 2 1 1 2 50,0,3 50,0,0 50,0,0 2 256 90 흑치상 칼쓰기 771 b 2 64 1 4 30,3,5 3 512 30 김유신 통 일 453 c 3 96 1 6 80,6,7 4 640 10 김인문 외 교 773 d 4 128 2 -1 10,4,-1 20,5,-1 5 768 20 김 명 왕 권 774 6 896 80 장보고 무 역 454 e 5 192 1 -1 40,1,-1 7 1024 60 이 면 충 효 456 f 6 224 2 -1 60,7,-1 70,9,-1 8 1152 100 정 운 화 포 556 g 7 256 2 90,2,-1 100,8,-1 9 1280 70 이장손 비격진 557 10 1408 컴퓨터멀티미디어학과 김여자

B Tree : 삽입 알고리즘 B Tree 파일 초기화 자료화일에서 key, 상대주소 읽어 오기 hold_tuple 만들기: [K,A,S] 삽입 위치 찾기: Search() 해당 위치에 삽입: Insert() 해당 노드 full이면 노드 분할: Split() 컴퓨터멀티미디어학과 김여자

Node Type Definition C Language /* Index File DS */ struct keyset { char key[7]; //Ki int relAddr; //Ai int s; // Si }; typedef struct nod { int n; int s0; struct keyset Keys[2]; } NODE; /* Data File DS */ struct relrec{ char sid[7]; char sname[12]; int age; char phonenum[10]; } relRecord; NODE node; NODE new_node; 컴퓨터멀티미디어학과 김여자

Insertion(){ index_file_creation(); while(!EOF(dfp)) { input(dfp, key, addr); make_hold_tuple = {key,addr,0}; Search(hold_tuple, root, insert_required); if(insert_required){ ++next; new_node = {1, root, hold_tuple}; Output(bfp, new_node, next); root = next; Output(bfp, root, zero); } 컴퓨터멀티미디어학과 김여자

Index_file_creation(){ root = 0; bfp=fopen(“bindex.dat”,”w”); // B Tree 파일 생성 Index_file_creation(){ root = 0; bfp=fopen(“bindex.dat”,”w”); root_Info_Node = {0, 0, {} }; Output(bfp, rootOfZero, zero); fclose(bfp); } 컴퓨터멀티미디어학과 김여자

Output(bfp, new_node, next){ fseek(bfp, next*RecSize, 0); // 입출력 파일 Output(bfp, new_node, next){ fseek(bfp, next*RecSize, 0); fwrite(new_node, 32, 1, bfp); } Input(bfp, node, p){ fseek(bfp, p*RecSize, 0); fread(node, 32, 1, bfp); 컴퓨터멀티미디어학과 김여자

삽입 75 70 80 90 100 60 g 75 f h c a 50 b c 30 80 d e f g 10 20 40 60 70 75 90 100 c 1, f, (80,A[80], g) => c 2, f, (70,A[70], h),(80,A[80],g) f 2, 0, (60,A[60],0),(75,A[75],0) => h 1, 0, (75, A[75], 0) f 1, 0, (60, A[60], 0) 컴퓨터멀티미디어학과 김여자

삽입 55 70 80 55 60 75 f h 90 100 g c a 50 b c 30 70 80 d e f h g 10 20 40 55 60 75 90 100 f 1,0,(60,A[60],0) =>f 2,0,(55,A[55],0),(60,A[60],0) 컴퓨터멀티미디어학과 김여자

삽입 57 a 50 c 70 80 55 57 60 75 f h 90 100 g b c 30 70 80 d e f h g 10 20 40 55 60 75 90 100 57 70 80 55 60 75 f h 90 100 g c 80 75 f h 90 100 g j 50 70 57 55 60 a c i 컴퓨터멀티미디어학과 김여자

B-Tree : Deletion 삭제 키 값 삭제 : 두 개 Node-> 한 개 Node로 병합 Leap Node 값 중 tuple 개수>( m/2 -1) Node 값을 가진 Tuple 삭제 Leap Node 값 중 tuple 개수 =< ( m/2 -1) 최소 tuple수보다 작아진다. 가장 가까운 형제 노드에 있는 tuple을 빼내어 채움. 컴퓨터멀티미디어학과 김여자

삭제: 5차 b-tree a b c d e f g h j k i 90 30 60 120 160 190 220 10 20 40 50 70 75 80 100 110 130 140 150 j k i 170 180 200 210 230 240 250 컴퓨터멀티미디어학과 김여자

삭제 : 50 삭제 준비 node e의 50 삭제 전 node e의 50 삭제 후 조건 검사 <2, 0, (40,A1,0), (50,A2,0)> node e의 50 삭제 후 조건 검사 <1, 0, (40,A1,0)> m / 2 - 1 > node.n => 조건 위반 node.n > m / 2 인 최근접 오른쪽 형제 node f 로부터 보충 => 조건충족 b의 60 => e로 이동 f 의 최소값 70 => 상위 노드 b로 이동 컴퓨터멀티미디어학과 김여자

삭제: 250 삭제 후, 50 삭제 준비 a b c d e f g h j k i 90 30 60 120 160 190 220 10 20 40 50 70 75 80 100 110 130 140 150 j k i 170 180 200 210 230 240 node e의 최근접 오른쪽 node f 컴퓨터멀티미디어학과 김여자

삭제: 50 삭제 후 결과 a 90 b c 30 70 120 160 190 220 d e f g h 10 20 40 60 75 80 100 110 130 140 150 j i k 170 180 200 210 230 240 node e의 최근접 오른쪽 node f 컴퓨터멀티미디어학과 김여자

삭제: 20 삭제 준비 a 90 b c 30 70 120 160 190 220 d e f g h 10 20 40 60 75 80 100 110 130 140 150 j i k 170 180 200 210 230 240 node d의 최근접 오른쪽 node f 컴퓨터멀티미디어학과 김여자

삭제 : 20삭제 과정 20삭제 후 node d 조건 위반 b b d e f d e f 최근접 오른쪽 node e로 부터 가져옴 node e 조건 위반 => d에 통합 node b 조건 위반 b b 30 70 70 d e f d e f 10 40 60 75 80 10 30 40 60 40 60 75 80 컴퓨터멀티미디어학과 김여자

삭제: 20 삭제 b 조건 위반 a b c d f g h j i k node b의 최근접 오른쪽 node c 90 70 120 160 190 220 d f g h 10 30 40 60 75 80 100 110 130 140 150 j i k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 20 삭제 조정 결과 a b c g d f h i j k 120 70 90 (90,A90,g) 160 190 220 10 30 40 60 75 80 100 110 130 140 150 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 160 삭제 준비 a ㅇ 160 삭제 후 조건충족 ㅇ h의 150 c로 승진 ㅇ c와 h 모두 조건충족 120 b c 70 90 160 190 220 g d f h 10 30 40 60 75 80 100 110 130 140 150 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 160 삭제 후 결과 a ㅇ 160 삭제 후 조건충족 ㅇ h의 150 c로 승진 ㅇ c와 h 모두 조건충족 120 b c 70 90 150 190 220 g d f h 10 30 40 60 75 80 100 110 130 140 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 90 삭제 준비 a ㅇ 90 삭제 후 b 조건위반 ㅇ f로부터 80 가져옴 ㅇ f 조건위반 ㅇ b의 70 => f, d의 60 =>b 120 b c 70 90 150 190 220 g d f h 10 30 40 60 75 80 100 110 130 140 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 90 삭제 과정 ㅇ 90 삭제 후 b 조건위반 ㅇ f로부터 80 가져옴 ㅇ f 조건위반 ㅇ b의 70 => f, d의 60 =>b b b 70 80 60 80 g g d f d f 10 30 40 60 75 100 110 10 30 40 70 75 100 110 컴퓨터멀티미디어학과 김여자

삭제: 90 삭제 결과 a ㅇ 90 삭제 후 b 조건충족 ㅇ f 조건 충족 120 b c 60 80 150 190 220 g d f h 10 30 40 70 75 100 110 130 140 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 120 삭제 준비 a ㅇ 120 삭제 후 g의 110=>a ㅇ g 조건위반 ㅇ f 기본조건 상태 ㅇ f에 g의 통합 120 b c 60 80 150 190 220 g d f h 10 30 40 70 75 100 110 130 140 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 120 삭제 과정 a ㅇ 120 삭제 후 g의 110=>a ㅇ g 조건위반, f 기본조건 ㅇ f에 g의 통합, b 조건위반 ㅇ c로부터 a를 b 110 b c 60 80 150 190 220 g d f h 10 30 40 70 75 100 130 140 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 120 삭제 과정 ㅇ 120 삭제 후 g의 110=>a ㅇ g 조건위반, f 기본조건 ㅇ f에 g의 통합, b 조건위반 ㅇ a의110->b로 이동 ㅇ c의150->a로 이동 a 110 b c 60 150 190 220 d f 10 30 40 70 75 80 100 h i j k 130 140 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 120 삭제 후 결과 a ㅇ a 조건만족 ㅇ b 조건만족 ㅇ f 조건만족 ㅇ c 조건만족 150 b c 60 110 190 220 d f h 10 30 40 70 75 80 100 130 140 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 190 삭제 준비 a ㅇ 190 삭제 후 i의 180=>c ㅇ i 조건위반, i에 j의 통합 ㅇ c 조건위반 ㅇ b에 a, c 통합 150 b c 60 120 190 220 d f h 10 30 40 70 75 80 100 130 140 i j k 170 180 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 190 삭제 과정 a ㅇ 190 삭제 후 i의 180=>c ㅇ i 조건위반, i에 j의 통합 ㅇ c 조건위반 ㅇ b에 a, c 통합 150 b c 60 120 180 220 d f h 10 30 40 70 75 80 100 130 140 i j k 170 200 210 230 240 컴퓨터멀티미디어학과 김여자

삭제: 190 삭제 과정 a ㅇ 190 삭제 후 i의 180=>c ㅇ i 조건위반, i에 j의 통합 ㅇ c 조건위반, b 기본조건 ㅇ b에 a, c 통합 150 b c 60 120 220 d f h 10 30 40 70 75 80 100 130 140 i k 170 180 200 220 230 240 컴퓨터멀티미디어학과 김여자

삭제: 190 삭제 결과 ㅇ 190 삭제 후 i의 180=>c ㅇ i 조건위반, i에 j의 통합 ㅇ c 조건위반, b 기본조건 ㅇ b에 a, c 통합 ㅇ 높이 1수준 낮아 짐 b 60 120 150 220 d f k h i 10 30 40 70 75 80 100 130 140 170 180 200 220 230 240 컴퓨터멀티미디어학과 김여자

B-Tree의 공간효율을 개선한B*-Tree 컴퓨터 멀티미디어학과 컴퓨터멀티미디어학과 김여자

B*-Tree 개념 B트리의 오버플로우된 노드의 키를 아직 꽉 차지 않은 노드에 넣어 삽입 알고리즘 개선 조건 노드가 없거나 hT >= 1 인 m원 트리 루트 노드 : 최소 자식 : 2개 최대 자식 : 2 (2m-2) / 3+1 내부 노드 : 최소 자식 (2m – 1) / 3 최소 키 값 (2m – 1) / 3 -1 모든 터미널 노드는 같은 레벨에 있음. Si=0 터미널을 제외한 모든 노드에 대하여 Si를 가리키는 포인터가 k개이면 k-1의 키 값을 가짐 컴퓨터멀티미디어학과 김여자

B*-Tree의 각 노드의 제원 7차 B-Tree의 경우 7차 B*Tree의 경우 루트노드 : (2,m) = 2  child  7 1  keys  6 내부노드 : ( m/2 ,m) = 4  child  7 3  keys  6 7차 B*Tree의 경우 루트노드 : (2, 2(2m-2)/3+1) = 2  child  9 = 1  keys  8 내부노드 : ((2m-1)/3, m) = 5  child  7 = 4  keys  6 컴퓨터멀티미디어학과 김여자

B-트리와 B*-트리 비교 B*-tree (m-way) B-tree (m-way) 루트 노드(root node) 키 갯수 : 1 ~ (m-1), Si 수 : 2 ~ m 중간 노드( nonterminal node) 키 갯수 : m / 2 - 1 ~ m - 1 , Si 수 = : m / 2 ~ m 리프 노드(leaf node,terminal node) 키 갯수 : 중간 노드와 동일 / Si : 0 B*-tree (m-way) 루트 최대 키 값의 수 :  2 (2m-2) / 3 중간 / 리프 노드의 최소 키 값의 수 : (2m-1) / 3 - 1 중간 노드가 가득차면 여유 있는 형제노드로 이동 두 형제 노드가 가득차면 3분할 나머지 조건은 같음 컴퓨터멀티미디어학과 김여자

7차 B*-tree 루트의 분열 60 50 10 20 30 40 60 70 80 90 7차 B*-tree 노드의 키 갯수 10 20 30 40 50 70 80 90 7차 B*-tree 노드의 키 갯수 루트(최대): (2*7-2)/3=4*2=8 중간(최소): (2*7-2)/2=4 중간(최대): 7-1 = 6 60 10 20 30 40 50 60 70 80 90 50 10 20 30 40 60 70 80 90 컴퓨터멀티미디어학과 김여자

7차 B*-tree에서 overflow 내가 다 가질 수 없으면 가난한 형제자매에게 주어라. 70 10 20 30 40 60 65 80 90 100 110 50 65 10 20 30 40 50 60 70 80 90 100 110 컴퓨터멀티미디어학과 김여자

7차 B*-tree 노드 분할 둘이 합치면 셋으로 분할. 분가 65 10 20 30 35 40 50 60 10 20 30 35 40 50 60 70 80 90 100 101 102 35 40 80 10 20 30 35 50 60 65 70 90 100 101 102 컴퓨터멀티미디어학과 김여자

m원 B*-tree node 분열 Key 위치 1) 첫번째 키 :  =  (2m-2)/3 + 1 Kp K1 K2 K3 … Km-2 Km-1 Km K’1 K’2 K’3 … K’m-2 K’m-1 Key 위치 1) 첫번째 키 :  =  (2m-2)/3 + 1 2) 두번째 키 :  =  (m-1)/3  + 1 컴퓨터멀티미디어학과 김여자

m원 B*-tree 노드 분할 Key 위치 K  K  K1 K2 … K -1 K +1…Km-1 Kp K1...K -1 컴퓨터멀티미디어학과 김여자

B+ - 트리 i) 인덱스 세트 (index set) ii) 순차 세트 (sequence set) · 루트 및 내부노드 : 키 값만 가짐 · leaf node 보유 키 값의 경로정보 제공 . 높이가 낮음 => 디스크 접근 횟수 감소 ii) 순차 세트 (sequence set) · leaf node · 모든 레코드의 키 값, 주소들을 포함 · 순차 세트는 순차적으로 연결 → 직접 또는 순차 접근 · 내부 노드와 다른 구조 컴퓨터멀티미디어학과 김여자

B+-Tree의 노드 정보 루트 및 내부노드 터미널 노드 빠른 순차적 탐색 위해 터미널 노드를 제외한 노드들은 n, S0, (K1, S1) (K2, S2) 터미널 노드 n, S0, (K1, A1, S1) (K2, A2, S2) 빠른 순차적 탐색 위해 Leap node들은 키 값 순으로 연결되어 있음 터미널 노드를 제외한 노드들은 더 많은 키 값을 가지므로 많은 수의 키 값 일 경우 B Tree보다 높이가 낮다. 빠른 탐색 또는 적은 디스크 접근횟수 제공 B+-Tree의 단점 각 탐색은 터미널까지 검색되어야 키를 찾을 수 있음. (단, B+는 B트리 보다 적은 레벨) 컴퓨터멀티미디어학과 김여자

B-Tree 또는 B*-Tree 예 50,1 30,5 80,9 10,4 20,2 40,0 60,7 70,3 90,6 100,8 키 위치 40 1 50 2 20 3 70 4 10 5 30 6 90 7 60 8 100 9 80 컴퓨터멀티미디어학과 김여자

B+-Tree 예 index set sequence set data file 40 20 40 60 80 10,4 20,2 30,5 40,0 50,1 60,7 70,3 80,9 90,6 100,8 data file 40 50 1 20 2 70 3 10 4 30 5 90 6 60 7 100 8 80 9 컴퓨터멀티미디어학과 김여자

B+-Tree 특성 ① 루트의 서브트리 : 0, 2, m/2 ∼ m ② 노드의 서브트리 (루트,리프제외) : 2 ∼ m ③ 모든 리프는 동일 레벨 ④ 리프가 아닌 노드의 키값 수 : 서브트리수-1 ⑤ 리프노드 : 데이타 화일의 순차세트 (리스트로 연결) 컴퓨터멀티미디어학과 김여자

B+-Tree의 연산 -삽입 · -탐색 -삭제 - B+-트리의 인덱스 세트 = m-원 탐색 트리 - leaf node에서 검색 · -탐색 - B+-트리의 인덱스 세트 = m-원 탐색 트리 - leaf node에서 검색 -삽입 - B-트리와 유사 - overflow(분열) → 부모노드, 분열노드 모두에 키값 존재 -삭제 - 리프에서만 삭제 (재분배, 합병 없는 경우) - 재분배시 : 인덱스의 키 값도 삭제 컴퓨터멀티미디어학과 김여자

B+-Tree의 적용 데이터파일 색인에 대한 상용구조 비터미널 노드는 데이터파일의 색인, 터미널노드는 데이터파일내의 레코드 블록이 됨 응용 예 CDC : SIS 파일 IBM : VSAM 파일 컴퓨터멀티미디어학과 김여자

탐색 트리 요약 상대 파일 접근 방안 hashing indexing static dynamic B-tree B*-tree 컴퓨터멀티미디어학과 김여자