데이터 베이스 - B Tree
B Tree자식 노드가 최대 두개인 이진 트리와는 다르게 B-Tree 는 M 개의 자식 노드를 가질 수 있다. Node 의 Key 개수가 N 개면 자식 Node 의 개수는 N+1 개다. Node 내 Key 값은 항상 정렬된 상태 여야 한다. Root Node 는 항상 2개 이상의 자식 Node 를 갖는다. 모든 Leaf Node 들은 항상 같은 Level 에 있어야 한다. B treeB-트리는 데이터를 저장하고 검색하기 위한 트리 자료 구조로, 데이터베이스의 인덱스와 파일 시스템 등에서 널리 사용됩니다. B-트리는 각 노드에 여러 개의 자식을 가질 수 있으며, 이를 통해 대량의 데이터를 효율적으로 저장할 수 있습니다. B-트리는 일반적으로 다음과 같은 특징을 가집니다. 균형 트리: B-트리는 노드의 균형을 유지하여 검색, 삽입, 삭제 연산에 대한 시간 복잡도를 보장합니다. 각 노드는 여러 개의 자식을 가지며, 자식 노드의 개수가 비슷한 것이 특징입니다. 다단계 인덱스: B-트리는 매우 높은 성능으로 인덱스 검색을 수행하므로 대부분의 데이터베이스에서 인덱스 구조로 사용됩니다. B-트리는 다단계 인덱스를 구성하여 빠른 검색 성능을 제공합니다. 블록 단위 입출력: B-트리는 블록 단위로 입출력을 수행하여 입출력 연산을 최소화합니다. 이는 데이터베이스나 파일 시스템에서 대량의 데이터를 다룰 때 매우 효과적입니다. 삽입, 삭제 연산: B-트리는 노드의 균형을 유지하여 삽입, 삭제 연산의 시간 복잡도를 로그 시간으로 보장합니다. 이는 대규모 데이터를 다룰 때 매우 효과적입니다. B-트리는 데이터베이스, 파일 시스템, 검색 엔진 등에서 널리 사용되는 자료 구조입니다. 또한 B+트리와 같은 변형 형태도 있으며, 이러한 변형 형태는 대규모 데이터를 다룰 때 더욱 효과적입니다. B tree 검색 알고리즘 루트 노드에서 시작합니다. 현재 노드에서 키 값을 검색합니다. 검색한 키 값이 현재 노드에 있으면 해당 포인터를 따라 해당 자식 노드로 이동합니다. 검색한 키 값이 현재 노드에 없으면, 키 값이 들어갈 위치를 찾고 해당 위치의 자식 노드로 이동합니다. 자식 노드로 이동한 후, 2단계로 돌아가서 검색을 계속합니다.