DBMS(Database Management System)
데이터 관리의 복잡성을 해결하는 동시에 데이터 추가, 변경, 삭제 및 백업, 복구, 보안 등의 기능을 지원하는 소프트웨어
- 키-값(key-value) DBMS : 유니크한 키에 하나의 값을 가지고 있는 형태
- 컬럼 기반 데이터 저장(Column Family Data Store) DBMS : key안에(colume,value)조합으로 된 여러개의 필드를 갖는 DBMS
- 문서 저장(Document Store) DBMS : 값(value)의 데이터 타입이 문서라는 타입을 사용하는 DBMS
- 그래프(Graph) DBMS : 시맨틱 웹과 온톨로지 분야에서 활용되는 그래프로 데이터를 표현하는 DBMS
- DBMS 특징 : 무결성, 일관성, 회복성, 보안성, 효율성
- 빅데이터 : 시스템, 서비스, 조직(회사)등에서 주어진 비용, 시간 내에 처리 가능한 수십 페타바이트(PB) 크기의 비정형 데이터
- 빅데이터 특성 : 데이터의 양, 데이터의 다양성, 데이터의 속도
- 빅데이터 수집,저장,처리 기술
- 비정형/반정형 데이터 수집 : 내/외부 정제되지 않은 데이터를 확보하여 수집 및 전송하는 기술
- 정형 데이터 수집 : 정제된 대용량 데이터의 수집 및 전송 기술
- 분산데이터 저장/처리 : 대용량 파일의 효과적인 분산 저장 및 분산 처리 기술
- 분산 데이터 베이스 : HDFS 칼럼 기반 데이터 베이스로 실시간 랜덤 조회 및 업데이트 가능
*HDFS: 대용량 데이터의 집합을 처리하는 응용 프로그램에 적합하도록 설계된 하둡 분산 파일 시스템
- NoSQL(Not only SQL) : 데이터 저장에 고정된 테이블 스키마가 필요하지 않고 조인 연산은 사용할 수 없으며, 수평적으로 확장이 가능한 DBMS
- NoSQL 특성
- Basically Available : 언제든지 데이터 접근할 수 있는 속성- Soft-State : 외부에서 전송된 정보를 통해 결정되는 속성
- Eventually Consistency : 이관성이 유지되는 속성
스키마
스키마는 데이터베이스의 구조와 제약조건에 관한 전반적인 명세를 기술한 것
외부 스키마 - 사용자나 응용 프로그래머가 각 개인의 입장에서 필요로 하는 데이터 베이스의 논리적 구조를 정의한 것
개념 스키마 - 데이터 베이스의 전체적인 논리적인 구조, 모든 응용 프로그램이나 사용자들이 필요로하는 데이터를 종합한 조직 전체의 데이트베이스로 하나만 존재함
내부 스키마 - 물리적 저장장치의 입장에서 본 데이터베이스 구조, 실제로 저장될 레코드의형식, 저장 데이터 항목의 표현방법, 내부 레코드의 물리적 순서 등을 나타냄
데이터 베이스 설계 시 고려사항
무결성 - 삽입, 삭제, 갱신 등의 연산 후에도 데이터 베이스에 저장된 데이터가 정해진 제약조건을 항상 만족해야함
일관성 - 데이터베이스에 저장된 데이터들 사이나, 특정 질의에 대한 응답이 처음부터 끝까지 변함없이 일정해야함
회복 - 시스템에 장애가 발생했을 때 장애 발생 직전의 상태로 복구할 수 있어야함
보안 - 불법적인 데이터의 노출 또는 변경이나 손실로부터 보호할 수 있어야함
효율성 - 응답시간의 단축, 시스템의 생산성, 저장 공간의 최적화 등이 가능해야함
데이터베이스의 확장 - 데이터베이스의 운영에 영향을 주지 않으면서 지속적으로 데이터를 추가할 수 있어야함
설계 순서
요구 조건 분석 - 요구 조건 명세서 작성
개념적 설계 - 개념적 스키마, 트랜젝션 모델링, E-R모델
논리적 설계 - 목표 DBMS에 맞는 노리 스키마 설계, 트랜젝션 인터페이스 설계
물리적 설계 - 목표 DBMS에 맞는 물리적 구조의 데이터로 변환
구현 - 목표 DBMS의 DDL(데이터 정의어)로 데이터베이스 생성, 트랜젝션 작성
개념적 설계(정보 모델링, 개념화)
현실 세계에 대한 인식을 추상적 개념으로 표현하는 과정
논리적 설계(데이터 모델링)
특정 DBMS가 지원하는 논리적 자료구조로 변환시키는 과정
물리적 설계(데이터 구조화)
논리적 구조로 표현된 데이터를 물리적 구조의 데이터로 변환하는 과정
데이터 베이스 구현
논리적 설계와 물리적 설계에서 도출된 데이터베이스 스키마를 파일로 생성하는 과정
데이터 모델 구성 요소
구조(Structure) : 논리적으로 표현된 개체 타입들 간의 관계로서 데이터 구조 및 정적 성질 표현
연산(Operation) : 데이터베이스에 저장된 실제 데이터를 처리하는 작업에 대한 명세로서 데이터베이스를 조작하는 기본 도구
제약 조건(Constraint) : 데이터베이스에 저장될 수 있는 실제 데이터의 논리적인 제약조건
E-R 다이어그램
관계형 데이터베이스
- 관계형 데이터베이스는 2차원적인 표(Table)를 이용해서 데이터 상호 관계를 정의하는 데이터베이스
- 개체(Entity)와 관계(Relationship)를 모두 릴레이션(Relation)이라는 표(Table)로 표현하기 때문에 개체를 개체 릴레이션과 관계 릴레이션이 존재
- 장점
간결하고 보기 편리
다른 데이터베이스로의 변환이 용이
- 단점
성능이 다소 떨어짐
관계형 데이터베이스의 릴레이션 구조
릴레이션(Relation)은 데이터들의 표(Table)의 형태로 표현한 것으로, 구조를 나타내는 릴레이션 스키마와 실제 값들인 릴레이션 인스턴스로 구성된다.
튜플(Tuple)
튜플은 릴레이션을 구성하는 각각의 행을 말하며 속성의 모임으로 구성된다. 파일 구조에서 레코드와 같은 의미이다. 튜플의 수를 카디널리티(Cardinality) 또는 기수, 대응수라고 한다.
속성(Attribute)
속성은 데이터베이스를 구성하는 가장 작은 논리적 단위이며 개체의 특성을 기술한다. 파일 구조상의 데이터 항목 또는 데이터 필드에 해당한다. 속성의 수를 디그리(Degree) 또는 차수라고 한다.
도메인(Domain)
도메인은 하나의 속성(attribute)이 취할 수 있는 같은 타입의 원자값들의 집합이다. 도메인은 실제 속성 값이 나타날 때 그 값의 합법 여부를 시스템이 검사하는데에도 이용된다
릴레이션의 특징
- 한 릴레이션에는 똑같은 튜플이 포함될 수 없음
- 한 릴레이션에 포함된 튜플 사이에는 순서가 없음
- 튜플들의 삽입, 삭제 등의 작업으로 인해 릴레이션은 시간에 따라 변함
- 릴레이션 스키마를 구성하는 속성들 간의 순서는 중요하지 않음
- 속성의 유일한 식별을 위해 속성의 명칭은 유일해야 함
- 하지만, 속성을 구성하는 값은 동일한 값이 있을 수 있음
- 릴레이션을 구성하는 튜플을 유일하게 식별하기 위해 속성들의 부분집합을 키로 설정
- 속성의 값은 논리적으로 더 이상 쪼갤 수 없는 원자값만을 저장
후보키(Candidate Key)
튜플을 유일하게 식별하기 위해 사용되는 속성들의 부분집합
후보키는 유일성과 최소성을 모두 만족시켜야 한다
슈퍼키(Super Key)
속성들의 집합으로 구성된 키
모든 튜플에 대해 유일성을 만족하지만 최소성은 만족하지 못한다
외래키(Foreign Key)
다른 릴레이션의 기본키를 참조하는 속성 또는 속성들의 집합을 의미
외래키로 지정되면 참조 릴레이션의 기본키에 없는 값은 입력할 수 없다
무결성은 데이터베이스에 저장된 데이터의 값과 현실 세계의 실제값이 일치하는 정확성을 의미
개체 무결성 - 기본 테이블의 기본키를 구성하는 어떤 속성도 null값이나 중복값을 가질 수 없다
참조 무결성 - 외래키 값은 null이거나 참조 릴레이션의 기본키 값과 동일해야 함. 릴레이션은 참조할 수 없는 외래키를 가질 수 없다
관계대수는 원하는 정보와 그 정보를 검색하기 위해서 어떻게 유도하는가를 기술하는 절차적인 언어
Select - 릴레이션에 존재하는 튜플 중에서 선택 조건을 만족하는 튜플의 부분집합을 구하여 새로운 릴레이션을 만드는 연산. 행에 해당하는 튜플을 구하는 것이므로 수평 연산 이라고도함.
기호 : 𝜎(시그마)
Project - 주어진 릴레이션에서 속성 리스트에 제시된 속성 값만을 추출하여 새로운 릴레이션으로 만드는 연산. 연산 결과에 중복이 발생하면 중복이 제거됨. 열에 해당하는 속성을 추출. 수직 연산자
기호 : 𝝅(파이)
Join - 공통 속성을 중심으로 두 개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만드는 연산.
기호 : ⋈
Division - X ⊃ Y인 두 개의 릴레이션R(X), S(Y)이 있을 때, R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성만을 구하는 연산
기호 : ÷
일반 집합 연산자는 수학적 집합 이론에서 사용하는 연산자이다
합집합 UNION ⋃ - 두 릴레이션에 존재하는 튜플의 합집합을 구하되, 결과로 생성된 릴레이션에서 중복되는 튜플은 제거되는 연산
일반 집합 연산자
-
집합 연산은 수학적 집합 이론에서 사용하는 연산자로 릴레이션 연산에도 그대로 적용할 수 있다.
-
집합 연산 중 UNION, DIFFERENCE, INTERSECTION을 처리하기 위해서는 합병 조건을 만족해야한다.
※ 합병 조건 : 합병하려는 두 릴레이션 간에 속성의 수가 같고, 대응되는 속성별로 도메인이 같아야한다. 즉, 릴레이션 R과 S가 합병 가능하다면, 릴레이션 R의 i번째 속성과 릴레이션 S의 i번째 속성의 도메인이 서로 같아야 한다. 속성의 이름이 같아야되는 것은 아님. -
두 릴레이션 R과 S가 있을 때 각 집합 연산의 특징
이상이란 테이블에서 데이터의 중복이 발생하고 이 중복으로 인해 테이블 조작 시 문제가 발생하는 현상
삽입 이상(Insertion Anomaly) : 테이블에 데이터를 삽입할 때 의도와는 상관없이 원하지 않은 값들로 인해 삽입할 수 없게 되는 현상
삭제 이상(Deletion Anomaly) : 테이블에서 한 튜플을 삭제할 때 의도와는 상관없는 값들도 함께 삭제되는, 연쇄 삭제가 발생하는 현상
갱신 이상(Update Anomaly) : 테이블에서 튜플에 있는 속성 값을 갱신할 때 일부 튜플의 정보만 갱신되어 정보에 불일치성이 생기는 현상
함수적 종속
Y는 X에 함수적 종속 또는 X가 Y를 함수적으로 결정한다고 하고, X(결정자)->Y(종속자)로 표기한다
함수적 종속은 데이터의 의미를 표현하는 것, 현실 세계를 표현하는 제약 조건이 되는 동시에 데이터베이스에서 항상 유지되어야할 조건
정규화는 테이블의 속성들이 상호 종속적인 관계를 갖는 특성을 이용하여 테이블을 무손실 분해하는 과정
관계형 데이터베이스 설계 시 중복을 최소화하여 데이터를 구조화 하는 과정
- 제 1정규형(1NF)
테이블 R에 속한 모든 속성의 도메인이 원자 값만으로 되어있는 정규형. 테이블의 모든 속성 값이 원자 값으로만 되어 있는 정규형
- 제 2정규형(2NF)
기본키가 아닌 모든 속성이 기본키에 대하여 완전 함수적 종속을 만족하는 정규형
- 제 3정규형(3NF)
테이블 R이 제 2정규형이고 기본키가 아닌 모든 속성이 기본키에 대해 이행적 함수적 종속을 만족하지 않는 정규형
- BCNF
테이블 R에서 모든 결정자가 후보키인 정규형. 제 3정규형에 후보키가 여러개 존재하고, 이런 후보키들이 서로 중첩되어 나타나는 경우에 적용 가능
- 제 4정규형(4NF)
테이블 R의 다중 값 종속 A->B가 존재할 경우 R의 모든 속성이 A에 함수적 종속 관계를 만족하는 정규형
- 제 5정규형(5NF)
테이블 R의 조인 종속이 R의 후보키를 통해서만 성립되는 정규형
(도부이결다조)
비정규 릴레이션 -> 도메인이 원자값
1NF -> 부분적 함수 종속 제거
2NF -> 이행적 함수 종속 제거
3NF -> 결정자이면서 후보키가 아닌 것 제거
BCNF -> 다치 종속 제거
4NF -> 조인 종속성 이용
5NF
반정규화는 정규화된 데이터 모델을 의도적으로 통합, 중복, 분리하여 정규화 원칙을 위배하는 행위
반정규화를 수행하면 시스템의 성능이 향상되고 관리 효율성이 증가하지만 데이터의 일관성 및 정합성이 저하됨
반정규화의 방법
- 테이블 통합
- 테이블 분할
- 중복 테이블 추가
- 중복 속성 추가
중복테이블 추가는 작업의 효율성을 향상시키기 위해 테이블을 추가하는 것
중복 테이블을 추가하는 경우
- 여러 테이블에서 데이터를 추출해서 사용해야 할 경우
- 다른 서버에 저장된 테이블을 이용해야 하는 경우
중복 테이블 추가 방법
집계 테이블의 추가 - 집계 데이터를 위한 테이블을 생성하고, 각 원본 테이블에 트리거를 설정하여 사용
진행 테이블의 추가 - 이력 관리 등의 목적으로 추가하는 테이블
특정 부분만을 포함하는 테이블의 추가 - 데이터가 많은 테이블의 특정 부분만을 사용하는 경우 해당 부분만으로 새로운 테이블을 생성
시스템 카탈로그는 다양한 객체에 관한 정보를 포함하는 시스템 데이터 베이스
카탈로그들이 생성되면 데이터 사전에 저장되기 떄문에 좁은의미로는 데이터 사전이라고도 한다
트랜젝션(Transaction) 은 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들을 의미
데이터베이스 시스템에서 병행 제어 및 회복 작업 시 처리되는 작업의 논리적 단위로 사용
상태 변환 과정의 작업 단위로 사용
트랜젝션의 특성
Atomicity(원자성) - 트랜잭션의 연산은 데이터베이스에 모두 반영되도록 완료(Commit)되던지, 전혀 반영되지 않도록 복구(Rollback)되어야함
Consistency(일관성) - 트렌잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환함
Isolation(독립성, 격리성, 순차성) - 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느하나의 트랜잭션 실행중에 다른 트랜잭션의 연산이 끼어들 수 없음
Durability(영속성, 지속성) - 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 함
CRUD 분석
프로세스와 테이블 간에 CRUD 매트릭스를 만들어서 트랜잭션을 분석하는 것
디스크 구성 시 유용한 자료로 활용할 수 있다
행(Row) - 프로세스
열(Column) - 테이블
행과 열이 만나는 위치에 프로세스가 테이블에 발생시키는 변화를 표시
프로세스와 데이터 간의 관계를 분석하는 분석표
CRUD 매트릭스를 통해 트랜젝션이 테이블에 수행하는 작업을 검증
Create, Read, Update, Delete C > D > U > R
트랜잭션 분석
테이블에 발생하는 트랜잭션양을 분석하여 테이블에 저장되는 데이터의 양을 유추하고 이를 근거로 DB의 용량 산정 및 구조의 최적화를 목적
업무 개발 담당자가 수행
트랜잭션 분석을 통해 프로세스가 과도하게 접근하는 테이블을 확인할 수 있으며, 이러한 집중 접근 테이블을 여러 디스크에 분산 배치함으로써 디스크 입,출력 향상을 통한 성능 향상을 가져올 수 있다
인덱스는 데이터 레코드를 빠르게 접근하기 위해 <키 값, 포인터> 쌍으로 구성되는 데이터 구조
인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공
인덱스를 통해서 파일의 레코드에 빠르게 액세스 할 수 있다
레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소로 하는 것이 효율적
뷰는 하나 이상의 기본 테이블로부터 유도된 가상테이블이다
뷰를 정의할때는 Create문, 제거할 때는 Drop을 사용
[장점]
- 논리적 데이터 독립성을 제공
- 동일 데이터에 대해 동시에 여러 사용자의 상이한 응용이나 요구를 지원
- 사용자의 데이터 관리를 간단한게 해줌
- 접근 제어를 통한 자동 보안 제공
[단점]
- 독립적인 인덱스를 가질 수 없음
- 뷰의 정의를 변경할 수 없음
- 뷰로 구성된 내용에 대한 삽입, 삭제, 갱신 연산에 제약이 따름
파티션(Partition) 은 대용량의 테이블이나 인덱스를 작은 논리적 단위인 파티션으로 나누는 것
대용량 DB의 경우 몇 개의 중요한 테이블에만 집중되어 데이터가 증가되므로, 이런 테이블을 작은 단위로 나눠 분산시키면 성능 저하를 방지할 뿐만 아니라 데이터 관리도 쉬워진다 (= 성능 향상, 가용성 향상, 백업 가능, 경합 감소)
데이터 처리는 테이블 단위로 이뤄지고 데이터 저장은 파티션 별로 수행된다
- 범위 분할(Range Partitioning) - 지정한 열의 값을 기준으로 분할함 ex) 일별, 월별, 분기별 등
- 해시 분할(Hash partitioning) - 해시 함수를 적용한 결과 값에 따라 데이터를 분할함. 특정 파티션에 데이터가 집중되는 범위 분할의 단점을 보완한 것, 데이터를 고르게 분산할 때 유용. 특정 데이터가 어디에 있는지 판단할 수 없음. 고객번호, 주민번호 등과 같이 데이터가 고른 컬럼에 효과적
- 조합 분할(Composite Partitioning) - 범위 분할로 분할한 다음 해시 함수를 적용하여 다시 분할하는 방식. 범위 분할한 파티션이 너무 커서 관리가 어려울 때 유용
분산 데이터베이스의 목표
- 위치 투명성(Location Transparency) : 액세스하려는 데이터베이스의 실제 위치를 알 필요 없이 단지 데이터베이스의 논리적인 명칭만으로 액세스할 수 있다
- 중복 투명성(Replication Transparency) : 동일 데이터가 여러 곳에 중복되어 있더라고 사용자는 마치 하나의 데이터만 존재하는 것 처럼 사용하고, 시스템은 자동으로 여러 자료에 대한 작업을 수행한다
- 병행 투명성(Concurrency Transparency) : 분산 데이터베이스와 관련된 다수의 트랜잭션들이 동시에 실현되더라도 그 트랜잭션의 결과는 영향을 받지 않는다
- 장애 투명성(Failure Transparency) : 트랜잭션, DBMS, 네트워크, 컴퓨터 장애에도 불구하고 트랜잭션을 정확하게 처리한다
RTO(Recovery Time Objective, 목표 복구 시간) - 비상사태 또는 업무 중단 시점으로부터 복구되어 가동될 때 까지의 소요시간을 의미 ex) 장애 발생 후 6시간 내 복구 가능
RPO(Recovery Point Objective, 목표 복구 시점) - 비상사태 또는 업무 중단 시점으로부터 데이터를 복구할 수 있는 기준점을 의미 ex) 장애 발생 전인 지난 주 금요일에 백업시켜 둔 복원 시점으로 복구 가능
암호화는 데이터를 보낼 때 송신자가 지정한 수신자 이외에는 그 내용을 알 수 없도록 평문을 암호문으로 변환하는 것
암호화(Encryption) 과정 : 암호화되지 않은 평문을 암호문으로 바꾸는 과정
복호화(Decryption) 과정 : 암호문을 원래의 평문으로 바꾸는 과정
암호화 기법
- 개인키 암호 방식(Private Key Encryption)
- 공개키 암호 방식(Public Key Encryption)
접근통제는 데이터가 저장된 객체와 이를 사용하려는 주체사이의 정보 흐름을 제한하는 것
접근통제 3요소
- 접근통제 정책
- 임의 접근 통제(DAC, Discretionary Access Control) : 데이터에 접근하는 사용자의 신원에 따라 접근 권한을 부여하는 방식. 데이터 소유자가 접근통제 권한을 지정하고 제어함. 객체를 생성한 사용자가 생성된 객체에 대한 모든 권한을 부여받고, 부여된 권한을 다른 사용자에게 허가할 수도 있음
- 강제 접근 통제(MAC, Mandatory Access Control) : 주체와 객체의 등급을 비교하여 접근 권한을 부여하는 방식. 시스템이 접근통제 권한을 지정함. 데이터베이스 객체별로 보안 등급을 부여할 수 있음. 사용자별로 인가 등급을 부여할 수 있음
- 역할기반 접근통제(RBAC, Role Based Access Control) : 사용자의 역할에 따라 접근 권한을 부여하는 방식. 중앙 관리자가 접근통제 권한을 지정함. 임의 접근통제와 강제 접근통제의 단점을 보완. 다중 프로그래밍 환경에 최적화된 방식 - 접근통제 매커니즘
- 접근통제 보안모델
SAN(Storage Area Network)
- SAN은 DAS의 빠른 처리와 NAS의 파일 공유 장점을 혼합한 방식. 서버와 저장장치를 연결하는 전용 네트워크를 별도로 구성하는 방식
- 파이버 채널(FC) 스위치를 이용하여 네트워크를 구성
- 파이버 채널 스위치는 서버와 저장장치를 광케이블로 연결하므로 처리속도가 빠르다
- 서버들이 저장장치 및 파일을 공유할 수 있다
- 확장성, 유연성, 가용성이 뛰어나다
자료구조는 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법등을 연구 분석하는 것
저장공간의 효율성과 실행시간의 단축을 위해 사용
<선형 구조>
- 배열(Array)
- 선형 리스트(Linear List)
- 연속 리스트(Contigous List)
- 연결 리스트(Linked List)
- 스택(Stack)
- 큐(Queue)
- 데크(Deque)
<비선형 구조>
- 트리(Tree)
- 그래프(Graph)
스택(Stack)
리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조
후입선출(LIFO) 방식으로 자료를 처리
저장할 기억 공간이 없는 상태에서 데이터가 삽입되면 오버플로가 발생
삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생
큐(Queue)
리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조
선입선출(FIFO)
방향/무방향 그래프의 최대 간선 수
- 방향 그래프의 최대 간선 수 : n(n-1)
- 무방향 그래프에서 최대 간선 수 : n(n-1)/2
트리(Tree)
정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
- 노드(Node) : 트리의 기본 요소. 자료 항목과 다른 항목에 대한 가지를 합친 것
- 근 노드(Root Node) : 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드. 즉 degree가 0인 노드
- 비단말 노드 : 자식이 하나라도 있는 노드. 디그리가 0이 아닌 노드
- 조상 노드 : 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식노드
- … 생략 p.251
Preorder 운행법(p.253~255 참고)
이진 트리를 Root - Left - Right 순으로 운행하며 노드들을 찾아가는 방법
Inorder
Left - Root - Right
Postorder
Left - Right - Root
전위표기법(Prefix) : 연산자 -> Left -> Right, +AB
중위표기법(Infix) : Left -> 연산자 -> Right, A+B
후위표기법(Postfix) : Left -> Right -> 연산자, AB+
삽입 정렬(Insertion Sort)
이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
선택 정렬(Selection Sort)
최소값을 찾아 첫 번째 레코드 위치에 놓고, 다시 최솟값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
버블 정렬(Bubble Sort)
인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드의 위치를 서로 교환하는 정렬 방식
퀵 정렬(Quick Sort)
키를 기준으로 작은 값을 왼쪽, 큰 값을 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식
평균 수행 시간 : O(nlogn), 최악 : O(n²)
힙 정렬(Heap Sort)
전이진 트리를 이용한 정렬 방식
2-Way 합병 정렬(Merge Sort)
이미 정렬되어 있는 두개의 파일을 한 개의 파일로 합병하는 정렬 방식
