By_Me

균형 이진 트리

- 리프 노드들의 레벨 차이가 최대 1레벨까지만 나는 트리, 검색할 때 O(logN) 시간 복잡도 유지(균형이 깨지면 별도 로직을 통해 다시 균형 유지)

- B-tree 처음 생성 당시에는 균형 트리이지만, 테이블 갱신(INSERT, UPDATE, DELETE)의 반복을 통해 서서히 균형이 꺠지고, 성능도 약화된다.

- 어느 정도 자동으로 균형을 회복하는 기능이 있지만, 갱신 빈도가 높은 테이블에 작성되는 인덱스 같은 경우 인덱스 재구성을 해서 트리의 균형을 되찾는 작업이 필요하다.

- AVL 트리, 레드 블랙 트리, B-tree, B+tree 등에서 사용

B-tree

- 데어베이스 인덱스, 파일 시스템, 파일 시스템 캐시 등에서 널리 사용되는 트리 자료구조

- 이진 트리의 확장, 하나의 노트에 자식 2개 이상

- 내부 노드에 key와 data를 담을 수 있다.

B-tree 조건

1. 모든 노드들은 최대 m개의 자식을 가질 수 있다.
2. k개의 자식을 가진 리프가 아닌 노드는 k-1개의 키를 가지고 있다.
3. 모든 내부 노드는 최소 [m/2]개의 자식을 가져야 한다.
4. 모든 리프 노드들은 같은 레벨에 있어야 한다.
5. 리프가 아닌 모든 노드들은 최소 2개 이상의 자식을 가져야 한다.

풀 스캔이 테이블 크키에 비례하는 형태로 실행 시간이 늘어가는 데에 비해 인덱스를 사용할 경우 실행 시간의 저하는 보통 원만한 곡선을 그리게 된다.

B+tree

- B-tree를 개선

- 모든 리프 노드들은 Linked 리스트 형태로 이루어진다.

- 실제 데이터는 리프 노드에만 저장, 내부 노드들은 단지 키만 가지고 있고 올바른 리프 노드로 연결해주는 라우팅 기능을 한다.

- B+tree는 중복 키를 가진다. -> 내부 노드들이 데이터를 가지고 있기 때문에 리프 노드들이 키와 데이터를 모두 가지고 있음.

B+tree의 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
   하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
2. 풀 스캔시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 full scan시 한 번의 선형탐색만으로 빠르게 확인할 수 있다.
   (B-tree는 모드 노드를 탐색해야 한다)

B+tree의 단점

1. B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 리프 노드까지 내려가 봐야 한다.

활용사례

ex) InnoDB에서 사용된 B+tree

- 같은 레벨의 노드끼리는 Double LinkedList 사용

- 자식 노드로는 Single Linked List로 연결

- key의 범위마다 찾아가야할 페이지 넘버(포인터)가 있는데, 해당 페이지 넘버를 통해 곧바로 다음 노드로 넘어감.

- 리프 노드에서 디스크에 존재하는 데이터의 주소값을 구할 수 있고, Linked List를 통해 탐색도 가능

B+Tree가 DB 인덱스에 사용되었을 때, 더 좋은 점

1. 한정된 메모리 안에 더 많은 key들을 수용할 수 있다. -> 동일한 데이터 개수라면, 트리의 높이는 더 낮아진다.
2. cache hit를 높일 수 있을 뿐만 아니라, 범위 검색이나 범위 쿼리에도 큰 강점을 갖고 있으며, 상대적으로 굉장히 느린 secondary storage에 대한 접근 횟수가 현저히 줄어든다.
3. 테이블 Full-Scan시, 모든 노드를 탐색해야하는 B-tree에 비해, B+tree는 리프노드에서 선형 탐색만으로 탐색이 가능하다.

참고: https://zorba91.tistory.com/293

참고: https://github.com/wjdansrl7/2024_CS_STUDY/blob/master/DB/B-tree%2C%20B%2Btree.md

데이터베이스 설계시 고려사항

개념적 설계(정보 모델링, 개념화)

• 스키마 모델링과 트랜잭션 모델링을 병행하여 수행한다.
• 요구 분석 단계에서 나온 결과(요구 조건 명세)를 DBMS에 독립적인 E-R 다이어그램(개체 관계도)으로 작성한다.
• DBMS에 독립적인 개념 스키마를 설계한다.

논리적 설계(데이터 모델링)

• 특정 DBMS가 지원하는 논리적 자료 구조로 변환시키는 과정
• 개념 스키마를 평가 및 정제하고 특정 DBMS에 종속적인 논리적 스키마를 설계하는 단계
• 트랜잭션의 인터페이스를 설계
• 관계형 데이터베이스라면 테이블을 설계하는 단계

물리적 설계(데이터 구조화)

• 논리적 구조로 표현된 데이터를 디스크 등의 물리적 저장장치에 저장할 수 있는 물리적 구조의 데이터로 변환하는 과정
• 트랜잭션을 작성한다.
• 반응시간(트랜잭션 수행을 요구한 시점부터 처리 결과를 얻을 때까지의 경과시간), 공간 활용도, 트랜잭션 처리량(단위 시간 동안 데이터베이스 시스템에 의해 처리될 수 있는 트랜잭션의 평균 개수)을 선택적으로 고려할 수 있다.

데이터베이스 설계 순서

관계 데이터베이스의 Relation 구조

- 릴레이션은 데이터들을 표(Table)의 형태로 표현한 것으로, 구조를 나타내는 릴레이션 스키마와 실제 값들인 릴레이션 인스턴스로 구성된다.

키의 개념 및 종류

1. 후보키(Candidate Key)
   - 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별하기 위해 사용하느 속성들의 부분집합
   - 모든 릴레이션은 반드시 하나 이상의 후보키를 가져야 함.
   - 릴레이션에 있는 모든 튜플에 대해서 유일성과 최소성을 만족시켜야 함.
   
   
2. 기본키(Primary Key)
   - 후보키 중에서 선택한 주키
   - 한 릴레이션에서 특정 튜플을 유일하게 구별할 수 있는 속성
   - Null 값을 가질 수 없음.
   - 기본키로 정의된 속성에는 값이 중복되어 저장될 수 없음.
   
   
3. 대체키(Alternate Key)
   - 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키들을 말함.
   - 보조키라고도 부름.
   
   
4. 슈퍼키(Super Key)
   - 슈퍼키로 구성된 속성의 집합과 동일한 값은 나타나지 않는다. -> 유일성은 만족 but, 최소성은 만족X
   
   
5. 외래키(Foreign Key)
   - 관계를 맺고 있는 릴레이션 R1, R2에서 릴레이션 R1이 참조하고 있는 릴레이션 R2의 기본키와 같은 R1 릴레이션의 속성
   - 외래키는 참조되는 릴레이션의 기본키와 대응되어 릴레이션 간에 참조 관계를 표현하는데 중요한 도구임.
   - 외래키로 지정되면 참조 테이블의 기본키에 없는 값은 입력할 수 없음.
   
   

무결성(Integrity)

1. 개체 무결성
   - 릴레이션에서 기본키를 구성하는 속성은 널(NULL) 값이나 중복값을 가질 수 없음.
2. 참조 무결성
   - 외래키 값은 NULL이거나 참조 릴레이션의 기본키 값과 동일해야 함.
3. 도메인 무결성
   - 특정 속성의 값이 정의된 도메인에 속한 값이어야 한다는 규정

관계대수

• 관계형 데이터베이스에서 원하는 정보와 그 정보를 어떻게 유도하는가를 기술하는 절차적인 언어
• 릴레이션을 처리하기 위해 연산자와 연산규칙을 제공하는 언어
• 피연산자가 릴레이션, 결과도 릴레이션
• 순수 관계 연산자 : Select(시그마), Project(파이), Join(나비), Division
• 일반 집합 연산자 : UNION(합집합), INTERSECTION(교집합), DIFFERENCE(차집합), Cartesian Product(교차곱)

순수 관계 연산자

• Select
• Project
  - 주어진 릴레이션에서 속성 List에 제시된 Attribute 만을 추출하는 연산
  - 릴레이션의 열에서 해당하는 Attribute를 추출하는 것이므로 수직 연산자라고도 함.
• Join
• Division

관계해석

• 관계해석은 원하는 정보가 무엇이라는 것만 정의하는 비절차적 특성을 지닌다.
• 튜플 관계해석과 도메인 관게해석이 있다.
• 관계해석과 관계대수는 관계 데이터베이스를 처리하는 기능과 능력 면에서 동등하다.
• 질의어로 표현한다.

정규화

1. 정규화의 개요
   잘못 설계된 관계형 스키마를 더 작은 속성의 세트로 쪼개어 바람직한 스키마로 만들어 가는 과정
2. 정규화의 목적
   - 데이터 구조의 안정성을 최대화
   - 어떠한 릴레이션이라도 데이터베이스 내에서 표현 가능하게 만든다.
   - 효과적인 검색 알고리즘을 생성
   - 중복을 배제하여 삽입, 삭제, 갱신 이상의 발생을 방지
   - 데이터 삽입 시 릴레이션을 재구성할 필요성을 줄인다.
   
   
3. 정규화 과정

Anormaly(이상)의 개념 및 종류

- 정규화를 거치지 않은 데이터베이스 내에 데이터들이 불필요하게 중복되어 릴레이션 조작 시 발생하는 예기치 못한 곤란한 현상
- 삽입, 삭제, 갱신 이상

정규화 과정

1. 함수적 종속 관계
   ex) <수강> 릴레이션 (학번, 이름, 과목명) -> '학번'이 결정되면, '과목명'에 상관없이 '학번'에 항상 같은 이름이 대응된다.
   -> 이럴 경우, '이름'을 '학번'에 함수 종속적이라고 하며, '학번' -> '이름' 과 같이 표기한다.
2. 이행적 종속 관계
   - A -> B이고 B -> C일 때, A -> C를 만족하는 관계

SQL의 분류

1. DDL(데이터 정의어)
   - SCHEMA, DOMAIN, TABLE, VIEW, INDEX 를 정의하거나 변경 또는 삭제할 때 사용하는 언어
   - CREATE, ALTER, DROP
2. DML(데이터 조작어)
   - 질의어를 통하여 저장된 데이터를 실질적으로 처리하는데 이용한다.
   - SELECT, INSERT, DELETE, UPDATE
3. DCL(데이터 제어어)
   - 데이터의 보안, 무결성, 데이터 회복, 병행수행 제어 등을 정의하는 데 사용하는 언어
   - COMMIT, ROLLBACK, GRANT, REVOKE

뷰(View)

- 사용자에게 접근이 허용된 자료만을 제한적으로 보여주기 위해 하나 이상의 기본 테이블로부터 유도된 가상 테이블

- 저장장치 내에 물리적으로 존재하지 않지만, 사용자에게 있는 것처럼 간주

- 데이터 보정작업, 처리고정 시험 등 임시적인 작업을 위한 용도
- 기본 테이블과 같은 형태의 구조를 가지며, 조작도 기본 테이블과 거의 같다.
- 가상 테이블이기 때문에, 물리적으로 구현되어 있지 않음.
- 필요한 데이터만 뷰로 정의해서 처리할 수 있기 때문에 관리가 용이하고, 명령문이 간단해진다.
- 조인문의 사용을 최소화, 뷰를 통해서만 데이터에 접근할 수 있기에 뷰에 나타나지 않은 데이터를 안전하게 보호할 수 있음
- 기본 테이블의 기본키를 포함한 속성 집합으로 뷰를 구성해야만 삽입, 삭제, 갱신 연산이 가능하다.
- 정의된 뷰는 다른 뷰의 정의에 기초가 될 수 있다.
- 하나의 뷰를 삭제하면 그 뷰를 기초로 정의된 다른 뷰도 자동으로 삭제된다.

1. 뷰의 장점
   - 논리적 데이터 독립성을 제공한다
   - 동일 데이터에 대해 동시에 여러 사용자의 상이한 응용이나 요구를 지원해준다.
   - 사용자의 데이터 관리를 간단하게 해준다.
   - 접근 제어를 통한 자동 보안이 된다.
   
   
2. 뷰의 단점
   - 독립적인 인덱스를 가질 수 없다.
   - 뷰의 정의를 변경할 수 없다.
   - 뷰로 구성된 내용에 대한 삽입, 삭제, 갱신 연산에 제약이 따른다.
3. 뷰 정의문
   CREATE VIEW 뷰이름[속성이름[.속성이름])]
   AS SELECT문;
4. 뷰 삭제문
   DROP VIEW 뷰이름 {RESTRICT | CASCADE}
   RESTRICT | CASCADE
   RESTRICT : 뷰를 다른 곳에서 참조하고 있으면 삭제가 취소됨.
   
   

시스템 카탈로그

• 시스템 그 자체에 관련이 있는 스키마 및 다양한 객체에 관한 정보를 포함하는 시스템 데이터베이스
• 카탈로그들이 생성되면 자료 사전(Data Dictionary)에 저장되기 때문에 좁은 의미로는 카탈로그를 자료 사전이라고도 한다.
• 카탈로그에 저장된 정보를 메타 데이터라고 한다.
• 카탈로그 자체도 시스템 테이블로 구성되어 있어 일반 이용자도 SQL을 이용하여 내용을 검색해 볼 수 있다.
• INSERT, DELETE, UPDATE문으로 갱신하는 것은 허용하지 않는다.
• DBMS가 스스로 생성하고 유지한다.
• 카탈로그는 사용자가 SQL문을 실행시켜 기본 테이블, 뷰, 인덱스 등에 변화를 주면 시스템이 자동으로 갱신된다.

트랜잭션

• 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들을 의미
• 데이터베이스 시스템에서 복구 및 병행 수행 시 처리되는 작업의 논리적 단위
• 하나의 트랜잭션은 Commit되거나 Rollback 된다.
• 트랜잭션은 일반적으로 회복의 단위가 된다.

트랜잭션의 특성

1. 원자성: 트랜잭션의 연산은 데이터베이스에 모두 반영되든지 아니면 전혀 반영되지 않아야 함.
2. 일관성: 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환함.
3. 독립성, 격리성: 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행중에 다른 트랜잭션의 연산이 끼어들 수 없음.
4. 영속성, 지속성: 성공적으로 완료된 트랜잭션의 결과는 영구적으로 반영되어야 함.

회복(Recovery)

• 회복은 트랜잭션들의 처리를 수행하는 도중 장애가 발생하여 데이터베이스가 손상되었을 때 손상도기 이전의 정상 상태로 복구시키는 작업
• 장애의 유형
  • 트랜잭션 장애: 입력 데이터 오류, 불명확한 데이터, 시스템 자원 요구의 과다 등 트랜잭션 내부의 비정상적인 상황으로 인하여 프로그램 실행이 중지되는 현상
  • 시스템 장애: 데이터베이스에 손상을 입히지는 않으나 하드에워 오동작, 소프트웨어의 손상, 교착 상태 등에 의해 모든 트랜잭션의 연속적인 수행에 장애를 주는 현상
  • 미디어 장애: 데이터베이스의 일부 또는 전부가 물리적으로 손상된 상태
• 회복 관리기(Recovery Management)
  • DBMS의 구성 요소
  • 메모리 덤프, 로그를 이용하여 수행
  • 트랜잭션 실행이 성공적으로 완료되지 못하면 트랜잭션이 데이터베이스에 만들었던 모든 변화를 취소시키고 트랜잭션 수행 이전의 원래 상태로 복구하는 역할을 담당
• 회복 기법의 종류
  • 연기 갱신 기법
  • 즉각 갱신 기법
  • 그림자 페이지 대체 기법
  • 검사점 기법

병행 제어

• 동시에 여러 개의 트랜잭션을 병행 수행시킬 때, 동시에 실행되는 트랜잭션들이 데이터베이스의 일관성을 파괴하지 않도록 트랜잭션 간의 상호작용을 제어하는 것

병행 제어의 문제점

1. 갱신 분실: 2개 이상의 트랜잭션이 같은 자료를 공유하여 갱신할 때, 갱신 결과의 일부가 없어지는 현상
2. 비완료 의존성: 하나의 트랜잭션 수행이 실패한 후 회복되기 전에 다른 트랜잭션이 실패한 갱신 결과를 참조하는 현상
3. 모순성: 두 개의 트랜잭션이 병행 수행될 때, 원치 않는 자료를 이용함으로써 발생하는 문제
4. 연쇄 복귀: 병행 수행되던 트랜잭션들 중 어느 하나에 문제가 생겨 Rollback하는 경우 다른 트랜잭션도 함께 Rollback되는 현상

병행 제어의 목적

• 데이터베이스의 공유를 최대화
• 시스템의 활용도를 최대화
• 데이터베이스의 일관성을 유지
• 사용자에 대한 응답 시간을 최소화

로킹(Lock)

- 주요 데이터의 액세스를 상호 배타적으로 하는 것

- 트랜잭션들이 어떤 로킹 단위를 액세스하기 전에 Lock을 요청해서 Lock이 허락되어야 만 그 로킹 단위를 액세스할 수 있도록 하는 기법

로킹 단위

- 병행 제어에서 한꺼번에 로킹할 수 있는 데이터 단위

- 데이터베이스, 파일, 레코드, 필드 등은 로킹 단위가 될 수 있다.

- 로킹 단위가 크면 로크 수가 작아 관리하기 쉽지만, 병행성 수준이 낮아지고, 로킹 단위가 작으면 로크의 수가 많아 관리하기 복잡하지만 병행성 수준이 높아진다.

보안

1. 데이터베이스 보안의 개요
2. 무결성과 보안
   1. 무결성은 권한이 있는 사용자로부터 데이터베이스를 보호하는 것
      정확하게 사용할 수 있도록 보장하는 것
   2. 보안은 권한이 없는 사용자로부터 데이터베이스를 보호하는 것
      데이터베이스 사용자들이 데이터베이스를 사용하고자 할 때 언제든지 사용할 수 있도록 보장하는 것
3. 암호화 기법
   
   1. 개인키 암호 방식 == 대칭 암호 방식 == 단일키 암호화 기법 ex) DES(Data Encryption Standard)
      - 암호화/복호화 속도가 빠르며, 알고리즘이 단순하고 파일 크기가 작음
      - 사용자의 증가에 따라 관리해야할 키의 수가 상대적으로 많아짐.
      -  DES는 56Bit의 16개 키를 이용하여 64Bit의 평문 블록을 16회의 암호 계산 단계를 거쳐 64Bit의 암호문을 얻는다.
   2. 공개키 암호 방식 == 비대칭 암호 방식 ex) RSA(Rivest Shamir Adleman)
      - 키의 분배가 용이하고, 관리해야 할 키의 개수가 적음
      - 암호화/복호화 속도가 느리며, 알고리즘이 복잡하고 파일 크기가 큼.

분산 데이터베이스

- 논리적으로 하나의 시스템에 속하지만 물리적으로는 네트워크를 통해 연결된 여러 개의 컴퓨터 사이트에 분산되어 있는 데이터베이스를 의미한다.
- 자료의 공유성 향상, 분산 제어가 가능, 시스템 성능 향상, 효용성과 융통성이 높음, 신뢰성 및 가용성이 높음
- DBMS가 수행할 기능이 복잡, 데이터베이스 설계가 어려움, 개발 비용이 증가, 처리 비용 증가, 잠재적 오류 발생 증가

1. 분산 데이터베이스의 4대 목표
   1. 위치 투명성
      액세스하려는 데이터베이스의 실제 위치를 알 필요 없이 단지 데이터베이스의 논리적인 명칭만으로 액세스할 수 있음.
   2. 중복 투명성
      동일 데이터가 여러 곳에 중복되어 있더라도 사용자는 마치 하나의 데이터만 존재하는 것처럼 사용하고, 시스템은 자동으로 여러 자료에 대한 작업을 수행함.
   3. 병행 투명성
      분산 데이터베이스와 관련된 다수의 트랜잭션들이 동시에 실현되더라도 그 트랜잭션의 결과는 영향을 받지 않음.
   4. 장애 투명성
      트랜잭션, DBMS, 네트워크, 컴퓨터 장애에도 불구하고 트랜잭션을 정확하게 처리함.

자료 구조의 분류

1. 선형: 선형 리스트(배열), 연결 리스트, 스택, 큐, 데크
2. 비선형 구조: 트리, 그래프

데크(Deque)

• 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조

트리(Tree)

• 근 노드(Root Node):  가장 상위의 노드
• 디그리(Degree, 차수): 각 노드에서 뻗어 나온 가지의 수
• 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
• 단말 노드 = Leaf Node: 자식이 하나도 없는 노드 
• 비단말 노드: 자식이 하나라도 있는 노드
• 자식 노드
• 부모 노드
• 형제 노드: 동일한 부모를 갖는 노드
• Level : 근 노드의 Level을 1로 가정
• 깊이: 어떤 Tree에서 노드가 가질 수 있는 최대의 레벨 (루트 노드 1로 가정)

이진 트리의 운행법

1. Preorder(전위) 운행 : Root -> L -> R
2. Inorder(중위) 운행: L -> Root -> R
3. Postorder(후위) 운행: L -> R -> Root

주요 정렬 알고리즘의 이해

이분 탐색

- 탐색 효율이 좋고, 탐색 시간이 적게 소요된다.

- 전체 파일을 두 개의 서브 파일로 분리해 가면서 Key 레코드를 검색하기 때문에 검색회수를 거듭할 떄마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦.

- 찾고자 하는 Key 값을 파일의 중간 레코드 Key됴 값과 비교하면서 검색한다.

- 중간 레코드 번호 mid = (low + high) / 2

해싱(Hashing)

- Hash Table이라는 기억공간을 할당하고, 해시 함수를 이용하여 레코드 키에 대한 Hash Table 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식

- 검색 속도가 가장 빠르지만, 기억 공간이 많이 요구됨.

- DAM(직접접근방법) 파일을 구성할 때, 해싱이 사용됨

- 삽입, 삭제 작업의 빈도가 많을 때, 유리한 방식

순차 파일 = 순서 파일 -> 자기 테이프(순차 접근)에서 많이 사용

- 입력되는 데이터들을 논리적인 순서에 따라 물리적 연속 공간에 순차적으로 기록

- 급여 관리 등과 같이 변동 사항이 크지 않고 기간별로 일괄 처리를 주로 하는 경우에 적합하다.

- 데이터 검색 시 순차 검색하므로 효율이 낮음.

- 새로운 레코드를 삽입, 삭제, 수정하는 경우 파일 전체를 복사해야 하므로 시간이 많이 소요된다.

색인 순차 파일 (Indexed Sequential File) -> 자기 디스크에서 많이 사용

• 순차 처리와 랜덤 처리가 모두 가능하도록 레코드들을 키 값 순으로 정렬시켜 기록하고, 레코드의 키 항목만을 모은 색인을 구성하여 편성하는 방식
• 레코드를 참조할 떄는 색인을 탐색한 후 색인이 가리키는 포인터(주소)를 사용하여 직접 참조할 수 있다.
• 자기 디스크에 많이 사용되며, 자기 테이브에서는 사용할 수 없다.
• 순차 처리와 랜덤 처리가 모두 가능, 효율적인 검색이 가능하고, 레코드이 삽입, 삭제, 갱신이 용이
• 색인 구역과 오버플로우 구역을 구성하기 위한 추가 기억 공간이 필요
• 파일이 정렬어 있어야 해서 -> 추가, 삭제가 많으면 효율이 떨어진다.
• 색인을 이용한 엑세스를 하기 때문에 엑세스 기간이 랜덤 편성 파일보다 느리다.

색인 순차 파일의 구성

1. 기본 구역(Prime Area): 실제 레코드들을 기록하는 부분으로, 각 레코드는 키 값 순으로 저장
2. 색인 구역(Index Area): 기본 구역에 있는 레코드들의 위치를 찾아가는 색인이 기록되는 부분
3. 오버플로 구역(OVerflow Area): 기본 구역에 빈 공간이 업성서 새로운 레코드의 삽입이 불가능할 때를 대비하여 예비적으로 확보해둔 부분
   1. 실린더 오버플로 구역 -> 독립 오버플로 구역 : 기본 구역에 빈 공간이 없어서 새로운 레코드의 삽입이 불가능할 때를 대비하여 예비적으로 확보해둔 부분

DBMS(DataBase Management System)

- 사용자와 데이터베이스 사이에서 사용자의 요구에 따라 정보를 생성해 해주고, 데이터베이스를 관리해 주는 소프트웨어

기존의 파일 처리 방식에서의 문제점

- 종속성으로 인한 문제점

• 일관성: 중복된 데이터 간에 내용이 일치하지 않는 상황이 발생하여 일관성이 없어짐
• 보안성: 중복되어 있는 모든 데이터에 동등한 보안 수준을 유지하기가 어려움
• 경제성: 저장공간의 낭비와 동일한 데이터의 반복 작업으로 인한 비용의 증가
• 무결성: 제어의 분산으로 인해 데이터의 정확성을 유지할 수 없음.

스키마(Schema)

- 데이터베이스의 구조와 제약조건에 관한 전반적인 명세를 기술

- 데이터베이스를 구성하는 데이터 객체, 속성, 관계 및 데이터 조작 시 데이터값들이 갖는 제약조건 등에 관해 전반적으로 정의

- 스키마는 데이터 사전에 저장되며, 다른 이름으로 메타 데이터라고도 한다.

스키마의 3계층

외부 스키마 = 서브 스키마 = 사용자 뷰

- 전체 데이터베이스의 한 논리적인 부분으로 볼 수 있으므로 서브 스키마라고도 부른다.

- 하나의 데이터베이스 시스템에는 여러 개의 외부 스키마가 존재할 수 있으며, 하나의 외부 스키마를 여러 개의 응용 프로그램이나 사용자가 공용할 수 있다.

- 일반 사용자는 SQL을 사용하여 DB를 사용한다.

개념 스키마 = 전체적인 뷰

- 데이터베이스의 전체적인 논리적 구조로서, 조직 전체의 데이터베이스로 하나만 존재한다.

- 개체 간의 관계와 제약조건을 나타내고 데이터베이스의 접근 권한, 보안 및 무결성 규칙에 관한 명세를 정의

- 단순한 스키마라고 하면 개념 스키마를 의미

- 데이터베이스 관리자에 의해서 구성

내부 스키마

- 물리적 저장장치의 입장에서 본 데이터베이스 구조

- 실제 데이터베이스에 저장될 레코드의 물리적인 구조를 정의하고, 저장 데이터 항목의 표현 방법, 내부 레코드의 물리적 순서 등을 나타낸다.

- 데이터베이스의 물리적 구조를 정의한다.

데이터베이스 언어(Database Language)

-  DB 구조, 데이터 형식, 접근 방식 등 DB를 구축하거나 수정할 목적으로 사용하는 언어

- 데이터 정의 언어의 기능

• 외부 스키마 명세 정의
• 데이터베이스의 논리적 데이터 구조와 물리적 데이터 구조의 정의 및 수정
• 스키마에 사용되는 제약조건에 대한 명세 정의

데이터 조작 언어(DML, Data Manipulation Language) = 서브 언어

• 사용자로 하여금 데이터를 처리할 수 있게 하는 도구 => 사용자(응용 프로그램)과 DBMS 간의 인터페이스를 제공
• 질의어가 있으며, 질의어는 터미널에서 주로 이용하는 비절차적 데이터 언어이다.

데이터 제어 언어(DCL, Data Control Language)

• 무결성, 보안 및 권한 제어, 회복 등을 하기 위한 언어
• 데이터를 보호하고 데이터를 관리하는 목적으로 사용
• 데이터 제어 언어의 기능
  • 불법적인 사용자로부터 데이터를 보호하기 위한 데이터 보안
  • 데이터의 정확성을 위한 무결성 유지
  • 시스템 장애에 대비한 데이터 회복과 병행수행 제어

데이터베이스 사용자

DBA

- 데이터베이스 시스템의 모든 권리와 운영에 대한 책임을 지고 있는 사람이나 그룹

- 개념 스키마와 내부 스키마 정의

- 무결성을 위한 제약조건의 지정

- 보안 및 데이터베이스의 접근 권한 부여 정책 수립

응용 프로그래머

- 일반 호스트 언어로 프로그램을 작성할 때, 데이터 조작어를 삽입해서 일반 사용자가 응용 프로그램을 사용할 숭 ㅣㅆ게, 인터페이스를 제공할 목저긍로 데이터베이스를 접근하는 사람들

- 호스트 언어와 DBMS가 지원하는 데이터 조작어에 능숙한 컴퓨터 전문가

일반 사용자

- 터미널을 이용하여 데이터베이스에 있는 자원을 활용할 목적으로 질의어(SQL)이나 응용 프로그램을 사용하여 데이터베이스에 접근하는 사람들

데이터 모델

- 현실 세계의 정보들을 컴퓨터에 표현하기 위해 단순화, 추상화하여 체계적으로 표현한 개념적 모형

- 데이터, 데이터의 관계, 데이터의 의미 및 일관성, 제약 조건 등을 기술하기 위한 개념적 도구들의 모임.

데이터 모델의 종류

1. 개념적 데이터 모델
   • 인간이 이해할 수 있는 구조로 표현하기 때문에 정보 모델이라고도 부름.
   • 속성들로 기술된 개체 타입과 이 개체 타입들 간의 관계를 이용하여 현실 셰계를 표현하는 방법
   • 개체-관계 모델(E-R)
2. 논리적 데이터 모델
   • 개념적 모델링 과정에서 얻은 개념적 구조를 컴퓨터가 이해하고 처리할 수 있도록 변환하는 과정
   • 단순히 데이터 모델이라고 한다면 논리적 데이터 모델을 의미한다.
   • 데이터 간의 관계를 어떻게 표현하느냐에 따라 관계 모델, 계층 모델, 네트워크 모델로 구분한다.

데이터 모델에 표시할 사항

• 구조 - 개체 타입들 간의 관계로서 데이터 구조 및 정적 성질을 표현
• 연산 - 데이터베이스에 저장된 실제 데이터를 처리하는 방법을 표시
• 제약조건 - 실제 데이터의 논리적인 제약조건 표시

데이터 모델의 구성 요소

• 개체(Entity)
  • 독립적으로 존재하거나 그 자체로서도 구별이 가능
  • 파일 시스템의 레코드에 대응
• 속성(Attribute)
  • 데이터의 가장 작은 논리적 단위로서 파일 구조의 데이터 항목 또는 데이터 필드에 해당
• 관계(Relationship)
  • 개체 간의 관계 또는 속성 간의 관계

개체-관계(Entity-Relationship) 모델

• 개념적 데이터 모델의 가장 대표적인 것.
• 데이터를 개체, 관계, 속성으로 묘사
• E-R 다이어그램으로 표현
• 특정 DB를 고려한 것이 아니기 때문에 관계 표현에 제약이 없다.

E-R 다이어그램

관계형 데이터 모델 -> 여기부터 논리적 데이터 모델에 관한 설명

- 계층 모델과 망 모델의 복잡한 구조를 단순화시킨 모델

- 표를 이용해서 데이터 상호 관계를 정의하는 DB 구조

- 데이터 간의 관계를 기본키와 이를 참조하는 외래키로 표현

- 대표적인 DBMS: Oracle, MS-SQL, Informix 등

계층형 데이터 모델

- 데이터의 논리적인 구조도가 트리 형태이며, 개체가 트리를 구성하는 노드 역할을 한다.

- 개체를 노드로 표현하고, 개체 집합들 사이의 관계를 링크로 연결

- 개체 타입 간에는 상위와 하위 관계가 존재하며, 1:N 대응 관계만 존재한다.

- 레코드 삭제 시 연쇄 삭제가 된다.

- 개체 타입들 간에는 사이클이 허용되지 않는다.

- 계층형 모델에서는 개체를 세그먼트라 부른다.

- 대표적인 DBMS는 IMS이다.

망(그래프, 네트워크)형 데이터 모델

- 그래프를 이용해서 데이터 논리 구조를 표현한 데이터 모델

- 상위와 하위 레코드 사이에서 N:M 대응 관계를 만족하는 구조

- 상위의 레코드를 Owner, 하위의 레코드를 Member라 하여 Owner-Member 관계라고도 한다.

- 레코드 타입 간의 관계는 1:1, 1:N, N:M이 될 수 있다.

라이브러리 vs 프레임워크의 차이

라이브러리

- 공통으로 사용될 수 있는 특정한 기능을 모듈화한 것

- 내가 직접 컨트롤할 수 있음.

- 프레임워크에 비해 자유로움.

프레임워크

- 공통으로 사용될 수 있는 특정한 기능을 모듈화한 것.

- 규칙이 엄격함.(폴더 구조, 파일 명 등)

- 제어권이 나한테 없음.(IOC)

디자인 패턴

- 프로그램을 설계할 때, 발생했던 문제점들을 객체 간의 상호 관계 등을 이용하여 해결할 수 있도록 하나의 "규약" 형태로 만들어 놓은 것.

싱글톤 패턴

- 하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴

- 데이터베이스 연결 모듈에 많이 쓰인다.

- 인스턴스를 생성할 때, 드는 비용이 줄어든다.

- 의존성이 높아진다.

중첩 클래스란?

- 클래스 내부에 클래스가 있는 형태

- 자바 기반의 UI 처리를 할 때, 사용자의 입력이나 외부의 이벤트에 대한 처리르 하는 곳에서 많이 사용했으나, 현재는 안드로이드 프로그래밍에서 위젯의 이벤트를 처리하는 핸들러를 구현할 때, 사용한다.

- 다른 클래스와 협력할 일이 적고, 외부 클래스와 밀접한 관련이 있다면 사용된다. -> 두 클래스를 한 번에 관리하기에 적합하고, 불필요한 관계를 감추고 높은 접근성을 얻을 수 있다.

- 외부 클래스와 내부 클래스가 서로의 멤버에 쉽게 접근할 수 있음.

- 소스의 가독성과 유지보수성을 높일 수 있다.

- 서로 관련 있는 클래스를 논리적으로 묶어서 표현함으로써, 코드의 캡슐화를 증가시킨다.

- 외부에서는 내부 클래스에 접근할 수 없으므로, 코드의 복잡성을 줄일 수 있다.

참고: https://velog.io/@blwasc/Java-%EC%A4%91%EC%B2%A9-%ED%81%B4%EB%9E%98%EC%8A%A4

* 중첩 클래스를 이용해서 활용한 예시

class Singleton {
	private static class singleInstanceHolder {
		private static final Singleton INSTANCE = new Singleton();
	}

	public static Singleton getInstance() {
		return singleInstanceHolder.INSTANCE;
	}
}

public class HelloWorld {
	public static void main(String[] args) {
		Singleton a = Singleton.getInstance();
		Singleton b = Singleton.getInstance();
		System.out.println(a.hashCode());
		System.out.println(b.hashCode());

		if (a == b) {
			System.out.println(true);
		}
	}
}

싱글톤 패턴의 단점

1. '독립적인' 인스턴스를 만들기가 어려움 -> 단위 테스트는 테스트가 서로 독립적이어야 하는데, 싱글톤 패턴은 미리 생성된 하나의 인스턴스를 기반으로 구현하는 패턴이므로

단위테스트가 '독립적' -> 테스트를 어떤 순서로든 실행할 수 있어야 한다.

2. 모듈 간의 결합을 강하게 만들 수 있다. => 의존성 주입(DI)를 통해 결합도를 낮출 수 있음.

의존성

- 종속성이라고도 불림.

- A가 B에 의존성이 있다는 것은 B의 변경 사항에 대해 A 또한 변해야 한다는 것.

의존성 주입 장점

- 모듈들을 쉽게 교체할 수 있는 구조로 만들 수 있다. -> 메인 모듈이 '직접' 다른 하위 모듈에 대한 의존성을 주기보다는 중간에 의존성 주입자가 이 부분을 가로채 메인 모듈이 '간접적'으로 의존성 주입을 주는 것.

- 테스팅하기 쉽고, 마이그레이션하기도 수월함.

구현할 때, 추상화 레이어를 넣고 이를 기반으로 구현체를 넣어 주기 때문에 애플리케이션 의존성 방향이 일관되고, 애플리케이션을 쉽게 추론할 수 있고, 모듈 간의 관계가 명확해짐.

의존성 주입 단점

- 모듈이 더 많이 분리되므로, 클래스 수가 많아지고 이로 인해, 약간의 런타임 패널티가 발생할 수 있음.

의존성 주입 원칙

"상위 모듈은 하위 모듈에서 어떠한 것도 가져와서는 안된다."

- 상위 모듈과 하위 모듈 모두 "추상화"에 의존해야 한다.

- 추상화는 "세부 사항"에 의존해서는 안된다.

팩토리 패턴

- 객체를 사용하는 코드에서 객체 생성 부분을 떼어내 추상화한 패턴

- 상속관계가 있는 두 클래스에서 상위 클래스는 크게 뼈대를 결정하고, 하위 클래스는 객체 생성에 관한 구체적인 내용을 결정하는 패턴

- 상위 클래스는 객체 생성 방식에 대해 알 필요가 없고, 느슨한 결합이 가능하다.

- 객체 생성 로직이 따로 분리되어 있기 때문에 수정할 일이 있다면 그 부분만 고치면 되므로 유지보수성이 늘어난다.

- 전달받은 값에 따라 다른 객체를 생성하며 인스턴스의 타입을 정한다.

enum CoffeeType {
	LATTE,
	ESPRESSO
}

abstract class Coffee {
	protected String name;

	public String getName() {
		return name;
	}
}

class Latte extends Coffee {
	public Latte() {
		name = "Latte";
	}
}
class Espresso extends Coffee {
	public Espresso() {
		name = "Espresso";
	}
}

class CoffeeFactory {
	public static Coffee createCoffee(CoffeeType type) {
		switch (type) {
			case LATTE:
				return new Latte();
			case ESPRESSO:
				return new Espresso();
			default:
				throw new IllegalArgumentException("invalid type");
		}
	}
}

public class Main {
	public static void main(String[] args) {
		Coffee coffee = CoffeeFactory.createCoffee(CoffeeType.LATTE);
		System.out.println(coffee.getName());
	}
}

Enum

- 상수의 집합을 정의할 때, 사용되는 타입

- 상수뿐만 아니라 메서드를 집어 넣어 관리할 수도 있음.

- 본질적으로  thread safe 하기 때문에 싱글톤 패턴을 만들 때 도움이 된다.

전략 패턴

- 객체의 행위를 바꾸고 싶은 경우, "직접" 수정하지 않고 전략이라고 부르는 '캡슐화된 알고리즘'을 컨텍스트 안에서 바꿔주면서 상호 교체가 가능하게 만드는 패턴

- 우리가 어떤 상품을 구매할 때, 네이버페이, 카카오페이 등 다양한 방법으로 결제하듯이 결제 방식의 '전략'만 바꿔서 두 가지 방식으로 결제하는 것

interface PaymentStrategy {
	public void pay(int amount);
}

class KAKAOCardStrategy implements PaymentStrategy {
	private String name;
	private String cardNumber;
	private String cvv;
	private String dateOfExpiry;

	public KAKAOCardStrategy(String name, String cardNumber, String cvv, String dateOfExpiry) {
		this.name = name;
		this.cardNumber = cardNumber;
		this.cvv = cvv;
		this.dateOfExpiry = dateOfExpiry;
	}

	@Override
	public void pay(int amount) {
		System.out.println(amount + " paid using KAKAOCard.");
	}
}

class LUNACardStrategy implements PaymentStrategy {
	private String emailId;
	private String password;

	public LUNACardStrategy(String emailId, String password) {
		this.emailId = emailId;
		this.password = password;
	}

	@Override
	public void pay(int amount) {
		System.out.println(amount + " paid using LUNACard.");
	}
}

class Item {
	private String name;
	private int price;

	public Item(String name, int price) {
		this.name = name;
		this.price = price;
	}

	public String getName() {
		return name;
	}

	public int getPrice() {
		return price;
	}
}

class ShoppingCart {
	List<Item> items;

	public ShoppingCart() {
		this.items = new ArrayList<>();
	}

	public void addItem(Item item) {
		this.items.add(item);
	}

	public void removeItem(Item item) {
		this.items.remove(item);
	}

	public int calculateTotal() {
		int sum = 0;
		for (Item item : items) {
			sum += item.getPrice();
		}

		return sum;
	}

	public void pay(PaymentStrategy paymentMethod) {
		int amount = calculateTotal();
		paymentMethod.pay(amount);
	}
}

public class HelloWorld {
	public static void main(String[] args) {
		ShoppingCart cart = new ShoppingCart();

		Item A = new Item("knudolA", 100);
		Item B = new Item("knudolB", 300);

		cart.addItem(A);
		cart.addItem(B);
		
		// pay by LUNACard
		cart.pay(new LUNACardStrategy("ex1@example.com", "pukubababo"));
		
		// pay by KAKAOCard
		cart.pay(new KAKAOCardStrategy("ex2", "123456", "123", "12/01"));

		/**
		 * 400 paid using LUNACard.
		 * 400 paid using KAKAOCard.
		 */
	}
}

컨텍스트

- 어떠한 작업을 완료하는데 필요한 모든 관련 정보를 말한다.

출처: 면접을 위한 전공 CS노트