본문으로 건너뛰기

"database" 태그로 연결된 9개 게시물개의 게시물이 있습니다.

모든 태그 보기

· 약 50분

필요한 데이터를 수집, 필요시에 처리하는 수단

  • 자료 : 관찰이나 측정을 통해 수집, 가공되지 않은 상태
  • 정보 : 자료를 가공

자료처리시스템

정보시스템의 서브시스템

  • 일괄처리시스템 : 급여, 회계, 세무 등 모아서 처리

  • 온라인실시간처리시스템 : 예약, 은행처리

  • 분산처리시스템

  • 데이터웨어하우스 : 업무 시스템에서 추출 된 데이터 집합체

DB 시스템

개념

  • 통합된데이터 : 중복을 배제한 데이터의 모임 (Integrated)
  • 저장된데이터 : 저장매체에 저장된 자료 (Stored)
  • 운영데이터 : 업무를 수행하는데 반드시 필요한 자료 (Operational), 임시불가
  • 공용데이터 : 공동으로 소유, 유지 하는 자료 (Shared)

특징

  • 실시간접근성 : (Real-Time Accessibility)
  • 계속적인변화 : (Continuous Evolution)
  • 동시공용 : (Concurrent Sharing)
  • 내용에 의한 참조 : 주소나 위치에 의해서가 아니라 사용자가 요구하는 데이터로 검색(Content Reference)

구성요소

  • 데이터베이스
  • 스키마
  • DBMS
  • DB언어
  • DB컴퓨터
  • DB사용자

DBMS

  • DB 관리 소프트웨어
  • 모든 응용 프로그램이 DB 공용하도록 관리
  • DB 구성, 접근방법, 유지관리에 책임

DBMS의 기능

  • 정의(조직)기능 : 데이터 타입과 구조 정의, 이용방식, 제약조건 명시 (Definition)
  • 조작기능 : CRUD를 위해 사용자와 DB사이의 인터페이스 수단을 제공 (Manipulation)
  • 제어기능 : 데이터 무결성, 보안, 권한, 병행제어 처리 (Control)

DBMS의 장단점

  • 단점 : 전문가부족, 비용증가, Overhead, Backup과 Recovery의 어려움, 복잡

파일시스템의 문제점

  • 종속성 : 데이터의 접근방법을 변경하면 응용프로그램도 변경
  • 중복성 : 일관성, 보안성, 경제성, 무결성 위반

데이터독립성

  • 논리적 독립성 : 응용프로그램과 DB를 독립, 논리적 구조를 변경해도 응용프로그램 변경하지 않음
  • 물리적 독립성 : 응용프로그램과 물리적장치 독립, DB에 디스크를 추가해도 응용프로그램 변경하지 않음

DB의 구성요소

  • 개체
  • 속성 : 개체의 성질
  • 관계

데이터사전

  • 모든 데이터 개체들에 대한 정보를 유지 관리
  • alias 시스템 카탈로그
  • 데이터에 관한 데이터

스키마

  • 외부스키마
  • 개념스키마
  • 내부스키마

특징

  • 데이터 사전에 저장
  • alias 메타데이터
  • 데이터의 구조적 특성을 의미
  • 인스턴스에 의해 규정

외부스키마

  • 개인이 필요로하는 DB의 논리적 구조
  • VIEW
  • alias 서브스키마
  • 여러 개 존재 가능
  • 사용자는 SQL을 사용해 접근
  • 응용 프로그래머는 COBOL, C를 사용해 접근

개념스키마

  • DB의 전체적인 논리적 구조
  • 하나만 존재
  • DB 파일에 저장되는 데이터의 형태를 나타냄
  • alias 스키마
  • DBA에 의해 구성

내부스키마

  • 물리적 저장장치에서 본 DB 구조
  • DB에 저장될 레코드의 물리적인 구조 정의
  • 내부 레코드의 물리적 순서를 기술
  • alias 저장스키마
  • 시스템 프로그래머나 시스템 설계자가 봄

DB언어

DDL

  • DB를 구축하거나 수정

DML

  • 비절차적 데이터 언어
  • SQL, IMS, DBTG, TOTAL

DCL

  • 무경설, 보안, 권한, 회복

DB 사용자

DBA

  • DDL, DML, DCL 사용

응용 프로그래머

  • DML을 사용해 일반 사용자에게 응용프로그램 제공

일반사용자

  • SQL 사용

데이터 모델

정보를 단순화, 추상화하여 체계적으로 표현한 개념적 모형

개념적 데이터 모델

  • 추상적인 개념으로 표현
  • 개체와 관계를 통해 현실을 표현
  • ER모델
  • 현실 세계의 개체를 인간이 이해하는 구조로 기술

논리적 데이터 모델

  • 데이터 타입과 데이터 타입간의 관계를 통해 현실을 표현
  • DBMS는 논리적 데이터 모델을 하나만 사용
  • 관계모델, 계층모델, 네트워크모델
  • 현실 세계의 개체를 컴퓨터의 데이터구조로 기술

표시요소

표현요소, 구성요소

  • 구조 : 논리적으로 표현된 개체 타입들 간의 관계로 데이터 구조 및 정적 성질을 표현 (Structure)
  • 연산 : DB에 저장된 실제 데이터를 처리하는 작업에 대한 명세로 DB를 조작하는 기본 도구 (Operation)
  • 제약조건 : 실제 데이터의 논리적인 제약조건 (Constraint)

구성요소

  • 개체 : DB에 표현하려는 것, 유무형의 정보, 서로 연관된 속성, fs의 레코드 (Entity)
  • 속성 : 데이터의 가장 작은 논리적 단위, fs의 데이터항목 또는 데이터 필드, 개체를 구성하는 항목 (Attribute)
  • 관계 : 개체 간 또는 속성 간의 관계 (Relationship)

ER모델

Perter Chen, 개념적 표현

ERD

  • 개체 : □
  • 관계 : ◇
  • 속성 : ○
  • 기본키속성 : 밑줄원 또는 ●
  • 연결 : 선, 링크로 개체와 속성을 연결
  • DB의 논리적 구조 표현

관계형 데이터모델

테이블 (Relation)으로 표현

계층형 데이터모델

트리, 노드 = 개체, 부모 자식 관계

특징

  • 연쇄삭제
  • 개체 간 사이클 허용 안됨
  • 개체 = 세그먼트
  • DBMS = IMS

장점

  • 구조 간단, 판독 용이
  • 구현, 수정, 검색 용이
  • 독립성 보장

단점

  • 데이터 상호 유연성 붖고
  • 검색경로 한정
  • 삽입 삭제 연산 매우 복잡
  • 다 대 다 관계 처리 어려움

망형 데이터모델

CODASTYL DBTG 모델, 그래프, Owner-Member, N:M 관계

DB설계

고려사항

  • 무결성
  • 일관성
  • 회복
  • 보안
  • 효율성
  • DB 확장가능

개념적 설계

  • 개념 스키마 모델링과 트랜젝션 모델링
  • ERD 작성
  • alias 정보 모델링
  • 독립적 개념스키마

논리적 설계

현실세계를 물리적저장장치에 저장할 수 있도록 논리적 자료구조로 변환

  • 트랜잭션 인터페이스 설계
  • 테이블 설계
  • alias 데이터 모델링
  • 종속적 논리스키마

물리적 설계

  • DB file의 저장구조 및 액세스 경로 결정
  • 데이터가 컴퓨터에 저장되는 방법 묘사
  • 저장 레코드 양식 설계
  • 데이터타입
  • 데이터 값의 분포
  • 접근 빈도
  • 레코드 집중의 분석 설계
  • 접근 경로 설계
  • 기본 단위는 저장레코드

고려사항

  • 인덱스 구조
  • 반응시간 : (Response Time)
  • 공간활용도 : (Space Utilization)
  • 트랜잭션 처리량 : (Transaction Throughput)

DB 구현

  • DDL 이용해 스키마 기술
  • 응용 프로그램을 위한 트랜잭션 작성
  • DB 접근을 위한 응용 프로그램 작성

설계 순서

구 분석 > 념적 설계 > 리적 설계 > 리적 설계 >

관계형 DB 구조

테이블로 표현

  • 릴레이션 스키마 : 속성명
  • 릴레이션 인스턴스 : 데이터

튜플

  • row
  • 튜플은 릴레이션을 구성하는 각각의
  • 속성의 모임
  • fs의 레코드
  • 튜플의 수 = 카디널리티 (Cardinality) = 기수 = 대응수

속성

  • column
  • DB를 구성하는 가장 작은 논리적 단위,
  • fs의 데이터 또는 데이터 필드
  • 개체의 특성
  • 속성의 수 = 디그리 (Degree) = 차수

도메인

  • 하나의 속성 값들의 집합

관계형 DB 제약조건

후보키

모든 튜플에 대해 유일성과 최소성 만족

  • 유일성 : 하나의 키값으로 하나의 튜플만 식별 가능
  • 최소성 : 모든 레코드를 유일하게 식별하는데 필요한 속성

기본키

특정 튜플을 유일하게 구별할 수 있는 속성으로 후보키 중 선택한 Main key

  • Null 값 불가

대체키

  • 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키
  • alias 보조키

슈퍼키

  • 속성들의 집합으로 구성된 키
  • 유일성은 만족, 최소성은 불만족

외래키

  • 기본키를 포함하면 참조 릴레이션
  • 외래키를 포함하면 참조하는 릴레이션

무결성

  • 개체무결성 : 기본키를 구성하는 속성은 NULL이나 중복 불가
  • 참조무결성 : 외래키 값은 NULL이거나 참조 릴레이션의 기본키와 동일, 도메인과 속성 갯수가 같아야함

관계대수

관계형 DB에서 원하는 정보를 얻기 위해 사용하는 절차적인 언어로 연산자와 연산규칙을 제공한다.

  • 순수 관계 연산자 : Select, Project, Join, Division
  • 일반 집합 연산자 : Union, Intersection, Difference, Cartesian Product

순수 관계 연산자

Select

  • 수평연산
  • 시그마(σ)

Project

  • 속성만 추출하는 연산
  • 수직연산
  • 파이(π)

Join

  • 두 개의 릴레이션을 합쳐서 새로운 릴레이션으로 반환
  • 나비넥타이 (▷◁)
  • 자연조인 : 중복된 속성을 제거하여 같은 속성을 한 번만 표기하는 방법

Division

  • 속성을 제외한 속성만을 구하는 연산
  • 나누기 (÷)

일반 집합 연산자

  • 합집합, 교집합, 차집합은 합병 조건이 가능해야함.
  • 합병조건 : 합병하려는 두 릴레이션 간에 속성 수가 같고 도메인의 범위가 같음

합집합

  • Union
  • A ∪ B ≤ A + B
  • 합집합의 카디널리티는 두 릴레이션의 카디널리티의 합보다 크지 않다.

교집합

  • Intersection
  • A ∩ B ≤ MIN(A, B)
  • 교집합의 카디널리티는 두 릴레이션 중 작은 릴레이션보다 크지 않다.

차집합

  • Difference
  • A-B ≤ A
  • 차집합의 카디널리티는 A의 카디널리티보다 크지 않다.

교차곱

  • Cartesian Product
  • (A×B) = (A)×(B)
  • 교차곱은 두 릴레이션의 카디널리티를 곱한 것과 같다.
  • 디그리(차수)는 더하고, 카디널리티(튜플 수)는 곱하면 된다.

관계해석

  • E.F.Codd가 Predicate Calculus에 기반
  • 연산을 표현하는 방법, 원하는 정보를 정의시 계산 수식 사용
  • 비절차적 특성
  • 튜플 관게해석과 도메인 관계해석
  • 질의어로 표현

정규화

잘못 설계된 관계형 스키마를 작은 스키마로 쪼개서 바람직하게 만드는 과정으로 DB의 논리적 설계 단계에서 수행

목적

  • 안정성 최대화
  • 어떠한 릴레이션이라도 DB에서 표현이 가능
  • 효과적인 검색 알고리즘
  • 중복 배제하여 CRUD 이상의 발생 방지
  • 데이터 삽입시 릴레이션 재구성 필요성 제거

Anomaly

속성 간 종속 또는 튜플의 중복으로 발생

  • 삽입이상 : 원하지 않는 값도 같이 삽입
  • 삭제이상 : 연쇄 삭제
  • 갱신이상 : 일부만 갱신

과정

단계
비정규릴레이션
도메인이 원자값
1NF
부분적 함수 종속 제거
2NF
이행적 함수 종속 제거
3NF
결정자이면서 후보키가 아닌 것 제거
BCNF
다치 종속 제거
4NF
조인 종속성 이용
5NF

1NF

원자값으로만 되어있는 릴레이션

2NF

키가 아닌 모든 속성이 기본키에 대해 완전 함수적 종속

  • 함수적 종속관계 : A에 따라 B가 항상 같은 값이 나올 때 (키->값)
  • 완전 함수적 종속관계 : A,B에 따라 C가 항상 같은 값이 나오지만 A-C, B-C에서는 종속이 사라질 때 (여러 키->값)

3NF

키가아닌 모든 속성이 기본키에 대해 이행적 종속관계를 제거

  • 이행적 종속관계 : A->B, B->C일 때 A->C 인 관계

BCNF

릴레이션에서 결정자가 모두 후보키인 관계 (Boyce-Codd Normal Form)

  • 결정자 : A->B 일 때 A를 결정자, B를 종속자
  • 모든 BCNF가 종속성을 보존하는 것은 아니다.

4NF

릴레이션에서 A->->B가 성립할 때 모든 속성이 A에 함수적 종속인 관계

  • 다치종속 : A,C에 대응하는 B값들이 A에만 종속되고 C에는 무관할 때 A->->B

5NF

조인 종속성이 후보키를 통해서만 만족될 때

  • 조인종속 : 어떤 릴레이션이 자신의 pROJECTION에 대한 조인의 결과가 자신과 같을 때

SQL

  • IBM에서 개발한 SEQUEL에서 진화

  • 관계대수와 관계해석을 기초로한 혼합 데이터 언어

  • 정의, 조작, 제어 기능

  • DDL : Create, Alter, Drop

  • DML : Select, Insert, Delete, Update

  • DCL : Commit, Rollback, Grank, Revoke

DDL

  • CREATE SCHEMA|DOMAIN
  • CREATE TABLE 테이블명 PRIMARY UNIQUE FOREIGN KEY REFERENCES CONSTRAINT CHECK
  • CREATE INDEX ON [CLUSTER]
  • ALTER TABLE ADD|ALTER|DROP [CASCADE]
  • DROP SCHEMA|DOMAIN|TABLE|VIEW|INDEX [CASCADE|RESTRICTED]

DML

  • SELECT FROM [WHERE][group by] [HAVING][order by]

DML

  • INSERT INTO VALUES
  • DELETE FROM WHERE
  • UPDATE SET

내장 SQL

컴퓨터 프로그램에 SQL 명령을 삽입한 것

  • 일반 SQL은 여러 개의 튜플을 반환하지만, 내장 SQL은 단 하나의 튜플을 반환
  • 반환되는 튜플은 일반 변수를 사용하여 저장 가능
  • 호스트 변수와 DB 필드명은 같아도 된다.
  • 내장 SQL 앞에 EXEC SQL 사용
  • 호스트 변수는 변수앞에 콜론(:)을 붙임

커서

  • 내장 SQL문의 수행 결과로 복수의 튜플이 반환될 시 액세스 할 수 있게 해준다.
  • 질의 수행 결과로 반환되는 첫 튜플에 대한 포인터

커서 명령어

  • DECLARE : 선언
  • OPEN : 첫번째 튜플 포인트
  • FETCH : 다음 튜플로 포인터 이동
  • CLOSE : 종료

  • 본 테이블로 유도된 가상 테이블
  • 조인 사용 최소화로 사용상의 편의성을 최대화
  • 외부 스키마
  • 물리적으로 구현되어 있지 않음
  • 뷰가 정의된 테이블이나 뷰를 삭제하면 그걸 참조한 다른 뷰도 삭제됨.

장점

  • 논리적 데이터 독립성 제공
  • 보안

단점

  • 독립적인 인덱스 사용 불가
  • 정의 변경 불가
  • CRUD 제한

시스템 카탈로그

  • 시스템에 관련된 다양한 객체가 담긴 시스템 DB
  • alias 자료사전 = data dictionary = 카탈로그 = 데이터사전
  • 메타데이터 : 카탈로그에 저장된 정보
  • SQL을 이용해 내용 검색 가능
  • 수정 및 삽입 불가
  • DB에 따라 다른 구조
  • DBMS가 스스로 생성하고 유지
  • 시스템, 사용자 접근가능

Data Directory

  • 데이터 사전에 있는 데이터를 실제로 접근하는데 필요한 정보를 관리하는 시스템
  • 시스템만 접근가능

트랜잭션

  • DB 상태를 변환시키는 하나의 논리적 기능의 단위
  • 한꺼번에 모두 수행되어야할 연산들
  • 병행 제어 및 회복 작업시 처리되는 작업의 논리적 단위
  • 시스템이 응답하기 위한 상태 변환 과정의 작업 단위

특성

무결성을 보장

원자성

  • Atomicity
  • 트랜잭션 내의 명령은 반드시 완벽히 수행
  • 모두가 수행되거나 오류시 전부가 취소되어야함

일관성

  • Consistency
  • DB의 전체 요소는 트랜잭션 수행 전과 트랜잭션 수행 완료 후의 상태가 같아야함 (질량 보존 법칙처럼)

독립성

  • Isolation = 격리성 = 순차성
  • 둘 이상의 트랜잭션이 병행 실행되는 경우 다른 트랜잭션 연산이 끼어들 수 없음
  • 수행 중인 트랜잭션은 완료될 때 까지 다른 트랜잭션에서 참조 불가.

영속성

  • Durability = 지속성
  • 시스템이 고장나도 영구적으로 반영

Commit

Rollback

  • Active : 트랜잭션 실행 중
  • Failed : 트랜잭션 오류 발생으로 중단
  • Aborted : 트랜잭션 비정상적 종료로 Rollback 연산 실행한 상태
  • Partially Committed : 트랜잭션 마지막 연산까지 실행됬으나 Commit은 안 한 상태
  • Committed : 트랜잭션이 성공적으로 종료되어 Commit 연산 실행한 상태

회복

장애 발생으로 DB가 손상되었을 때 복구하는 작업, Recovery

  • 트랜잭션 장애 : 실행 또는 로직 오류
  • 시스템 장애 : 하드웨어 오동작, 소프트웨어 손상, 교착상태
  • 미디어 장애 : 물리적 데미지

회복기법

연기 갱신 기법

  • Deferred Update
  • 트랜잭션동안 갱신된 내용이 Log에 보관됨
  • Partially Committed 상태에서 Log에 보관한 내용을 실제 DB에 기록
  • Redo 작업만 가능

즉시 갱신 기법

  • Immediate Update
  • 트랜잭션 중이라도 DB에 반영
  • 장애 대비로 갱신 내용을 Log에 보관
  • Redo, Undo 모두 사용 가능

그림자 페이지 대체 기법

  • Shadow Paging
  • 트랜잭션을 Rollback할 때, 갱신된 이후의 실제 페이지 부분에 그림자 페이지를 대체하여 회복
  • 로그, Undo, Redo 필요 없음

검사점 기법

  • Check Point
  • 복구 시점을 로그에 보관하고 그 시점부터 회복작업을 수행

병행제어

다중 실행되는 트랜잭션들이 DB의 일관성을 파괴하지 않도록 트랜잭션 상호작용을 제어하는 것

목적

  • DB 공유 최대화
  • 시스템 활용도 최대화
  • DB 일관성 유지
  • 응답시간 최소화

직렬화 가능성

병행수행된 각각의 트랜잭션 결과는 각 트랜잭션을 독자적으로 실행했을 때의 결과와 같아야한다.

문제점

  • 갱신 분실 : 갱신 결과의 일부가 없어짐 (Lost Update)
  • 비완료 의존성 : 하나의 트랜잭션이 실패 후 회복되기 전에 다른 트랜잭션이 실패한 갱신결과를 참조하는 현상 (Uncommitted Dependency)
  • 모순성 : 두 개의 트랜잭션이 병행될 때 원치 않는 자료를 이용 (Inconsistency)
  • 연쇄 복귀 : 하나를 Rollback시 다른 것도 Rollback 되는 경우 (Cascading Rollback)

병행제어 기법

로킹

  • Lock이 허락되어야만 액세스할 수 있도록 하는 기법
로킹단위Lock 수병행성공유도
작음낮음감소
작음높음증가

2단계 로킹 규약

  • Tow-Phase Locking
  • 직렬성을 보장하지만 교착상태 예방 불가

타임 스탬프 순서

  • 트랜잭션을 실행 하기 전에 Time Stamp를 부여하여 부여된 시간에 따라 처리
  • 교착상태 발생 안함

최적 병행수행

  • 검증 = 확인 = 낙관적 기법
  • Read Only 트랝개션일 경우 충돌률이 낮으므로 병행제어를 안하고 실행

다중 버전 기법

  • 갱신될 때마다 버전을 부여하여 관리

무결성

  • DB 데이터의 정확성, 일관성을 보장하기 위해 부정확한 자료가 DB내에 저장되는 것을 방지하기 위한 제약조건
  • 사용자로부터 DB를 보호
  • 사용자가 정확하게 DB를 사용할 수 있도록 보장
  • 대표적인 방법은 중앙 통제에 의한 데이터 갱신
  • Null 무결성 : 특정 속성이 Null이 될 수 없음
  • 고유 무결성 : 각 튜플의 값이 서로 달라야함
  • 참조 무결성 : 외래키 값은 Null이거나 참조 릴레이션의 기본키 값과 같아야함.
  • 도메인 무결성 : 특정 속성이 그 도메인에 속해야함.
  • 키 무결성 : 하나의 테이블에는 적어도 하나의 키가 존재해야함.
  • 관계 무결성 : 릴레이션에 한 튜플의 삽입 가능 여부 또는 다른 릴레이션 튜플 사이의 관계에 대한 적절성 여부를 지정.
  • 개체 무결성 : 기본 키를 구성하는 어떤 속성도 Null이나 중복값을 가질 수 없음

DB 보안

  • 권한이 없는 사용자로부터 DB를 보호
  • 사용자들이 DB를 사용하고자 할 때 언제든지 사용할 수 있도록 보장

암호화

개인키 암호방식

  • alias 비밀키 암호방식 = 대칭 암호방식 = 단일키 암호화 기법
  • 동일한 키로 데이터를 암복호화
  • 전위, 대체, 대수, 합성기법
  • 암복호화 속도가 빠름
  • 알고리즘 단순
  • 파일 크기가 작음
  • 사용자가 증가하면 키 파일이 많아짐
  • DES : 64Bit의 평문 블록56Bit의 16개의 키를 이용해 암호 계산

공개키 암호방식

  • 서로 다른키로 데이터를 암복호화
  • 암호화키는 공개키로 복호화키는 관리자가 관리
  • alias 비대칭 암호 방식
  • 키 분배가 용이
  • 관리할 키 개수가 적음
  • 암복호화 속도가 느림
  • 알고리즘 복잡
  • 파일 크기가 큼
  • RSA

권한 부여

  • GRANT 사용자 등급 TO
  • REVOKE 사용자 등급 FROM
  • CASCADE 사용시 권한을 부여받았던 사용자가 다른 사용자에게 부여한 권한도 연쇄적으로 삭제됨

사용자 등급

  • DBA : DB 관리 책임자
  • RESOURCE : DB 및 테이블 생성 가능자
  • CONNECT : 단순 사용자

분산 DB

보안, 보호가 어렵다.

구성

  • 분산처리기
  • 분산db
  • 통신네트워크

목표

  • 위치 투명성 : DB의 논리적인 명칭으로 액세스 가능 (Location Transparency)
  • 중복 투명성 : 사용자는 하나의 데이터만 존재하는 것처럼 사용 (Replication Transparency)
  • 병행 투명성 : 다수의 트랜잭션이 실행 가능 (Concurrency Transparency)
  • 장애 투명성 : 장애가 나도 트랜잭션 처리 가능 (Failure Transparency)

미들웨어

  • 분산 환경에서 구성원을 연결하고 구성원 간의 차이를 극복하도록 범용으로 개발된 소프트웨어
  • 클라이언트와 서버 사이에 존재하면서 다중통신, 데이터 액세스 프로토콜과 인터페이스를 지원
  • 통신 미들웨어 : NOS
  • DB 미들웨어 : ODBC
  • 분산 객체 미들웨어 : CORBA, DCOM

자료구조

어떠한 자료구조에서도 필요한 모든 연산을 처리하는 것이 가능하다.

분류

{
"선형":{
"리스트":["선형", "연결"],
"스택",
"큐",
"덱"
},
"비선형":["트리","그래프"]
}

리스트

선형 리스트

  • 연접 리스트 = Dense List = 축차 구조 = Sequential Structure
  • 배 열
  • 간단한 자료 구조
  • 접근 속도 빠름
  • 중간 자료 삽입시 연속된 빈공간이 있어야함
  • 기억장소 효율 가장 좋음
  • 이동횟수 : 삽입시 n+12\frac{n+1}{2} 삭제시 n12\frac{n-1}{2}
  • 삽입 삭제 시 자료의 이동이 필요하기 때문에 번거로움

연결 리스트

  • 노드의 삽입 삭제 작업 용이
  • 기억공간이 연속적이지 않아도 저장 가능
  • 연결을 위한 포인터가 필요하기 때문에 기억공간 효율이 좋지 않음
  • 트리를 표현할 때 가장 적합
  • 희소행렬을 표현하면 기억장소가 절약됨
  • 희소행렬 : 행렬의 요소 중 많은 항이 0으로 되어 있는 형태

종류

  • 단순 연결 리스트
  • 단순 환상 연결 리스트
  • 이중 연결 리스트
  • 이중 환상 연결 리스트

스택

  • 한 쪽에서만 삽입 삭제 가능

  • 후입선출 (LIFO)

  • Top : 마지막으로 삽입된 자료의 위치 = 스택 포인터

  • Bottom : 스택 바닥

  • Overflow

  • Underflow

  • 부 프로그램 호출시 복귀주소 저장

  • 함수 호출의 순서 제어

  • 인터럽트 복귀주소 저장

  • 후위 표기법 연산

  • 0 주소 지정방식 명령어의 자료 저장소

  • 재귀 프로그램

  • 컴파일러를 사용한 언어 번역

  • 선형 리스트의 한쪽에서는 삽입, 다른쪽에서는 삭제만 이루어짐

  • 선입선출 (FIFO)

  • 시작과 끝을 표시하는 두개의 포인터 존재

  • 프런트 포인터

    • 가장 먼저 삽입된 자료의 포인터
    • 삭제 작업시 사용
  • 리어 포인터

    • 가장 마지막에 삽입된 자료의 포인터
    • 삽입 작업시 사용
  • 운영체제 작업 스케줄링

  • spool

  • 삽입과 삭제가 리스트 양쪽에서 일어남
  • Double Ended Queue
  • Stack과 Queue를 합쳐서 만듦
  • Scroll : 입력 제한 데크
  • Shelf : 출력 제한 데크

트리

  • 족보, 연산수식, 구조도, 힙(heap)에 사용
  • 근노드 : Root node
  • 단말노드 : Terminal Node = Leaf Node
  • 차수 : Degree = 가지 수
  • 레벨 : 노드의 레벨
  • 깊이 : 최대 레벨
  • 숲 : Forest 여러 트리의 집합
  • tree의 degree : MAX(degree)

이진트리

  • 차수가 2이하인 노드로 구성된 트리
  • 레벨 i에서의 최대 노드의 수는 $2^{n-1}$
  • 전체의 최대 노드의 수는 $2^n-1$
  • 단말 노드 수가 $N_0$, 차수(가지 수)가 2인 노드의 수가 $N_2$라고 할 때 $N_0=N_2+1$ 성립

정이진 트리

꽉찬 트리

전이진 트리

왼쪽부터 오른쪽으로 하나씩 빠짐없이 채워진 트리

사향트리

한 쪽 자식 노드가 없는 치우친 트리

  • 왼쪽 사향 이진 트리
  • 오른쪽 사향 이진 트리

이진트리 운행법

  • Preorder : Root > Left > Right
  • Inorder : Left > Root > Right
  • Postorder : Left > Right > Root

수식의 표기

  • Prefix : 연산자 > Left > Right

  • Infix : Left > 연산자 > Right

  • Postfix : Left > Right > 연산자

  • Infix to Prefix or Postfix : 연산에 따라 괄호로 묶고 연산자를 괄호 앞뒤로 옮김

  • Prefix or Postfix to Infix : 운행 순서에 따라 괄호로 묶어 연산자를 피연산자 사이로 이동

스레드 이진트리

  • 이진트리에서 발생하는 Null 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 된 트리
  • Nil로 Null pointer 기록
  • 왼쪽이 Nil이면 운행상 전 노드를 가리킴
  • 오른쪽이 Nil이면 운행상 후 노드를 가리킴
  • Nil이 아닐경우 다음 노드를 가리킴

그래프

  • 정점 (Vertex)와 간선 (Edge)로 이루어짐
  • 차수
    • 무방향 그래프 : 한 정점에 연결된 간선 수
    • 방향 그래프 : 진입(Indegree), 진출(Outdegree)
  • 완전 그래프의 간선 수
    • 무방향 그래프 : $\frac{n(n-1)}{2}$
    • 방향 그래프 : n(n1)n(n-1)
  • 사이클 : 같은 정점으로 시작과 끝이 이루어짐
  • 최대 사이클 : 사이클을 이루는 경로 중 최대 경로의 길이

인접행렬

  • Adjacency Matrix
  • 선이 있으면 1, 없으면 0으로 표기

최소 비용 신장 트리

  • MST = Minimum-Cost Spanning Tree
  • 가중치가 작은 간선들을 사이클을 이루지 않게 연결한 그래프

정렬

{
"내부정렬": {
"선택": ["힙"],
"삽입": ["삽입", "쉘"],
"교환": ["버블", "선택", "퀵"],
"병합": ["2-Way Merge Sort"],
"분배": ["기수"]
},
"외부정렬": [
"밸런스 병합",
"케스케이드 병합",
"폴리파즈 병합",
"오실레이팅 병합"
]
}

고려사항

  • 데이터의 양
  • 초기 데이터의 배열 상태
  • 키 값들의 분포 상태
  • 소요공간 및 작업시간
  • 시스템의 특성

내부정렬

삽입정렬

  • 이미 순서화된 파일에 NN번째 키를 앞의 N1N-1개의 키와 비교
  • 뒤에서 앞으로 비교

쉘정렬

  • 매개변수
  • 입력파일이 부분적으로 정렬되어 있는 경우

선택정렬

  • NN개의 레코드에서 최소값을 찾아 첫 번째 레코드에 놓고 나머지 N1N-1개 중에서 다시 최소값을 찾아 두번째... 를 반복
  • 앞에서 뒤로 비교

버블정렬

  • 주어진 파일에서 인접한 두 개의 레코드를 비교하여 그 크기에 따라 레코드 위치를 서로 교환
  • 계속 정렬 여부를 플래그 비트로 결정

퀵정렬

  • 작은 값은 왼쪽에 큰 값은 오른 쪽에 모이도록해서 분할해서 정렬
  • 가장 바름
  • 스택 필요

힙 정렬

  • 전이진 트리를 이용한 정렬 방식

2-Way 합병 정렬

  • Merge Sort
  • 두 개의 키를 한 쌍으로 하여 각 쌍에 대해 순서를 정함
  • 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 병합

기수 정렬

  • 큐를 이용하여 자릿수 별로 정렬
  • 레코드의 키를 분석하여 같은 수 또는 문자끼리 그 순사에 맞는 버킷에 분배했다가 버킷 순으로 레코드를 꺼내어 정렬
  • 키워드를 나타내는 레이블 내의 주소로 키워드를 변경

검색

선형 검색

  • 첫 번쨰 레코드 키 값부터 차례로 비교하여 검색
  • 순차 검색

제어 검색

  • 반드시 순서화된 파일이여야 검색 가능
  • 한 번의 비교가 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 사용
  • 이분 검색 : M = F+L2\frac{F+L}{2}
  • 피보나치 검색
  • 보간 검색 : 있음직한 부분의 키를 택하여 검색, 프로그래밍 불가
  • 블록 검색 : 블록으로 분할해 인덱싱 후 어느 인덱스에 있는지 검색 후 블록 내를 다시 선형 검색

이진 트리 검색

  • 파일을 이진 검색 트리로 구성하여 검색
  • 이진 검색 트리 : 왼쪽 자식노드는 부모보다 작고, 오른쪽 자식노드는 부모보다 크게 구성

해싱

  • 해싱은 DAM 파일을 구성할 때 사용, 접근 속도는 빠르나 기억공간 요구
  • 다른 방식에 비해 검색속도가 가장 빠름
  • 삽입 삭제 작업이 많을 때 유리
  • 키-주소 변환방법

해시테이블

  • 버킷 : 하나의 주소를 갖는 파일의 한 구역
  • 슬롯 : 한 개의 레코드를 저장할 수 있는 공간, N개의 슬롯이 모여 하나의 버킷
  • Collision : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
  • Synonym : 충돌로 인해 같은 주소를 같는 레코드들의 집합
  • Overflow : 버킷에 저장할 공간이 없는 상태, Collision은 발생해도 Overflow는 발생하지 않을 수 있음

해싱함수

  • 제산법 : 소수를 사용함 (Division)
  • 제곱법 : 키를 제곱해 중간부분을 추출 (Mid-Square)
  • 폴딩법 : 키를 여러부분으로 나눠 각 부분을 더하거나 XOR한 값을 추출 (Folding)
  • 기수 변환법 : 키 숫자의 진수를 다른 진수로 변환시켜 초과한 자릿수를 절삭
  • 대수적 코딩법 : 키 값의 비트 수를 다항식의 계수로 간주
  • 계수 분석법 : 숫자 분포를 분석하여 비교적 고른자리
  • 무작위법 : 랜덤

Overflow 해결

개방 주소법

  • 선형 방법
  • 순차적으로 그 다음 빈 버킷을 찾아 저장
  • Open Addressing

폐쇄 주소법

  • Overflow된 레코드를 별도의 Overflow영역에 저장하고 체인(Pointer)로 홈버킷과 연결
  • Direct Chaining : Cylinder Overflow Area에 보관 (해시테이블 내)
  • Indirect Chaining : Independent Overflow Area에 보관 (해시테이블 밖)

재해싱

새로운 해싱함수로 새로운 홈 주소

인덱스

  • 데이터 레코드를 빠르게 접근하기 위해 구성하는 것
  • 데이터가 저장된 물리적 구조와 밀접한 관계
  • 레코드가 저장된 물리적 구조에 접근하는 방법을 제공
  • 삽입과 삭제가 빈번하면 인덱스의 갯수를 최소화

m-원 검색 트리

  • m-Way Search Tree
  • 키 값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는데 효과적
  • 삽입, 삭제시 트리 균형을 유지하기 위해 복잡한 연산이 필요

B트리

  • 균형된 m원 검색트리
  • 모든 Leaf는 같은 레벨이 있다.
  • 한 노드 안에 있는 키 값들은 오름차순을 유지

B+트리

  • B트리의 변형, 인덱스 세트와 리프 노드로만 구성된 순차 데이터 세트로 구성
  • B트리의 연산과정을 줄일 수 있는 트리구조

트라이 색인

  • Trie
  • 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조
  • 키 값이 문자 또는 숫자일 경우, 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되어있을 때 적합
  • 삽입, 삭제시 노드의 분열과 병합이 없음
  • 키 값의 분포를 예측할 수 있다면 기억장소를 절약 가능

파일 편성

순차 파일

  • Sequential File = 순서파일
  • 물리적 연속 공간에 순차적으로 기록
  • 급여관리 등 기간별로 일괄처리를 주로 하는 경우에 적합
  • 자기테이프

장점

  • 기록 밀도가 높아 기억공간 효율적 사용
  • 어떠한 매체에도 적용
  • 키 순서대로 편성되어 취급 용이
  • 키 순서대로 레코드 처리시 빠름

단점

  • 새로운 레코드 삽입, 삭제시 재구성을 위해 전체를 복사해야함
  • 검색시 처음부터 순차적으로 하기에 효율이 낮고 응답시간이 느림

색인 순차 파일

  • Indexed Sequential File
  • 순차 처리와 랜덤처리가 모두 가능하도록 레코드를 키 값순으로 정렬시켜 기록
  • 레코드의 키 항목만을 모은 색인 파일을 구성하여 편성
  • 색인을 이용한 순차적인 접근방법을 제공하여 ISAM
  • 레코드를 참조시 색인 탐색 후 색인이 가리키는 포인터를 사용해 직접 참조
  • 자기디스크
  • 자기테이프 불가능

구성

  • 기본 구역 : 실제 레코드를 기록하는 부분, 키 값 순으로 저장
  • 색인 구역
    • 마스터 색인 구역 : 실린더 색인 구역의 정보가 많을 경우, 해당 레코드가 어느 실린더 색인 구역에 기록되어 있는지를 기록
    • 실린더 색인 구역 : 트랙 색인의 최대키 값과 해당 레코드가 기록된 실린더의 정보가 기록, 한 파일당 하나씩 만들어짐
    • 트랙 색인 구역 : 트랙상 기록되어 있는 데이터 레코드 중의 최대 키 값과 주소가 기록, 한 실린더당 하나씩, 처리할 레코드가 실제로 어느 트랙에 기록되어있는지를 판별
  • 오버플로 구역 : 기본구역에 빈공간이 없어서 예비적으로 확보해둔 구역
    • 실린더 오버플로 구역 : 해당 실린더의 기본구역에서 오버플로된 데이터 기록
    • 독립 오버플로 구역 : 실린더 오버플로에 더 이상 기록할 수 없을 때 사용할 수 있는 예비 공간

장점

  • 삽입, 삭제, 갱신 용이
  • 파일 전체를 복사할 필요 없음

단점

  • 색인 및 오버플로 구역을 구성하기 위한 추가 기억공간 필요
  • 오버플로 레코드가 많아지면 파일을 재편성
  • 파일이 정렬되어 있어야함
  • 삽입, 삭제가 많으면 효율이 떨어짐
  • 액세스 시간이 랜덤 편성파일보다 느림

정적 인덱스

  • 인덱스의 구조가 변경되지 않고 내용만 변하는 구조
  • ISAM

동적 인덱스

  • 추가로 삽입될 레코드를 감안하여 빈 공간을 미리 예비해 두는 인덱스
  • VSAM
  • 블록에 레코드가 가득차면 동적으로 분열
  • 일정 수의 레코드가 유지되지 않는 블록은 병합

VSAM

동적 인덱스 방법을 이용한 색인 순차 파일

  • 기본 구역과 오버플로 구역을 구분하지 않음
  • 레코드를 삭제하면 그 공간을 재사용
  • 제어 구간에 가변 길이 레코드를 쉽게 수용

직접 파일

  • Direct File = Random File = DAM (Direct Access Method)
  • 레코드에 특정 기준으로 키가 할당, 해시 함수를 이용해 이 키에 대한 물리적 상대 레코드 주소를 계산 후 레코드 저장
  • 자기 디스크, 자기 드럼

장점

  • 물리적 주소를 통해 각 레코드에 직접 접근
  • 접근시간이 빠름
  • 삽입, 삭제, 갱신 용이
  • 어떤 레코드라도 평균 접근 시간에 검색 가능

단점

  • 레코드 주소 변환 과정 필요
  • 기억 공간 효율 저하
  • 물리적 구조에 대한 지식 필요
  • 프로그래밍 복잡
  • 충돌 발생 염려로 기억공간 확보

역파일

  • Inverted File
  • 여러 개의 색인을 만들어 항목별 특성에 맞게 분배한 파일로 다중 키 파일에 속함
  • 다중 키 파일 : 하나의 데이터에 여러개의 접근 방법을 지원하는 구조
    • 순차 처리와 임의 처리가 모두 가능하도록 편성
    • 검색 속도가 빨라 빠른 시간 내에 정보를 얻고자하는 시스템에 적합
  • 색인 값을 결합하여 레코드 주소를 결정
  • 레코드를 파일 중간에 삽입하기 쉬움
  • 검색 속도 빠름
  • 데이터 파일에 접근하지 않아 응답시간이 줄어듦
  • 처리가 쉬움
  • 색인 항목이 가변적

다중 리스트 파일

  • Multi-List File
  • 다중 키파일의 한 종류
  • 각 키에 대해 색인을 만든 후 각 데이터 레코들 간에 다중 리스트를 구축하여 구성
  • 색인의 각 항목들의 길이가 고정적으로 관리가 용이
  • 수정, 삭제 검색이 효율적

다중 링 파일

  • Multi-Ring File
  • 같은 특성을 가진 레코드들을 포인터로 연결하여 구성
  • 같은 항목값을 가진 레코드를 한꺼번에 처리하는 효과적
  • 기억장소 절약
  • 자료 중복성 배제
  • 레코드 형식이 달라도 처리 가능

· 약 4분

Maria DB 를 써야하는 이유는 MySQL 이 지원이 끝났기 때문이고, 오라클이 소유하고 있어 언제 유료화가 될지 모르고, Thread Pool, 강화된 스토리지 엔진 (InnoDB -> XtraDB), 새로운 스토리지 엔진 (Aria, Cassandra)과 HandlerSocket, Virtual Column 등의 새로운 기능이 있기 때문이다.

설치를 시작해보자!

버전 및 bit 확인

# get version
$ cat /etc/*release*
# get bit
$ getconf LONG_BIT

yum repo 복사

maria로 이동해 맞는 버전을 추가한다.

image from hexo

yum repo 추가

$ vi /etc/yum.repos.d/MariaDB.repo

명령어로 MariaDB repository 를 생성한 뒤 복사한 내용을 붙히고 저장한다.

설치

$ yum install -y MariaDB-server MariaDB-client

혹여 설치가 안되면 maria 문서를 참고해서 따라해보자 (영어)

부팅 서비스 등록

$ chkconfig mysql on
# 또는
$ chkconfig --add mysql
$ chkconfig --level 345 mysql on

# 등록 확인
$ chkconfig --list mysql

maria에서는 345 레벨을 on 하라고 했는데, chkconfig mysql on 으로 실행시켜 2345 레벨을 모두 on 시켰다. 2 레벨은 not networking 이라 DB 의 원격지 접속이 안될테니 off 시켜도 무관하다.

서비스 실행

$ service mysql start

Starting MySQL.... [ OK ]

Maria 의 서비스명은 MySQL 로 뜬다.

Config 파일 수정 및 통합

처음 설치시 my.cnf 에서 my-server, my-client 등의 파일을 임포트해 분할 관리하게 되어있는데, 하나로 합쳐보자.

MariaDB 설치 폴더를 들어가면 My innoDB Huge 라는 config 파일이 존재한다. 이걸 그대로 사용해도 되고, 사용자 환경에 맞게 커스터마이징해서 사용해도 된다.

서버의 메모리가 8 GB 이상, innoDB 환경에서 사용가능한 config 파일을 첨부하니 이걸 써도 된다.

Thread Pool 기능을 사용하기 위해 extra_port 를 3307 로 줬다.

소스

my.cnf
[client]
port = 3306
socket = /var/lib/mysql/mysql.sock

[mysqld]
port = 3306
socket = /var/lib/mysql/mysql.sock

character-set-server = utf8mb4
collation_server = utf8mb4_general_ci

back_log = 100
max_connections = 100
max_connect_errors = 10
table_open_cache = 2048
max_allowed_packet = 16M

binlog_cache_size = 4M
binlog_format = row

max_heap_table_size = 16M

read_buffer_size = 2M
read_rnd_buffer_size = 16M
sort_buffer_size = 8M
join_buffer_size = 8M

query_cache_type = 0
default-storage-engine = InnoDB
thread_stack = 256K
tmp_table_size = 16M

secure_auth =1

skip_external_locking
skip_symbolic_links

# Replication related settings
server-id = 1
expire_logs_days = 3
log_slave_updates

# MyISAM Specific options
key_buffer_size = 32M
bulk_insert_buffer_size = 64M
myisam_sort_buffer_size = 8M
myisam_max_sort_file_size = 16M
myisam_repair_threads = 1
myisam_recover = FORCE,BACKUP

# INNODB Specific options
innodb_additional_mem_pool_size = 16M
innodb_buffer_pool_size = 2G
innodb_data_file_path = ibdata1:10M:autoextend
#innodb_data_home_dir = <directory>
innodb_thread_concurrency = 16
innodb_flush_log_at_trx_commit = 0

innodb_log_buffer_size = 32M
innodb_log_file_size = 1024M
innodb_log_files_in_group = 2
#innodb_log_group_home_dir

innodb_max_dirty_pages_pct = 75

[mysqldump]
quick
max_allowed_packet = 16M
default-character-set = utf8

[mysql]
no-auto-rehash

[myisamchk]
key_buffer_size = 512M
sort_buffer_size = 512M
read_buffer = 8M
write_buffer = 8M

[mysqlhotcopy]
interactive-timeout

[mysqld_safe]
open-files-limit = 8192

[mariadb]
# thread pool
thread_handling=pool-of-threads
thread_pool_idle_timeout = 3600
thread_pool_stall_limit = 100
extra_port = 3307
extra_max_connections=10

· 약 1분

스크립트 생성

$ vi dump.sh

dump.sh 파일을 만들고 아래 내용을 추가해 준다.

$ mysqldump -u 유저명 -p비밀번호 데이터베이스명> 경로`date+%y%m%d%H`.sql

스크립트를 원하는 시간대로 cron 에 등록한다.

예제

ID : test, PW: test, DB : test 의 dump 를 생성하고 싶을 때

$ mysqldump -u test-ptest test> /home/test/dump/`date+%y%m%d%H`.sql

· 약 1분
CREATE USER '유저명'@'%' IDENTIFIED BY '비밀번호'; -- 모든 아이피 접근
CREATE USER '유저명'@'localhost' IDENTIFIED BY '비밀번호'; -- 로컬호스트 접근
CREATE USER '유저명'@'127.0.0.1' IDENTIFIED BY '비밀번호'; -- 로컬호스트 접근

데이터베이스에 모든 권한 부여

-- 해당 디비명의 유저의 모든권한 설정
GRANT ALL PRIVILEGES ON 디비명.* TO '유저명'@'%' WITH GRANT OPTION;

권한 적용

FLUSH PRIVILEGES;

권한 확인

SHOW GRANTS FOR '유저명'@'%';

여담

권한 부여는 쉘상에서 접근해야지 오류가 없다.

부분 권한 또는 부분 테이블로 권한을 제한하고 싶다면, MySQL Grant Syntax를 참조한다.

· 약 2분

@Rownum 변수를 사용해 페이징 쿼리를 구현했는데, MySQL 에서는 정상적으로 정렬이 되다가 Maria 로 이관 후에 정렬이 반대로 나오는 경우가 있다.

쿼리

SELECT SQL_CALC_FOUND_ROWS @RNUM:=@RNUM+1 AS ROWNUM, R.* FROM (
SELECT @RNUM:=0, Q.* FROM (

SELECT * FROM TABLE1
WHERE ID = '1'
ORDER BY REG DESC
) Q
) R
LIMIT 0,10

설명

Rownum 변수를 사용해 TABLE1 에서 최신 날짜 순으로 데이터를 가지고 온다.

해결

LIMIT 2^64-1를 서브쿼리 내에 추가해준다.

LIMIT 의 최댓값은 unsigned 64bit-1 이므로 해당 값을 날려준다.

쿼리

SELECT SQL_CALC_FOUND_ROWS @RNUM:=@RNUM+1 AS ROWNUM, R.* FROM (
SELECT @RNUM:=0, Q.* FROM (

SELECT * FROM TABLE1
WHERE ID = '1'
ORDER BY REG DESC

LIMIT 18446744073709551615
) Q
) R
LIMIT 0,10

원인

Optimizer 가 임시테이블을 만든 후 filesort 하기 때문에 발생한다.

· 약 1분

Database Migration 또는 Module 설치시 MySQL 버전을 자주 물어본다.

SELECT version();

SHOW variables LIKE 'datadir';

설명

첫번째 쿼리 실행시 버전이 나오고, 두번째 쿼리 실행시 설치 경로가 나온다.

· 약 1분

잘못된 업데이트 쿼리를 돌리다가 테이블이 잠길 경우 Lock을 해제해줘야 한다.

show processlist

kill ${processid}

설명

show processlist 쿼리를 날리면 현재 database를 사용 중인 프로세스의 목록이 나온다. 목록에서 해당 쿼리를 찾은 뒤 process id를 가지고 kill 쿼리를 실행하면 된다.