JUNGLE 240329 (W02)
KRAFTON JUNGLE Week 02
1. Keywords
B-Tree
[8, 14]
/ \
[3, 5] [10, 12]
/ | \ / | \
[1, 2] [4] [9] [11] [13, 15]
- 데이터 베이스와 파일 시스템에서 사용되는 트리 자료구조의 일종
- 데이터를 효율적으로 저장하고 탐색하는데 사용
- 매우 큰 데이터 집합을 효율적으로 관리하기 위해 고안
- DB 인덱스 구조나 파일 시스템의 디스크에서 사용되는 인덱스 구조로 널리 사용됨
B-Tree의 특징
- 균형 트리
- 모든 리프 노드가 같은 높이에 있는 균형 이진 트리
- 탐색 시간을 일정하게 유지하여 DB나 파일 시스템 성능 향상
- 다차원 탐색
- 다차원 데이터의 효율적인 탐색 지원
- 각 노드는 여러 키를 저장할 수 있으며, 이를 통해 다차원 데이터의 탐색 수행
- 노드의 차수
- B-Tree의 각 내부 노드는 여러 키를 가질 수 있음
- 이 때 각 노드가 가질 수 있는 키의 개수는 트리의 차수에 의해 결정
- 디스크 기반의 구현
- B-Tree는 주로 디스크 기반의 데이터 구조로 사용
- 디스크에서 데이터를 읽거나 쓰는 데 소요되는 비용을 고려하여 설계
- 자기 균형화
- 삽입과 삭제 연산을 수행할 때 자동으로 균형 유지
- 이를 통해 트리의 높이를 최소화하고 탐색 시간을 일정하게 유지
트라이 (Trie)
(root)
/ \
a b
/|\ \
p p b a
| | | |
p p a t
| |
l n
|
e ($)
- 트리 자료 구조의 일종, 키-값 쌍을 저장하고 검색하는 데 사용
- 문자열 검색과 관련된 문제를 해결하는 데 특히 유용
트라이의 특징
- 접두사 검색
- 문자열의 접두사 검색에 특히 효율적
- 트라이의 각 노드는 특정 문자열의 한 글자
- 루트에서 해당 문자열까지의 경로를 따라가면 해당 문자열을 찾을 수 있음
- 공통 접두사
- 트라이는 키가 공통 접두사를 가지고 있는 경우에도 메모리를 효율적으로 저장
- 공통된 접두사 부분은 하나의 경로로 공유되므로 메모리를 효율적으로 사용
- 메모리 효율성
- 문자열의 일부가 중복되는 경우에도 메모리를 효율적으로 사용
- 각 노드는 해당 문자열의 한 글자를 나타내므로, 중복되는 부분이 많은 문자열의 경우 다른 자료 구조보다 효율적
- 문자열 검색 및 삽입 시간
- 문자열 검색과 삽입이 문자열의 길이에 비례하여 빠르게 수행
- 트라이의 높이는 문자열의 길이와 관련있으며 각 노드는 상수 시간에 접근 가능
2. CS:APP (1.5 ~ )
프로세서(Processor) vs 프로세스(Process)
- 프로세서는 컴퓨터 시스템에서 데이터를 처리하고 명령어를 실행하는 장치
- 주로 CPU를 가리키며, 컴퓨터 시스템에서 계산과 연산을 수행하는 핵심적인 하드웨어
- 프로세스는 프로그램의 실행 단위, 여러 프로세스가 동시에 실행
- 메모리에 로드되어 CPU에 의해 실행되는 프로그램의 인스턴스, 실행 중인 프로그램의 상태와 실행 정보를 가짐
- 각 프로세스는 고유한 메모리 공간, 자원, 실행 상태를 가지며 운영 체제에 의해 관리
운영 체제
- 프로세스 (Process)
- 실행 중인 프로그램
- 각 프로세스는 독립적인 메모리 공간을 가지며, 운영체제로부터 실행을 위해 할당받은 자원 사용
- 각 프로세스는 하나 이상의 스레드로 구성
- 가상 메모리 (Virtual Memory)
- 실제 물리적인 메모리(RAM)를 확장하여 프로세스가 더 큰 메모리 공간을 사용할 수 있도록 하는 메모리 관리 기술
- 프로세스에게 실제 메모리 주소가 아닌 가상 주소 공간을 제공하여, 물리적 메모리의 효율적인 사용과 메모리 보호 달성
- 가상 메모리는 페이지 단위로 관리되며 필요에 따라 물리적 메모리와 디스크 사이에서 페이지 스왑
- 스레드 (Thread)
- 프로세스 내에서 실행되는 실행 단위
- 하나의 프로세스는 여러 개의 스레드를 가질 수 있으며, 각 스레드는 프로세스의 자원을 공유
- 프로세스의 코드, 데이터, 힙 등의 자원을 공유하며, 각 스레드는 독립적으로 실행
- 파일 (File)
- 데이터를 저장하는 논리적인 단위
- 운영체제는 파일을 관리하고, 파일을 읽고 쓰는 인터페이스 제공
- 파일은 디스크 등의 보조 저장 장치에 저장되며, 응용 프로그램은 파일 시스템을 통해 파일을 관리
가상 메모리
운영 체제에서 제공하는 메모리 관리 기술 중 하나로, 프로세스가 물리적인 메모리보다 큰 메모리 공간을 사용할 수 있도록 하는 기술
- 가상 주소 공간 (Virtual Address Space)
- 각 프로세스에게 제공되는 가상 주소 공간은 프로세스가 사용할 수 있는 주소의 범위
- 가상 주소 공간은 주로 텍스트, 데이터, 힙, 스택 등의 섹션으로 구성
- 이러한 섹션은 프로세스의 실행 및 데이터 저장에 사용
- 페이징 (Paging)
- 가상 메모리는 페이징 기술을 사용하여 물리적인 메모리와 가상 주소 공간 간의 매핑을 관리
- 프로세스의 가상 주소 공간은 페이지로 나뉘어져 있으며, 물리적인 메모리도 페이지 단위로 관리
- 페이지 교체 (Paging Replacement)
- 가상 메모리가 물리적인 메모리보다 작은 경우, 페이지 교체 알고리즘이 사용
- 페이지 교체 알고리즘은 페이지 부재가 발생했을 때 어떤 페이지를 디스크에서 메모리로 로드할지 결정
- 스와핑 (Swapping)
- 프로세스의 전체 가상 주소 공간이 물리적인 메모리에 들어갈 수 없는 경우, 스와핑 발생
- 스와핑은 메모리에 올라와 있는 페이지를 디스크로 옮기고, 새로운 페이지를 메모리로 가져오는 과정
- 스와핑은 물리적인 메모리와 디스크 사이의 데이터 전송을 관리
- 페이지 테이블 (Page Table)
- 가상 주소와 물리적인 주소 간의 매핑 정보를 저장하는 자료구조
- 각 프로세스마다 페이지 테이블이 별도로 존재하며, 가상 주소를 물리적인 주소로 변환하는 데 사용
- 페이지 테이블은 가상 주소의 일부를 검색하여 해당 페이지의 물리적인 주소를 찾음
가상 주소 공간
- 프로세스가 실행될 때 해당 프로세스에게 할당되는 가상적인 주소 공간
- 프로세스가 메모리를 관리하고 사용하는 데 필요한 모든 주소 범위를 포함
- 텍스트(코드) 섹션
- 프로그램 코드가 저장되는 공간
- CPU가 실행하는 명령어들이 포함되어 있으며, 보통 읽기 전용
- 실행 파일의 명령어들을 포함하고, 프로세스가 실행되면 CPU가 여기에 있는 명령어들을 읽어와 실행
- 데이터 섹션
- 초기화된 및 초기화되지 않은 데이터가 저장되는 공간
- 초기화된 데이터는 프로그램에서 명시적으로 초기화된 변수들을 저장
- 초기화되지 않은 데이터는 프로그램에서 초기화되지 않은 전역 변수들을 저장
- 프로그램이 실행될 때 초기화되며, 읽기/쓰기 권한을 가짐
- 힙(Heap) 섹션
- 동적으로 할당되는 메모리가 저장되는 공간
- 프로그램이 실행 중에 동적으로 할당된 메모리를 관리하는 데 사용
- 동적으로 할당된 메모리는 일반적으로
malloc(),calloc(),realloc()과 같은 함수를 사용하여 힙에서 할당되고 해제됨
- 스택(Stack) 섹션
- 지역 변수 및 함수 호출 시 사용되는 데이터가 저장되는 공간
- LIFO 방식으로 동작하며, 함수 호출 시 매개변수, 복귀 주소 등의 정보가 저장
- 프로그램이 실행될 떄 자동으로 생성되며, 스택 프레임이라는 구조로 함수 호출 정보를 저장
