변수의 기록

B-Tree와 데이터베이스 인덱스1. B-Tree의 시간 복잡도B-Tree는 self-balancing 트리로, 다음과 같은 시간 복잡도를 가진다:탐색 (Search): O(logₙ N)삽입 (Insert): O(logₙ N)삭제 (Delete): O(logₙ N)여기서 N은 전체 키의 수, n은 자식 노드의 수(= branching factor)이다.즉, 자식 수가 많을수록 log의 밑이 커지므로 깊이가 얕아지고 탐색 횟수가 줄어든다.예시:자식 노드 수가 100일 경우, 1억 개의 키를 탐색할 때 최대 4단계만으로도 검색 가능.2. Secondary Storage의 특징하드디스크(HDD) 또는 SSD와 같은 보조 기억장치(Secondary Storage)는 다음과 같은 특징을 가진다:접근 속도는 RAM..

B-Tree : 구조, 작동 원리, DB에서의 활용1. B-Tree란?B-Tree는 **Binary Search Tree(이진 탐색 트리)**를 일반화한 트리 자료구조입니다. 데이터베이스와 파일 시스템 등, 디스크 기반의 저장 시스템에서 대량의 데이터를 효율적으로 검색, 삽입, 삭제할 수 있도록 설계된 구조입니다.왜 B-Tree가 필요한가?일반 이진 탐색 트리는 삽입 순서에 따라 한쪽으로 치우칠 수 있어 최악의 경우 O(n) 시간복잡도를 가집니다.반면 B-Tree는 항상 균형을 유지하며, 트리의 높이를 제한해 모든 연산이 O(log n) 시간에 수행됩니다.특히 디스크 I/O 비용이 큰 환경에서 적은 횟수의 블록 접근으로 원하는 데이터를 찾을 수 있도록 설계되었습니다.2. B-Tree의 구조기본 구성M차 ..