[면접을 위한 CS 전공지식 노트] CHAPTER 4 데이터베이스

SECTION 1 데이터베이스 기본

1. 데이터베이스(DB; DataBase)

일정한 규칙/규약 ~> 구조화되어 저장되는 데이터 모음

• DBMS(DataBase Management System): 데이터베이스 제어, 관리하는 통합 시스템
• 특정 DBMS마다 정의된 쿼리 언어 ~> 삽입/삭제/수정/조회 등 수행
• 실시간 접근, 동시 공유 가능
• 응용 프로그램 <-> DBMS <-> 데이터베이스

 

엔터티(entity)

사람, 장소, 물건, 사건, 개념 등 여러 개의 속성을 지닌 명사

서비스의 요구 사항에 맞춰 속성이 정해짐

ex. 회원이라는 엔터티 -> 속성: 이름, 아이디, 주소, 전화번호

 

<강한 엔터티 & 약한 엔터티>

• A가 혼자서 존재 X B의 여부에 따라 종속적 -> A: 강한 엔터티 / B: 약한 엔터티
• ex. 방은 건물 안에서만 존재 -> 건물: 강한 엔터티 / 방: 약한 엔터티

 

릴레이션(relation)

데이터베이스에서 정보를 구분하여 저장하는 기본 단위

엔터티에 관한 데이터를 데이터베이스는 하나의 릴레이션에 담아서 관리

• 관계형 데이터베이스 - 테이블 / NoSQL 데이터베이스 - 컬렉션
  • MySQL: 레코드-테이블-데이터베이스
  • MongoDB: 도큐먼트-컬렉션-데이터베이스
•  

속성(attribute)

릴레이션에서 관리하는 구체적이며 고유한 이름을 갖는 정보

서비스의 요구 사항을 기반으로 관리해야 할 필요가 있는 속성들만 엔티티의 속성이 됨

ex. '차'라는 엔터티의 속성: 차 넘버, 바퀴 수, 차 색깔, 차종 등

 

도메인(domain)

릴레이션에 포함된 각각의 속성들이 가질 수 있는 값의 집합

ex. 속성: 성별 -> 값: {남, 여}

---

2. 필드와 레코드

• 레코드(= 튜플): 테이블에 쌓이는 행(row) 단위의 데이터
• 엔티티: 책 -> `book` 테이블
  • 속성: 아이디, 제목, 저자의 아이디, 출판년도, 장르, 생성 일시, 업데이트 일시

CREATE TABLE book(
	id INT NOT NULL AUTO_INCREMENT,
    title VARCHAR(255),
    auther_id INT,
    publishing_year VARCHAR(255),
    genre VARCHAR(255),
    created_at DATETIME,
    updated_at DATETIME,
    PRIMARY KEY (id)
);

 

필드 타입

• 숫자 타입: `TINYINT`, `SMALLINT`, `MEDIUMINT`, `INT`, `BIGINT`

• 날짜 타입
  • `DATE`: 날짜 부분 O, 시간 부분 X/ 1000-01-01~9999-12-31/ 3바이트
  • `DATETIME`: 날짜 및 시간 부분 모두 포함/ 1000-01-01 00:00:00 ~ 9999-12-31 23:59:59/ 8바이트
  • `TIMESTAMP`: 날짜 및 시간 부분 모두 포함/ 1970-01-01 00:00:01~2038-01-19 03:14:07/ 4바이트
• 문자 타입
  • `CHAR`와 `VARCHAR`: 그 안에 수를 입력해서 몇 자까지 입력할지 정함
    / ex. CHAR(30): 최대 30글자까지 입력
    • `CHAR`: 테이블을 생성할 때 선언한 길이로 고정/ 0~255 => 유동적이지 X 길이 가진 데이터 
    • `VARCHAR`: 가변 길이 문자열/ 0~65,535
      / ex. 10글자 이메일 저장 -> 10글자에 해당하는 바이트 + 길이기록용 1바인트
      => 유동적인 길이 가진 데이터
  • `TEXT`와 `BLOB`: 큰 데이터를 저장할 때 사용
    • `TEXT`: 큰 문자열 저장/ 게시판 본문 저장
    • `BLOB`: 이미지, 동영상 등 큰 데이터 저장
      / (아마존의 이미지 호스팅 서비스인 S3를 이용하는 등 서버에 파일을 올리고 파일에 관한 경로를 VARCHAR로 지정)
  • `ENUM`과 `SET`: 문자열을 열거한 타입/ (+) 공간적으로 이점, (-) 애플리케이션 수정 -> 정의한 목록 수정
    • `ENUM`(x-small, small, medium, large, x-large 중 단일 선택): 잘못된 값 삽입 -> 빈 문자열 삽입
      / x-small 등 -> 0, 1로 매핑 => 메모리 적게 사용/ 최대 65,535개 요소 넣을 수 있음
    • `SET`: 여러 개의 데이터를 선택 O, 비트 단위의 연산 O, 최대 64개의 요소를 집어넣을 수 있음

---

3. 관계

여러 개의 테이블이 있고, 서로 관계가 정의되어 있음 => 관계화살표로 나타냄

1:1 관계

• ex. 한 유저당 유저 이메일은 한 개
• 1개 테이블 -> 2개의 테이블로 나눠 테이블 구조를 더 이해하기 쉽게 만듦

 

1:N 관계

• ex. 한 유저당 여러 개의 상품을 장바구니에 넣을 수 있음
• 하나도 넣지 않는 0개의 경우도 있음
• 한 개체가 다른 많은 개체를 포함하는 관계

 

N:M 관계

• ex. 학생도 강의를 많이 들을 수 있고, 강의도 여러 명의 학생을 포함할 수 있음
• 테이블 2개를 직접적으로 연결 X, 1:N, 1:M이라는 관계를 갖는 테이블 2개로 나눠서 설정
  • 학생(ID, 이름, 전화번호, 주소), 강의(ID, 이름, 교수명) => 학생_강의(학생ID, 강의ID)

---

4. 키

• 기본키(PK; Primary Key): 테이블의 데이터 중 고유하게 존재하는 속성, 중복 X/ 유일성 + 최소성 
  • 자연키: 언젠가는 변하는 속성
    • ex. 유저 테이블 -> 속성: 주민등록번호, 이름, 성별
      -> 이름, 성별은 중복된 값 들어올 수 있어서 부적절 => 주민등록번호 O
    • 중복되는 값들 제외 -> 자연스레 뽑다가 나오는 키
  • 인조키: 변하지 X -> 보통 인조키를 기본키로 설정
    • ex. 유저 테이블 -> 회원 테이블 -> 속성: 주민등록번호, 이름, 성별 + 유저 아이디 
      ~> 고유 식별자 생김
    • 오라클 - `sequence`, MySQL - `auto increment` 등 
• 외래키(FK; Foreign Key): 다른 테이블의 기본키를 그대로 참조하는 값, 개체와의 관계 식별하는 데 사용
  • 중복되어도 됨
    • `client` 테이블의 기본키: ID -> `product` 테이블의 `user_id`
• 후보키(candiate key): 기본키가 될 수 있는 후보/ 유일성 + 최소성
• 대체키(alternate key): 후보키 2개 이상 -> 어느 하나를 기본키로 지정, 남은 후보키들
• 슈퍼키(super key): 각 레코드를 유일하게 식별할 수 있는 유일성을 갖춘 키

---

SECTION 2 ERD와 정규화 과정

1. ERD(Entity Relationship Diagram)

• 데이터베이스를 구축할 때 가장 기초적인 뼈대 역할
• 릴레이션 간의 관계 정의
• 시스템의 요구 사항 -> ERD -> 데이터베이스
• 데이터베이스를 구축한 이후에도 디버깅 or 비즈니스 프로세스 재설계가 필요한 경우 설계도 역할 담당
• 관계형 구조로 표현할 수 있는 데이터를 구성하는 데 유용 But, 비정형 데이터를 충분히 표현 X

---

2. 정규화 과정

릴레이션 간의 잘못된 종속 관계 -> 데이터베이스 이상 현상

=> 해결 or 저장 공간을 효율적으로 사용하기 위해 릴레이션 여러 개로 분리하는 과정

 

ex. 회원이 1개의 등급 가져야 하는데 3개의 등급 갖음 or 삭제할 때 필요한 데이터 같이 삭제

or 데이터 삽입할 때 하나의 필드 값이 `NULL`이 되면 안되어서 삽입하기 어려운 상황

 

정규형 정도 -> 정규형(NF, Normal Form)으로 표현

• 기본 정규형: 제1정규형, 제2정규형, 제3정규형, 보이스/코드 정규형
• 고급 정규형: 제4정규형, 제5정규형

 

정규형 원칙

같은 의미를 표현하는 릴레이션이지만, 좋은 구조, 자료의 중복성 ↓

, 독립적인 관계는 별개의 릴레이션으로 표현, 각각의 릴레이션은 독립적인 표현이 가능해야 하는 것

• 제1정규형: 릴레이션의 모든 도메인이 더 이상 분해 X 원자 값(atomic value)만으로 구성되어야 함
  • 릴레이션의 속성 값 중에서 1개의 기본키에 대해 2개 이상의 값을 가지는 반복 집합 X (O -> 제거)
  • ex. 유저번호: 1/ 유저ID: 홍철/ 수강명: {C++코딩테스트, 프런트특강}/ 성취도: {90%, 10%}
    • 유저번호: 1/ 유저ID: 홍철/ 수강명: C++코딩테스트/ 성취도: 90%
    • 유저번호: 1/ 유저ID: 홍철/ 수강명:  프런트특강/ 성취도: 10%
• 제2정규형: 릴레이션이 제1정규형 + 부분 함수의 종속성 제거한 형태
  • 부분 함수의 종속성 제거: 기본키가 아닌 모든 속성이 기본키에 완전 함수 종속적인 것
  • ex. 기본키인 {유저ID, 수강명}과 완전 종속된 유저번호 릴레이션, {유저ID, 수강명}에 따른 성취도 릴레이션으로 분리
    • 유저번호: 1/ 유저ID: 홍철
    • 유저ID: 홍철/ 수강명: C++코딩테스트/ 성취도: 90%
  • 주의: 릴레이션 분해할 때 동등한 릴레이션으로 분해, 정보 손실이 발생 X 무손실 분해로 분해
• 제3정규형: 릴레이션이 제2정규형 + 기본키가 아닌 모든 속성이 이행적 함수 종속(transitive FD) 만족 X 상태
  • 이행적 함수 종속: A -> B와 B -> C 존재 => A -> C 성립: 집합 C가 집합 A에 이행적으로 함수 종속이 되었다
  • ex. 쇼핑몰 -> 유저ID: 홍철/ 등급: 플래티넘/ 할인율: 30%
    • 유저ID: 홍철/ 등급: 플래티넘
    • 등급: 플래티넘/ 할인율: 30%
• 보이스/코드 정규형(BCNF): 릴레이션이 제3정규형
  + 결정자가 후보키가 아닌 함수 종속 관계 제거 -> 릴레이션의 함수 종속 관계에서 모든 결정자가 후보키
  결정자: 함수 종속 관계에서 특정 종속자(dependent)를 결정짓는 요소, 'X -> Y'일 때 X: 결정자/ Y: 종속자
  • ex. 요구사항: 각 수강명에 대해 한 학생은 오직 한 강사의 강의만 수강
    / 각 강사는 한 수강명만 담당/ 한 수강명은 여러 강사가 담당할 수 있음
    • 강사 속성이 결정자이지만 후보키 X -> 속성 분리 => 학번-강사/수강명-강사

---

SECTION 3 트랜잭션과 무결성

1. 트랜잭션

• 데이터베이스에서 하나의 논리적인 기능을 수행하기 위한 작업의 단위
• 데이터베이스에 접근하는 방법: 쿼리 -> 여러 개의 쿼리들을 하나로 묶는 단위
• ACID 특징: 원자성, 일관성, 독립성, 지속성

 

원자성(atomicity)

트랜잭션과 관련된 일이 모두 수행되었거나 되지 않았거나를 보장하는 특징(all or nothing)

• ex. 트랜잭션 커밋 -> 문제 발생해 롤백 => 그 이후에 모두 수행 X 보장
• 트랜잭션 단위로 여러 로직들을 묶을 때 외부 API를 호출하는 것 X
  • O -> 롤백이 일어났을 때 어떻게 해야 할 것인지에 대한 해결 방법 있어야 하고 트랜잭션 전파 신경 써서 관리해야 함
• 커밋(`commit`)과 롤백(`rollback`): 데이터 무결성 보장, 데이터 변경 전에 변경 사항 쉽게 확인, 해당 작업 그룹화 O
  • 커밋(`commit`): 여러 쿼리)가 성공적으로 처리되었다고 확정하는 명령어
    • `update`, `insert`, `delete` 쿼리 -> 하나의 트랜잭션 단위로 수행, 변경된 내용 모두 영구 저장
    • 커밋이 수행되었다 = 하나의 트랜잭션이 성공적으로 수행되었다
  • 롤백(`rollback`): 트랜잭션으로 처리한 하나의 묶음 과정을 일어나기 전으로 돌리는 일(취소)
• 트랜잭션 전파(`@Transactional`)
  • 트랜잭션 수행할 때 커넥션 단위로 수행 -> 커넥션 객체를 넘겨서 수행해야 함
    But, 매번 넘겨주기 어렵고 귀찮음
    => 넘겨서 수행 X 여러 트랜잭션 관련 메서드의 호출을 하나의 트랜잭션에 묶이도록 하는 것

@Service
@Transactional(readOnly = true)
public class MemberService {
	private final MemberRepository memberRepository;
    
    public MemberService(MemberRepository memberReposiotry) {
    	this.memberRepository = memberRepository;
    }
}

 

일관성(consistency)

'허용된 방식'으로만 데이터를 변경해야 하는 것

• 데이터베이스에 기록된 모든 데이터는 여러 가지 조건, 규치게 따라 유효함을 가져야 함

 

격리성(isolation)

트랜잭션 수행 시 서로 끼어들지 못하는 것

• 복수의 병렬 트랜잭션: 서로 격리 -> 순차적으로 실행되는 것처럼 작동되어야 함
  / 데이터베이스: 여러 사용자가 같은 데이터에 접근할 수 있어야 함
• 여러 개의 격리 수준으로 나뉘어 격리성 보장
  • `SERIALIZABLE`, `REPEATABLE_READ`, `READ_COMMITED`, `READ_UNCOMMITED` (동시성 ↑, 격리성 ↓)

 

<격리 수준에 따라 발생하는 현상>

• 팬텀 리드(phantom read): 한 트랜잭션 내에서 동일한 쿼리를 보냈을 때 해당 조회 결과가 다른 경우
  • 다른 트랜잭션이 새로운 행 추가/삭제 -> 조회 조건에 맞는 행 개수 바뀜
  • ex. 사용자 A) 회원 테이블에서 `age`가 12 이상인 회원 조회하는 쿼리, 3개의 테이블 조회
    -> 사용자 B) `age`가 15인 회원 레코드 삽입 -> 3개 X 4개 테이블 조회
• 반복 가능하지 않은 조회(non-repeatable read): 한 트랜잭션 내의 같은 행에 2번 이상 조회했을 때 값이 다른 경우
  • 다른 트랜잭션이 기존 데이터 수정 -> 같은 행의 값이 바뀜
  • ex. 사용자 A) 보석 개수 100개 -> 사용자 B) 값을 1로 변경해서 커밋 -> 사용자 A) 100 X 1 읽게 됨
• 더티 리드(dirty read): 한 트랜잭션이 실행 중일 때 다른 트랜잭션에 의해 수정 But, 커밋 X 행의 데이터 읽을 수 있는 경우
  • ex. 사용자 A) 보석 개수 100개 -> 사용자 B) 값을 1로 변경해서 커밋 X -> 사용자 A) 100 X 1 읽게 됨

 

<격리 수준>

• `SERIALIZABLE`
  • 트랜잭션을 순차적으로 진행시키는 것, 여러 트랜잭션이 동시에 같은 행 접근 X
  • 매우 엄격한 수준으로 해당 행에 대해 격리, 이후 트랜잭션이 이 행에 대해 일어난다면 기다려야 함
  • 교착 상태 일어날 확률 ↑, 성능 ↓
• `REPEATABLE_READ`
  • 하나의 트랜잭션이 수정한 행 -> 다른 트랜잭션이 수정 X
  • 새로운 행 추가하는 것 막지 X -> 이후에 추가된 행이 발견될 수 있음
• `READ_COMMITED`
  • 가장 많이 사용되는 격리 수준, MySQL8.0, PostgreSQL, SQL Server, 오라클 기본값
  • `commit` 완료된 데이터에 대해서만 조회 허용 (<-> `READ_UNCOMMITED`)
  • 어떤 트랜잭션이 접근한 행 -> 다른 트랜잭션이 수정 O
• `READ_UNCOMMITED`
  • 가장 낮은 격리 수준
  • 하나의 트랜잭션이 커밋되기 이전에 다른 트랜잭션에 노출되는 문제 But, 가장 빠름
    
    • (이상) 데이터 무결성 -> 되도록 사용 X/ 어림잡아 집계하는 데 사용

 

지속성(durability)

성공적으로 수행된 트랜잭션은 영원히 반영되어야 하는 것

데이터베이스 시스템에 장애 발생 -> 원래 상태로 복구하는 회복 기능이 있어야 함 => 체크섬, 저널링, 롤백 등 기능 제공

• 체크섬: 중복 검사의 한 형태/ 오류 정정 ~> 송신된 자료의 무결성 보호
• 저널링: 파일 시스템 or 데이터베이스 시스템에 변경 사항을 `commit`하기 전에 로깅하는 것
  / 트랜잭션 등 변경 사항에 대한 로그 남기는 것

---

2. 무결성

데이터의 정확성, 일관성, 유효성을 유지하는 것

데이터베이스에 저장된 데이터 값, 그 값에 해당하는 현실 세계의 실제 값 -> 일치하는지에 대한 신뢰가 생김

 

종류

• 개체 무결성: 기본키로 선택된 필드는 빈 값 허용 X
• 참조 무결성: 서로 참조 관계에 있는 두 테이블의 데이터는 항상 일관된 값을 유지해야 함
• 고유 무결성: 특정 속성에 대해 고유한 값을 가지도록 조건이 주어진 경우 그 속성 값은 모두 고유한 값을 가짐
• `NULL` 무결성: 특정 속성 값에 `NULL`이 올 수 없다는 조건 주어짐 -> 그 속성 값은 `NULL`이 될 수 없다는 제약 조건

---

SECTION 4 데이터베이스 종류

1. 관계형 데이터베이스(RDBMS)

• 행과 열을 가지는 표 형식의 데이터를 저장하는 형태의 데이터베이스
• SQL이라는 언어를 써서 조작
• MySQL, PostgreSQL, 오라클, SQL Server, MSSQL 등
• 표준 SQL을 지키기는 하지만, 각각의 제품에 특화시킨 SQL 사용
• ex. 오라클 - PL/SQL, SQL Server - T-SQL, MySQL - SQL

 

MySQL

• 대부분의 운영체제와 호환, 현재 가장 많이 사용하는 데이터베이스
• C, C++로 만들어짐, MyISAM의 인덱스 압축 기술, B-트리 기반의 인덱스
  , 스레드 기반의 메모리 할당 시스템, 매우 빠른 조인, 최대 64개의 인덱스 제공
• 대용량 데이터베이스 위해 설계/ 롤백, 커밋, 이중 암호 지원 보안 등 기능 제공

• 데이터베이스의 심장과도 같은 역할 하는 곳: 스토리지 엔진 -> 모듈식 아키텍처로 쉽게 스토리지 엔진 변경 O
• (+) 데이터 웨어하우징, 트랜잭션 처리, 고가용성 처리 
• 커넥터 API 및 서비스 계층 ~> MySQL 데이터베이스와 쉽게 상호작용 O
• 쿼리 캐시 지원 -> 입력된 쿼리 문에 대한 전체 결과 집합 저장
  => 사용자가 작성한 쿼리와 캐시에 있는 쿼리 동일 -> 구문 분석, 최적화 및 실행 건너뛰고 캐시의 출력만 표시

 

PostgreSQL

• 특징: 디스크 조각이 차지하는 영역을 회수할 수 있는 장치인 VACUUM
• 최대 테이블의 크기: 32TB
• `SQL`, `JSON` 이용해서 데이터에 접근 O
• 지정 시간에 복구하는 기능, 로깅, 접근 제어, 중첩된 트랜잭션, 백업 등 할 수 있음

---

2. NoSQL 데이터베이스

• NoSQL(Not only SQL)이라는 슬로건에서 생겨난 데이터베이스
• SQL을 사용하지 않는 데이터베이스
• MongoDB, redis

 

MongoDB

• `JSON` ~> 데이터에 접근할 수 있고, Binary JSON 형태(`BSON`)로 데이터 저장
• 데이터를 디스크에 저장하는 방식(스토리지 엔진)으로 WiredTiger를 기본으로 사용
  • 동시성 처리, 데이터 압축, 트랜잭션 지원 등 성능과 안정성이 개선된 엔진
• 키-값 구조에서 `value` 부분을 단순 값이 아닌 `BSON`으로 저장
  • 계층 구조를 가진 복잡한 데이터도 문서 하나로 저장할 수 있음 => 도큐먼트 기반 데이터베이스
• 확장성 ↑, 빅데이터 저장할 때 성능 좋음, 고가용성, 샤딩(Sharding), 레플리카셋(Replica Set) 지원
  • 구조가 유연, 인덱싱이나 내부 처리 방식이 `JSON` 문서 최적화에 맞춰져 있음
    -> 비정형 데이터 or 대용량 데이터 빠르게 처리 O
  • 자동 장애 조치(failover) ~> 서버가 일부 장애나도 다른 노드가 자동으로 역할을 넘겨받아 중단 X 운영
  • 수평 확장(샤딩) ~> 분산 저장 가능 -> 처리 성능 유지하기 쉬움
  • 하나의 데이터 -> 여러 서버에 복제 => 장애 대응, 데이터 안정성 확보
• 스키마 정해 놓지 X 데이터 삽입 -> 다양한 도메인의 데이터베이스를 기반으로 분석 or 로깅 등 구현
• 새로운 도큐먼트 생성 -> 다른 컬렉션에서 중복되기 어려운 유니크한 값(`ObjectID`) 생성
  • 유닉스 시간 기반의 타임스탬프(4바이트) + 랜덤 값(5바이트) + 카운터(3바이트)
  • (+) 개발자가 직접 `UUID` 만들 필요 X, 고유성 보장, 정렬 가능(타임스탬프), 서버 간 충돌 X

 

redis

• 인메모리 데이터베이스/ 키-값 데이터 모델 기반 데이터베이스
• 데이터 타입: 문자열(`string`), 최대 512MB까지 저장할 수 있음
• 셋(`set`), 해시(`hash`) 등 지원
• pub/sub 기능 -> 채팅 시스템
• 다른 데이터베이스 앞단에 두어 사용하는 캐싱 계층
  • (+) 속도 향상, 부하 분산
  • `Cache-Aside` 패턴 (Lazy Loading 캐시)
    
    • 데이터 조회 요청
      -> 캐시에 해당 데이터 O -> 캐시에서 반환 (캐시 히트)
      -> 캐시에 해당 데이터 X -> DB에서 가져온 후, 캐시에 저장 (캐시 미스) -> 캐시된 데이터 이후 요청에서 재사용
    • 데이터 변경 시 -> 캐시 삭제 or 캐시 업데이트
• 단순한 키-값이 필요한 세션 정보 관리
• 정렬된 셋(sorted set) 자료 구조 -> 실시간 순위표 서비스

---

SECTION 5 인덱스

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

 

1. B- 트리

• 이진 트리 확장 버전
• M차 B-트리: 최대 자식 수가 M개인 트리 = 하나의 노드가 최대 M개의 자식 노드를 가질 수 있음
  
  • 키 개수: 자식 수 - 1 (최대: M - 1개)
    
    • ex. M = 4인 B-트리 -> 한 노드는 최대 자식 4개, 최대 키 3개
  • 최소차수 t: 한 노드가 가질 수 있는 최소 자식 수(루트 예외)
    • 각 노드는 최소 t - 1개의 키, t개의 자식
    • 균형잡힌 트리(절반은 무조건 채워야 한다) -> M = 2t - 1 
      • 한 노드는 최대 자식 M개, 최소 자식 t개(M / 2)
      • ex. t = 2 -> M = 2 * 2 - 1: 3차 B-트리 => 자식 수: 최소 2개, 최대 3개/ 키 수: 최소 1개, 최대 2개
• 모든 리프 노드는 같은 깊이(레벨)에 존재, 삽입/삭제 -> 자동으로 균형 유지
• 루트 노드, 브랜치 노드, 리프 노드
• key 검색 과정(하향식): 루트 -> 브랜치 -> 리프 노드
  
  • 리프 노드가 꽉 차 있음 -> 중간 키를 부모로 올리고 양쪽을 분할
  • 루트도 꽉 차 있음 -> 루트가 새로 생기고 트리 높이 증가
• key 삽입 과정(상향식): 삭제할 키가 있는 노드 -> 삭제
  • 루트 노드부터 리프까지 삽입할 위치 검색 -> 삽입 시 항상 리프 노드에 삽입
  • 리프 노드가 꽉 차 있음 -> 노드 분할/ 부모 노드에 키 전달 -> 부모도 꽉 차면 상위 분할 반복
• key 삭제 과정: 단순 삭제 + 균형 조정
  • 삭제 후 노드 내 키 개수가 너무 적어지면 형제 노드와 병합 or 차용 => 트리 균형 유지

 

<인덱스가 효율적인 이유>

효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조 + 트리 깊이의 대수확장성

인덱스가 한 깊이씩 증가할 때마다 최대 인덱스 항목의 수는 4배씩 증가

 

대수확장성: 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것

---

2. 인덱스를 만드는 방법

MySQL

• 클러스터형 인덱스: 테이블당 하나를 설정할 수 있음
  • `primary key` 옵션으로 기본키를 만들면 클러스터형 인덱스 생성 
  • 기본키로 만들지 X `unique not null` 옵션 -> 클러스터형 인덱스 만들 수 있음
• 세컨더리 인덱스: 보조 인덱스로 여러 개의 필드 값을 기반으로 쿼리를 많이 보낼 때 생성해야 하는 인덱스
  • `create index ...` -> 세컨더리 인덱스 생성
• ex. `age`라는 하나의 필드만으로 쿼리 보냄 -> 클러스터형 인덱스만 필요
  / But, `age`, `name`, `email` 등 다양한 필드를 기반으로 쿼리 보냄 -> 세컨더리 인덱스 사용
• => 하나의 인덱스만 생성 -> 클러스터형 인덱스를 만드는 것이 (세컨더리 인덱스 만드는 것보다) 성능 좋음

 

MongoDB

• 도큐먼트 만들면 자동으로 `ObjectID` 형성 -> 기본키로 설정
• 세컨더리키도 부가적으로 설정해서 복합 인덱스(기본키 + 세컨더리키) 설정할 수 있음

---

3. 인덱스 최적화 기법

• 인덱스는 비용이다
  • 인덱스는 2번 탐색하도록 강요
    • 인덱스 리스트 -> 컬렉션 순으로 탐색 => 관련 읽기 비용 듦
  • 컬렉션이 수정되었을 때 인덱스도 수정되어야 함
    • B-트리의 높이를 균형 있기 조절하는 비용, 데이터를 효율적으로 조회할 수 있도록 분산시키는 비용
    • 컬렉션에서 가져와야 하는 양 ↑ -> 인덱스 사용하는 것은 비효율적
    • -> 쿼리에 있는 필드에 인덱스를 무작정 다 설정 X
• 항상 테스팅하라
  • 최적화 기법은 서비스의 특징에 따라 달라짐
    • 서비스에서 사용하는 객체의 깊이, 테이블의 양 등이 다르기 때문
  • `explain()` 함수 ~> 인덱스 만들고 쿼리를 보낸 이후에 테스팅을 하며 걸리는 시간 최소화해야 함

EXPLAIN
SELECT * FROM t1
JOIN t2 ON t1.c1 = t2.c1

• 복합 인덱스: (같음, 정렬, 다중 값, 카디널리티) 순서
  • 여러 필드를 기반으로 조회 -> 복합 인덱스 생성 => 생성할 때 순서가 있고, 순서에 따라 인덱스 성능 달라짐
  • 어떠한 값과 같음을 비교하는 == or equal이라는 쿼리 O -> 제일 먼저 인덱스로 설정
  • 정렬에 쓰는 필드 -> 그 다음 인덱스로 설정
  • 다중 값을 출력해야 하는 필드, 즉 쿼리 자체가 > or < 등 많은 값을 출력해야 하는 쿼리에 쓰는 필드 -> 나중에 인덱스로 설정
  • 카디널리티: 유니클한 값의 정도/ 카디널리티가 높은 순서를 기반으로 인덱스 생성
    • ex. `age`, `email` -> `email`이 더 높음 => `email`이라는 필드에 대한 인덱스 먼저 생성

---

SECTION 6 조인의 종류

조인(join)

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

• MySQL - `JOIN`, MongoDB - `lookup`
• MongoDB는 조인 연산에 대해 관계형 데이터베이스보다 성능 ↓
  -> 여러 테이블 조인하는 작업 ↑ => 관계형 데이터베이스 사용

 

종류

• 내부 조인(inner join): 교집합/ 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기

SELECT * FROM TableA A
INNER JOIN TableB B ON
A.key = B.key

• 왼쪽 조인(left outer join): 왼쪽 테이블의 모든 행이 결과 테이블에 표기

SELECT * FROM TableA A
LEFT JOIN TableB B ON
A.key = B.key

• 오른쪽 조인(right outer join): 오른쪽 테이블의 모든 행이 결과 테이블에 표기

SELECT * FROM TableA A
RIGHT JOIN TableB B ON
A.key = B.key

• 합집합 조인(완전 외부 조인/ full outer join): 두 개의 테이블 기반 -> 조인 조건에 만족하지 않는 행까지 모두 표기

SELECT * FROM TableA A
FULL OUTER JOIN TableB B ON
A.key = B.key

---

SECTION 7 조인의 원리

1. 중첩 루프 조인(NLJ; Nested Loop Join)

• 중첩 for 문과 같은 원리로 조건에 맞는 조인을 하는 방법
• 랜덤 접근에 대한 비용 증가 ↑ -> 대용량 테이블에서 사용 X
• ex. t1, t2 테이블 조인
  1. 첫 번째 테이블에서 행을 한 번에 하나씩 읽음
  2. 그 다음 테이블에서도 행을 하나씩 읽어 조건에 맞는 레코드 찾아 결괏값 반환
• 블록 중첩 루프 조인(BNL; Block Nested Loop)
  • 중첩 루프 조인에서 발전/ 조인할 테이블 -> 작은 블록으로 나눠서 블록 하나씩 조인

for each row in t1 matching reference key {
	for each row in t2 matching reference key {
    	if row satisfies join conditions, send to client
    }
}

---

2. 정렬 병합 조인

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

---

3. 해시 조인

• 해시 테이블 기반으로 조인하는 방법
• 두 개의 테이블을 조인한다고 햇을 때 하나의 테이블이 메모리에 온전히 들어간다면 중첩 루프 조인보다 효율적
  • 메모리에 올릴 수 없을 정도로 크다면 디스크를 사용하는 비용 발생 
• 동등(=) 조인에서만 사용 O 

 

단계

• 빌드 단계
  • 입력 테이블 중 하나를 기반으로 메모리 내 해시 테이블을 빌드하는 단계
  • ex. 2개의 테이블(`persons`, `countries`) 조인 -> 둘 중 바이트가 더 작은 테이블을 기반으로 해서 테이블 빌드
  • 조인에 사용되는 필드 -> 해시 테이블의 키로 사용(`countries.country_id`)
• 프로브 단계
  • 레코드 읽기를 시작, 각 레코드에서 `persons.country_id`에 일치하는 레코드를 찾아서 결괏값으로 반환
  • 각 테이블은 한 번씩만 읽게 되어 중첩 루프 조인(: 중첩해서 두 개의 테이블을 읽음)보다 성능이 좋음
  • 사용 가능한 메모리양: 시스템 변수 `join_buffer_size`에 의해 제어, 런타임 시 조정할 수 있음