1. 텍스트를 위한 파일 1) 개념 : 텍스트 필드로만 구성된 레코드를 접근할 수 있는 화일 2) 특징 - 텍스트 필드는 하나의 필드 안에 여러 개의 탐색 값(단어, keyword)가 포함 - keyword : '데이터베이스', '시스템', '질의어' 라는 단어를 어떤 방법으로 탐색할 것 2. 역 리스트 화일 1) 특징 - 역 리스트 화일 구조 : 인덱스 화일 + 포스팅 화일 + 데이터 화일로 구성 - 인덱스 화일 : 키워드 + 관련 레코드 수 + 포스팅에 대한 포인터 - 포스팅 화일 : 키워드를 포함한 데이터 레코드에 대한 포인터 리스트, 발생빈도, 키워드의 중요도, 발생 위치 추가 - 데이터 화일 : 문서 화일 2) 예시 - 키워드는 가나다 순으로 정렬 3) 장단점 ⓐ 장점 : 구현이 용이, 속도가 ..
Major/Database
1. 다차원 공간 화일 1) 특징 - 여러 개의 필드를 동시에 키로 사용한 화일 2) 종류 - PAM(Point Access Method) : 다차원의 점 데이터를 저장, 검색 - SAM(Spatial Access Method) : 선, 면과 같은 다차원 도형 데이터를 저장, 검색 2. k-d 트리 1) 개념 - 이원 탐색 트리를 다차원 공간으로 활장한 것 - 기본 구조와 알고리즘은 이원 탐색 트리와 유사 - 트리의 레벨에 따라 차원을 번갈아 가며 비교 2) 특징 - 주기억 장치 상에서 동작 - 소규모의 다차원 점데이터를 인덱싱 할 때 적합 - 균형 트리가 아님 3) 삽입 - 4사분면에서 루트 점 저장하고 x값과 y값을 번갈아가며 비교하며 자식 노드에 삽입한다. 4) 단점 : 균형트리가 아니므로 검색 성..
01 다중 키 화일 1. 다중 키 화일의 개념 1) 단일 키화일 - 지금까지 살펴 본 화일들로 기본 키를 사용하는 화일 - 순차 화일, 직접화일, 인덱스된 순차화일 2) 다중 키 화일 - 하나의 데이터 화일에 대해 여러 다른 탐색키를 이용한 여러 개의 접근 경로를 제공 3) 구현 방법 - 데이터를 중복 이용하여 각 응용에 맞는 화일을 각각 구성 - 한 화일에 대한 다수의 접근 경로 구축 : 다중 키 화일 역 화일 : 인덱스 이용 다중리스트 화일 : 레코드 사이의 리스트 이용 02 역 화일 1. 역 화일 구조 - 역 인덱스를 이용하는 구조 - 역 : 인덱스와 데이터 레코드 화일을 연결 2. 역 인덱스 1) 특징 - 데이터 화일에 있는 키 필드 값을 인덱스 키로 포함 - 인덱스 엔트리 = (키 값, 레코드 ..
01. 직접 화일의 개념 1. 직접화일 1) 임의 접근 화일 = 직접 화일 - 다른 레코드를 참조하지 않고도 개개 레코드에 접근 가능 - 인덱스된 화일, 인덱스된 순차 화일, 상대 화일, 해시 화일 2) 상대 화일 - 레코드의 키와 레코드의 위치 사이에 설정된 관계를 통해 레코드에 접근 - 상대 레코드 번호 : 화일이 시작되는 첫 번째 레코드를 1번으로 지정, 기준으로 번호 지정 > 사상 함수 - A : 키 값 => 주소 - 레코드 기록 시 : 키 값 => 레코드가 저장될 주소 - 레코드 검색 시 : 키 값 => 레코드가 저장되어있는 주소 - 모든 레코드에 직접 접근 가능(메인 메모리, 디스크등 직접 저장 장치에 저장하는 것이 효율적) - 사상함수 구현방법 : 디렉터리 검사, 계산을 이용한 방법 3) 디..
1. 인덱스된 순차화일의 구조 1) 구조 - 순차적으로 정렬된 순차데이터 화일과 이 데이터 화일에 대한 포인터를 가지는 인덱스로 구성 - 각 화일은 블록으로 구성 : 인덱스 블록(트리 구조), 데이터 블록(데이터 레코드와 자유공간) ⓐ 마스터 인덱스 : 최상위 레벨의 인덱스 블록 ⓑ 인덱스 엔트리의 구성 : ⓒ 자유 공간 : 레코드의 추가를 위해 남겨둔 여분의 공간, 화일 생성 시 각 블록에 만듦 > 인덱스된 순차 화일 - 키 값에 따라 정렬된 레코드를 순차적으로 접근 or 직접 접근하는 경우 사용 - 사전 검색 시 사전 옆면의 색인이 인덱스랑 같은 역할 * 일괄처리와 대화식 처리가 적합한 경우 2) 삽입 - 최대 키값에 따라 삽입, 만약 블록이 꽉찼다면 반으로 분할한다. - 분할됐으면 포인터 되는 키 ..
1. m-원 탐색 트리 1) 특징 : 이원 탐색 트리보다 분기율을 높여 m개 서브트리로 만든 것 ① 장점 : 트리의 높이가 감소(특정 노드 탐색시간 감소) ② 단점 : 삽입, 삭제 시 트리의 균형 유지를 위해 복잡한 연산이 필요함 ③ 노드 구조 : ex) 3-원 탐색 트리 2) m-원 탐색 트리의 검색 - 루트부터 시작하여 찾으려는 노드의 키 인덱스를 증가시키면서 키 값과 찾으려는 키 값이 동일하면 탐색을 멈춘다. ⓐ 탐색 시간 : 탐색 경로 길이(높이)에 비례 ⓑ 한 노드에는 m-1개 키 값을 저장 ⓒ 높이가 h일 때 - 최대 키 값의 개수: m^h-1 개 - 최소 높이 : logm(n+1) - 최대 탐색 시간 : O(logm(n+1)) 2. B-트리 1) 특징 : 균형된 m-원 탐색트리 ⓐ 루프와 리..
1. 인덱스 1) 특징 : 파일의 레코드들에 대한 효율적 접근 - 쌍 2) 종류 - 키에 따른 인덱스 : 기본 인덱스, 보조 인덱스 - 파일 조직에 따른 인덱스 : 집중 인덱스, 비집중 인덱스 - 데이터 범위에 따른 인덱스 : 밀집 인덱스, 희소 인덱스 3) 이진 트리 : 왼쪽 서브트리와 오른쪽 서브트리로 구성 2. 이원 탐색 트리 - 이진트리이면서 각 노드 Ni 레코드 키Ki와 이 키를 가지고 있는 레코드 포인터를 포함함 - 왼쪽 서브트리 Ki : 루트의 오른쪽 서브트리를..
1. 정렬/합병의 개요 1) 정렬 ① 내부 정렬 - 데이터가 적어서 메인 메모리 내에 모두 저장시켜 정렬 가능할 때 ② 외부 정렬 - 데이터가 많아서 메인 메모리의 용량을 초과해 보조 저장 장치에 저장된 화일을 정렬할 때 - 레코드 판독, 기록에 걸리는 시간이 중요 - 정렬/합병 : 런 이용(하나의 화일을 여러 개의 서브 화일로 나누어 내부 정렬 기법을 사용해 정렬시킨 화일) 2) 화일 정렬/합병 ⓐ 정렬 단계 : 정렬할 화일의 레코드들을 서브화일로 분할해서 정렬하여 런을 만들어 입력 파일로 분배 ⓑ 합병 단계 : 정렬된 런들을 합병해 보다 큰 런으로 만들고 다시 입력 파일로 재분배하여 합병해 모든 레코드들이 하나의 런에 포함되도록 만드는 단계 ⓒ 런 : 정렬된 서브파일 3) 정렬 단계 ⓐ 런 생성 방법..
1. 순차 화일 1) 정의 - 레코드를 조작하는 가장 기본적인 방법으로 화일 생성 시 레코드들을 연손적으로 저장 - 레코드들을 접근할 때도 저장할 때 순서대로 연속적으로 접근 2) 종류 - 입력 순차 화일 : 레코드가 입력되는 순서대로 저장 - 키 순차 화일 : 레코드의 특정 필드 값 순서에 따라 저장 2. 스트림 화일 1) 정의 - 연속적인 판독 연산을 통해 레코드가 화일에 저장되어있는 순서에 따라 데이터를 접근하는 화일 - 데이터가 하나의 연속된 바이트 스트림으로 구성 2) 종류 ⓐ 순차 접근 스트림 화일 : 기본 스트림 화일을 판독(read)모드로 열면 판독 포인터는 화일의 첫번째 바이트를 가르킴 > 판독 연산 - 해당 위치에서 시작하여 해당 바이트 값을 전송 - 판독 포인터를 스트림 화일의 다음 ..
