재민의 IT 공부기록

B-tree와 B+tree는 데이터베이스와 파일 시스템에서 데이터를 효율적으로 저장하고 검색하기 위해 사용되는 트리 구조이다. 두 트리는 여러 면에서 비슷하지만 몇 가지 중요한 차이점이 있다. 구조적 측면:B-tree는 모든 노드가 키와 데이터를 모두 가질 수 있다. 리프 노드와 내부 노드 모두 데이터 항목을 포함할 수 있다.B+tree는 내부 노드는 키와 데이터 포인터를 가지지만 실제 데이터는 리프 노드에만 저장된다. 리프 노드가 연결 리스트로 구성되어 있어 리프 노드 간의 순차 접근이 용이하다.검색 성능 측면:B-tree는 키를 찾기 위해 내부 노드와 리프 노드를 모두 탐색해야 할 수 있다.B+tree는 데이터가 리프 노드에만 있으므로 검색 작업이 리프 노드에서 끝난다. 또한 리프 노드가 연결 리스트..

B-트리의 필요성( BST와 AVL 트리의 문제점)BST (Binary Search Tree)는 편향될 경우 높이가 최대 N이 될 수 있다. 이는 탐색, 삽입, 삭제 시 최악의 경우 O(N)의 시간 복잡도를 초래한다. AVL 트리는 항상 균형을 유지하지만, 높이는 여전히 O(log N)이다. 이는 메모리 접근 속도가 느린 대용량 데이터베이스 시스템에서는 비효율적이다. BST와 AVL 트리는 메모리 내에서 사용될 때는 효율적일 수 있지만, 데이터베이스 시스템처럼 대용량 데이터를 다루는 경우에는 디스크 접근이 빈번해질 수 있고, 이는 매우 비용이 크기 때문에 디스크 접근 횟수를 최소화하는 것이 중요하다. B-트리는 이러한 문제를 해결하기 위해 고안되었다.  - B-tree의 특징균형 유지: B-트리는 항상 ..