File Processing

화일처리론 / 이석호 교수님 / 2003 Fall


Chapter 6. 인덱스 구조

B*-tree
- 모든 노드는 [(2m-2)/3]+1 ~ m 개의 서브트리를 가짐
- 루트는 2 ~ 2[(2m-2)/3]+1 개의 서브트리를 가짐
- B-tree 에 비해 분열의 빈도가 줄어듬

B+-tree
- index set 과 sequence set 으로 구성
- 모든 노드는 [m/2] ~ m 개의 서브트리를 가짐
- 리프 노드는 데이타의 순차 세트이며 리스트로 연결되어 있음
- 검색 : O(log_(m/2) n ) 시간 (최소 m/2개의 서브트리를 가지므로)
- insert : overflow이면 spilit
- delete : underflow이면 redistribution 또는 merge

trie
- 초기엔 널 포인트. 입력될 경우에 새 노드를 생성


Chapter 7. 인덱스된 순차 화일

정적 인덱스
- 마스터 인덱스, 실린더 인덱스, 트랙 인덱스
- 입력시 오버플로 구역 활용, 삭제시 물리적으로 삭제하지 않을 수 있음

ISAM file
- 트랙0:인덱스, 트랙1~n-1:데이타. 트랙n:오버플로
- 각 실린더별 오버플로 구역 외에 별도의 실린더에 독립된 오버플로 구역

인덱스 분기율(fan-out ratio) = [ B / V+P ]
- B : 블록 크기
- V : 키값 크기, P : 포인터 크기
- 최상위 인덱스는 블록 1개, 메모리에 상주


Chapter 8. 직접 화일

생략-_- (hashing에 관한 내용)


Chapter 9. 다중 키 화일

역 인덱스
- 보조키와 기본키의 쌍 : 역 인덱스 화일에 변화를 주지 않고도 데이타 화일을 물리적으로 재구성, 재조직 가능하게끔 함

역 화일과 다중 리스트 화일의 비교
- 다중 리스트 방식은 인덱스의 엔트리가 고정길이이므로 인덱스 관리가 용이
- 역 인덱스 방식은 역 인덱스만 접근해서 질의에 응답 가능하므로 질의문 처리 능력에서 우위
- 역 인덱스 방식은 프로그래머에게 투명하다.


Chapter 10. 다차원 공간 화일

R-트리
- 검색 : k-NN(Nearest Neighbor) 질의
- 삽입 : 기존 MBR을 최소로 확장시키는 것 선택 - 오버플로우면 최소가 되도록 분할 - 루트 방향으로 영향 전달
- 삭제 : 언더플로우면 노드를 삭제하고 노드에 있던 엔트리들을 재삽입

R*-트리
- 겹치는 부분이 최소가 되도록
- 사각형의 면적이 최소가 되도록
- 사각형의 둘레이 길이가 최소가 되도록
- 강제 재삽입 : 오버플로우 사각형의 변두리 엔트리를 재삽입하여 재분배의 효과

R+-트리
- 겹치는 부분이 없음
- 높이 증가 - 사용 공간 증가