 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
||||
1장 B-트리
1. B-트리 구조
2. B-트리 연산
3. B-트리 삽입
4. 한 레벨 증가된 B-트리
5. B-트리 삭제
6. 노드 d에서 키 값 16의 삭제
2장 B*-트리
1. B*-트리 삽입
2. 재분배를 이용한 삽입 예
3. 차수가 m인 B*-트리에서의 노드 분열
4. 노드분열을 이용한 삽입
3장 B+-트리
1. 차수가 3인 B+-트리
2. B+-트리 특성
3. B+-트리 연산
4장 트라이 (Trie)
1. m-원 트라이
2. 높이가 4인 10원 트라이
인덱스 구조 b-트리 균형 m-원 탐색 트리 차수 m인 b-트리의 특성 (m-원 탐색트리) ① 루트와 리프를 제외한 노드의 서브트리 수 m/2 ≤ 개수 ≤ m
② 루트는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
③ 모든 리프는 같은 레벨에 있다.
④ 키값의 수 리프 : m/xxx-xxx ~ (m-1) 리프가 아닌 노드 : 서브트리수-1
⑤ 한 노드 내의 키 값들은 오름차순을 유지함.
▶ b-트리 구조 노드 구조 ki → (ki, ai) n p 1 k 1 p 2 k 2 p 3 … p n-1 k n-1 p n n p1 k1 p2 k2 p3 … pn-1 kn-1 pn * 차수 3인 b-트리 구조 ▶ b-트리 연산 연산 직접 탐색-키 값에 의존한 분기 순차 탐색-중위 순회 삽입, 삭제-트리의 균형 유지 분할 → 높이 증가 합병 → 높이 감소 삽입 (a) 노드 l에 22 삽입 ▶ b-트리 삽입 (b) 노드 n에 41 삽입 (c) 노드 o에 59 삽입 ▶ b-트리 삽입 (d) 노드 o에 57 삽입 (e) 54의 삽입으로 노드 o의 분열 (f) 노드 f에 54 삽입 ▶ b-트리 삽입 (g) 노드 b에 58 삽입 (h) 노드 a에 43 삽입 ▶ 한 레벨 증가된 b-트리 ▶ b-트리 삭제 삭제 노드 e에서 키 값 40의 삭제 ▶ 노드 d에서 키 값 16의 삭제 b*-트리 2/3 정도 찬 노드들을 가지는 b-트리 노드 분할의 횟수 줄임 노드가 가득참 → 형제노드로 분산 (이동) 두 개의 이웃노드가 모두 가득 찼을 때의 삽입 두 개의 노드를 세 개로 분할시킴 2/3 가득 참 ▶ b*-트리 삽입 차수가 m인 b*-트리
차수가 m인 b*-트리에서 재분배를 이용한 키 값 km의 삽입
▶ 재분배를 이용한 삽입 예
차수가 5인 b*-트리에서 재분배를 이용한 키 값 24의 삽입
▶ 차수가 m인 b*-트리에서의 노드 분열 ▶ 노드분열을 이용한 삽입
차수가 5인 b*-트리에서 노드 분열을 이용한 키 값 24의 삽입
b-트리 인덱스 셶 (index set) 내부 노드 리프에 있는 키들에 대한 경로정보 제공 순차 셶 (sequence set) 리프 노드 모든 키 값들을 포함 순차셶은 순차적으로 연결 직접 또는 순차 접근 내부 노드와 다른 구조 ▶ 차수가 3인 b-트리 ▶ b-트리 특성 ① 루트의 서브트리 : 0, 2, m/2 ∼ m ② 노드의 서브트리 (루트,리프제외) : 2 ∼ m ③ 모든 리프는 동일 레벨 ④ 리프가 아닌 노드의 키값 수 : 서브트리수-1
⑤ 리프노드 : 데이타 화일의 순차셶 (리스트로 연결)
▶ b-트리 연산 연산 탐색 b-트리의 인덱스 셶 m-원 탐색 트리 리프에서 검색 삽입 b-트리와 유사
오버플로우(분열) → 부모노드, 분열노드 모두에 키값 존재
삭제 리프에서만 삭제 (재분배, 합병 없는 경우) 재분배시 : 인덱스의 키값도 삭제 트라이 (trie)
글자나 숫자의 위치에 의해 키값을 나타내는 자료구조
10원 트라이의 노드 구조 ▶ m-원 트라이 m진 트리 m 10 : 숫자 m 26 : 글자 레벨 j, pi
: j 번째 값이 pi인 모든 키 값을 나타내는 서브트리를 가리킴 (이하 생략)
