19. 트랜잭션 분석 / CRUD 분석
트랜잭션 (Transaction)
•
데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들
•
데이터베이스 시스템에서 병행 제어 및 회복 작업 시 처리되는 작업의 논리적 단위로 사용된다.
•
사용자가 시스템에 대한 서비스 요구 시 시스템이 응답하기 위한 상태 변환 과정의 작업 단위로 사용된다.
트랜잭션의 특성
•
원자성 (Atomicity)
◦
트랜잭션의 연산은 데이터베이스에 모두 반영되도록 완료(Commit)되든지, 아니면 전혀 반영되지 않도록 복구(Rollback) 되어야 함.
◦
All Or Nothing
•
일관성 (Consistency)
◦
트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환됨
•
독립성 (Isolation)
◦
둘 이상의 트랜잭션이 동시에 병행, 실행되는 경우, 어느 하나의 트랜잭션 실행 중에 다른 트랜잭션의 연산이 끼어들 수 없음
•
영속성, 지속성 (Durability)
◦
성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 함
CRUD 분석
•
프로세스와 테이블 간에 CRUD 매트릭스를 만들어서 트랜잭션을 분석하는 것
•
CRUD 분석을 통해 많은 트랜잭션이 물리는 테이블을 파악할 수 있으므로, 디스크 구성 시 유용한 자료로 활용할 수 있다.
트랜잭션 분석
•
CRUD 매트릭스를 기반으로 테이블에 발생하는 트랜잭션 양을 분석하여 테이블에 저장되는 데이터의 양을 유추하고 이를 근거로 DB의 용량 산정 및 구조의 최적화를 목적으로 한다.
•
트랜잭션 분석 → 업무 개발 담당자가 수행
•
트랜잭션 분석을 통해 프로세스가 과도하게 접근하는 테이블을 확인할 수 있으며, 이러한 집중 접근 테이블을 여러 디스크에 분산 배치함으로써 디스크 입출력 향상을 통한 성능 향상을 가져올 수 있다.
20. 인덱스
인덱스 (Index)
•
데이터 레코드를 빠르게 접근하기 위해 <키 값, 포인터> 쌍으로 구성되는 데이터 구조
•
레코드가 저장된 물리적 구조에 접근하는 방법을 제공한다.
•
인덱스를 통해서 파일의 레코드에 빠르게 엑세스 할 수 있다.
•
레코드의 삽입과 삭제가 수시로 일어나는 경우에는, 인덱스의 개수를 최소로 하는 것이 효율적이다.
인덱스의 종류
•
트리 기반 인덱스
◦
인덱스를 저장한느 블록들이 트리 구조를 이루고 있는 것
•
비트맵 인덱스
◦
인덱스 컬럼의 데이터를 Bit 값이 0 또는 1로 변환하여 인덱스 키로 사용하는 방법
•
함수 기반 인덱스
◦
컬럼의 값 대신 컬럼에 특정 함수(Function)나 수식(Expression)을 적용하여 산출된 값을 사용하는 것
•
비트맵 조인 인덱스
◦
다수의 조인된 객체로 구성된 인덱스
•
도메인 인덱스
◦
개발자가 필요한 인덱스를 직접 만들어 사용하는 것
클러스터드 / 넌클러스터드 인덱스
•
클러스터드 인덱스 (Clustered Index)
◦
인덱스 키의 순서에 따라 데이터가 정렬되어 저장되는 방식
◦
실제 데이터가 순서대로 저장되어 있어 인덱스를 검색하지 않아도 원하는 데이터를 빠르게 찾을 수 있음
•
넌클러스터드 인덱스 (Non- Clustered Index)
◦
인덱스의 키 값만 정렬되어 있고, 실제 데이터는 정렬되지 않는 방식
◦
데이터 삽입, 삭제 발생 시, 순서를 유지하기 위해 데이터를 재정렬해야 함
21. 뷰 / 클러스터
뷰 (View)
•
사용자에게 접근이 허용된 자료만을 제한적으로 보여주기 위해, 하나 이상의 기본 테이블로부터 유도된, 이름을 가지는 가상 테이블
•
뷰는 저장장치 내에 물리적으로 존재하지는 않지만, 사용자에게는 있는 것처럼 간주된다.
•
뷰를 통해서만 데이터에 접근하게 되면, 뷰에 나타나지 않는 데이터를 안전하게 보호하는 효율적인 기법으로 사용할 수 있다.
•
뷰가 정의된 기본 테이블이나 뷰를 삭제하면 그 테이블이나 기초로 정의된 다른 뷰도 자동으로 삭제된다.
•
뷰를 정의할 때는 CREATE 문, 제거할 때는 DROP 문을 사용한다
뷰의 장단점
장점
•
논리적 데이터 독립성을 제공함
•
동일 데이터에 대해 동시에 여러 사용자의 상이한 응용이나 요구를 지원해 줌
•
사용자의 데이터 관리를 간단하게 해줌
•
접근 제어를 통한 자동 보안이 제공됨
단점
•
독립적인 인덱스를 가질 수 없음
•
뷰의 정의를 변경할 수 없음
•
뷰로 구성된 내용에 대한 삽입, 삭제, 갱신 연산에 제약이 따름
클러스터 (Cluster)
•
데이터 저장 시, 데이터 액세스 효율을 향상시키기 위해, 동일한 성격의 데이터를 동일한 데이터 블록에 저장하는 물리적 저장 방법
•
클러스터링 된 테이블은 데이터 조회 속도를 향상시키지만 입력, 수정, 삭제에 대한 작업 성능을 저하시킨다.
•
클러스터는 데이터의 분포도가 넓을수록 유리하다
◦
분포도, 선택성 (Selectivity)
▪
(조건에 맞는 레코드 수 / 전체 릴레이션 레코드 수) * 100
▪
전체 레코드 중 조건에 맞는 레코드의 숫자가 적은 경우, 분포도가 좋다고 한다.
▪
인덱스는 분포도가 좁은 테이블이 좋지만, 클러스터링은 분포도가 넓은 테이블에 유리하다.
•
데이터 분포도가 넓은 테이블을 클러스터링 하면 저장 공간을 절약할 수 있다.
•
처리 범위가 넓은 경우에는 단일 테이블 클러스터링을, 조인이 많이 발생하는 경우에는 다중 테이블 클러스터링을 사용한다.
◦
단일 테이블 클러스터링은 여러 개의 테이블 뿐만 아니라, 한 개의 테이블에 대해서도 클러스터링을 수행할 수 있다.
▪
특정 컬럼의 동일한 값을 동일 블록이나 연속된 블록에 저장하므로, 데이터 조회 성능이 향상된다.
22. 파티션 (Partition)
파티션
•
데이터베이스에서 파티션은 대용량의 테이블이나 인덱스를 작은 논리적 단위인 파티션으로 나누는 것을 말한다.
•
대용량 DB의 경우, 몇 개의 중요한 테이블에만 집중되어 데이터가 증가되므로, 이런 테이블들을 작은 단위로 나눠 분산시키면 성능 저하를 방지할 뿐만 아니라 데이터 관리도 쉬워진다.
•
데이터 처리는 테이블 단위로 이뤄지고, 데이터 저장은 파티션별로 수행된다.
◦
하나의 테이블이 여러 개의 파티션으로 나눠져 있어도, DB에 접근하는 애플리케이션은 테이블 단위로 데이터를 처리하기 때문에 파티션을 인식하지 못한다.
파티션의 장단점
장점
•
데이터 접근 시, 액세스 범위를 줄여 쿼리 성능이 향상됨
•
파티션 별로 데이터가 분산되어 저장되므로, 디스크의 성능이 향상됨
•
파티션 별로 백업 및 복구를 수행하므로 속도가 빠름
•
시스템 장애 시, 데이터 손상 정도를 최소화 할 수 있음
•
파티션 단위로 입출력을 분산시킬 수 있음
단점
•
하나의 테이블을 세분화하여 관리하므로 세심한 관리가 요구됨
•
테이블간 조인에 대한 비용이 증가함
•
용량이 작은 테이블에 파티셔닝을 수행하면 오히려 성능이 저하됨
파티션의 종류
•
범위 분할 (Range Partitioning)
◦
지정한 열의 값을 기준으로 분할
◦
ex) 일별, 월별, 분기별 등
•
해시 분할 (Hash Partitioning)
◦
해시 함수를 적용한 결과값에 따라 데이터를 분할
◦
특정 파티션에 데이터가 집중되는 범위 분할의 단점을 보완, 데이터를 고르게 분산할 때도 유용
◦
특정 데이터가 어디에 있는지 판단할 수 있음
◦
고객변호, 주민번호 등과 같이 데이터가 고른 컬럼에 효과적임
•
조합 분할 (Composite Partitioning)
◦
범위 분할로 분할한 다음 해시 함수를 적용하여 다시 분할하는 방식
◦
범위 분할한 파티션이 너무 커서 관리가 어려울 때 유용
23. 분산 데이터베이스 설계
데이터베이스 용량 설계
•
데이터가 저장될 공간을 정의하는 것
•
데이터베이스 용량을 설계할 때는 테이블에 저장될 데이터 양과 인덱스, 클러스터 등이 차지하는 공간 등을 예측하여 반영해야 한다.
•
데이터베이스 용량 설계의 목적
◦
용량을 정확히 산정하여 디스크의 저장 공간을 효과적으로 사용하고 확장성 및 가용성을 높인다.
◦
디스크의 특성을 고려하여 설계함으로써, 디스크의 입출력 부하를 분산시키고 채널의 병목 현상을 최소화한다.
분산 데이터베이스 설계
•
분산 데이터베이스는 논리적으로는 하나의 시스템에 속하지만, 물리적으로는 네트워크를 통해 연결된 여러 개의 사이트에 분산된 데이터베이스를 말한다.
•
분산 데이터베이스는 데이터의 처리나 이용이 많은 지역에 데이터베이스를 위치시킴으로써 데이터의 처리가 가능한 해당 지역에서 해결될 수 있도록 한다.
•
분산 데이터베이스 설계는 애플리케이션이나 사용자가 분산되어 저장된 데이터에 접근하게 하는 것을 목적으로 한다.
분산 데이터베이스의 목표
•
위치 투명성 (Location Transparency)
◦
액세스하려는 데이터베이스의 실제 위치를 알 필요 없이 단지 데이터베이스의 논리적인 명칭만으로 액세스 할 수 있다.
•
중복 투명성 (Replication Transparency)
◦
동일 데이터가 여러 곳에 중복되어 있더라도 사용자는 마치 하나의 데이터만 존재하는 것처럼 사용하고, 시스템은 자동으로 여러 자료에 대한 작업을 수행한다.
•
병행 투명성 (Concurrency Transparency)
◦
분산 데이터베이스와 관련된 다수의 트랜잭션들이 동시에 실현되더라도, 그 트랜잭션의 결과는 영향을 받지 않는다.
•
장애 투명성 (Failure Transparency)
◦
트랜잭션, DBMS, 네트워크, 컴퓨터 장애에도 불구하고 트랜잭션을 정확하게 처리한다.
분산 설계 방법
•
테이블 위치 분산
◦
데이터베이스의 테이블을 각기 다른 서버에 분산시켜 배치하는 방법
•
분할 (Fragmentation)
◦
테이블의 데이터를 분할하여 분산
◦
분할 규칙 : 완전성(Completeness), 재구성(Reconstruction), 상호 중첩 배제(Disjointness)
◦
주요 분할 방법
▪
수평 분할
▪
수직 분할
•
할당 (Allocation)
◦
동일한 분할을 여러 개의 서버에 생성하는 분산 방법
◦
중복이 없는 할당과 중복이 있는 할당으로 나뉨
24. 데이터베이스 이중화 / 서버 클러스터링
데이터베이스 이중화 (Database Replication)
•
시스템 오류로 인한 데이터베이스 서비스 중단이나, 물리적 손상 발생 시, 이를 복구하기 위해 동일한 데이터베이스를 복제하여 관리하는 것
•
이중화를 수행하면 하나 이상의 데이터베이스가 항상 같은 상태를 유지하므로, 데이터베이스에 문제가 발생하면 복제된 데이터베이스를 이용하여 즉시 문제를 해결할 수 있다.
•
여러 개의 데이터베이스를 동시에 관리하므로 사용자가 수행하는 작업은 데이터베이스 이중화 시스템에 연결된 다른 데이터베이스에도 동일하게 적용된다.
•
애플리케이션을 여러 개의 데이터베이스에 분산 처리하므로, 데이터베이스의 부하를 줄일 수 있다.
•
데이터베이스 이중화를 이용하면 손쉽게 백업 서버를 운영할 수 있다.
데이터베이스 이중화의 분류
Eager 기법
•
트랜잭션 수행 중 데이터 변경이 발생하면 이중화된 모든 데이터베이스에 즉시 전달하여 변경 내용이 즉시 적용 되도록 하는 기법
Lazy 기법
•
트랜잭션의 수행이 종료되면 변경 사실을 새로운 트랜잭션에 작성하여 각 데이터베이스에 전달되는 기법
•
데이터베이스마다 새로운 트랜잭션이 수행되는 것으로 간주됨
데이터베이스 이중화 구성 방법
활동-대기 (Active-Standby) 방법
•
대기하고 있다가 장애 발생하면 자동을 모든 서비스를 대신 수행
•
많은 기업에서 이용
활동-활동 (Active-Active) 방법
클러스터링 (Clustering)
•
두 대 이상의 서버를 하나의 서버처럼 운영하는 기술
•
서버 이중화 및 공유 스토리지를 사용하여 서버의 고가용성을 제공한다.
◦
공유 스토리지(NAS) : 데이터 저장소를 네트워크로 연결하여 파일 및 데이터를 공유하는 것으로, 다수의 사용자 또는 서버가 데이터를 안전하고 편리하게 공유할 수 있다.
◦
고가용성(HA) : 시스템을 오랜 시간동안 계속해서 정상적으로 운영이 가능한 성질
•
클러스터링 종류
◦
고가용성 클러스터링
◦
병렬 처리 클러스터링
RTO
RTO (Recovery Time Objective, 목표 복구 시간)
•
비상사태 또는 업무 중단 시점으로부터 복구되어 가동될 때까지의 소요 시간
•
ex) 장애 발생 후 6시간 내 복구 가능
RPO
RPO ( Recovery Point Objective, 목표 복구 시점)
•
비상사태 또는 업무 중단 시점으로부터 데이터를 복구할 수 있는 기준점
•
ex) 장애 발생 전인 지난 주 금요일에 백업시켜 둔 복원 시점으로 복구 가능
25. 데이터베이스 보안
데이터베이스 보안
•
데이터베이스의 일부 또는 전체에 대해서 권한이 없는 사용자가 액세스하는 것을 금지하기 위해 사용되는 기술
•
보안을 위한 데이터 단위는 테이블 전체부터 특정 테이블의 특정 행과 열에 있는 데이터 값에 이르기까지 다양하다.
암호화 (Encryption)
•
데이터를 보낼 때 송신자가 지정한 수신자 이외에는 그 내용을 알 수 없도록 평문을 암호문으로 변환하는 것
•
암호화(Encryption) 과정
◦
평문 → 암호문
•
복호화(Decryption) 과정
◦
암호문 → 평문
•
암호화 기법
◦
개인기 암호화 방식 (Private Key Encryption)
◦
공개키 암호화 방식 (Public Key Encryption)
접근 통제
•
데이터가 저장된 객체와 이를 사용하는 주체 사이의 정보 흐름을 제한하는 것
•
접근 통제 3요소
◦
접근통제 정책
◦
접근통제 매커니즘
◦
접근통제 보안모델
임의 접근통제 (DAC, Discretionary Access Control)
•
데이터에 접근하는 사용자의 신원에 따라 접근 권한을 부여하는 방식
•
데이터 소유자가 접근 통제 권한을 지정하고 제어함
•
객체를 생성한 사용자가 생성된 객체에 대한 모든 권한을 부여받고, 부여된 권하능ㄹ 다른 사용자에게 허가할 수도 있음
강제 접근통제 (MAC, Mandatory Access Control)
•
주체와 객체의 등급을 비교하여 접근 권한을 부여하는 방식
•
시스템이 접근통제 권한을 지정함
•
데이터베이스 객체별로 보안 등급을 부여할 수 있음
•
사용자 별로 인가 등급을 부여할 수 있음
역할 기반 접근통제 (RBAC, Role Based Access Control)
•
사용자의 역할에 따라 접근 권한을 부여하는 방식
•
중앙관리자가 접근통제 권한을 지정함
•
임의 접근통제와 강제 접근통제의 단점을 보완하였음
•
다중 프로그래밍 환경에 최적화된 방식
접근통제 정책
•
어떤 주체가(Who), 언제(When), 어디서(Where), 어떤 객체(What)에게, 어떤 행위(How)에 대한 허용 여부를 정의하는 것
•
신분 기반 정책
◦
주체나 그룹의 신분에 근거하여, 객체의 접근을 제한하는 방법으로, IBP와 GBP가 있음
◦
IBP (Individual-Based Policy)
▪
최소 권한 정책으로, 단일 주체에게 하나의 객체에 대한 허가를 부여함
◦
GBP (Group-Based Policy)
▪
복수 주체에 하나의 객체에 대한 허가를 부여함
•
규칙 기반 정책
◦
주체가 갖는 권한에 근거하여 객체의 접근을 제한하는 방법으로, MLP와 CBP가 있음
◦
MLP (Multi-Level Policy)
▪
사용자나 객체별로 지정된 기밀 분류에 따른 정책
◦
CBP (Compartment-Based Policy)
▪
집단별로 지정된 기밀 허가에 따른 정책
•
역할 기반 정책
◦
GBP의 변형된 정책으로, 주체의 신분이 아니라 주체가 맡은 역할에 근거하여 객체의 접근을 제한하는 방법
접근통제 매커니즘
•
정의된 접근통제 정책을 구현하는 기술적인 방법
•
접근통제 매커니즘에는 접근통제 목록, 능력 리스트, 보안 등급, 패스워드, 암호화 등이 있다.
◦
접근통제 목록(Access Control List) : 객체를 기준으로 특정 객체에 어떤 주체가 어떤 행위를 할 수 있는지를 기록한 목록
◦
능력 리스트(Capability List) : 주체를 기준으로 주체에게 허가된 자원 및 권한을 기록한 목록
접근 통제 보안 모델
•
보안 정책을 위한 정형화된 모델
•
접근통제 보안 모델의 종류
•
기밀성 모델
◦
군사적인 목적으로 갭라된 최초의 수학적 모델
◦
기밀성 보장이 최우선
◦
군대 시스템 등 특수 환경에 주로 사용
•
무결성 모델
◦
기밀성 모델에서 발생하는 불법적인 정보 변경을 방지하기 위해 무결성을 기반으로 개발된 모델
•
접근통제 모델
◦
접근통제 매커니즘을 보안 모델로 발전시킨 것
◦
접근통제 행렬
접근통제 조건
•
값 종속 통제
•
다중 사용자 통제
•
컨텍스트 기반 통제
감사 추적
•
사용자나 애플리케이션이 데이터베이스에 접근하여 수행한 모든 활동을 기록하는 기능
•
요류가 발생한 데이터베이스를 복구하거나, 부적절한 데이터 조작을 파악하기 위해 사용
26. 데이터베이스 백업
데이터베이스 백업
•
전산 장비의 장애에 대비하여, 데이터베이스에 저장된 데이터를 보호하고 복구하기 위한 작업
•
치명적인 데이터 손실을 막기 위해서는 데이터베이스를 정기적으로 백업해야 한다.
로그 파일
•
데이터베이스의 처리 내용이나 이용 상황 등 상태 변화를 시간의 흐름에 따라 모두 기록한 파일
•
데이터베이스의 복구를 위해 필요한 가장 기본적인 자료
•
로그 파일을 기반으로 데이터베이스를 과거 상태로 복귀(UNDO)시키거나, 현재 상태로 재생(REDO)시켜 데이터베이스 상태를 일관성 있게 유지할 수 있다.
•
로그 파일은 트랜잭션 시작 시점, ROLLBACK 시점, 데이터 입력, 수정 삭제 시점 등에서 기록된다.
데이터베이스 복구 알고리즘
NO-UNDO / REDO
•
데이터베이스 버퍼의 내용을 비동기적으로 갱신한 경우의 복구 알고리즘
•
NO-UNDO
◦
트랜잭션 완료 전에는 변경 내용이 데이터베이스에 기록되지 않으므로 취소할 필요가 없음
•
REDO
◦
트랜잭션 완료 후, 데이터베이스 버퍼에는 기록되어 있고, 저장매체에는 기록되지 않았으므로 트랜잭션 내용을 다시 실행해야 함
UNDO / NO-REDO
•
데이터베이스 버퍼의 내용을 동기적으로 갱신한 경우의 복구 알고리즘
•
UNDO
◦
트랜잭션 완료 전에 시스템이 파손되었다면 변경된 내용을 취소함
•
NO-REDO
◦
트랜잭션 완료 전에 데이터베이스 버퍼 내용을 이미 저장 매체에 기록했으므로 트랜잭션 내용을 다시 실행할 필요가 없음
UNDO / REDO
•
데이터베이스 버퍼의 내용을 동기/비동기적으로 갱신한 경우의 복구 알고리즘
•
데이터베이스 기록 전에 트랜잭션이 완료될 수 있으므로, 완료된 트랜잭션이 데이터베이스에 기록되지 못했다면 다시 실행해야 함
NO-UNDO / NO-REDO
•
데이터베이스 버퍼의 내용을 동기적으로 저장 매채에 기록하지만, 데이터베이스와는 다른 영역에 기록한 경우의 복구 알고리즘
•
NO-UNDO
◦
변경 내용은 데이터베이스와 다른 영역에 기록되어 있으므로 취소할 필요가 없음
•
NO-REDO
◦
다른 영역에 이미 기록되어 있으므로, 트랜잭션을 다시 실행할 필요가 없음
백업 종류
•
복구 수준에 따라서 운영체제를 이용하는 물리 백업과 DBMS 유틸리티를 이용하는 논리 백업으로 나뉜다.
•
물리 백업
◦
데이터베이스 파일을 백업하는 방법
◦
백업 속도가 빠르고 작업이 단순하지만, 문제 발생 시 원인 파악 및 문제 해결이 어렵다.
•
논리 백업
◦
DB 내의 논리적 객체들을 백업하는 방법
◦
복원 시 데이터 손상을 막고 문제 발생 시 원인 파악 및 해결이 수월하지만, 백업/복원 시 시간이 많이 소요된다.
27. 스토리지
스토리지 (Storage)
•
단일 리스크로 처리할 수 없는 대용량의 데이터를 저장하기 위해 서버와 저장장치를 연결하는 기술
•
DAS, NAS, SAN
DAS (Direct Attached Storage)
•
서버와 저장장치를 전용 케이블로 직접 연결하는 방식
•
일반 가정에서 컴퓨터에 외장하드를 연결하는 것이 여기에 해당
NAS ( Network Attached Storage)
•
서버와 저장장치를 네트워크를 통해 연결하는 방식
•
다른 서버에서도 스토리지에 접근할 수 있어 파일 공유 가능
•
쉽게 접근 가능
•
확장성 및 유연성 우수
SAN (Storage Area Network)
•
DAS의 빠른 처리와 NAS의 파일 공유 장점을 혼합한 방식, 서버와 저장장치를 연결하는 전용 네트워크를 별도로 구성하는 방식
•
서버와 저장장치를 광케이블로 연결하므로 처리 속도 빠름
28. 논리 데이터 모델의 변환
엔티티(Entity)를 테이블로 변환
•
논리 데이터 모델에서 정의된 엔티티를 물리 데이터 모델의 테이블로 변환하는 것
슈퍼타입 기준 테이블 변환
서브타입 기준 테이블 변환
개별타입 기준 테이블 변환
속성을 컬럼으로 변환
관계를 외래키로 변환
•
논리 데이터 모델에서 정의된 관계는 기본키와 이름 참조하는 외래키로 변환한다.
29. 물리 데이터 모델 품질 검토
물리 데이터 모델 품질 검토
•
물리 데이터 모델을 설계하고 데이터베이스 객체를 생성한 후, 개발 단계로 넘어가기 전에 모델러와 이해관계자들이 모여 수행한다.
•
물리 데이터 모델 품질 검토의 목적은 데이터베이스의 성능 향상과 오류 예방이다.
•
물리 데이터 모델을 검토하려면, 모든 이해관계자가 동의하는 검토 기준이 필요하다.
물리 데이터 모델 품질 기준
30. 자료구조
배열
•
크기와 자료형이 동일한 자료들이 순서대로 나열된 자료의 집합
•
반복적인 데이터 처리 작업에 적합
•
정적인 자료구조, 기억장소의 추가 어렵다
•
데이터 삭제 시, 기억장소가 빈 공간으로 남아 있어 메모리 낭비 발생한다
연속 리스트
•
배열과 같이 연속되는 기억장소에 저장되는 자료구조
•
중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
•
삽입 삭제 시 자료의 이동이 필요하다.
연결 리스트
•
자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조
•
연결을 위한 링크(포인터) 부분이 필요하기 때문에, 기억 공간의 이용 효율이 좋지 않다.
•
접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어렵다.
스택
큐
그래프
방향/무방향 그래프의 최대 간선 수
31. 트리
트리
•
정점(Node, 노드)과 선분(Branch, 가지)를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
•
트리는 하나의 기억 공간을 노드라고 하며, 노드와 노드를 연결한 선을 링크라고 한다.
32. 이진트리
•
차수가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리
•
이진 트리의 레벨 i에서 최대 노드의 수는 2^(i-1)
트리의 운행법
Preorder
Inorder
Postorder
수식의 표기법
Infix → Postfix, Prefix
Postfix, Prefix → Infix
33. 정렬
삽입 정렬 (Insertion Sort)
•
가장 간단한 정렬 방식, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
•
평균과 최악 시간복잡도 O(N^2)
선택 정렬 (Selection Sort)
•
n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지(n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
•
평균과 최악 시간복잡도 O(N^2)
버블 정렬 (Bubble Sort)
•
주어진 파일에서 인접한 2개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
•
평균과 최악 시간복잡도 O(N^2)
쉘 정렬 (Shell Sort)
•
입력 파일을 어떤 매개변수의 값으로 서브 파일을 구성하고, 각 서브 파일을 삽입정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식
•
삽입 정렬을 확장한 개념
•
평균 시간복잡도 O(N^1.5), 최악 시간복잡도 O(N^2)
퀵 정렬 (Quick Sort)
•
키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식
•
코드의 많은 자료 이동을 없애고, 하나의 파일을 부분적으로 나누어 가면서 정렬
•
평균 시간복잡도 O(NlogN), 최악 시간복잡도 O(N^2)
힙 정렬 (Heap Sort)
•
전이진 트리를 이용한 정렬 방식
•
구성된 전이진 트리(Complete Binary Tree)를 힙 트리(Heap Tree)로 변환하여 정렬
•
평균, 최악 시간복잡도 O(NlogN)
2-Way 합병 정렬 (Merge Sort)
•
이미 정렬되어 있는 2개의 파일을 1개의 파일로 합병하는 정렬 방식
•
평균, 최악 시간복잡도 O(NlogN)
기수 정렬 (Radix Sort) = 버킷 정렬 (Bucket Sort)
•
큐를 이용하여 자릿수(Digit)별로 정렬하는 방식
•
레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
•
평균, 최악 시간복잡도 O(dN)