CH 4 순차 파일
저장 장치 내의 레코드 순서 = 레코드 리스트의 순서
입력 순차 파일, 키 순차 파일
트랜잭션 화일 : 레코드 수집 및 편집을 위해, 입력 레코드를 임시로 보관하는 곳 즉 레코드의 삽이만 이루어짐
- 입력 순차 화일 형태
마스터 화일 : 레코드를 영구히 보관하는 곳
- 키 순차 화일 형태
기본동작 = 레코드에 대한 실제 갱신은 트랜잭션 화일과 마스터 화일의 합병을 통해 이루어진다
트랜잭션 화일 + 마스터 화일 의 합병 = 뉴 마스터 화일
완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다
포화 이진 트리 : 마지막 레벨까지 꽉찬 트리
(1) 이원 탐색 트리
임의 접근 : 최소 log2N, 최대 N
N개의 노드를 갖는 높이 h인 BST의 최소 높이
N <= 2h - 1 = N + 1 <= 2h (2의 h제곱임)
(그 반올림수 괄호 0.5면 1인거) [log2(N+1) <= h]
BST = log2(N+1) <= h <= N : 최소, 최대 높이
(2) AVL = 완전 균형 BST
시간 복잡도 : 최소 : log2N, 최대 : 1.44*logxN
LL : 2, 1, ? = a, b, c(root) => a, b(root), c
RR : -2, -1, ? = a(root), b, c => a, b(root), c
LR : 2, -1, ? = a, b, c(root) => b, a(root), c
RL : -2, 1, ? = a(root), b, c => a, c(root), b
AVL 트리의 최소, 최대 높이 : [log2(N+1)] <= h <= [1.44 * log2(N+2)]
(3) MST = m-원 탐색트리
시간 복잡도 : 최소 : logm(N), 최대 : N
높이 : [logm(N+1)] <= h <= N
(4) B-트리
시간 복잡도 : 최소 : logmN, 최대 : logm/2N
검색 성능 : 최소 logm(N+1)
최대 높이 : logm/2(N+1)
최소 높이 : logm(N+1)
인덱스 블럭 : 인덱스 엔트리 들이 키 값으로 정렬되어 있음
엔덱스 블럭들이 트리 구조를 이룸
데이터 블럭 : 데이터 레코드 들이 키 값으로 정렬되어 있음
데이터 블럭들은 순서대로 연결 되어있다
PAM : 다차원 점 데이터를 저장
SAM : 선, 면과 같은 다차우너 영역 데이타 저장
