1. 텍스트를 위한 파일 1) 개념 : 텍스트 필드로만 구성된 레코드를 접근할 수 있는 화일 2) 특징 - 텍스트 필드는 하나의 필드 안에 여러 개의 탐색 값(단어, keyword)가 포함 - keyword : '데이터베이스', '시스템', '질의어' 라는 단어를 어떤 방법으로 탐색할 것 2. 역 리스트 화일 1) 특징 - 역 리스트 화일 구조 : 인덱스 화일 + 포스팅 화일 + 데이터 화일로 구성 - 인덱스 화일 : 키워드 + 관련 레코드 수 + 포스팅에 대한 포인터 - 포스팅 화일 : 키워드를 포함한 데이터 레코드에 대한 포인터 리스트, 발생빈도, 키워드의 중요도, 발생 위치 추가 - 데이터 화일 : 문서 화일 2) 예시 - 키워드는 가나다 순으로 정렬 3) 장단점 ⓐ 장점 : 구현이 용이, 속도가 ..

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) 상대 화일 - 레코드의 키와 레코드의 위치 사이에 설정된 관계를 통해 레코드에 접근 - 상대 레코드 번호 : 화일이 시작되는 첫 번째 레코드를 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) 1차 저장 장치 메인 메모리 : 내용을 접근하는 시간은 일정하고 빠름, 프로그램/데이터 처리 위한 작업 공간 캐시 메모리 : 메인 메모리의 성능 향상 목적 2) 2차 저장 장치 자기 디스크 : 데이터 접근이 느림 BUT 싸서 주로 화일 저장에 쓰임 광 디스크, 자기 테이프 2. 저장 장치의 계층 1) 캐시 메모리 - 가장 빠르고 가장 비싼 저장장치, 용량 아주 작음 - 저장 매체 : SRAM(Static Random Access Memory) - CPU 성능을 증진 시키기 위해 사용 - 소멸성 : 데이터 저장에는 부적합 2) 메인 메모리 - 프로그램 실행과 이에 필요한 데이터 유지 공간 - 저장매체 : DRAM(Dynamic Ran..

1. 화일의 종류 - 정보와 데이터는 다르다. - 데이터(D)가 처리(P)되어 정보(I)가 된다. I = P(D) - 대용량 데이터는 디스크에, 그 데이터를 메인 메모리에 가져와서 처리한다. 👉 디스크에 저장하는 데이터는 크게 '화일'로 구분된다. 1) 화일 구조 - 디스크에 저장할 데이터의 표현과 데이터를 접근하기 위한 연산의 조합 2) 데이터 집합을 디스크 화일로 구성하는 이유 주 기억장치에 저장하기에 데이터 양이 너무 많음 프로그램은 특정 시간에 데이터 집합의 일부만 접근함 데이터의 독립성을 유지하기 위해 3) 화일의 분류 ① 기능에 따른 분류 - 마스터 화일 : 영속적 데이터 레코드를 포함한 화일(현재성을 유지해야함) - 트랜잭션 화일 : 마스터 화일에 적용할 변경 내용(삽입, 삭제, 수정)을 모..