B+Tree

·
자료구조&알고리즘
B-TreeB-Tree는 하나의 노드에 여러 데이터가 저장될 수 있다. 따라서 같은 노드 내에서 데이터를 탐색할 때는 포인터를 따라가는 방식이 아니라, 디스크(또는 메모리)에 연속적으로 저장된 인덱스를 순차적으로 확인하는 방식으로 탐색이 이루어진다. 이때, 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.특징예를 들어, 위의 B-Tree 구조에서 33이라는 값이 존재하는지 확인한다고 가정해보자. 루트 노드에는 20, 40이 저장되어 있는 상태이기 때문에 루트 노드에는 해당 값이 존재하지 않아 자식 노드를 가리키는 포인터의 존재 유무를 확인한다. 20과 40 사이의 범위에 해당하는 자식 노드를 가리키는 포인터가 있는 것을 확인했다면, 포인터를 따라가 자식 노드에 도달한다. 자..