ITPE * JackerLab

개요B+Tree는 B-Tree의 확장 구조로, 모든 데이터가 리프 노드(Leaf Node)에 저장되고 내부 노드는 인덱스 역할만 수행하는 균형 다진 트리이다. 데이터베이스와 파일 시스템에서 범위 검색과 순차 접근 성능을 극대화하기 위해 널리 사용된다.1. 개념 및 정의B+Tree는 B-Tree와 유사하지만, 실제 데이터는 리프 노드에만 저장되고 내부 노드는 탐색을 위한 키만 포함하는 구조이다. 또한 리프 노드들이 연결 리스트 형태로 연결되어 있어 범위 검색에 매우 효율적이다.2. 특징항목설명비고리프 집중 저장데이터는 리프에만 존재탐색 단순화연결 리스트 구조리프 노드 간 연결범위 검색 최적화높은 팬아웃하나의 노드에 많은 자식트리 높이 감소한줄 요약: 데이터 접근과 범위 검색에 최적화된 구조이다.3. 구성 ..

개요B-Tree는 다진 탐색 트리(Multi-way Search Tree)의 일종으로, 하나의 노드가 여러 개의 자식 노드를 가질 수 있는 균형 트리 구조이다. 디스크 기반 시스템에서 I/O를 최소화하기 위해 설계되었으며, 데이터베이스와 파일 시스템에서 핵심 인덱스 구조로 널리 사용된다.1. 개념 및 정의B-Tree는 노드가 여러 개의 키와 자식을 가질 수 있도록 설계된 자가 균형 트리로, 트리의 높이를 최소화하여 탐색, 삽입, 삭제 연산을 모두 O(log n) 시간에 수행할 수 있도록 한다. 특히 블록 단위 저장장치(HDD, SSD)에 최적화된 구조이다.2. 특징항목설명비고다진 트리 구조하나의 노드에 여러 키 저장I/O 감소균형 유지모든 리프 노드 동일 깊이성능 안정정렬 상태 유지키가 항상 정렬탐색 효..

개요레드-블랙 트리(Red-Black Tree)는 자가 균형(Self-Balancing)을 유지하는 이진 탐색 트리(BST)의 한 종류로, 삽입과 삭제 연산 시 트리의 높이를 일정하게 유지하여 O(log n)의 시간 복잡도를 보장한다. 주로 표준 라이브러리의 Map, Set 구조 및 데이터베이스 인덱스 구현에 활용된다.1. 개념 및 정의레드-블랙 트리는 각 노드가 색상(빨강 또는 검정)을 가지며, 특정 규칙을 통해 트리의 균형을 유지하는 자료구조이다. AVL 트리보다 삽입/삭제 비용이 낮아 실무에서 널리 사용된다.2. 특징항목설명비고색상 속성각 노드는 Red 또는 Black균형 유지 핵심루트/리프 규칙루트는 항상 Black안정성 확보연속 Red 금지Red 노드의 자식은 Black균형 유지Black Hei..

개요이진 트리(Binary Tree)는 트리(Tree) 자료구조의 한 종류로, 각 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지는 계층적 구조이다. 트리의 기본이자 다양한 트리 기반 알고리즘의 뼈대 역할을 하며, 이진 탐색 트리(BST), 힙(Heap), 트라이(Trie), 표현식 트리 등으로 확장된다. 노드의 위치와 순서가 중요한 구조로, 다양한 순회 알고리즘이 적용된다.1. 이진 트리의 구조와 용어 용어 설명 노드(Node)데이터를 저장하는 기본 단위루트(Root)트리의 시작 노드 (부모 없음)왼쪽 자식(Left Child)루트 기준 왼쪽 하위 노드오른쪽 자식(Right Child)루트 기준 오른쪽 하위 노드리프(Leaf)자식이 없는 노드서브트리(Subtree)특정 노드를 루트로..