Mukho
Mukho
Made by Mukho

CS 전공지식 복습

~

면접을 위한 CS 전공지식노트(주홍철 지음) 책의 내용을 정리했습니다.

디자인 패턴

  • 싱글톤 패턴: 하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴으로, 인스턴스 생성 비용을 아낄 수 있다.
  • 의존성 주입(DI): 모듈 간의 결합을 느슨하게 만듬

  • passport: Node.js에서 인증 모듈을 구현할 때 쓰는 미들웨어 라이브러리로, 여러 가지 전략을 기반으로 인증할 수 있게 한다.

  • 옵저버 패턴: 주체가 어떤 객체의 상태 변화를 관찰하다가 상태 변화가 있을 때마다 메소드 등을 통해 옵저버 목록에 있는 옵저버들에게 변화를 알려주는 디자인 패턴이다.

  • 프록시 서버: 서버 앞단에 둬서 캐싱, 로깅, 데이터 분석을 서버보다 먼저 하는 서버이다. 포트 번호를 바꾸어 사용자가 실제 서버의 포트에 접근하지 못하게 할 수 있고 공격자의 DDOS 공격을 차단하거나 CDN을 프록시 서버로 달아서 캐싱 처리를 용이하게 할 수 있다.

  • 상속: 자식 클래스가 부모 클래스의 메소드를 상속받아 사용하며 자식 클래스에서 추가 및 확장을 할 수 있는 것으로, 재사용성, 중복성의 최소화가 이루어진다.
  • 구현: 부모 인터페이스를 자식 클래스에서 재정의하여 구현하는 것으로, 상속과는 달리 반드시 부모 클래스의 메소드를 재정의하여 구현해야 한다.
  • 프록시 서버: 서버와 클라이언트 사이에서 클라이언트가 자신을 통해 다른 네트워크 서비스에 간접적으로 접속할 수 있게 해주는 컴퓨터 시스템이나 응용 프로그램으로, nginx가 있다.

  • nginx: 비동기 이벤트 기반의 구조와 다수의 연결을 효과적으로 처리 가능한 웹 서버로, 주로 Node.js 서버 앞단의 프록시 서버로 활용된다. - 보안성 강화

  • MVC(ex- React.js): 앱의 구성 요소를 세 가지 역할로 구분하여 개발 프로세스에서 각각의 구성 요소에만 집중해서 개발할 수 있고, 재사용성과 확장성이 용이하다.
    • 모델: 애플리케이션의 데이터인 데이터베이스, 상수, 변수 등을 의미한다.
    • 뷰: inputbox, checkbox, textarea 등 사용자 인터페이스 요소를 나타낸다.
    • 컨트롤러: 하나 이상의 모델과 하나 이상의 뷰를 잇는 다리 역할을 하며 이벤트 등 메인 로직을 담당한다. 모델의 뷰의 생명주기를 관리한다.
  • 함수형 프로그래밍: 순수 함수를 쌓아 로직을 구현하고 고차 함수를 통해 재사용성을 높인 프로그래밍 패러다임이다.
    • 순수 함수: 출력이 입력에만 의존하는 것이다.
    • 고차 함수: 함수가 함수를 값처럼 매개변수로 받아 로직을 생성할 수 있는 것이다.
    • 일급 객체: 변수나 메소드에 함수를 할당할 수 있고, 함수 안에 함수를 매개변수로 담을 수 있고, 함수가 함수를 반환할 수 있는 특징을 가진 언어이다.
  • 객체지향 프로그래밍의 특징
    • 추상화: 복잡한 시스템으로부터 핵심적인 개념 또는 기능을 간추려내는 것이다.
    • 캡슐화: 객체의 속성과 메소드를 하나로 묶고 일부를 외부에 감추어 은닉하는 것이다.
    • 상속성: 상위 클래스의 특성을 하위 클래스가 이어받아서 재사용하거나 추가, 확장하는 것이다.
    • 다형성: 하나의 메소드나 클래스가 다양한 방법으로 동작하는 것이다.
    • 오버로딩: 같은 이름을 가진 메소드를 여러 개 두는 것으로 메소드의 타입, 매개변수의 유형, 개수 등으로 여러 개를 둘 수 있다. 정적 다형성이다.
    • 오버라이딩: 주로 메소드 오버라이딩을 말하며, 상위 클래스로부터 상속받은 메소드를 하위 클래스가 재정의하는 것이다. 동적 다형성이다.
  • 객체지향 프로그래밍 설계
    • 단일 책임 원칙: 모든 클래스는 각각 하나의 책임을 가져야 한다.
    • 개방-폐쇄 원칙: 기존의 코드는 잘 변경하지 않아야 하고, 확장은 쉽게 할 수 있어야 한다.
    • 리스코프 치환 원칙: 프로그램의 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다.
    • 인터페이스 분리 원칙: 하나의 일반적인 인터페이스보다 구체적인 여러 개의 인터페이스를 만들어야 한다.
    • 의존 역전 원칙: 상위 계층은 하위 계층의 변화에 대한 구현으로부터 독립해야 한다.

네트워크

  • 네트워크: 노드와 링크가 서로 연결되어 있거나 연결되어 있지 않은 집합체로 처리량이 높고 지연 시간이 짧아야 한다. 트리, 버스, 스타, 링, 메시 토폴로지가 있다.

  • TCP/IP 4계층 모델
    • 응용 계층(세표응): FTP/HTTP/SSH/SMTP/DNS 등 응용 프로그램이 사용되는 프로토콜 계층이며, 서비스를 실질적으로 사람들에게 제공하는 계층이다.
    • 전송 계층(전): TCP/UDP/QUIC. 송신자와 수신자를 연결하는 통신 서비스를 제공하며 연결 지향 제이터 스트림 지원, 신뢰성과 흐름 제어를 제공하며, 응용과 인터넷 계층 사이의 데이터가 전달될 때의 중계 역할을 한다.
      • TCP: 패킷 사이의 순서를 보장하고, 연결 지향 프로토콜을 사용하여 연결을 해 신뢰성을 구축하고 수신 여부를 확인하며 가상회선 패킷 교환 방식을 사용한다.
      • UDP: 순서를 보장하지 않고, 수신 여부를 확인하지 않으며 단순히 데이터만 주는 데이터그램 패킷 교환 방식을 사용한다.
    • 인터넷 계층(네): IP/ARP/ICMP. 장치로부터 받은 네트워크 패킷을 IP 주소로 지정된 목적지로 전송하기 위해 사용되는 계층이다.
    • 링크 계층(물데): 이더넷. 실질적으로 데이터를 전달하며 장치 간에 신호를 주고받는 규칙을 정하는 계층이다.
  • 3-way handshake
    1. SYN: 클라이언트는 서버에 ISN을 담아 SYN을 보낸다.
    2. SYN+ACK: 서버는 클라이언트의 SYN을 수신하고 서버의 ISN을 보내며, 승인번호로 클라이언트의 ISN+1을 보낸다.
    3. ACK: 클라이언트는 서버의 ISN+1한 값인 승인번호를 담아 ACK를 서버에 보낸다.
  • 4-way handshake
    1. 클라이언트는 FIN으로 설정된 세그먼트를 보낸다. FIN_WAIT_1 상태로 바뀌고 서버의 응답을 기다린다.
    2. 서버는 클라이언트로 ACK 승인 세그먼트를 보낸다. CLOSE_WAIT 상태로 바뀌고, 클라이언트는 세그먼트를 받으면 FIN_WAIT_2 상태로 바뀐다.
    3. 서버는 ACK를 보내고 일정 시간 후에 클라이언트에 FIN이라는 세그먼트를 보낸다.
    4. 클라이언트는 TIME_WAIT 상태가 되고 다시 서버로 ACK를 보내서 서버는 CLOSED 상태가 된다. 이후 클라이언트는 일정 시간을 대기한 후 연결이 닫히고, 클라이언트와 서버의 모든 자원의 연결이 해제된다.
  • 유선 LAN - 이더넷: IEEE802.3, 전이중화 통신(양쪽 장치가 동시에 송수신할 수 있는 방식). 트위스트 페어 케이블(랜선), 광섬유 케이블 CSMA/CD: 반이중화 통신으로, 한 경로로 데이터를 보내고, 데이터를 보낸 이후 충돌이 발생한다면 일정 시간 이후 재전송하는 방식이다.
  • 무선 LAN: 반이중화 통신- 양쪽 장치는 서로 통신할 수 있지만, 동시에는 통신할 수 없는 방식이다.
  • CSMA/CA: 반이중화 통신 중 하나로 장치에서 데이터를 보내기 전에 캐리어 감지 등으로 사전에 가능한 한 충돌을 방지하는 방식을 사용한다.
  • 2.4GHz: 장애물에 강한 특성을 가지지만 전파 간섭이 일어나는 경우가 많다.
  • 5GHz: 사용 가능한 채널 수가 많고 동시에 사용할 수 있기 때문에 상대적으로 깨끗한 전파 환경을 구축할 수 있다.

  • 와이파이: 전자기기들이 무선 LAN 신호에 연결할 수 있게 하는 기술로, 무선 접속 장치(AP)-공유기가 있어야 한다.

  • 캡슐화: 상위 계층의 헤더와 데이터를 하위 계층의 데이터 부분에 포함시키고, 해당 계층의 헤더를 삽입하는 과정이다.
  • 비캡슐화: 하위 계층에서 상위 계층으로 가며 각 계층의 헤더 부분을 제거하는 과정이다.

  • PDU: Protocol Data Unit으로, 네트워크의 어떤 계층에서 계층으로 전달될 때의 데이터의 단위이다. 헤더(제어 관련 정보)-페이로드(데이터)로 구성되어 있다.

  • 응용 계층 - L7 스위치
  • 인터넷 계층 - 라우터, L3 스위치
  • 데이터 링크 계층 - L2 스위치, 브리지

  • 물리 계층 - NIC(네트워크 인터페이스 카드), 리피터-패킷 신호 증폭, AP-패킷 복사

  • ARP: Address Resolution Protocol로, IP 주소를 실제 주소인 MAC 주소로 변환한다.

  • 게이트웨이: 서로 다른 통신망, 프로토콜을 사용하는 네트워크 간의 통신을 가능하게 하는 관문 역할을 하는 컴퓨터나 소프트웨어이다.

  • IPv4: 32비트를 8비트 단위로 나눈 주소이다.

  • IPv6: 64비트를 16비트 단위로 나눈 주소이다.

  • DHCP: Dynamic Host Configuration Protocol로, IP 주소 및 기타 통신 매개변수를 자동으로 할당하기 위한 네트워크 관리 프로토콜이다.

  • NAT: Network Address Translation으로, 패킷이 라우팅 장치를 통해 전송되는 동안 패킷의 IP 주소 정보를 수정하여 IP 주소를 다른 주소로 매핑하는 방법이다. 공인 IP와 사설 IP로 나눠서 많은 주소를 사용할 수 있다.

  • HTTP/1.0: 기본적으로 한 연결당 하나의 요청을 처리하도록 설계되었고, 이로 인해 RTT(패킷이 목적지에 도달하고 나서 다시 출발지로 돌아오기까지 걸리는 시간이며 패킷 왕복 시간) 증가를 불러오게 되었다.
    • 이를 해결하기 위해 이미지 스플리팅, 코드 압축, 이미지 Base64 인코딩을 사용했다.
  • HTTP/1.1: 매번 TCP 연결을 하는 것이 아니라 한 번 TCP 초기화를 한 이후에 keep-alive라는 옵션으로 여러 개의 파일을 송수신할 수 있게 바뀌었다. 헤더에 쿠키 등 많은 메타데이터가 들어 있고 압축이 되지 않아 무거웠다.
  • HTTP/2: 지연 시간을 줄이고 응답 시간을 더 빠르게 할 수 있으며 멀티플렉싱, 헤더 압축, 서버 푸시, 요청의 우선순위 처리를 지원하는 프로토콜이다.
  • HTTPS: HTTP/2 위에서 동작하며, 응용 계층과 전송 계층 사이에 신뢰 계층인 SSL/TLS 계층을 넣은 신뢰할 수 있는 HTTP 요청이다. 통신을 암호화한 것이다.
    • SSL/TLS: 전송 계층에서 보안을 제공하는 프로토콜이다.
  • 해싱 알고리즘: 데이터를 추정하기 힘든 더 작고, 섞여 있는 조각으로 만드는 알고리즘이다.
  • SHA-256 알고리즘: 해시 함수의 결과값이 256비트인 알고리즘이며 비트 코인을 비롯한 많은 블록체인 시스템에서도 사용한다.
  • HTTP/3: QUIC라는 계층 위에서 돌아가며 TCP 기반이 아닌 UDP 기반으로 돌아간다. 3-way handshake 과정이 없으므로 초기 연결 설정 시 지연 시간이 감소된다. QUIC는 순방향 오류 수정 메커니즘(FEC)이 적용되어 있는데, 이는 전송한 패킷이 손실되었다면 수신 측에서 에러를 검출하고 수정하는 방식이며 열악한 네트워크 환경에서도 낮은 패킷 손실률을 자랑한다.

운영체제

  • 운영체제: 사용자가 컴퓨터를 쉽게 다룰 수 있게 해주는 인터페이스로, 한정된 메모리나 시스템 자원을 효율적으로 분배한다. CPU 스케줄링과 프로세스 관리, 메모리 관리, 디스크 파일 관리, I/O 디바이스 관리 등을 담당한다.
    • 유저 프로그램
    • GUI: 단순 명렁어 창이 아닌 아이콘을 마우스로 클릭하는 단순한 동작으로 컴퓨터와 상호 작용할 수 있도록 하는 인터페이스
    • 시스템콜: 운영체제가 커널에 접근하기 위한 인터페이스로, 유저 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출할 때 사용한다.
      • 메모리(프로세스-스레드) -> 시스템콜 -> 커널 -> OS의 구조이다.
      • modebit: 시스템콜이 작동될 때 유저 모드(1)와 커널 모드(0)을 구분하는 플래그 변수이다.
    • 커널: 운영체제의 핵심 부분이자 시스템콜 인터페이스를 제공하며 보안, 메모리, 프로세스, 파일 시스템, I/O 디바이스, I/O 요청 관리 등 운영체제의 중추적인 역할을 한다.
    • 드라이버
    • 하드웨어
  • CPU: 인터럽트에 의해 메모리에 존재하는 명령어를 해석하여 실행하는 역할을 하며 산술논리연산장치, 제어장치, 레지스터로 구성되어 있다.
  • 제어장치: 프로세스 조작을 지시하는 CPU의 한 부품으로, 입출력장치 간 통신을 제어하고 명령어들을 읽고 해석하며 데이터 처리를 위한 순서를 결정한다.
  • 레지스터: CPU 안에 있는 매우 빠른 임시기억장치로, CPU와 직접 연결되어 있으므로 연산 속도가 메모리보다 매우 빠르다.
  • 산술논리연산장치(ALU): 두 숫자의 산술 연산과 배타적 논리합, 논리곱 같은 논리 연산을 계산하는 디지털 회로이다.
    1. 제어장치가 메모리와 레지스터에 계산할 값을 로드한다.
    2. 제어장치가 레지스터에 있는 값을 계산하라는 명령을 산술논리연산장치에 명령한다.
    3. 제어장치가 계산된 값을 다시 ‘레지스터에서 메모리로’ 계산한 값을 저장한다.
  • 인터럽트: 어떤 신호가 들어왔을 때 CPU를 잠깐 정지시키는 것으로 IO 디바이스, 산술 연산, 프로세스 오류 등으로 발생한다. 하드웨어 인터럽트와 소프트웨어 인터럽트로 나뉜다.

  • DMA 컨트롤러: I/O 디바이스가 메모리에 직접 접근할 수 있도록 하는 하드웨어 장치로, CPU 부하를 막아준다.

  • 메모리 계층
    • 레지스터: CPU 안에 있는 작은 메모리로 휘발성, 속도가 매우 빠름, 기억 용량이 가장 적은 특징이 있다.
    • 캐시(L1, L2 캐시): 휘발성, 속도 빠름, 기억 용량이 적은 특징이 있다.
    • 메모리/주기억장치: RAM을 가리키며 휘발성, 속도 보통, 기억 용량이 보통인 특징이 있다.
    • 저장장치/보조기억장치: HDD, SSD를 가리키며 휘발성, 속도 낮음, 기억 용량이 많은 특징이 있다.
  • RAM: 하드디스크로부터 일정량의 데이터를 복사해서 임시 저장하고 이를 필요 시마다 CPU에 빠르게 전달하는 역할을 한다.

  • 캐시: 데이터를 미리 복사해 놓는 임시 저장소이자, 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리이다. 캐시를 통해 데이터를 접근하는 시간이 오래 걸리는 경우를 해결하고 무언가를 다시 계산하는 시간을 절약할 수 있다. 메모리와 CPU 사이의 속도 차이가 크기 때문에 ‘레지스터’를 두어 속도 차이를 해결하는데, 계층과 계층 사이에서 속도 차이를 해결하는 계층을 ‘캐싱 계층’이라고 한다.

  • 시간 지역성: 최근 사용한 데이터에 다시 접근하려는 특성이다.
  • 공간 지역성: 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성이다.

  • 캐시 hit과 캐시 miss: 캐시에서 원하는 데이터를 찾았다면 캐시 히트, 해당 데이터가 캐시에 없다면 주기억장치로 가서 데이터를 찾아오는 것을 캐시 미스라고 한다.

  • 웹 브라우저의 캐시: 사용자의 커스텀 정보와 인증 모듈 관련 사항들을 웹 브라우저에 저장해서 추후 서버에 요청할 때 본인 인증이나 중복 요청 방지를 위해 쓰인다.
    • 쿠키: 만료기한이 있는 키-값 저장소로, 주로 서버에서 만료기한을 정한다.
    • 로컬 스토리지: 만료기한이 없는 키-값 저장소로, 도메인 단위로 저장, 생성되고 클라이언트에서만 수정 가능하다.
    • 세션 스토리지: 만료기한이 없는 키-값 저장소로, 탭 단위로 세션 스토리지를 생성하고 탭을 닫을 때 해당 데이터가 삭제된다. 클라이언트에서만 수정 가능하다.
  • 가상 메모리: 메모리 관리 기법의 하나로 컴퓨터가 실제로 이용 가능한 메모리 자원을 추상화하여 이를 사용하는 사용자들에게 매우 큰 메모리로 보이게 만드는 것이다. 이때 가상적으로 주어진 주소를 가상 주소(logical address)라고 하며, 실제 매모리상에 있는 주소를 실제 주소(physical address)라고 한다. 가상 주소는 메모리관리장치(MMU)에 의해 실제 주소로 변환된다. 가상 메모리는 가상 주소와 실제 주소가 매핑되어 있고 프로세스의 주소 정보가 들어 있는 ‘페이지 테이블’로 관리된다. 이때 속도 향상을 위해 TLB를 사용한다.

  • TLB: 메모리와 CPU 사이에 있는 주소 변환을 위한 캐시이다. 페이지 테이블에 있는 리스트를 보관하며 CPU가 페이지 테이블까지 가지 않도록 해 속도를 향상시킬 수 있는 캐시 계층이다.

  • 메모리 연속 할당: 메모리에 연속적으로 공간을 할당하는 것이다.
    • 고정 분할 방식: 메모리를 미리 나누어 관리하는 방식으로 융통성이 없으며, 내부 단편화가 발생한다.
      • 내부 단편화(Internal Fragmentation)는 메모리를 나눈 크기보다 프로그램이 작아서 들어가지 못하는 공간이 많이 발생하는 현상이다.
    • 가변 분할 방식: 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용한다. 내부 단편화는 발생하지 않지만 외부 단편화가 발생한다.
      • 외부 단편화(External Fragmentation)는 메모리를 나눈 크기보다 프로그램이 커서 들어가지 못하는 공간이 많이 발생하는 현상이다.
      • 최초적합(first fit): 위쪽이나 아래쪽부터 시작하여 홀을 찾으면 바로 할당한다.
      • 최적적합(best fit): 프로세스의 크기 이상인 공간 중 가장 작은 홀부터 할당한다.
      • 최악적합(worst fit): 프로세스의 크기가 가장 많이 차이가 나는 홀에 할당한다.
  • 메모리 불연속 할당
    • 페이징: 동일한 크기의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당한다. 홀의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡해진다.
    • 세그먼테이션: 페이지 단위가 아닌 의미 단위인 세그먼트로 나누는 방식이다. 프로세스는 ‘코드, 데이터, 힙, 스택’ 등으로 이루어지는데, 코드와 데이터 등 이를 기반으로 나눌 수도 있으며 함수 단위로 나눌 수도 있다. 공유와 보안 측면에서는 좋지만 홀 크기가 균일하지 않다.
  • 페이지 교체 알고리즘: 메모리는 한정되어 있기 때문에 스와핑이 많이 일어난다. 하지만 스와핑이 많이 일어나면 성능 저하가 일어나기 때문에 스와핑이 최대한 적게 발생하도록 설계되어야 하며, 페이지 교체 알고리즘을 기반으로 스와핑이 일어난다.
    • 오프라인 알고리즘: 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘으로 이론상 가장 좋은 방법이지만 구현할 수 없어 전투력 측정기 역할을 한다.
    • FIFO: 가장 먼저 온 페이지를 교체 영역에 가장 먼저 좋는 방법이다.
    • LRU: Least Recently Used로, 참조가 가장 오래된 페이지를 바꾼다. 오래된 것을 파악하기 위해 각 페이지마다 계수기, 스택을 두어야 하는 문제점이 있다. 주로 해시 테이블과 이중 연결 리스트를 통해 구현하는데 해시 테이블은 이중 연결 리스트에서 O(1)을 만족시키기 위해 쓰고, 이중 연결 리스트는 한정된 메모리를 의미한다.
    • NRU: Not Used Recently로, LRU에서 발전한 방법이다. Clock 알고리즘이라고 하며 먼저 0과 1을 가진 비트를 둔다. 1은 최근에 참조되었고 0은 참조되지 않음을 의미한다. 시계 방향으로 돌면서 0을 찾고 0을 찾은 순간 해당 프로세스를 교체하면서 비트를 1로 바꾸는 알고리즘이다.
    • LFU: Least Frequently Used로, 참조 횟수가 가장 적은 페이지를 교체한다.
  • 프로세스: 컴퓨터에서 실행되고 있는 프로그램을 말하며, CPU 스케줄링의 대상이 되는 작업(task)이라는 용어와 거의 같은 의미로 쓰인다.

  • 스레드: 프로세스 내 작업의 흐름이다.

  • 컴파일 과정
    1. 전처리: 소스 코드의 주석을 제거하고 헤더 파일을 병합하여 매크로를 치환한다.
    2. 컴파일러: 오류 처리, 코드 최적화 작업을 하며 어셈블리어로 변환한다.
    3. 어셈블러: 어셈블러를 목적 코드(object code)로 변환한다. 이때 확장자는 OS마다 다른데 리눅스에서는 .o이다.
    4. 링커: 프로그램 내에 있는 라이브러리 함수 또는 다른 파일들과 목적 코드를 결합하여 실행 파일을 만든다. .exe 또는 .out 확장자를 가진다.
      • 라이브러리
      • 정적 라이브러리: 프로그램 빌드 시 라이브러리가 제공하는 모든 코드를 실행 파일에 넣는 방식이며, 시스템 환경 등 외부 의존도가 낮지만 코드 중복 등 메모리 효율성이 떨어지는 단점이 있다.
      • 동적 라이브러리: 프로그램 실행 시 필요할 때만 DLL이라는 함수 정보를 통해 참조하는 방식이며, 메모리 효율성에서의 장점이 있지만 외부 의존도가 높아진다는 단점이 있다.
  • 프로세스의 상태
    • 생성(Create): 프로세스가 생성된 상태를 의미하며 fork() 또는 exec() 함수를 통해 생성한다. 이때 PCB가 할당된다.
      • fork(): 부모 프로세스의 주소 공간을 그대로 복사하며, 새로운 자식 프로세스를 생성하는 함수이다. 주소 공간만 복사할 뿐이지 부모 프로세스의 비동기 작업 등을 상속하지는 않는다.
      • exec(): 새롭게 프로세스를 생성하는 함수이다.
    • 대기(Ready): 메모리 공간이 충분하면 메모리를 할당받고 아니면 아닌 상태로 대기하고 있으며 CPU 스케줄러로부터 CPU 소유권이 넘어오기를 기다리는 상태이다.
      • 대기 중단(Ready Suspended): 메모리 부족으로 일시 중단된 상태이다.
    • 실행(Running): CPU 소유권과 메모리를 할당받고 인스트럭션을 수행 중인 상태로, CPU burst가 일어났다고 표현하기도 한다.
    • 중단(Blocked): 어떤 이벤트가 발생한 이후 기다리며 프로세스가 차단된 상태이다. I/O 디바이스에 의한 인터럽트로 이런 현상이 많이 발생한다.
      • 일시 중단(Blocked Suspended): 대기 중단과 유사하며, 중단된 상태에서 프로세스가 실행되려고 했지만 메모리 부족으로 일시 중단된 상태이다.
    • 종료(Terminated): 메모리와 CPU 소유권을 모두 놓고 가는 상태이다. 자연스럽게 종료되는 경우도 있지만 부모 프로세스가 자식 프로세스를 강제 종료시키는 비자발적 종료(abort)가 일어나는 경우도 있다. 자식 프로세스에 할당된 자원의 한계치를 넘어서거나, 부모 프로세스가 종료되거나, 사용자가 process.kill 등 여러 명령어로 프로세스를 종료할 때 발생한다.
  • 프로세스의 메모리 구조
    • 동적 영역: 스택은 위 주소부터 할당되고 힙은 아래 주소부터 할당된다.
      • 스택: 지역변수, 매개변수, 함수가 저장되고 컴파일 시에 크기가 결정되며 ‘동적’인 특징을 가진다. 함수가 함수를 재귀적으로 호출하면서 동적으로 크기가 늘어날 수 있는데, 이때 힙과 스택의 메모리 영역이 겹치면 안 되기 때문에 힙과 스택 사이의 공간을 비워 놓는다.
      • 힙: 동적 할당할 때 사용되며 런타임 시 크기가 결정된다. ‘동적’인 특징을 가진다.
    • 정적 영역
      • 데이터 영역: 전역변수와 정적변수가 저장되고, ‘정적’인 특징을 갖는 프로그램이 종료되면 사라지는 변수가 들어 있는 영역이다. 데이터 영역은 BSS 영역(Segment)과 Data 영역으로 나뉜다.
        • BSS 영역: 초기화가 되지 않는 변수가 0으로 초기화되어 저장된다.
        • Data 영역: 0이 아닌 다른 값으로 할당된 변수들이 저장된다.
      • 코드 영역: 프로그램에 내장되어 있는 소스 코드가 들어가는 영역이다. 수정 불가능한 기계어로 저장되어 있으며 ‘정적’인 특징을 가진다.
  • PCB: Process Control Block, 프로세스 제어 블록은 운영체제에서 프로세스에 대한 메타데이터를 저장한 ‘데이터’이다. 프로세스가 생성되면 OS가 생성한다.
    • 프로그램이 실행되면 프로세스가 실행되고 프로세스 주소 값들에 앞서 스택, 힙 등의 구조를 기반으로 메모리가 할당된다. 그리고 이 프로세스의 메타데이터들이 PCB에 저장되어 관리된다. 이는 프로세스의 중요한 정보를 포함하고 있기 때문에 일반 사용자가 접근하지 못하도록 커널 스택의 가장 앞부분에서 관리된다.
    • 프로세스 스케줄링 상태, 프로세스 ID, 프로세스 권한, 프로그램 카운터, CPU 레지스터, CPU 스케줄링 정보, 계정 정보, I/O 상태 정보 등으로 이루어져 있다.

  • 메타데이터: 데이터에 관한 구조화된 데이터이자 데이터를 설명하는 작은 데이터이다.

  • Context Switching: PCB를 교환하는 과정으로 한 프로세스에 할당된 시간이 끝나거나 인터럽트에 의해 발생한다. 컴퓨터는 많은 프로그램을 동시에 실행하는 것처럼 보이지만 어떠한 시점에 실행되고 있는 프로세스는 단 1개(싱글코어 기준)이며, 많은 프로세스가 동시에 구동되는 것처럼 보이는 것은 다른 프로세스와이 컨텍스트 스위칭이 아주 빠른 속도로 실행되기 때문이다.
    • 비용: 캐시미스. 컨텍스트 스위칭이 일어날 때 프로세스가 가지고 있는 메모리 주소가 그대로 있으면 잘못된 주소 변환이 생기므로 캐시클리어 과정을 겪게 되고 이 때문에 캐시미스가 발생한다.
    • 스레드에서도 컨텍스트 스위칭이 일어난다. 스레드는 스택 영역을 제외한 모든 메모리를 공유하기 때문에 스레드 컨텍스트 스위칭의 경우 비용이 더 적고 시간이 더 적게 걸린다.
  • 멀티프로세싱: 여러 개의 프로세스, 즉 멀티프로세스를 통해 동시에 두 가지 이상의 일을 수행할 수 있는 것을 의미한다. 하나 이상의 일을 병렬로 처리할 수 있으며 특정 프로세스에 문제가 생겨도 다른 프로세스를 사용하면 되기 때문에 신뢰성이 높다.
  • IPC: Inter Process Communication으로 프로세스끼리 데이터를 주고받고 공유 데이터를 관리하는 메커니즘이다. 클라이언트는 데이터를 요청하고 서버는 클라이언트 요청에 응답하는 것도 IPC의 예시이다. IPC의 종류로는 공유 메모리, 파일, 소켓, 익명 파이프, 명명 파이프, 메시지 큐가 있으며, 이들은 메모리가 (스택을 제외하면)완전히 공유되는 스레드보다는 속도가 느리다.
    • 소켓: 동일한 컴퓨터의 다른 프로세스나 네트워크의 다른 컴퓨터로 네트워크 인터페이스를 통해 전송하는 데이터를 의미하며 TCP와 UDP가 있다.
    • 익명 파이프: 프로세스 간에 FIFO 방식으로 읽히는 임시 공간인 파이프를 기반으로 데이터를 주고받으며, 단방향 방식의 읽기 전영, 쓰기 전용 파이프를 만들어서 작동하는 방식이다. 이는 부모-자식 프로세스 간에만 사용할 수 있으며 다른 네트워크상에서는 사용이 불가능하다.
    • 명명된 파이프: 파이프 서버와 하나 이상의 파이프 클라이언트 간의 통신을 위한 명명된 단방향/이중 파이프를 말한다. 클라이언트/서버 통신을 위한 별도의 파이프를 제공하며, 여러 파이프를 동시에 사용할 수 있다. 컴퓨터의 프로세스/다른 네트워크상의 컴퓨터와도 통신할 수 있다.
  • 스레드: 프로세스의 실행 가능한 가장 작은 단위로, 프로세스는 여러 스레드를 가질 수 있다. 코드, 데이터, 힙, 스택을 각각 생성하는 프로세스와는 달리 스레드는 코드, 데이터, 힙은 스레드끼리 서로 공유한다.

  • 멀티스레딩: 프로세스 내 작업을 여러 개의 스레드, 즉 멀티스레드로 처리하는 기법이며 스레드끼리 서로 자원을 공유하기 때문에 효율성이 높다. 또한 동시성-서로 독립적은 작업들을 작은 단위로 나누고 동시에 실행되는 것처럼 보여주는 것-에도 큰 장점이 있다. 하지만 한 스레드에 문제가 생기면 다른 스레드에도 영향을 끼쳐 스레드로 이루어져 있는 프로세스에 영향을 줄 수 있는 단점이 있다.

  • 공유 자원: 시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 모니터, 프린터, 메모리, 파일, 데이트 등의 자원이나 변수 등을 의미한다.
  • 경쟁 상태(Race Condition): 공유 자원을 두 개 이상의 프로세스가 동시에 읽거나 쓰는 상황으로, 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결괏값에 영향을줄 수 있는 상태이다.
  • 임계 영역: 공유 자원에 접근할 때 순서 등의 이유로 결과가 달라지는 영역이다. 이를 해결하기 위한 방법은 크게 뮤텍스, 세마포어, 모니터 세 가지가 있으며, 이 방법 모두 상호 배제, 한정 대기, 융통성이라는 조건을 만족한다. 이 방법들의 토대가 되는 메커니즘은 잠금(Lock)이다.
    • 상호 배제: 한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어갈 수 없다.
    • 한정 대기: 특정 프로세스가 영원히 임계 영역에 들어가지 못하면 안 된다.
    • 융통성: 한 프로세스가 다른 프로세스의 일을 방해해서는 안 된다.
    • 뮤텍스(Mutex): 공유 자원을 사용하기 전에 설정하고, 사용한 후에 해제하는 잠금이다. 잠금이 설정되면 다른 스레드는 잠긴 코드 영역에 접근할 수 없다. 뮤텍스는 하나의 상태(잠금/잠금 해제)만 가진다.
    • 세마포어(Semaphore): 일반화된 뮤텍스로, 간단한 정수 값과 두 가지 함수 wait(P 함수라고도 함) 및 signal(V 함수라고도 함)로 공유 자원에 대한 접근을 처리한다. wait()은 자신의 차례가 올 때까지 기다리는 함수이고 signal()은 다음 프로세스로 순서를 넘겨주는 함수이다.
      • 프로세스가 공유 자원에 접근하면 세마포어에서 wait() 작업을 수행하고 프로세스가 공유 자원을 해제하면 세마포어에서 signal() 작업을 수행한다. 세마포어에는 조건 변수가 없고 프로세스가 세마포어 값을 수정할 때 다른 프로세스는 동시에 세마포어 값을 수정할 수 없다.
      • 바이너리 세마포어는 0과 1의 두 가지 값만 가질 수 있는 세마포어이다. 구현의 유사성 때문에 뮤텍스는 바이너리 세마포어라고 할 수 있지만, 뮤텍스는 리소스에 대한 접근을 동기화하는 데 사용되는 잠금 메커니즘이고, 세마포어는 신호를 기반으로 상호 배제가 일어나는 신호 메커니즘이다.
      • 카운팅 세마포어는 여러 개의 값을 가질 수 있는 세마포어로 여러 자원에 대한 접근을 제어하는 데 사용한다.
    • 모니터(Monitor): 둘 이상의 스레드나 프로세스가 공유 자원에 안전하게 접근할 수 있도록 공유 자원을 숨기고 해당 접근에 대해 인터페이스만 제공한다. 모니터큐를 통해 공유 자원에 대한 작업들을 순차적으로 처리한다. 세마포어보다 구현하기 쉬우며 모니터에서 상호 배제는 자동인 반면에, 세마포어에서는 상호 배제를 명시적으로 구현해야 한다는 차이점이 있다.
  • 교착 상태(Deadlock): 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 말한다. 프로세스 A가 프로세스 B의 어떤 자원을 요청할 때 프로세스 B도 프로세스 A가 점유하고 있는 자원을 요청하는 것이다.
    • 교착 상태의 원인
      • 상호 배제: 한 프로세스가 자원을 독점하고 있으며 다른 프로세스들은 접근이 불가능하다.
      • 점유 대기: 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태이다.
      • 비선점: 다른 프로세스의 자원을 강제적으로 가져올 수 없다. – 환형 대기: 프로세스 A는 프로세스 B의 자원을 요구하고, 프로세스 B는 프로세스 A의 자원을 요구하는 등 서로가 서로의 자원을 요구하는 상황이다.
    • 교착 상태의 해결 방법
      1. 자원을 할당할 때 애초에 조건이 성립되지 않도록 설계한다.
      2. 교착 상태 가능성이 없을 때만 자원 할당되며, 프로세스당 요청할 자원들의 최대치를 통해 자원 할당 가능 여부를 파악하는 ‘은행원 알고리즘’을 사용한다.
        • 은행원 알고리즘: 총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고 안정 상태로 가도록 자원을 할당하는 알고리즘이다.
      3. 교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 하나씩 지운다.
      4. 교착 상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 커서 교착 상태가 발생하면 사용자가 작업을 종료한다. 현대 운영체제는 이 방법을 채택했다.
  • CPU 스케줄링 알고리즘: CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, ready queue에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다.
    • 비선점형(Non-preemptive): 프로세스가 스스로 CPU 소유권을 포기하는 방식으로, 강제로 프로세스를 종료하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.
      • FCFS: First Come First Served로 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다. 길게 수행되는 프로세스 때문에 ready queue에서 오래 기다리는 현상인 convoy effect가 발생할 수 있다.
      • SJF: Short Job First로, 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다. 긴 시간을 가진 프로세스가 실행되지 않은 현상(Starvation)이 일어나며, 평균 대기 시간이 가장 짧다. 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거에 실행했던 시간을 토대로 추측해서 사용한다.
      • 우선순위: 기존의 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었는데, 이를 해결하기 위해 ‘오래된 작업일수록 우선순위를 높이는 방법’인 aging을 통해 단점을 보완한 알고리즘이다.
    • 선점형(Preemptive): 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고, 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식이다.
      • Round Robin(RR): 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링(Priority Scheduling)의 일종으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 ready queue의 뒤로 가는 알고리즘이다. 할당 시간이 너무 길면 FCFS가 되고 너무 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커진다. 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.
      • SRF: SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존에 수행하던 작업을 모두 수행하고 그 다음 짧은 작업을 이어나가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.
      • Multi-Level Queue: 다단계 큐는 우선순위에 따른 ready queue를 여러 개 사용하고, queue마다 RR이나 FCFS, SJF 등 다른 스케줄링 알고리즘을 적용한 것을 말한다. 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 그만큼 유연성이 떨어진다.

자료구조

  • Data Structure는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합이다.

  • 시간 복잡도: 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계로, 어떠한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내는 데 쓰인다.
    • 빅오 표기법: 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다. 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤 것이다.

  • 공간 복잡도: 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양이다. 정적 변수로 선언된 것 말고도 동적으로, 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함된다. C++에서 int a[1004] 배열은 1004 * 4 byte의 크기를 가진다.

  • 자료구조의 평균 시간 복잡도
자료구조 접근 탐색 삽입 삭제
배열(array) O(1) O(n) O(n) O(n)
스택(stack) O(n) O(n) O(1) O(1)
큐(queue) O(n) O(n) O(1) O(1)
단일 연결 리스트(singly linked list) O(n) O(n) O(1) O(n)
이중 연결 리스트(doubly linked list) O(n) O(n) O(1) O(1)
해시 테이블(hash table) O(1) O(1) O(1) O(1)
이진 탐색 트리(BST) O(logn) O(logn) O(logn) O(logn)
AVL 트리 O(logn) O(logn) O(logn) O(logn)
레드 블랙 트리 O(logn) O(logn) O(logn) O(logn)
  • 자료구조의 최악 시간 복잡도
자료구조 접근 탐색 삽입 삭제
배열(array) O(1) O(n) O(n) O(n)
스택(stack) O(n) O(n) O(1) O(1)
큐(queue) O(n) O(n) O(1) O(1)
단일 연결 리스트(singly linked list) O(n) O(n) O(n) O(n)
이중 연결 리스트(doubly linked list) O(n) O(n) O(1) O(1)
해시 테이블(hash table) O(n) O(n) O(n) O(n)
이진 탐색 트리(BST) O(n) O(n) O(n) O(n)
AVL 트리 O(logn) O(logn) O(logn) O(logn)
레드 블랙 트리 O(logn) O(logn) O(logn) O(logn)
  • 선형 자료 구조: 요소가 일렬로 나열되어 있는 자료구조이다.
    • 연결 리스트: 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다. 삽입과 삭제 시 O(1)이 걸리며 탐색에는 O(n)이 걸린다. 맨 앞의 노드를 head, (맨 뒤의 노드를 tail이)라고 하며, 각 노드는 prev 포인터, next 포인터와 데이터를 가진다.
      • 싱글 연결 리스트: next 포인터만 가진다.
      • 이중 연결 리스트: next 포인터와 prev 포인터를 가진다.
      • 원형 이중 연결 리스트: 이중 연결리스트와 같지만 마지막 노드의 next 포인터가 head 노드를 가리키는 것이다.
    • 배열: (C++)같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다. 중복을 허용하고 순서가 있다. 정적 배열의 경우 탐색이 O(1)이 되어 random access가 가능하다. 삽입과 삭제 시에는 O(n)이 걸린다. 배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용한다.
      • 데이터 추가와 삭제를 많이 하는 경우 연결 리스트를, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.
    • 벡터: 동적으로 요소를 할당할 수 있는 동적 배열이다. 컴파일 시점에 개수를 모른다면 벡터를 사용해야 한다. 중복을 허용하고 순서가 있으며 랜덤 접근이 가능하다. 탐색과 맨 앞/뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 앞/뒤가 아닌 요소를 삭제하거나 삽입하는 데 O(n)의 시간이 걸린다.
    • 스택: LIFO 성질을 가진 자료 구조이다. 재귀적인 함수, 깊이 우선 탐색(DFS) 등의 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다. push로 값을 넣고, pop으로 값을 뺀다.
    • 큐: FIFO 성질을 가진 자료 구조이다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다. CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색(BFS), 캐시 등에 사용한다. enqueue로 back에 값을 넣고, dequeue로 front에서 값을 뺀다.
  • 비선형 자료 구조: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조이다. 일반적으로 트리나 그래프를 의미한다.
    • 그래프: 정점과 간선으로 이루어진 자료 구조이다.
      • 어떤 곳에서 어떤 곳으로 무언가를 통해 간다고 했을 때, ‘어떤 곳’은 정점(Vertex)이고, ‘무언가’는 간선(Edge)이다. 간선의 방향성이 없다면 ‘무방향 간선’이고, 한 정점에서 다른 정점 방향으로 이동하는 간선이 단방향인 경우 ‘단방향 간선’, 양 방향으로 이동하는 간선이 있을 경우 ‘양방향 간선’이다.
      • 어떤 정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 한다.
      • 정점의 약자는 V 또는 U이다.
      • 가중치: 간선과 정점 사이에 드는 비용이다.
    • 트리: 그래프 중 하나로 그래프의 특징처럼 정점과 간서으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 트리의 특징은 다음과 같다.
      1. 부모, 자식 계층 구조를 가진다. 같은 경로 상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 된다.
      2. V - 1 = E라는 특징이 있다. 이때 E는 간선 수, V는 노드 수이다.
      3. 임의의 두 노드 사이의 경로는 ‘유일무이’하게 ‘존재’한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.
        • 루트 노드: 가장 위에 있는 노드를 뜻한다. 해당 루트를 통해 탐색을 시작한다.
        • 내부 노드: 루트 노드의 리프 노드 사이에 있는 노드이다.
        • 리프 노드: 자식 노드가 없는 노드이다.
      • 깊이: 트리에서의 깊이는 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리이다. 루트 노드는 깊이가 0이다.
      • 높이: 트리의 높이는 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리이다. 루트 노드만 있는 경우 높이는 0이 된다.
      • 레벨: 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 지닌다. 루트 노드를 레벨 0으로 두는 경우도 있고 레벨 1로 두는 경우도 있다.

      • 서브 트리: 트리 내의 하위 집합을 서브트리라고 한다. 트리 내에 있는 부분집합이라고 볼 수도 있다.

      • 이진 트리: 자식의 노드 수가 두 개 이하(최대 두 개)인 트리이다.
        • 정이진 트리(Full Binary Tree): 자식 노드가 0 또는 2개인 이진 트리이다.
        • 완전 이진 트리(Complete Binary Tree): 왼쪽에서부터 채워져 있는 이진 트리이다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
        • 변질 이진 트리(Degenerate Binary Tree): 자식 노드가 하나밖에 없는 이진 트리이다.
        • 포화 이진 트리(Perfect Binary Tree): 모든 노드가 꽉 차 있는 이진 트리이다.
        • 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 노드 차이가 1 이하인 이진 트리이다. map, set를 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나이다.
      • 이진 탐색 트리(Binary Search Tree): 노드의 오른쪽 하위 트리에는 ‘노드 값보다 큰 값’이 있는 노드만 포함되고, 왼쪽 하위 트리에는 ‘노드 값보다 작은 값’이 들어 있는 트리이다. 각 하위 트리에도 같은 성질이 적용된다. 보통 요소를 찾을 때 BST의 경우 O(logn)이 걸리지만, 최악의 경우 O(n)이 걸릴 수도 있다.
        • 최악의 경우 O(n)이 걸리는 이유는, 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 때문이다.
      • AVL 트리: Adelson-Velsky and Landis Tree로, BST가 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 BST이다. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다. 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.
      • 레드 블랙 트리: 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며 이는 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용된다. C++ STL의 set, multiset, map, multimap이 레드 블랙 트리를 이용하여 구현되어 있다. ‘모든 리프 노드와 루트 노드는 블랙이고, 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.’ 등의 규칙을 기반으로 균형을 잡는 트리이다.
    • 힙: 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리이다.
      • 최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 각 자식의 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
      • 최소힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야 한다. 각 자식의 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
      • 힙에는 어떤 값이 들어와드 특정 힙의 규칙을 지키게 만들어져 있다.
        • 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어져 삽입한다. 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환함으로써 힙의 성질을 만족시킨다.
        • 최대힙/최소힙에서 최대값/최소값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 힙을 재구성한다.
    • 우선순위 큐: 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조이다. 힙을 기반으로 구성된다.
    • 맵: 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조이다. {'naver': 0, 'google': 1} 식으로 string : int 형태로 값을 할당해야 할 때 map을 사용한다. 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다. C++에서 사용할 경우 map<string, int> 형태로 사용한다. 해시 테이블을 구현할 때 쓰며, 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map 두 형태가 있다. C++에서 맵을 순회할 때 key에 해당하는 값을 first, key에 매핑된 value를 second로 탐색 가능하다.
    • 셋: Set는 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소 없이 오로지 희소한(Unique) 값만 저장하는 자료 구조이다.
    • 해시 테이블: 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현한다.

데이터베이스

  • Database: 일정한 규칙, 혹은 규약을 통해 구조화되어 저장되는 데이터의 모음이다.
  • DBMS: DataBase Management System은 해당 데이터베이스를 제어, 관리하는 통합 시스템으로, 데이터베이스 안에 있는 데이터들은 특정 DBMS마다 정의된 쿼리 언어를 통해 삽입, 삭제, 수정, 조회 등을 수행할 수 있다. DB는 실시간 접근과 동시 공유가 가능하다. MySQL 등이 있다.
    • 응용 프로그램 <-> DBMS <-> 데이터베이스
  • Entity(엔터티): 사람, 장소, 물건, 사건, 개념 등 여러 개의 속성을 지닌 명사이다. 서비스의 요구 사항에 맞춰 속성이 정해진다.
    • 약한 엔터티: 혼자서는 존재하지 못하고 다른 엔터티의 존재 여부에 따라 종속적인 엔터티
    • 강한 엔터티: 혼자서 존재할 수 있는 엔터티
  • Relation(릴레이션): 데이터베이스에서 정보를 구분하여 저장하는 기본 단위이다. 데이터베이스는 ‘엔터티에 관한 데이터’를 릴레이션 하나에 담아서 관리한다.
    • 단과대학 엔터티는 DB에서 관리될 때 릴레이션으로 변화되어 관리된다. 릴레이션은 관계형 데이터베이스에서는 테이블이라고 하며, NoSQL 데이터베이스에서는 컬렉션이라고 한다.
      • ‘경희대학교’라는 데이터베이스에는 ‘이과대학’이라는 릴레이션이 있고, 그 릴레이션에는 속성 값으로 ‘학과명, 정원, …’ 등의 속성이 있다.
  • 테이블과 컬렉션: 데이터베이스의 종류는 크게 관계형 데이터베이스와 NoSQL 데이터베이스로 나눌 수 있다.
    • 관계형 데이터베이스(MySQL): Record-Table-Database -> 레코드가 쌓여 테이블이 되고, 테이블이 쌓여 데이터베이스가 된다.
    • NoSQL 데이터베이스(MongoDB): Document-Collection-Database
  • Attribute(속성): 릴레이션에서 관리하는 구체적이며 고유한 이름을 갖는 정보이다. ‘자동차’ 엔터티의 속성은 차 번호, 바퀴 수, 차 색깔, 차종 등이 있다. 이 중에서 서비스의 요구 사항을 기반으로 관리해야 할 필요가 있는 속성들만 엔터티의 속성이 된다.
  • Domain(도메인): 릴레이션에 포함된 각각의 속성들이 가질 수 있는 값의 집합니다. 성별이라는 속성이 있다면, 성별이 가질 수 있는 도메인은 {남자, 여자}라는 집합이다.
  • Field와 Record/Tuple(필드와 레코드/튜플) member |name|age| |:—:|:—:| |mukho|26| |muk|22|
    • member 테이블은 ‘이름’과 ‘나이’ 속성을 가지고 있으며, ‘name’과 ‘age’ 필드를 가진다. 테이블에 쌓이는 행(row) 단위의 데이터를 레코드라고 하며, 레코드는 튜플이라고도 한다.

  • 위의 member 테이블을 MySQL로 구현하려면 다음과 같은 코드를 입력하면 된다.

      CREATE TABLE member(
      name VARCHAR(20) NOT NULL,
      age INT NOT NULL,
      PRIMARY KEY (name)
  );
  • 필드 타입: 필드는 타입을 가진다.
    • 숫자: TINYINT(1byte), SMALLINT(2bytes), MEDIUMINT(3bytes), INT(4bytes), BIGINT(8bytes)
    • 날짜: DATE, DATETIME, TIMESTEMP
      • DATETIME: 날짜 및 시간 지원(1000-01-01 00:00:00 ~ 9999-12-31 23:59:59), 8bytes
      • TIMESTEMP: 날짜 및 시간 지원(1970-01-01 00:00:01 ~ 2038-01-19 03:14:07), 4bytes
    • 문자: CHAR, VARCHAR, TEXT, BLOB, ENUM, SET
      • CHAR: 0~255 사이의 길이를 가질 수 있으며, 레코드를 저장할 때 무조건 테이블을 생성할 때 선언한 길이로 고정된다.
      • VARCHAR: 가변 길이 문자열로, 0~65535의 길이를 가질 수 있다. 저장할 때 길이에 해당하는 바이트 + 길이 기록용 1바이트로 가변된다.
      • TEXT: 큰 문자열 저장에 쓰며, 주로 게시판의 본문을 저장할 때 쓴다.
      • BLOB: 이미지, 동영상 등 큰 데이터 저장에 쓴다. 보통은 AMAZON의 이미지 호스팅 서비스인 S3 등 서버에 파일을 올리고 파일에 관한 경로를 VARCHAR로 저장한다.
      • ENUM: 문자열을 열거한 타입이다. ENUM(‘xs’, ‘s’, ‘m’, ‘l’, ‘xl’) 형태로 쓰이고, 쓸 때는 enum[0, 1, …, n] 꼴로 사용한다. 단일 선택만 가능하고 ENUM 리스트에 없는 값을 입력하면 공백이 삽입된다.
      • SET: ENUM과 비슷하지만 여러 개의 데이터를 선택할 수 있고 비트 단위의 연산을 할 수 있으며 최대 64개의 요소를 집어넣을 수 있다.
  • 관계: 데이터베이스의 테이블은 하나만 있는 것이 아니다. 여러 개의 테이블이 있고 이러한 테이블은 서로의 관계가 정의되어 있다.
    • 1:1 관계, 1:N 관계, N:M 관계가 있다. 이때, N:M 관계는 테이블 두개를 직접적으로 연결해서 구축하지는 않고, 1:N과 1:M이라는 관계를 갖는 테이블 2개로 나눠서 설정한다.
  • 키: 테이블 간의 관계를 조금 더 명확하게 하고 테이블 자체의 인덱스를 위해 설정된 장치이다.
    • 슈퍼키(Super Key): 각 레코드를 유일하게 식별할 수 있는 키이다. 이하 대체키까지의 속성들은 모두 유일성(중복되는 값이 없음)을 만족한다.
    • 후보키(Candidate Key): 기본키가 될 수 있는 후보들이다. 이하 대체키까지의 속성들은 모두 최소성(필드를 조합하지 않고 최소 필드만 써서 키를 형성할 수 있는 것)을 만족한다.
    • 기본키(Primary Key,PK): 후보키 중 선택된 키이다. 유일성과 최소성을 만족하는 키이다. 기본키에 해당하는 속성 데이터들은 서로 중복되면 안된다. 여러 속성을 조합한 {name, age} 꼴의 복합키도 기본키로 설정할 수는 있지만 최소성을 만족하지 못한다.

    • 대체키(Alternate Key): 후보키 중 기본키가 아닌 모든 키들이다.

    • 자연키: 중복되지 않는 것들을 데이터로 가지는 키로, 언젠가는 변하는 속성을 가진다.

    • 인조키: 유저 순번’과 같이 인위적으로 생성한 키이다. 자연키와는 대조적으로 변하지 않는다.

    • 외래키(Foreign Key,FK): 라고 한다. 다른 테이블의 기본키를 그대로 참조하는 값으로 개체와의 관계를 식별하는 데 사용한다. 외래키는 중복되어도 무방하다.
  • ERD: Entity Relationship Diagram으로, 데이터베이스를 구축할 때 가장 기초적인 뼈대 역할을 하며, 릴레이션 간의 관계를 정의한 것이다. 어떤 서비스를 구축할 때 가장 먼저 신경써야 할 부분이다.
    • ERD는 시스템의 요구 사항을 기반으로 작성되며, 이를 기반으로 데이터베이스를 구축한다. 구축 이후에도 디버깅 또는 비즈니스 프로세스 재설계가 필요한 경우 설계도 역할을 담당하기도 한다.
    • 관계형 구조로 표현할 수 있는 데이터를 구성하는 데 유용할 수 있지만, 비정형 데이터를 충분히 표현할 수 없다.
  • 정규화: 릴레이션 간의 잘못된 종속 관계로 인해 데이터베이스 이상 현상이 일어나서 이를 해결하거나, 저장 공간을 효율적으로 사용하기 위해 릴레이션을 여러 개로 분리하는 과정이다.
    • 이상 현상(Anomaly)
      • 삽입 이상: 특정 데이터가 존재하지 않아 중요한 데이터를 데이터베이스에 삽입할 수 없을 때 발생한다.
      • 삭제 이상: 특정 정보를 삭제하면 원치 않는 정보도 삭제되는 현상이다.
      • 업데이트 이상: 테이블의 특정 데이터를 업데이트 했는데 정상적으로 변경되지 않은 경우나 너무 많은 행을 업데이트 하는 것이다.
    • 정규화 과정은 정규형 원칙을 기반으로 정규형을 만들어가는 과정이며, 정규화된 정도는 정규형(NF, Normal Form)으로 표현한다. 기본 정규형인 제1정규형, 제2정규형, 제3정규형, 보이스/코드 정규형이 있고, 고급 정규형인 제4정규형, 제5정규형이 있다.
    • 정규형 원칙: 같은 의미를 표현하는 릴레이션이지만 좀 더 좋은 구조로 만들어야 하고, 자료의 중복성은 감소해야 하고, 독립적인 관계는 별개의 릴레이션으로 표현해야 하며, 각각의 릴레이션은 독립적인 표현이 가능해야 한다.
    • 제1정규형: 릴레이션의 모든 도메인이 더 이상 분해될 수 없는 원자값(Atomic Value)만으로 구성되어야 한다. 릴레이션의 속성 값 중에서 1개의 기본키에 대해 2개 이상의 값을 가지는 반복 집합이 있어서는 안된다.
    • 제2정규형: 릴레이션이 제1정규형이고, 부분 함수의 종속성을 제거한 형태입니다. 부분 함수의 종속성 제거는 기본키가 아닌 모든 속성이 기본키에 완전 함수 종속적인 것을 말합니다. 릴레이션을 분리할 때 동등한 릴레이션으로 분해해야 하고, 정보 손실이 발생하지 않는 무손실 분해로 분해되어야 한다.
    • 제3정규형: 릴레이션이 제2정규형이고, 기본키가 아닌 모든 속성이 이행적 함수 종속을 만족하지 않는 상태이다.
      • 이행적 함수 종속: A->B와 B->C가 존재하면 논리적으로 A->C가 성립하는데, 이때 집합 C가 집합 A에 이행적으로 함수 종속이 되었다고 한다.
    • 보이스/코드 정규형(BCNF): 릴레이션이 제3정규형이고, 결정자가 후보키가 아닌 함수 종속 관기를 제거하여 릴레이션의 함수 종속 관계에서 모든 결정자가 후보키인 상태를 말한다.
      • 결정자: 함수 종속 관계에서 특정 종속자를 결정짓는 요소로, X->Y에서 X는 결정자, Y는 종속자이다.
    • 정규화를 한다고 성능이 100% 좋아지지는 아니며 오히려 나빠질수도 있다. 서비스에 따라 정규화 또는 비정규화 과정을 진행해야 한다.
  • 트랜잭션: 데이터베이스에서 하나의 논리적 기능을 수행하기 위한 작업의 단위를 말하며 데이터베이스에 접근하는 방법은 쿼리이므로, 여러 개의 쿼리들을 하나로 묶는 단위를 말한다.
    • ACID 특징
      • Actomicity(원자성): 트랜잭션과 관련된 일이 모두 수행되었거나 되지 않았거나를 보장하는 특징이다.
        • 트랜잭션 단위로 여러 로직들을 묶을 때 외부 API를 호출하는 것이 있으면 안된다.
        • Commit: 여러 쿼리가 성공적으로 처리되었다고 확정하는 명령어로, 변경된 내용을 모두 영구적으로 저장한다.
        • Rollback: 트랜잭션으로 처리한 하나의 묶음 과정을 일어나기 전으로 돌리는 명령어이다.
        • 트랜잭션 전파: 트랜잭션 관련 메소드의 호출을 하나의 트랜잭션에 묶이도록 하는 것이다.
      • Consistency(일관성): 허용된 방식으로만 데이터를 변경해야 하는 것이다.
        • 데이터베이스에 기록된 모든 데이터는 여러 가지 조건, 규칙에 따라 유효함을 가져야 한다.
      • Isolation(격리성): 트랜잭션 수행 시 서로 끼어들지 못하는 것이다.
        • 복수의 병렬 트랜잭션은 서로 격리되어 마치 순차적으로 실행되는 것처럼 작동되어야 하고, 데이터베이스는 여러 사용자가 같은 데이터에 접근할 수 있어야 한다.
        • 격리성은 여러 개의 격리 수준으로 나누어 격리성을 보장한다.
          • READ_UNCOMMITED, READ_COMMITTED, REPEATABLE_READ, SERIALIZABLE
          • 동시성 <-> 격리성. /더티 리드/반복 가능하지 않은 조회/팬텀 리드/
          • 팬텀 리드: 한 트랜잭션 내에서 동일한 쿼리를 보냈을 때 해당 조회 결과가 다른 경우이다.
          • 반복 가능하지 않은 조회: 한 트랜잭션 내의 같은 행에 두 번 이상 조회가 발생했는데, 그 값이 다른 경우이다.
          • 더티 리드: 반복 가능하지 않은 조회와 유사하며, 한 트랜잭션이 실행 중일 때 다른 트랜잭션에 의해 수정되었지만 아직 ‘커밋되지 않은’ 행의 데이터를 읽을 수 있을 때 발생한다.
          • SERIALIZABLE: 트랜잭션을 순차적으로 진행시키는 것으로, 교착 상태가 일어날 확률도 많고 가장 성능이 떨어지는 격리 수준이다.
          • REPEATABLE_READ: 하나의 트랜잭션이 수정한 행을 다른 트랜잭션이 수정할 수 없도록 막아주지만 새로운 행을 추가하는 것은 막지 않는다.
          • READ_COMMITED: 가장 많이 사용되는 격리 수준이며 MySQL8.0, SQL Server, Oracle 등에서 기본값으로 설정되어 있다. READ_UNCOMMITTED와는 달리 다른 트랜잭션이 커밋하지 않은 정보는 읽을 수 없기 때문에 커밋 완료된 데이터에 대해서만 조회를 허용한다. 하지만 어떤 트랜잭션이 접근한 행을 다른 트랜잭션이 수정할 수 있어, 그 행을 다시 읽을 때 다른 내용이 발견될 수 있다.
          • READ_UNCOMMITTED: 가장 낮은 격리 수준으로, 하나의 트랜잭션이 커밋되기 이전에 다른 트랜잭션에 노출되는 문제가 있지만 가장 빠르다. 데이터 무결성을 위해 되도록이면 사용하지 않는 것이 이상적이고, 거대한 양의 데이터를 ‘어림잡아’ 집계하는 데 사용하면 좋다.
      • Durability(지속성): 성공적으로 수행된 트랜잭션은 영원히 반영되어야 한다. 데이터베이스에 시스템 장애가 발생해도 원래 상태로 복구하는 회복 기능이 있어야 한다는 의미로 ‘체크섬, 저널링, 롤백’ 등의 기능을 제공한다.
        • 체크섬: 중복 검사의 한 형태로, 오류 정정을 통해 송신된 자료의 무결성을 보호하는 단순한 방법이다.
        • 저널링: 파일 시스템 또는 데이터베이스 시스템에 변경 사항을 반영(Commit)하기 전에 로깅하거나, 트랜잭션 등 변경 사항에 대한 로그를 남기는 것이다.
  • 무결성: 데이터의 정확성, 일관성, 유효성을 유지하는 것으로 무결성이 유지되어야 데이터베이스에 저장된 데이터 값과 그 값에 해당하는 현실 세계의 실제 값이 일치하는지에 대한 신뢰가 생긴다.
    • 개체 무결성: 기본키로 선택된 필드는 빈 값을 허용하지 않는다.
    • 참조 무결성: 서로 참조 관계에 있는 두 테이블의 데이터는 항상 일관된 값을 유지해야 한다.
    • 고유 무결성: 특정 속성에 대해 고유한 값을 가지도록 조건이 주어진 경우 그 속성 값은 모두 고유한 값을 가진다.
    • NULL 무결성: 특정 속성 값에 NULL이 올 수 없다는 조건이 주어진 경우 그 속성 값은 NULL이 될 수 없다.
  • 관계형 데이터베이스(RDBMS): 행과 열을 가지는 표 형식 데이터를 저장하는 형태의 데이터베이스를 가리키며 SQL이라는 언어를 써서 조작한다. 표준 SQL을 지키기는 하나 각각의 제품에 특화시킨 SQL을 사용한다.
    • MySQL: 대부분의 운영체제와 호환되며 현재 가장 많이 사용하는 데이터베이스이다.
      • C, C++로 만들어졌으며 대용량 데이터베이스를 위해 설계되어 있다. 롤백, 커밋, 이중 암호 지원 보안 등의 기능을 제공한다.
      • MyISAM 인덱스 압축 기술, B-트리 깆반의 인덱스, 스레드 기반의 메모리 할당 시스템, 매우 빠른 조인, 최대 64개의 인댁스를 제공한다.
    • PostgreSQL: MySQL 다음으로 개발자들이 선호하는 데이터베이스이다.
      • 디스크 조각이 차지하는 영역을 회수할 수 있는 장치인 VACUUM이 특징이다. 최대 테이블의 크기는 32TB이고 SQL뿐만 아니라 JSON을 이용해서 데이터에 접근할 수 있다.
      • 지정 시간에 복구하는 기능, 로깅, 접근 제어, 중첩된 트랜잭션, 백업 등을 할 수 있다.
  • NoSQL 데이터베이스: Not only SQL이라는 슬로건에서 태어났으며 SQL을 사용하지 않는 데이터베이스다.
    • MongoDB: JSON을 통해 데이터에 접근할 수 있고, Binary JSON(BSON)로 데이터가 저장되며, 와이어드타이어 엔진이 기본 스토리지 엔진으로 장착된, 키-값 데이터 모델에서 확장된 document 기반의 데이터베이스다.
      • 확장성이 뛰어나며 빅데이터를 저장할 때 성능이 좋고 고가용성과 샤딩, 레플리카셋을 지원한다. 스키마를 정해 놓지 않고 데이터를 삽입할 수 있기 때문에 다양한 도메인의 데이터베이스를 기반으로 분석하거나 로깅 등을 구현할 때 강점을 보인다.
      • 도큐먼트를 생성할 때마다 다른 컬렉션에서 중복된 값을 지니기 힘든 유니크한 값인 ObjectID가 생성된다.
        • ObjectID는 기본키로, 유닉스 시간 기반의 timestemp(4 bytes), random value(5 bytes), counter(3 bytes)로 이루어져 있다.
    • redis: 인메모리 데이터베이스이자 키-값 데이터 모델 기반의 데이터베이스이다.
      • 기본적인 데이터 타입은 문자열(string)이며 최대 512MB까지 저장할 수 있다. 셋(set), 해시(hash) 등을 지원한다.
      • pub/sub 기능을 통해 채팅 시스템, 다른 데이터베이스 앞단에 두어 사용하는 캐싱 계층, 단순한 키-값이 필요한 세션 정보 관리, 정렬된 셋(sorted set) 자료구조를 이용한 실시간 순위표 서비스에 사용한다.
  • 인덱스: 데이터를 빠르게 찾을 수 있는 하나의 장치이다. 인덱스를 설정하면 테이블 안에 내가 찾고자 하는 데이터를 빠르게 찾을 수 있다.
    • B-트리: 인덱스는 보통 B-트리라는 자료구조로 이루어져 있다. 이는 루트 노드, 리프 노드, 그리고 루트 노드와 리프 노드 사이에 있는 브랜치 노드로 나뉜다.
      • 어떤 값을 탐색할 때 전체 테이블을 탐색하는 것이 아니라 ‘해당 데이터가 있을 법한’ 노드를 우선적으로 탐색한다.
    • 인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수확장성 때문이다.

      • 대수확장성: 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미한다. 인덱스의 깊이가 1 증가할 때마다 최데 인덱스 항목의 수는 4배씩 증가한다. 트리 깊이가 10이면 100만 개의 레코드를 검색할 수 있다. 실제 인덱스는 이것보다 훨씬 더 효율적이므로 인덱스는 효율적이다.

        트리 깊이 인덱스 항목의 수
        3 64
        4 256
        5 1,024
        6 4,096
        7 16,384
        8 65,536
        9 262,144
        10 1,048,576
  • 조인(Join): 하나의 테이블이 아닌 2개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것이다. MySQL에서는 JOIN이라는 쿼리로, MongoDB에서는 lookup이라는 쿼리로 이를 처리할 수 있다.
    • MongoDB에서 lookup은 되도록이면 사용하면 안된다. RDBMS보다 성능이 떨어지기 때문이다. 여러 테이블을 조인하는 작업이 많을 경우 RDBMS를 사용하는 것이 낫다.
    • 내부 조인(Inner Join): 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기한다.(교집합) 
        SELECT * FROM TableA A INNER JOIN TableB as B ON A.key = B.key;
    • 왼쪽 조인(Left Outer Join): 오른쪽 테이블의 일치하는 부분의 레코드와 함께 왼쪽 테이블을 기준으로 완전한 레코드 집합을 만든다. 오른쪽 테이블에 일치하는 항목이 없으면 해당 값은 null이 된다. 
        SELECT * FROM TableA A LEFT JOIN TableB as B ON A.key = B.key;
    • 오른쪽 조인(Right Outer Join): 왼쪽 테이블의 일치하는 부분의 레코드와 함께 오른쪽쪽 테이블을 기준으로 완전한 레코드 집합을 만든다. 왼쪽 테이블에 일치하는 항목이 없으면 해당 값은 null이 된다. 
        SELECT * FROM TableA A RIGHT JOIN TableB as B ON A.key = B.key;
    • 합집합 조인(Full Outer Join): 완전 외부 조인이라고도 하며, 양쪽 테이블에서 일치하는 레코드와 함께 왼쪽 테이블과 오른쪽 테이블의 모든 레코드 집합을 생성한다. 이때 일치하는 항목이 없으면 누락된 쪽에 null 값이 포함되어 출력된다. 
        SELECT * FROM TableA A FULL OUTER JOIN TableB as B ON A.key = B.key;

Table of Contents