<정보처리기사>1.데이터베이스(4)

자료구조

-저장방법, 관계 , 정렬, 인덱스, 검색 등을 처리하는데 쓰는 방법

-선형구조:리스트 스택 큐 데크 비선형구조: 트리 그래프

선형리스트- 배열처럼 연속되는 기억장소에 저장됨, 간단한구조

              - 접근 속도 빠름, 중간에 넣으려면 빈공간있어야함, 삽입삭제 번거로움

연결리스트- 임의의 기억공간에 기억시키는 방법

              - 삽입,삭제 간편 , 접근속도 느림, 트리에 적합

스택- 한쪽 끝에만 삽입 삭제, LIFO 후입선출

      - 분야: 복귀주소 저장, 순서제어, 수식연산, 언어번역               

 

큐- 한쪽끝 삽입 다른쪽끝 삭제 FIFO 선입선출, 포인터사용(F먼저삽입, R막에삽입)

데크- 삽입과 삭제가 양쪽에서 이루어짐

트리- 정점과 선을 이용 사이클이 없는 그래프형태, 디그리=가지, level=층수

      - 이진트리: 디그리가 2이하 , 종류로 정이진 전이진 사향이진

      - 운행법 peroder, inorder postorder 

      - preFix: 연산자가 앞으로 나오는 방식, postFix: 연산자가 뒤로 나오는 방식

     

그래프- 정점과 간선으로 이루어진 사이클있는 그래프

         - 최소비용신장트리: 가장 단거리로 사이클을 이루지 않는 그래프 

-------------------------------------------------------------------------------------

내부정렬- 주기억장치에 기억시키는 정렬방식, 소량데이터

           - 선택법 삽입법 교환법 병합법 분배법

           - 삽입정렬: 앞뒤 비교, 선택정렬:앞부터 정렬 작은값이 앞으로

           - 버블정렬: 인접두개 비교 정렬 큰값이 뒤로

           - 그외 쉘정렬 퀵정렬 힙정렬 2way병합정렬 기수정렬

외부정렬- 보조기억장치에 기억시키는 정렬방식 대량데이터

           - 밸럴스 캐스케이드 폴리파즈 오실레이팅

---------------------------------------------------------------------------------------

선형검색- 순서화 되지않는 파일에서 순차적 검색방법, 프로그램 간단

 

제어검색- 순서화된 파일만 가능, 종류로 이분,피보나치,보간,블록,이진트리 검색방법

해싱- 해시테이블에 기억공간 할당하고 해시함수를 이용 HA를 계산 후 해당 기억장소         에 저장 or 검색 방식

      - 기억공간 많이필요, 검색속도 빠름, 삽입삭제 많이할때 적합, called 키주소변환

 해시테이블- 레코드 한개이상 보관하는 bucket(파일의 한 구역)들로 구성된 기억공간,                   보조기억장치 와 주기억장치 모두 구성가능

----------------------------------------------------------------------------------------

인덱스- 레코드를 빠르게 접근하기 위해 구성, 빠른 엑세스

m원 검색트리- 동일한 문자열 or 숫자 일 경우 효율적

B트리- 오름차순 유지, 모든 것은 root로 부터 , 삭제삽입해도 구조의 균형유지

트라이색인- 문자나 숫자 자체의 순서로 키 값 구성

-----------------------------------------------------------------------------------------

순차파일- 기억공간 효율적 사용, 어떤매체든 가능, 삭제시 많은 시간 소요, 응답느림

색인순차파일- 순차처리 랜덤처리 가능, 구성으로 기본 색인 오버플로우 구역 구성

                 - 자기디스크에서 사용되며 자기테이프는 사용불가

                 - called ISAM( Index Sequential Access Method)

정적인덱스- 구조 변경되지 않고 내용만 변함, ISAM

동적인덱스- 각 블록에 추가로 빈공간을 미리 예비해 두는 방식, VSAM