Computer Science Knowledge Storage

배열은 같은 타입의 데이터를 모은 집합으로 메모리 공간에서 연속적인 공간을 할당받습니다. 런타임에 배열의 크기가 결정되며 랜덤접근을 통해 데이터를 접근하는데에 O(1)의 시간복잡도를 가져 접근이 많은 프로그램에 유용한 자료구조 입니다.

리스트는 같은 타입의 데이터를 모은 집합으로 배열과 동일하나 메모리 공간에서 연속적인 공간을 할당받지 않습니다. 리스트는 크기가 동적으로 할당할 수 있으며 순차적인 접근을 하기에 삽입, 삭제에는 O(1)의 시간복잡도를 가지지만 탐색에는 O(N)의 시간복잡도를 가집니다.

스택은 선형 자료 구조의 일종으로 나중에 들어간 원소가 먼저 나오는 LIFO 구조인 자료구조입니다. 재귀함수의 콜스택이나 방문 기록 등에 사용되고 있습니다.

큐는 선형 자료구조의 일종으로 먼저 들어간 원소가 먼저 나오는 FIFO 구조의 자료구조입니다. CPU 작업을 기다리는 프로세스나 캐시 등에 사용되고 있습니다.

해시 테이블은 무한에 가까운 데이터들을 유한한 갯수의 해시 값으로 매핑한 테이블입니다.

이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있습니다.

그래프는 정점과 간선으로 이루어진 자료구조를 말하며 트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져있고 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다. 트리는 그래프와 달리 사이클이 존재하지 않습니다.

이진 탐색 트리는 선형적으로 구성될 때 시간 복잡도가 O(N)으로 커지는 문제점이 있습니다. 선형적으로 구성되지 않고 균형 잡힌 트리로 구성하기 위해 나온 트리로 AVL트리와 레드 블랙 트리가 있습니다.

AVL트리는 스스로 균형을 잡는 이진 탐색 트리입니다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 나는 특징이 있습니다. 탐색 삽입 삭제 모두 시간 복잡도가 O(logN)이며 삽입 삭제할 때마다 균형을 맞추기 위해 회전을 진행합니다.

레드 블랙 트리는 균형을 유지하기 위해 노드에 색상(빨강 또는 검정)을 부여하고 몇 가지 규칙을 따릅니다. 레드 블랙 트리는 AVL 트리보다 느슨한 균형을 유지하기 때문에 삽입과 삭제 시 회전 연산이 더 적게 발생합니다. 이로 인해 삽입과 삭제의 성능은 더 나은 경우가 많습니다. 레드 블랙 트리는 AVL 트리와 마찬가지로 탐색, 삽입, 삭제의 시간 복잡도는 O(log N)으로 보장되지만, AVL 트리만큼 탐색 속도가 빠르진 않을 수 있습니다.

복잡도

시간복잡도

빅오 표기법

• 시간 복잡도: 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간.
• 반복 횟수를 중점으로 체크하며 빅오 표기법으로 표현
• 10N^2 + 100N이면 O(N^2)으로 표현

공간복잡도

• 공간복잡도: 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.
• 정적 변수 + 동적 변수
• 예: int[] a = new int[1000]은 1000 * 4byte

자료구조에서의 시간 복잡도

평균

worst

선형 자료구조

연결 리스트

• 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조
• 삽입 삭제 O(1) 탐색 O(N)
• prev 포인터와 next 포인터, 데이터를 담는 용량
• 싱글 연결 리스트
  • next 포인터만 가짐
• 이중 연결 리스트
  • next, prev 포인터를 가짐
• 원형 리스트
  • 이중 연결 리스트와 같지만 마지막 노드의 next가 head를 가르킴.

배열

• 같은 타입의 변수들로 이루어져있고, 크기가 정해져있으며 인접한 메모리 위치에 데이터를 모아놓은 집합.
• 중복 허용, 순서가 있음.
• 접근: O(1) 랜덤 접근 가능, 삽입, 삭제: O(N)
• 데이터 추가 + 삭제가 많을 때에는 연결리스트, 접근을 많이할 때에는 배열로.

랜덤 접근과 순차적 접근

• 랜덤 접근(직접 접근): 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능.
• 데이터를 순서대로 접근하는 순차적 접근과는 정반대
• 배열 ⇒ 랜덤접근, 연결리스트 ⇒ 순차적 접근

벡터

• 동적으로 요소를 할당할 수 있는 동적 배열.
• 컴파일 시점에 갯수를 모른다면 백터를 사용
• 중복을 허용하고 랜덤접근이 가능.
• 탐색 O(1) 삭제, 삽입 O(N)

스택

• 가장 마지막에 들어간 데이터가 가장 첫번째로 나오는 LIFO(Last In First Out)
• 재귀 함수(콜스택), 알고리즘, 방문기록에 사용
• 삽입 삭제 O(1) 탐색 O(N)

큐

• 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out), 스택과 반대
• 삽입, 삭제 O(1) 탐색 O(N)
• CPU 작업을 기다리는 프로세스, 스레드 행렬, 네트워크 접속을 기다리는 행렬, 너비우선탐색, 캐시에 사용

비선형 자료 구조

그래프

• 정점과 간선으로 이루어진 자료구조

정점과 간선

• 어떠한 곳: 정점
• 무언가: 간선
• 단방향 간선과 양방향 간선이 있음
• 정점으로 나가는 간선은 outdegree, 들어오는 간선은 indegree
• 정점과 간선으로 이루어진 집합을 그래프

가중치

• 간선과 정점 사이에 드는 비용.

트리

• 그래프의 특징처럼 정점과 간선으로 이루어져있고 사이클이 없는 구조

특징

• 루트 노드, 내부 노드, 리프 노드가 존재
• 루트 노드
  • 가장 위에 있는 노드.
• 내부 노드
  • 루트 노드와 리프 노드 사이에 있는 노드
• 리프 노드
  • 자식 노드가 없는 노드. 마지막 노드.

이진트리

• 자식 노드 수가 두개 이하인 트리
• full binary tree
  • 자식 노드가 0또는 두개인 이진 트리
• 완전 이진 트리
  • 왼쪽에서부터 채워져있는 이진 트리
  • 마지막 레벨을 제외하고는 다 채워져있으며 마지막 레벨의 경우 왼쪽부터
• 변질 이진 트리
  • 자식 노드가 하나밖에 없는 이진 트리
• 포화 이진 트리
  • 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리
  • 왼쪽과 오른쪽 노드의 높이 차이가 1이하인 이진 트리를 의미
  • map이나 set으로 구성
• 이진탐색트리
  • 왼쪽 트리에는 노드 값보다 작은 노드들만 오른쪽 트리에는 노드 값보다 큰 노드들만.
  • 탐색에는 평균 O(logN) 최악은 O(N)
• AVL 트리
  • 최악의 선형 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리.
  • 두 자식 서브 트리의 높이가 항상 최대 1만큼 차이나는 특징
  • 탐색 삽입 삭제 O(logN)
  • 회전을 함
• 레드 블랙 트리
  • 균형 이진 트리
  • 탐색 삽입 삭제 O(logN)
  • 모든 리프 노드와 루트노드는 블랙이며 어떤 노드가 레드면 그 노드의 자식은 블랙이다.

힙

• 완전 이진 트리 기반의 자료구조.
• 최대 힙: 루트의 키가 키 중에 가장 큰 값.
• 최소 힙: 루트의 키가 키 중에 가장 작은 값.
• 삽입
  • 힙의 성질을 통해 리프 노드에 삽입
  • 그 이후에 heapify
• 삭제
  • 루트 노드 삭제
  • 리프 노드와 교체
  • heapify

우선순위 큐

• 우선순위 대기열이라고도 하며 우선순위가 높은 요소나 우선순위가 낮은 요소보다 먼저 제공되는 자료구조
• 힙을 기반으로.

맵

• 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조
• 레드블랙 트리 자료구조를 기반으로 형성
• 정렬을 보장하지 않을때 해시테이블로

셋

• 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
• unique한 값만을 저장.

해시 테이블

• 무한에 가까운 데이터를 유한한 개수의 해시 값으로 매핑한 테이블
• 삽입 삭제 탐색시 평균적으로 O(1)

• 면접을 위한 CS 전공지식 노트(주홍철 저) -길벗

Commit은 데이터베이스에서 트랜잭션 작업을 영구적으로 저장하는 명령입니다. 트랜잭션이 성공적으로 완료되었음을 나타내며, 이 시점 이후에는 롤백이 불가능합니다.

트랜잭션은 데이터베이스에서 하나의 작업 단위를 의미하며, ACID 특성을 만족해야 합니다. 이 특성에는 원자성, 일관성, 고립성, 지속성이 포함됩니다. 트랜잭션은 데이터의 무결성과 일관성을 보장합니다.

격리 수준은 트랜잭션 간의 동시성 제어를 정의하며, READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE 네 가지 수준이 있습니다. 높은 격리 수준일수록 데이터 일관성이 강화되지만 성능 오버헤드가 커질 수 있습니다.

• 면접을 위한 CS 전공지식 노트(주홍철 저) -길벗
•  

1정규형은 테이블의 모든 속성이 원자값만을 가져야 한다는 조건입니다. 즉, 한 칸에 여러 값이 아닌 하나의 값만 저장되도록 테이블을 구성합니다. 이를 통해 데이터 중복과 불필요한 복잡성을 줄입니다.

2정규형은 1정규형을 만족하면서, 기본 키의 부분적 종속성을 제거하는 것입니다. 즉, 기본 키의 일부에만 의존하는 속성을 별도로 분리하여 테이블을 재구성합니다.

3정규형은 2정규형을 만족하면서, 이행적 종속성을 제거하는 것입니다. 즉, 비기본 속성이 다른 비기본 속성에 의존하지 않도록 테이블을 분리하여 데이터의 일관성을 높입니다.

BCNF는 3정규형을 강화한 형태로, 모든 결정자가 후보 키가 되도록 테이블을 설계합니다. 이를 통해 복잡한 종속성을 제거하고 데이터의 무결성을 강화합니다.

반정규화는 성능 향상을 목적으로 데이터의 중복을 허용하거나 테이블을 결합하여 정규화 수준을 낮추는 것을 의미합니다. 이는 읽기 작업이 많은 환경에서 쿼리 성능을 향상시키는 데 유용합니다.

DDL(Data Definition Language)은 데이터베이스 구조를 정의하거나 변경하는 데 사용되며, CREATE, ALTER, DROP과 같은 명령어가 포함됩니다.

DML(Data Manipulation Language)은 데이터를 조회하거나 수정, 삭제, 삽입하는 데 사용되며, SELECT, INSERT, UPDATE, DELETE 등이 있습니다.

DCL(Data Control Language)은 데이터베이스 접근 권한을 제어하는 명령으로, GRANT와 REVOKE가 대표적입니다. 

DROP은 테이블 자체를 삭제하며, 구조와 데이터가 모두 제거됩니다. 삭제 후에는 복구가 불가능하며, 테이블과 관련된 인덱스 및 참조 관계도 삭제됩니다.
TRUNCATE는 테이블의 모든 데이터를 삭제하지만, 테이블 구조는 유지됩니다. 로그 기록이 간소화되므로 대량 데이터 삭제에 효율적입니다.
DELETE는 데이터를 행 단위로 삭제하며, WHERE 조건을 사용할 수 있어 특정 데이터만 삭제할 수 있습니다. DELETE는 로그 기록을 남기므로 트랜잭션을 통해 롤백이 가능합니다.

SQL Injection은 사용자가 입력한 데이터를 SQL 쿼리에 삽입하는 과정에서 악의적인 SQL 코드를 주입하여 데이터베이스를 공격하는 기법입니다. 이를 통해 데이터 유출, 변경, 삭제 등이 가능하며, 심각한 보안 위협이 됩니다.

이를 예방하기 위해, 첫째, Prepared Statement나 Parameterized Query를 사용하여 쿼리와 데이터를 분리합니다.

둘째, 입력값에 대한 유효성 검사를 철저히 수행하고, 셋째, 데이터베이스 계정을 최소 권한 원칙에 따라 설정합니다.

인덱스는 테이블의 데이터를 빠르게 조회하기 위해 사용하는 데이터 구조입니다. 책의 목차와 유사하며, 특정 열의 값을 기준으로 데이터의 위치를 빠르게 찾을 수 있습니다. 인덱스를 사용하면 SELECT와 같은 읽기 작업의 성능이 크게 향상됩니다. 그러나, INSERT, UPDATE, DELETE와 같은 쓰기 작업에는 오버헤드가 발생할 수 있습니다.

MySQL 기준으로 인덱스는 일반적으로 B-Tree 구조를 사용하여 동작합니다. B-Tree는 데이터를 균형 있게 저장하여 탐색, 삽입, 삭제 시 일정한 성능을 보장합니다. 데이터 검색 시, 루트 노드에서부터 시작해 리프 노드까지 탐색하며, 해당 키 값을 빠르게 찾습니다. 또한, 자주 사용되는 데이터에 대해 캐싱을 통해 접근 속도를 더 향상시킵니다.

클러스터링 인덱스는 테이블의 데이터가 인덱스 키 값에 따라 물리적으로 정렬되어 저장되는 방식입니다. 기본 키가 클러스터링 인덱스로 사용되는 경우가 많으며, 동일한 키 값을 가진 데이터가 인접하게 저장됩니다. 이는 범위 검색 시 높은 성능을 발휘하지만, 데이터 삽입이나 업데이트 시 정렬을 유지해야 하므로 비용이 증가할 수 있습니다.

데이터베이스는 데이터를 효율적으로 저장하고 관리하기 위해 조직화된 데이터의 집합입니다.

이는 데이터를 저장할 뿐만 아니라, 데이터에 대한 접근, 관리, 수정, 삭제를 지원하며, 여러 사용자와 애플리케이션이 데이터를 공유할 수 있도록 설계되었습니다.

주요 특징으로는 데이터의 무결성 유지, 중복 최소화, 데이터 일관성, 다중 사용자 환경에서의 동시성 제어 등이 있습니다. 이를 통해 데이터베이스는 안정성과 효율성을 제공하며, 관리 시스템(DBMS)을 통해 이러한 작업을 처리합니다.

스키마는 데이터베이스의 구조와 설계를 정의한 것으로, 데이터베이스가 어떻게 구성되어 있는지를 설명합니다.

테이블, 뷰, 인덱스, 제약 조건 등 데이터베이스 객체들의 논리적인 관계를 포함합니다.

데이터 스키마는 크게 물리적 스키마, 논리적 스키마, 그리고 외부 스키마로 나뉘며, 각각 저장 구조, 데이터 모델, 사용자 관점에서의 구조를 정의합니다.

릴레이션의 차수(Degree)는 테이블의 열(Column)의 개수를 의미하며, 테이블이 어떤 속성들을 포함하고 있는지를 나타냅니다. 카디널리티(Cardinality)는 테이블의 행(Row)의 개수를 의미하며, 데이터의 수량을 나타냅니다.

예를 들어, 고객 정보를 저장하는 테이블에 열이 5개 있고, 행이 100개 있다면 차수는 5, 카디널리티는 100이 됩니다.

키는 데이터베이스에서 레코드를 고유하게 식별하기 위해 사용되는 속성 또는 속성의 집합입니다.

기본 키(Primary Key)는 각 행을 유일하게 식별하며, 중복 값과 NULL 값을 허용하지 않습니다.

후보 키(Candidate Key)는 기본 키로 선택될 수 있는 모든 키의 집합입니다.

또한, 외래 키(Foreign Key)는 다른 테이블의 기본 키를 참조하여 테이블 간의 관계를 정의합니다.

이러한 키는 데이터베이스에서 무결성을 유지하고 데이터를 효율적으로 관리하는 데 핵심 역할을 합니다.

무결성 제약 조건은 데이터의 정확성과 일관성을 보장하기 위한 규칙입니다. 주요 제약 조건으로는 다음과 같은 것들이 있습니다.

첫째, 개체 무결성(Entity Integrity)은 기본 키가 NULL이나 중복 값을 가질 수 없도록 보장합니다.

둘째, 참조 무결성(Referential Integrity)은 외래 키가 참조하는 테이블의 값과 일치해야 함을 보장합니다.

셋째, 도메인 무결성(Domain Integrity)은 속성의 값이 정의된 데이터 타입과 범위 내에 있어야 함을 보장합니다.

이러한 제약 조건은 데이터베이스의 신뢰성과 안정성을 유지하는 데 필수적입니다.

데이터베이스는 일정한 규칙, 규약을 통해 구조화되어 저장되어 있는 데이터의 모음입니다. 이를 관리하는 시스템을 DBMS라고 하며 각 DBMS마다 쿼리 언어를 통해 삽입, 삭제, 수정, 조회를 수행할 수 있습니다.

중첩 루프 조인은 중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법이며 랜덤 접근에 대한 비용이 많이 증가하므로 대용량의 테이블에서는 사용하지 않습니다.

인덱스는 두번의 탐색이 이루어집니다. 인덱스 리스트와 컬렉션으로 탐색이 진행되기 때문에 읽기 관련 비용이 더 들게 됩니다. 또 데이터 삽입 시나 수정 시에 인덱스가 수정되어야하기 때문에 모든 필드에 대해서 인덱스를 지정하는 것은 오히려 성능 저하를 야기합니다. 따라서 인덱스는 카디널리티가 높은 값으로 인덱스를 설정해야합니다.

데이터베이스 기본

데이터베이스는 일정한 규칙, 혹은 규약을 통해 구조화되어 저장되어 있는 데이터 모음.

데이터베이스를 제어 및 관리하는 통합 시스템을 DBMS라고 하며데이터베이스 안에 있는 데이터들은 특정 DBMS마다 특정 쿼리 언어를 통해 CRUD 가능.

실시간 접근과 동시 공유가 가능.

엔티티

• 여러개의 속성을 가진 명사를 의미.
• 서비스의 요구사항에 맞춰 속성이 정해짐.

약한 엔티티와 강한 엔티티

• 혼자서 존재하지 못하면 약한 엔티티 그 반대면 강한 엔티티

릴레이션

• 데이터베이스에서 정보를 구분하여 저장하는 기본 단위.
• 엔티티에 관한 데이터를 릴레이션 하나에 담아서 관리.
• 관계형 데이터베이스에서는 테이블이라고 하며 NoSQL에서는 컬렉션이라고 함.

테이블과 컬렉션

• RDBMS의 구조: 레코드 - 테이블 - 데이터베이스로 이루어져있음
• NoSQL의 구조: 도큐먼트 - 컬렉션 - 데이터베이스로 이루어져있음.

속성

• 릴레이션에서 관리하는 구체적이고 고유한 이름을 갖는 정보.
• 서비스의 요구사항을 기반으로 관리해야할 필요가 있는 속성들만 엔티티의 속성

도메인

• 릴레이션에 포함된 각각의 속성들이 가질 수 있는 값의 집합.(속성들의 집합)
• 성별이라는 속성에 [남, 여]라는 집합이 도메인

필드와 레코드

• 필드는 속성을 표현한 값.
• 레코드는 테이블에서의 하나의 행. 튜플이라고 하기도 함.

필드 타입

• 타입은 DBMS마다 다름. 여기서는 MySQL 기준
• 숫자 타입
  • TINYINT, SMALLINT, MEDIUMINT, INT, BIGINT 가 존재
• 날짜 타입
  • DATE
    • 날짜 부분만 존재
    • 3바이트용량
  • DATETIME
    • 날짜 + 시간
    • 8바이트 용량
  • TIMESTAMP
    • DATETIME보다 조금 더 큰 범위 지원
    • 4바이트 용량
• 문자 타입
  • CAHR + VARCHAR
    • 그 안에 수를 입력해서 몇자까지 입력할 것인지 지정. CHAR(30)
    • CHAR
      • 고정 길이 문자열. 0 ~ 255 값.
      • CHAR(100)이라고 하고 10글자 지정하면 100글자 저장
    • VARCHAR
      • 가변 길이 문자열. 0 ~ 65,535 사이 값으로 지정
      • 입력된 데이터에 따라 용량을 가변시켜 저장.
      • 길이 저장용 1바이트가 필요.
  • TEXT + BLOB
    • TEXT
      • 큰 문자열 저장에 쓰이며 게시판의 본문을 저장할 때 쓰임
    • BLOB
      • 이미지, 동영상 등 큰 데이터 저장에 사용.
      • 보통 이미지나 동영상의 경로로 사용함.
  • ENUM과 SET
    • ENUM
      • ENUM 형태로 쓰이며, 하나만 선택하는 단일 선택만 가능하고 잘못된 값을 삽입하면 빈 문자열이 대신 삽입.
      • 0, 1등으로 매핑되어 메모리를 적게 사용하는 이점이 있음.
    • SET
      • ENUM과 비슷하지만 여러개의 데이터를 선택할 수 있고 비트 단위의 연산을 할 수 있으며 최대 64개의 요소를 집어넣을 수 있다는 점.

관계

여러개의 테이블이 존재하고 각 테이블 간의 연관 관계가 정의 되어 있음.

1:1 관계

• 두개의 테이블로 나누어 테이블의 구조를 이해하기 쉽게 만들어 줌.

1:N 관계

• 한 유저당 여러개의 상품을 장바구니에 넣을 때

N:M 관계

• 여러명의 학생이 여러개의 강의를 들을 때
• 중간에 테이블을 두어 1:N, 1:M으로 분리함.

키

테이블 자체의 인덱스를 위해 설정된 장치.

기본키

• 유일성과 최소성을 만족하는 키
• 자연키 또는 인조키중에 골라 설정
• 자연키
  • 속성의 값으로 들어가 있는 값.
• 인조키
  • 인공적으로 키를 만드는 것.

외래키

• 다른 테이블의 기본키를 그대로 참조하는 값.
• 개체와의 관계를 식별하는데 사용
• 중복 가능

후보키

• 기본키가 될 수 있는 후보들
• 유일성과 최소성을 동시에 만족하는 키

슈퍼키

• 각 레코드를 유일하게 식별할 수 있는 유일성을 갖춘 키

대체키

• 후보키가 두개 이상일 경우 기본키를 지정하고 나머지 키를 의미

ERD와 정규화 과정

릴레이션을 정의하고 릴레이션 간의 관계를 정의한 것.

ERD 중요성

• 시스템의 요구사항을 기반으로 작성되며 ERD를 기반으로 데이터베이스 구축.
• 구축한 이후에도 디버깅 또는 비즈니스 프로세스 재설계가 필요한 경우 설계도 역할들 담당.

정규화 과정

• 릴레이션 간의 잘못된 종속 관계로 인해 데이터베이스 이상 현상이 일어나 이를 해결하거나 저장 공간을 효율적으로 사용하기 위해 릴레이션을 여러개로 분리하는 과정
• 이상현상이란 데이터베이스의 무결성 등과 같은 현상

정규형 원칙

• 자료의 중복성은 감소해야하며, 독립적인 관계는 별개의 릴레이션으로 표현해야함.

제 1 정규형

• 릴레이션의 모든 도메인은 더이상 분해될 수 없는 원자 값으로만 구성되어 있어야 함.
• 한개의 기본키에 두개 이상의 값을 가지는 반복 집합이 있으면 안됨.

제 2 정규형

• 제 1정규형을 포함하며 부분함수 종속성을 제거한 형태
• 기본키가 아닌 모든 속성이 기본키에 완전 함수 종속적인 것을 의미.
• 릴레이션 분해. 무손실 분해 필요

제 3정규형

• 제 2정규형이며 기본키가 아닌 모든 속성은 이행적 함수 종속을 만족하지 않는 상태
• 이행적 함수 종속: A → B이고 B → C이면 A → C인 것.

보이스/코드 정규형

• 제 3정규형이며 결정자가 후보키가 아닌 함수 종속 관계를 제거하여 모든 결정자가 후보키인 상태.

정규화 과정은 테이블 조인이 필수적이므로 더 느려지기도 함. 비정규화 과정을 거치기도 함.

트랜잭션과 무결성

트랜잭션

• 하나의 논리적인 기능을 수행하기 위한 작업의 단위.
• 데이터베이스에 접근하는 방법 ⇒ 쿼리
• 여러개의 쿼리를 하나로 묶는 단위 ⇒ 트랜잭션

원자성

• all or nothing
• 트랜잭션과 관련된 일이 모두 수행되었거나 되지 않았거나를 보장하는 특징.
• 트랜잭션을 커밋했는데, 문제가 발생하여 롤백하는 경우 그 이후에 모두 수행되지 않음을 보장하는 것.
• 트랜잭션 단위로 여러 로직을 묶을 때 외부 API를 호출하는 것이 있으면 안됨. ⇒ 롤백이 일어났을 때 어떻게 대처해야할지 해결방법이 필요함

💡

커밋과 롤백

커밋은 여러 쿼리가 썽공적으로 처리되었다고 확정하는 명령어. 트랜잭션 단위로 수행되며 변경된 내용이 모두 영구적으로 저장되는 것.

에러나 이슈때문에 트랜잭션 이전으로 돌리기 위해서는 롤백. 롤백이란 트랜잭션으로 처리한 하나의 묶음 과정을 일어나기 전으로 돌리는 일.

데이터의 무결성이 보장. 데이터 변경 전에 변경사항을 쉽게 확인할 수 있고 해당 작업을 그룹화 할 수 있음.

💡
트랜잭션 전파
트랜잭션을 수행할 때 커넥션 단위로 수행하기 때문에 커넥션 객체를 넘겨서 수행해야 함. 여러 트랜잭션 관련 메소드 호출을 하나의 트랜잭션에 묶이도록 하는 것을 트랜잭션 전파라고 함.

일관성

• 허용된 방식으로만 데이터를 변경해야하는 것을 의미.
• 조건과 규칙에 따라 유효함을 가져야함.

격리성

• 트랜잭션 수행 시 다른 트랜잭션이 서로 끼어들지 못하는 것을 의미.
• 병렬 트랜잭션은 서로 격리되어 마치 순차적으로 실행되는 것처럼 작동해야하고
  데이터베이스는 여러 사용자가 같은 데이터에 접근할 수 있어야 함.
• 여러개의 격리 수준으로 나누어 격리성을 보장
  • 위로 갈수록 동시성은 강해지고 격리성은 약해짐.

💡 부작용
팬텀 리드
한 트랜잭션 내에서 동일한 쿼리를 보냈을 때 해당 조회 결과가 다른 경우 ⇒ 조회 갯수가 다른 경우

반복 가능하지 않은 조회
같은 행에 두번 이상 조회가 발생했는데 그 값이 다른 경우 ⇒ 값이 다른 경우

더티 리드
반복가능하지 않은 조회와 유사하며 한 트랜잭션이 실행중 일 때 다른 트랜잭션이 수정되었지만 아직 커밋되지 않은 행의 데이터를 읽을 수 있을 때 발생

• SERIALIZABLE
  • 트랜잭션을 순차적으로 진행 시키는 것.
  • 여러 트랜잭션이 동시에 같은 행에 접근할 수 없음.
  • 해당 행에 대해 격리 시키고 다른 트랜잭션이 이 행에 작업을 하기 위해서는 기다려야함 ⇒ 데드락의 가능성
  • 가장 성능이 떨어짐
• REPEATABLE_READ
  • 팬텀 리드 발생 가능
  • 하나의 트랜잭션이 수정한 해을 다른 트랜잭션이 수정할 수 없도록 막아주지만 추가하는 것은 막지 않는 것.
  • MySQL8.0의 innoDB의 기본 값.
• READ_COMMITTED
  • 팬텀 리드, 반복 가능하지 않은 조회 발생가능
  • 가장 많이 사용되는 격리 수준, 오라클의 기본값.
  • 다른 트랜잭션이 커밋하지 않은 정보는 읽을 수 없음.
  • 어떤 트랜잭션이 접근한 행을 다른 트랜잭션이 수정할 수 있음.
• READ_UNCOMMITTED
  • 팬텀 리드, 반복 가능하지 않은 조회 발생, 더티 리드 발생 가능
  • 하나의 트랜잭션이 커밋되기 전에 다른 트랜잭션에 노출되는 문제가 있지만 가장 빠름
  • 데이터 무결성을 위해 되도록 사용하지 않는 것이 좋음.

지속성

• 성공적으로 수행된 트랜잭션은 영원히 반영되어야 하는 것을 의미.
• 회복 기능이 필요함.
• 데이터베이스는 이를 위해서 체크섬, 저널링, 롤백등의 기능을 제공

무결성

• 데이터의 정확성, 일관성, 유효성을 유지하는 것.
• 개체 무결성
  • 기본 키로 선택된 필드는 빈 값을 허용하지 않습니다
• 참조 무결성
  • 서로 참조 관계에 있는 두 테이블의 데이터는 항상 일관된 값을 유지해야합니다.
• 고유 무결성
  • 특정 속성에 대해 고유한 값을 가지도록 조건이 주어진 경우 해당 값은 항상 고유한 값을 가져야합니다.
• NULL 무결성
  • 특정 속성 값에 NULL이 올 수 없다는 조건이 주어진 경우 그 속성 값은 NULL이 될 수 없다는 제약 조건

데이터베이스의 종류

관계형 데이터베이스

• 행과 열을 가지는 표 형식의 데이터를 저장하는 데이터베이스
• SQL 언어 사용.
• MySQL
  • 대부분의 운영체제와 호환되며 가장 많이 사용
  • C, C++ 기반
  • 인덱스 압축 기술, B-트리 기반, 스레드 기반의 메모리 할당, 빠른 조인, 64개의 인덱스 제공
  • 롤백, 커밋, 이중 암호 지원 보안 등의 기능 제공
  • 스토리지 엔진
    • 모듈식 아키텍처로 쉽게 스토리지 엔진을 바꿀 수 있으며 데이터 웨어 하우징, 트랜잭션 처리, 고가용성 처리에 강점.
    • 스토리지 엔진 위에는 커넥터 API 및 서비스 계층을 통해 MySQL 데이터베이스와 상호 작용
  • 쿼리 캐시
    • 입력된 쿼리 문에 대해 전체 결과 집합을 저장
    • 동일한 쿼리 시 캐시의 출력만 표시 ⇒ 구문 분석 최적화 건너 뜀
• PostgreSQL
  • 디스크 조각이 차지하는 영역을 회수할 수 있는 장치.
  • JSON을 이용하여 데이터에 접근 가능
  • 복구 기능, 로깅, 접근 제어, 중첩된 트랜잭션, 백업 가능.

NoSQL 데이터베이스

• MongoDB
  • JSON을 통해 데이터에 접근하고 BinayJSON 형태로 데이터가 저장되어 와이어드타이거 엔진이 기본 스토리지 엔진으로 장착된 키-값 데이터 모델에서 확장된 도큐먼트 기반의 데이터베이스
  • 확장성이 뛰어나며 빅데이터를 저장할 때 성능이 좋고 고 가용성과 샤딩, 레플리카셋을 지원.
  • 스키마를 정해놓지 않고 데이터를 삽입할 수 있기 때문에 다양한 도메인의 데이터베이스를 기반으로 분석하거나 로깅등을 구현할 때 강점.
  • 도뮤먼트를 생성할 때마다 다른 컬렉션에서 중복된 값을 지니기 힘든 유니크한 값인 ObjectID 생성
    • 유닉스 기반 타임스탬프(4byte) 랜덤 값(5 바이트), 카운터(3바이트)로 이루어져있음
• Redis
  • 인메모리 데이터베이스이자 키-값 데이터 모델 기반의 데이터베이스
  • 기본 데이터 타입은 문자열. 512MB까지 저장 가능. set, hash 지원
  • pub/sub 기능을 통한 채팅 시스템, 캐싱 계층, 정렬 셋을 시용해 순위표 서비스에 사용 가능.

인덱스

인덱스의 필요성

• 데이터를 빠르게 찾을 수 있는 하나의 장치.

B-트리

• 인덱스는 보통 B-트리 기반
• 루트 노드, 리프 노드, 리프노드와 루트 노드 사이의 브랜치 노드
• 트리의 깊이가 리프 노드 수에 비해 느리게 성장.

인덱스 만드는 방법

MySQL

• 클러스터형 인덱스
  • 테이블당 하나.
  • primary key 옵션으로 만들면 기본적으로 생성되고 기본키를 만들지 않고 unique not null 옵션을 통해서도 생성 가능.
• 세컨더리 인덱스
  • create index 명령어로 세컨더리 인덱스 생성 가능.
  • 하나의 인덱스가 필요할 때는 클러스터형 인덱스만 있는 것이 좋음

MongoDB

• 도큐먼트를 생성하면 자동적으로 ObjectID 형성.
• 해당 키가 기본키로 설정.
• 복합 인덱스로 설정 가능

인덱스 최적화 기법

인덱스는 비용

• 인덱스는 두번 탐색해야 함.
  • 인덱스 리스트 + 컬렉션 수능로 탐색.
  • 관련 읽기 비용
• 컬렉션이 수정되었을 때 인덱스도 수정되어야 함.

항상 테스팅해라

• 인덱스 최적화는 서비스마다 다름.
• explain() 함수를 통해 테스팅하며 걸리는 시간 최소화.

복합 인덱스는 같음, 정렬, 다중 값, 카디널리티 순

• 어떠한 값과 같음을 비교하는 ==나 equal이 있다면 제일 먼저 인덱스로 설정
• 정렬에 쓰는 필드라면 다음 인덱스
• 다중 값을 출력해야 하는 필드면 나중 인덱스
• 유니크한 값의 정도 = 카디널리티. 카디널리티가 높은 순으로 인덱스를 생성.

조인의 종류

하나의 테이블이 아닌 두개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것

내부 조인

• 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만을 표기

왼쪽 조인

• 왼쪽 테이블의 모든 행이 결과 테이블에 표기

오른쪽 조인

• 오른쪽 테이블의 모든 행이 결과 테이블에 표기

합집합 조인

• 두개의 테이블을 기반으로 조인 조건에 만족하지 않는 행까지 모두 표기

조인 원리

중첩 루프 조인

• Nested Loop Join은 중첩 for문과 같은 원리로 조건에 맞는 조인
• 랜덤 접근에 대한 비용이 많이 증가하므로 대용량 테이블에서는 사용하지 않음

정렬 병합 조인

• 각 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 이후에 조인 작업을 수행하는 조인.
• 적절한 인덱스가 없고 대용량의 테이블을 조인하고 조인 조건으로 < , >등 범위 비교 연산자가 있을 때 사용

해시 조인

• 해시 테이블을 기반으로 조인하는 방법.
• 동등 조인에서만 사용 가능.
• MySQL 방법

• 면접을 위한 CS 전공지식 노트(주홍철 저) -길벗

하나의 프로세스에 대해 멀티 프로세스나 멀티 스레드 기법을 도입할 수 있고 각 메모리를 공유하는 멀티 스레드와 같은 경우에는 동기화가 중요한 포인트입니다.

공유되는 데이터의 일관성을 보장하기 위해 lock이나 세마포어 등을 사용합니다.

lock은 하드웨어 기반 해결책으로 동시에 공유하는 자원의 접근을 막기 위해 critical section에 진입하는 프로세스가 있을 시 lock을 걸고 다른 프로세스의 접근을 막는 방법입니다.

세마포어는 세마포어 변수를 통해 lock이 걸렸는지 아닌지 확인할 수 있습니다. 

컨택스트 스위칭은 하나의 task가 끝날때까지 기다리지 않고 동시에 여러 task를 번갈아가며 실행하는 방법입니다.

인터럽트가 발생하면 현재 프로세스의 상태를 PCB에 저장하고 새로운 프로세스의 상태를 레지스터에 저장하여 잦은 컨텍스트 스위칭은 성능 저하를 야기합니다.

메모리 관리 전략은 페이징과 세그멘테이션이 존재합니다.

페이징은 프로세스를 일정 크기인 페이지로 잘라서 메모리에 적재하는 방식을 의미합니다. 하지만 이는 내부 단편화와 외부 단편화가 발생할 수 있습니다. 

세그멘테이션은 프로세스를 논리적 내용 단위인 세그먼트로 잘라 메모리에 적재하는 방법을 의미합니다. 이는 세그먼트 테이블을 통해 연속된 메모리 공간에 위치하도록 보이는 기법입니다. 하지만 이도 단점이 있는데 외부 단편화가 발생할 수 있습니다.

가상 메모리는 운영체제가 물리적 메모리와 독립된 가상 주소 공간을 프로세스에 제공하는 기술입니다. 이를 통해 프로그램은 실제 물리적 메모리 크기에 구애받지 않고 실행될 수 있습니다.

운영체제는 프로세스마다 별도의 가상 메모리를 제공하며, 이를 물리적 메모리와 매핑하여 관리합니다. 가상 주소를 물리적 주소로 변환하는 작업은 MMU(Memory Management Unit)라는 하드웨어 장치가 담당합니다.

이를 통해 각 프로세스는 실제 물리적 메모리의 제약 없이 동작하며, 물리적 메모리와 가상 메모리는 페이징(Paging) 기법을 통해 매핑됩니다.

요구 페이징은 가상 메모리에서 핵심적인 개념 중 하나입니다. 요구 페이징은 프로그램 실행 시 필요한 페이지만 메모리에 적재하는 방식으로, 처음부터 모든 페이지를 메모리에 올리지 않습니다.

캐시 지역성은 프로그램이 메모리에 접근하는 패턴에서 시간적 또는 공간적으로 반복적으로 사용되는 경향을 의미합니다. 이 특성을 사용하면 프로그램의 성능을 크게 향상시킬 수 잇습니다.

시간 지역성은 최근에 접근한 데이터는 다시 참조할 가능성이 높은 것을 의미합니다.

공간 지역성은 메모리 접근이 특정 주소 주변의 데이터에 집중되는 경향을 의미합니다.