데이타베이스 기초개념

데이터베이스 관리자(DBA)

        ∙ 데이터 정의어와 제어어를 이용하여 데이터베이스를 정의, 제어, 관리하는 관리자

        ∙ 데이터베이스에 대한 접근 권한 설정, 제작과 갱신, 보전과 관리, 데이터베이스 성능 변경 요구에 대한 응답 등의 임무를 가짐

데이터베이스 모델의 종류

        ∙ 계층적 데이터베이스 모델 : 하나의 루트 레코드 타입과 다수의 종속 레코드 타입으로 구성된 순서 트리 → 데이터를 빠르게 검색할 수 있지만 유연성이 부족

        ∙ 네트워크형 데이터베이스 모델 : 계층 모델을 개선하여 그래프(Graph) 구조를 기반으로 구성 → 데이터의 변경이 어려워 확장성이 떨어짐

        ∙ 관계형 데이터베이스 모델 : 개체를 테이블(Table)로 사용하고 개체 집합들 사이의 관계를 공통 속성으로 연결하는 독립된 형태의 데이터 모델 → 현재 가장 많이 사용되고 있는 모델

        ∙ 객체 지향형 데이터베이스 모델 : 데이터와 절차(Procedure)를 일체화한 단위로 다루는 개체 지향의 사고 방식을 이용한 데이터 모형

관계형 데이터베이스의 용어

        ∙ 속성(Attribute) : 테이블의 열을 구성하는 필드

        ∙ 도메인(Domain) : 애트리뷰트에서 나타날 수 있는 값의 집합

        ∙ 차수(Degree) : 테이블에서 속성/필드의 수

        ∙ 튜플(Tuple) : 데이터베이스 모델에서 테이블의 행

        ∙ 카디날리티(Cardinality) : 관계 데이터베이스에서 하나의 릴레이션에 포함되어 있는 데이터 레코드의 개수

        ∙릴레이션(Relationship) : 연관된 속성의 집합으로 관계형 모델에서 테이블(Table)을 의미

키(Key)의 개념

        ∙ 기본 키 : 튜플을 유일하게 식별할 수 있는 속성값으로 후보 키가 두 개 이상인 경우에 그 중 하나를 선택한 키

        ∙ 후보 키 : 유일성과 최소성을 만족하는 튜플의 최소성을 갖는 키

        ∙ 대체 키 : 후보 키에서 기본 키를 제외한 나머지 후보 키들을 의미

        ∙ 슈퍼 키 : 한 개 이상의 속성들로 구성되며, 이 속성들이 그 개체 내에서 유일하게 지정되는 키

        ∙ 외래 키 : 어떤 릴레이션에 속하여 있는 속성이나 속성 집합이 다른 릴레이션의 기본 키가 되는 키 

[출처] 컴활1급필기 데이타베이스부분2|작성자 이플

E-R다이어그램으로 표현 p.Chen이 제안
개체타입과 이들간의 관계타입을 이용해 현실 세계를 개념적으로 펴현한 방법
E-R다이어 그램은 E-R모델을 그래프 방식으로 표현

1. 데이터베이스의 논리적 구성

   ① 개체(Entity)

        - 파일에서 하나의 레코드(Tuple) - 하나 이상의 속성(Attribute)로 구성 - 현실 세계에 존재

        * 개체타입(Entity Type) : - 같은 개체들이 가지고 있는 속성들의 집합

                                  - a Set of Attribute that have the same entities

   ② 속성(Attribute) - 개체들의 특성, 속성

2. 스키마(Schema)

   - d/b 전체적인 논리적 설계에 대한, 구조에 대한 정의 - 데이터 사전에 저장 - 메타데이터(Meta-Data)

   ① 외부스키마(=서브스키마) : 사용자나 프로그래머 관점의 구조

   ② 개념스키마 : - d/b 전체적인(범 기관적인) 입장의 구조

                   - 개체들의 정의, 접근권한, 보안, 무결성 규칙 등을 기술

   ③ 내부스키마 : 물리적인 저장장치 입장의 구조

3. DBMS의 필수 기능(언어)

   ① 데이터정의 기능(언어:DDL) : DB와 응용프로그래머 사이의 인터페이스

   ② 데이터조작 기능(언어:DML) : 사용자와 DBMS 사이의 인터페이스

                - 자료의 검색, 수정, 삽입, 삭제 등의 기능 지원

     * 질의어(Query Language) : 독자적이고 대화식 상호작용 형태로 터미널에서 많이 사용하고 있는

                                 독립된 데이터 조작어, 비절차적인 언어

   ③ 데이터제어 기능(언어:DCL) : 보안, 무결성, 동시(병행) 제어 등

4. DBMS의 장점과 단점

   - 장점 : 중복 데이터 최소화, 데이터 공유, 무결성 유지, 표준화 가능, 보안유지

   - 단점 : 비용이 많이 들고 구축 방법이 복잡, 예비(Backup) 및 회복(Recovery)이 어렵다.

5. DBA(데이터베이스 관리자)의 역할

   - 스키마 정의, 예비/회복 절차 수립, 저장구조와 접근 방법 설정, 데이터 사전 유지 관리

   - 보안검사와 무결성 검사 정의, D/B설계와 운영, 시스템 감시 및 성능분석

   * 응용프로그램 개발(코딩)과는 관계없다.

6. E-R 다이어그램

   - Peter Chen 제안, 가장 많이 사용

   - 표기법 ① □ : 개체  ② ○(타원) : 속성  ③ ◇ : 관계  ④ - : 연결선

   - 대응관계의 표시 ① 1:1(일대일)  ② 1:n(일대다)  ③ n:m(다대다)

7. 논리적 데이터 모델

   ① 관계형 모델 : 표(Table)구조

   ② 계층형 모델 : 트리(tree)구조, 1:n(일대다)

   ③ 망형 모델 : 그래프구조, Owner-member관계, n:m(다대다)

8. 정규화(Normalization)

   - 함수의 종속성 이론을 이용하여 잘못 설계된 관계형 스키마를 저 작은 속성의 세트로 쪼개어 바람직한

     스키마로 만들어 가는 과정

   - 데이터의 중복방지, 논리적 설계단계에서 수행한다. - 목적: 이상현상의 해결

   - 정규화 유형

        ① 제1정규형(1NF) : 모든 도메인이 원자값만으로

        ② 제2정규형(2NF) : 완전한(충분한) 함수종속

        ③ 제3정규형(3NF) : 이행적 함수 종속 제거

        ④ BCNF(보이스코드) : - 릴레이션의 모든 결정자가 후보키인 경우

                               - 3NF를 결정자가 후보키가 아닌 함수 종속을 제거

        ⑤ 제4정규형(4NF) : 다치종속 제거

        ⑥ 제5정규형(5NF) : 조인 속성

9. 이상현상(Anomaly)

   - 관계 조작할 때 데이터 중복현상으로 삭제이상, 삽입이상, 갱신이상

10. D/B 설계 순서

   요구조건 분석 → 개념적 설계 → 논리적 설계 → 물리적 설계 → 구현(프로그래밍)

11. 관계형 D/B의 구조

   ① 속성(Attribute) - 개체 특성에 대한 이름

   ② 튜플(Tuple) - 테이블의 행, Attribute 값들의 집합

   ③ 도메인(Domain) - 하나의 속성이 취할 수 있는 원자값들의 집합

   ④ 차수(Degree) - 어트리뷰트(Attrtbute)의 개수, 필드의 개수(항목의 수)

   ⑤ 카디널리티(Cardinality) - 튜플(Tuple)의 개수, 레코드의 개수(자료의 개수)

12. 무결성

   ① 개체무결성 - 기본키의 값은 널(Null)일수 없다.

   ② 참조무결성 - 두 릴레이션에 저장된 튜플간에 데이터 일관성 유지

13. 관계 D/B의 연산

   ① 관계대수   - 다른 릴레이션을 만드는 연산자의 집합, 절차적

                - 셀렉션(Selection : σ) : 조건에 맞는 레코드(튜플)을 분리연산, 수평적 부분집합

                - 프로젝트(Project : π) : 릴레이션에서 어트리뷰트를 선택분리, 수직적 부분집합

   ② 관계해석 - 비절차적 언어, 튜플관계해석, 도메인 관계해석

14. 질의어(SQL)

   ① 데이터 정의문

        - CREATE : 스키마, 도메인, 테이블, 인덱스, 뷰(View)등의 생성(정의)

        - ALTER : 도메인, 테이블 변경

        - DROP : 스키마, 도메인, 테이블, 인덱스, 뷰(View)등의 삭제(제거)

                * RESTRICTED : 제거 개체가 참조중일 때 명령 실행 거부

                * CASCADE : 제거시 참조중인 개체를 함께 제거(참조의 무결성)

   ② 데이터 조작문

        - SELECT(검색)

             SELECT ~ FROM  WHERE 조건 GROUP BY ~ HAVING ~ ORDER BY  ASC/DESC

        - INSERT(삽입) :  INSERT INTO ~

        - UPDATE(갱신) :        UPDATE ~ SET

        - DELETE(삭제) :        DELETE FROM ~

15. 뷰(View)

   - 기본 테이블로부터 유도된 가상 테이블   - 자료의 접근 제어로 보안을 제공

   - 테이블과 동일하게 이용                       - 뷰의 정의만 DD(데이터 사전)에 저장

   - 실제적인 물리적인 구조가 없고, 물리적으로 분리 될 수도 없다.

   - 정의된 뷰를 변경할 수 없다.

 

16. 시스템 카탈로그(데이터 사전)

   - 객체에 대한 정보를 유지 관리하는 시스템 데이터베이스

   - 테이블 형식으로 구성, 검색가능 변경 불가능

    * 데이터 디렉토리(Data Directory) : 데이터를 실제로 접근하는데 필요한 정보를 유지 관리하는 시스템

17. 트랜잭션

   - d/B에서 회복, 병행 수행 시 처리되는 작업의 논리적 단위

   - 속성  ① 고립성(Isolation)  ② 일관성(Consistency) : 무결성 유지  ③ 영속성(Duability)

           ④ 원자성(Atomicity) : 분리될 수 없는 특성

   - 연산  ① Commit(종료, 완료) : 실행이 성공적으로 완료

           ② Rollback(복귀) : 실행의 실패

18. 회복에 따른 연산

   ① REDO :- 가장 최근의 복제본을 적재하여 복제본 이후의 변경사항 민을 복원,

                갱신 완료된 데이터를 로그를 이용

   ② UNDO :- 변경 데이터를 취소하여 원래의 내용으로 복원시키는 연산

19. 병행수행(동시수행=병행제어)의 문제점

   ① 갱신분실(Lost Update)   ②모순성(Inconsistency)=불 일치성   ③연쇄복귀(Cascading Rollback)

20. Locking(로킹)

   :- 하나의 트랜잭션이 데이터를 Access하는 동안 다른 트랜잭션이 이 데이터에 대하여 Lock(사용권한)를

      소유하고 경우에만 Access하도록 하는 방법

   ① 로킹 단위가 크면 - 관리는 용이하나, 병행수준이 낮다.

   ② 로킹 단위가 작으면 - 관리는 불편하나, 병행 수준은 높다.

21. 자료구조

   ※ 선형구조 - 리스트, Queue(큐), Stack(스택), Deque(데큐)

   ※ 비선형구조 - TREE, GRAPH

22. STACK(스택)   ~　called Top

   - 운용규칙(LIFO : Last-In First-Out 후입선출)

   - 삽입시 : Top = Top + 1(Top 이 1씩 증가)

   - 용도 : 되부름, 반환주소의 저장 (인터럽트), 수식 표현

23. Queue(큐) - 양쪽 끝에서 삽입/삭제

   - Front(앞) : 삭제, Real(뒤) : 삽입

   - 운용규칙(FIFO : First-In First-Out 선입선출)

   - 용도 : 스케쥴러, 모의 실험

24. 트리의 용어

   ① 차수(Degree):- 각 Node의 뻗은 가지수

   ② 트리의 차수 :- 차수 중에서 최대값

   ③ 단말노드(Terminal=Leaf):- 차수가 0인 노드(Node)

   ※ 레벨(=높이=깊이)가 L일 때 노드의 수 n=

   ※ 차수가 0인 노드수(n0) = 차수가 2인 노드수(n2) + 1

25. 경로 길이

    외부 경로 = 내부경로 + 2 * 노드수           E = 1+2n

26. 트리운행(수식=Polish)

    ① Preorder(Prefix) : ROOT(연산자) - Left - Right

    ② Inorder(Infix) : Left - ROOT(연산자) - Right

    ③ Postorder(Postfix) : Left - Right - ROOT(연산자)

27. 신장트리(Spanning Tree)

    - 모든 정점을 통과하면서 사이클이 형성되지 않는 트리

 

      완전그래프       신장그래프     신장그래프       신장그래프

    ※ 최소비용 신장트리 :- 신장트리 중 비용의 합이 최소가 되는 트리

30. 2진 검색(Binary Search)

    -자료가 반드시 정렬(Sort)되어 있어야 한다.

31. 외부정렬

    :- 자료의 양이 많을 때 보조기억장치의 Merge를 이용한 정렬

    ① Balanced Merge Sort(균형 정렬)

    ② Polyphase Merge Sort(다단계 정렬) - 피보나치수열 이용, 최소 Tape 장치 3개 필요

    ③ Cascade Merge Sort(계단 정렬)

    ④ Oscillating Merge Sort(오실레이팅 정렬) - 테이프의 순방향/역방향 모두 가능상태에서 사용

32. 트라이(Trie)

    ;- 검색을 위한 킷값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서에 의하여

       킷값을 표한하는 구조

    - 차수는 킷값을 표한하기 위해 사용하는 문자의 수에 의해 결정

    - 킷값을 예측할 수 있다면 기억장소 절약 가능

    - 트라이의 크기는 킷값의 기수와 키필드에 의해 결정

    - 트라이의 높이는 키필드의 크기와 동일하다. 

[출처] 정보처리 - 데이타베이스|작성자 블루윈드

001 DBMS의 필수기능

- 정의기능 : 데 이터베이스의구조(모델,스키마 등)를 기술

- 조작기능 : 데 이터를 검색,삽입,삭제,갱신

- 제어기능 : 데 이터의 정확성과 안전성을 유지하기 위한 무셜성 유지,보안 권한 검사, 병행제어 등

002 3단계 스키마 : 스 키마는 데이터베이스이 구조에 대한 정의와 제약조건등을 기술

 - 외부 스키마 : 개개 사용자나 응용 관점의 슴키마

 - 개념 스키마 : 기관 전체적인 관점의 스키마

 - 내부 스키마 : 물리적저장장치 관점의 스키마(접근 권한,보안정책,무결성 규칙등을 포함)

003 - 데이터정의어 (DDL) : 데이터베이스의 정의 및 수정

    - 데이터조작어 (DML) : 데이터의 조작,즉 검색,삽입,삭제,갱 신

    - 데이터제어어 (DCL) : 보안,무결성,병행 수행과 같은 데이터 제어에 사용

004 데이터베이스 사용자 (DBA) : 질의어르 이용해 데이터베이스를 접근하는 일반 사용자,호스 트 언어에 데이터 조작어를 삽입시켜 데이터베이스를 접근(즉,응용 프로그램을 작성)하는 응용 프로그래머,데이터베이스의 전체적인 관리 운영에 책임을 지는 사람 또는 집단인 데이터베이스 관리자(DBA)로 구분

005 데이터베이스 관리자의 책임: 데이터베이스 설계와 운영,행정 및 불평해결,시스템 감시 및 성능 분석 수행,데이터 베이스 설계 및 운영과 관련하여 스키마 정의,저장 구조와 접근방법 선정,보안 정책 수립, 예비 및 회복 절차 수립,무결성 유지,성능향상과 새로운 요구에 대응한 재구성 등의 임무 수행

006 시스템카탈로그 : 기 본 테이블,뷰,인덱스,접근권한 등의 정보를 저장하고 있는 시스템 데이터베이스로 데이터사전이라고도 함.SQL을 이용해 내용을 검색할수 있으나 직접 갱신 불가능

007 데이터모델 : 현 실세계를 데이터베이스로 표현하는 중간 과정을 의미 , 논리적으로 표현된 데이터구조(Structure)와 연산에서의 제약조건(Constraint)에 대한 명세를 기술한 것

008 개체-관계모 델 : 개체 사이의 관계를 사람들이 이해할 수 있는 개념적 표현을 통해 모델화 한 것.관계의 대응 수에는 1:1,n:1,n:m이 있으면 E-R 다이어그램을 통하여 그래프 방식으로 표현

009 논리적데이터모델 : 데 이터필드로 기술된 데이터 타입과 이 데이터 타입들 간의 관계를 이용하여 현실 세계를 표현하는 방법 , 데이터의 논리적 구조를 모델링 하기위한 도구로 관계 데이터 모델이 대표적임

010 후보키 : 튜 플을 유일하게 식별할수 있는 애트리뷰트의 집합으로 유일성(Uniqueness)과 최소성(Minimality)을 만족해야함

011 개체 무결성 제약조건 : 기본 키에 속해있는 애트리뷰트는 언제 어느때고 널(Null)값을 가질수 없다.

012 참조 무겨성 제약조건 : 릴레이션은 참조할 수 없는 외래 키 값을 가져서는 안된다는 제약조건. 참 조할수 없는 외래 키란 널(Null)이 아니면서 참조되는 릴레이션의 어떤 기본키 값돠고 일치하지 않는 값을 의미

013 관게해석 : 관 계 데이터 모델에서 릴레이션을 조작하기 위한 기본 연산으로, 무슨(What)데이터를 원하는 지만 선언하면 되는 비절차적 언어임,튜 플관계해석과 도메인 관계 해석이 존재

014 관계 대수 : 관 계 데이터모델에서 릴레이션을 조작하기 위한 기본 연산으로 구성되며, 절차적 특성을 가짐. 일반 집합 연산자(합집합,교집합,차집합,카티션 프로덕트)와 순수 관계연산(셀렉트,프로젝트,조인,디비전)으 로 나누어짐

015 SQl 정의어 :

- Create문 : 스 키마,도메인,테이블,뷰,인덱스의 정의

- Drop문 : 제 거

- Alter문 : 기 존 테이블에 대해 열이나 제약 조건을 변경(뷰나 인덱스에 대해서는 사용불가능)

016 SQl 조작어

- 검색 : SELECT-FROM-WHERE문

- 삽입 : INSERT INTO-VALUES문

- 갱신 : UPDATE-SET-WHERE문

- 삭제 : DELETE FROM-WHERE문

- SELECT문의 경우 GROUP BY-HAVING과 ORDER BY절을 옵션으로 사용

017 SQL 뷰 : 하 나이상의 기본 테이블로부터 유도되어 만들어지는 가상 테이블로,뷰에 실제로 데이터가 저장되는 것이 아니며,뷰에 대한 검색은 일반 테이블과 동등하게 수행. 뷰는 사용자의 데이터 관리를 간단하게 해주고 접근 제어(보 안)의 편의를 제공. 뷰는 정의 변경이 불가능하고 변경이나 갱신 연산에 제약 존재

018 삽입 SQL : c와 같은 범용 프로그램안에 삽입된 SQL. 호스트 변수와 데이터베이스 필드의 이름은 같아도 무방하나,SQL문에 사용되는 호스트 변수는 구분을 위해 콜론(;)을 앞에 붙임.호스트 변수와 대응하는 필드의 데이터 타입은 일치 필요

019 데이터베이스 설계 단계 : 사용자 요구 조건에서부터 데이터베이스 구조를 도출해 내는 과정 : 요 구조건분석-개념적설계-논리적설계-물리적설계-구현

020 함수종속 : 어 떤 릴레이션 R에서 X와 Y가 각각 R의 애트리뷰트 집합의 부분집합 이라할 때,애트리뷰트 Y의 값이 오직 하나만 연관되어 있을 때 Y는 X에 함수적으로 종속된다고 하며, X->Y로 표시

021 제1정규형 : 어떤 릴레이션 R에 속한 모든 도메인이 원자 값(ATOMIC VALUE)만으로 되어 있음

022 제2정규형 : 어떤 릴레이션 R이 제1정규형이고 키에 속하지 않은 애트리뷰트 모두가 기본키에 완전 함수 종속이면,제2정규형(2NF)에 속함

023 제3정규형 : 어떤 릴레이션 R이 제2정규형이고 키에 속하지 않은 모든 애트리뷰트들이 기본 키에 이행적 함수 종속이 아닐 때 제 3정규형(3NF)에 속함

024 BCNF : 릴레이션 R의 모든 결정자(determinant)가 후보 키이면 릴레이션 R은 보이스/코드 정규형(BCNF)에 속함

025 트랜잭션 : 한 꺼번에 모두 수행되어야 하는 일련의 데이터베이스 연산들.이 연산들은 모두 수행되거나 나하도 수행되지 않거나 하는 원자성을 만족시켜야 함.모든 연산의 완료에는 commit 연산, 모든 연산의 최소에는 rollback 연산 사용

026 트랜잭션의 acid 성 질

- 원자성(Actomicy) : 트랜잭션 내의 모든 연산은 한꺼번에 완료되거나 취소되어야 함

- 일관성(Consistency) : 트랜잭션의 성공적완료는 데이터베이스를 일관성있는 상태로 변환시킨다.

- 격리성(Isolation) : 트랜잭션이 실행중에 있는 연산의 중간 결과는 다른 트랜잭션이 접근하지 못한다.

- 영속성(Durability) : 성공적으로 완료한 트랜잭션의 결과는 영속적으로 데이터베이스에 반영된다.

027 병행제어기법 : 동 시에 수행되는 다중 트랜잭션에 대해 병행제어를 하지 않으면 갱신 분실,모순성,연쇄복귀 등의 문제 발생.대표적인 병행제어 기법은 로킹기법으로,로킹단위로는 테이블,페 이지,행레벨 등이있고, 로킹 단위가 작아질수록 공유도는 증가하나 로킹 오버헤드도 증가(로킹을 사용해도 교착 상태는 발생가능)

028 SQL의 보안기법 : GRANT와 REVOKE 명령을 이용. 사용자 등급으로는 DBA,RESOURCE,CONNECT가 존재. 데이터베이스 및 테이블 생성을 위해서는 RESOURCE 등급 필요. 테이블에 대한 조작 권한 부여시 WITH GRANT OPTION을 사용하면 부여받은 권한을 다른 사용자에게 재부여 가능

029 분산 데이터베이스의 목표 : 저장 사이트의 위치를 알 필요가 없는 위치 투명성, 중복 데이터의 일관성 유지에 신경을 쓰지 않아도 되는 중복 투명성, 데이터가 단편화 되지 ㅇ낳은것처럼 사용할 수 있도록 해주는 단편화 투명성등을 제공하는 것

030 분산 데이터베이스의 장-단 점

- 장점 : 지역 자치성의 유지,점진적인 시스템용향확장의 용이,신 뢰성 및 가용성의 증대,효율성 및 융통성의 증대

- 단점 : 소프트 웨어 개발 비용, 오류의 잠재성 , 처 리비용의 증대

031 배열(Array) : 연 속적인 기억 공간을 배정하여 데이터를 저장하되, 동일한 데이터 Type만을<인덱스,값>의 쌍으로 저장하는 자료구조이다. 따라서 데이터를 저장하거나 데이터를 검색할때는 항상 인덱스가 지정하는 데이터 값을 저장하거나 검색하게 된다.

032 스택(Stack) : 연 속적인 기억공간을 배정하여 데이터를 순서적으로 저장하는데, 데이터를 검색할때는 스택에 마지막으로 저장된 데이터부터 먼저 검색하게 되는 자료구조(LIFO:Last in First Out)(서브루틴호출,순환 프로그램,인터럽트 처리,수식 계산,컴파일러 등에 응용)

033 큐(Queue) : 연 속적인 기억공간을 배정하여 데이터를 순서적으로 저장하는데, 데이터를 검색할때는 큐에 저장된 데이터 순서대로 검색하게 되는 자료구조(FIFO : First in First Out) (운영작업의 작업 스케쥴링등에 응용)

034 이진 트리의 순회 방법

- 전위 순회(Preorder Traversal) : 루트->왼쪽자식트리->오른쪽자식트리의 모든 노드순회

- 중위 순회(Inorder Traversal) : 왼쪽자식트리->루트->오른쪽자식트리의모든 노드순회

- 후위순회(Postorder Traversal):왼쪽자식트리->오른쪽자식트리->루트 노드를 순회

035 그래프의 순회방법 : 무 방향 그래프에서의 순회(검색)방법

- 깊이우선탐색(DFS:Depth First Search):스택을 사용하여,트리의 전위 순회방법과 유사

- 너비우선탐색(BFS:Breadth First Search):큐를 사용하며,트리의 레벨순서순회방법과 유사

036 내부정렬 : 정 렬하고자 하는 데이터의 양이 적어서 주기억 공간에 한꺼번에 저장해 두고 주기억장치에서 정렬하는 방법(삽입정렬,버블정렬,퀵정렬,히프정렬,선택정렬,2원합병정렬등), 이중에서 가장 효율이 좋은 히프정렬은 최악의 경우 평균의 경우 연산속도가 모드 0(nlog2n)이다.

037 외부정렬 : 정 렬하고자 하는 데이터의 양이 많아서 주기억 공간에 한꺼번에 저장하여 주기억 장치에서 정렬할수 없는경우,데이터를 몇 개의 서브 파일(런)로 나누어 각각 내부정렬을 한후,디스크에서는 정렬된 서브 파일들을 단순히 합병만 하는 방법(자연합병,균형합병,다단계합병,계단식합병 등)

038 이진탐색 : 정 렬된 많은 데이터들 중에서 검색할 데이터를 효율적으로 탐색하는 방법이다. 탐색방법은 첫번째 데이터와 마지막 데이터에 대한 중간 데이터를 설정한 후,찾고자 하는 데이터의 키 값과 중간 데이터의 키 값을 비교해보아서,작으면 찾고자 하는 데이터는 처음부터 중단 데이터 사이에 존재하고,크면 찾고자하는 데이터는 중간부터 마지막 데이터 사이에 존재하며, 이와 같은 방법을 반복 실행하고,만약 같으면 검색은 끝난다. 이 방법은 반드시 데이터가 정렬이 된 데이터들이어야 한다.

039 B-트리 : 인 덱스는 데이터의 검색을 빠르게 하기 위해 필요하다.B-트리는 인덱스를 조직하는 방법중에서 가장 많이 사용되는 것으로 일반적으로 m-원 탐색트리의 구조를 갖는다

B*-트리 : 데이 터의 갑입으로 인해 노드A가 가득차면 A노 드와 바로 인접한 형제노드에 재분배하여 A노드의 분열을 지연시키는 구조이다.

B+-트리 : B-트 리의 순차검색시 속도가 느린 단점을 보와하기 위해서 인덱스 세트와 순차 세트로 구분하여 구성하는 구조이다. 인덱스 세트는 트리로서 직접 접근 시에 경로만 제공하고, 순차세트는 데이터들로서 순차 접근시에 연결 리스트를 이용하여 검색속도를 향상시키는 구조이다.

040 해싱(Hashing)  직접파일은 저장할 데이터의 키 값을 디스크의 물리적 주소로 변환할수 있는 어떤 관계(알고리즘,프로그램)를 이용하는 파일구조이다. 이 관계를 해싱 함수(hashing function)라고 하며,함 수를 이용하여 저장할 데이터의 키를 디스크의 물리적주소로 변환하여그 주소에 데ㅣ터를 저장하는 과정을 해싱 이라고 한다.

- 제산 잔여 해싱,중 간 제곱 해싱,중첩해싱 , 이동 변환 해싱 , 진수 변환 해싱등

- 해싱에서 가장 고려해야 할 사항은 같은 주소로 해싱되는 문제를 해경하는 것이다.

[출처] 정보처리기 사 핵심용어 - 데이타베이스|작성자 위글