데이터 베이스 - B Tree

B Tree

자식 노드가 최대 두개인 이진 트리와는 다르게 B-Tree 는 M 개의 자식 노드를 가질 수 있다.

1. Node 의 Key 개수가 N 개면 자식 Node 의 개수는 N+1 개다.
2. Node 내 Key 값은 항상 정렬된 상태 여야 한다.
3. Root Node 는 항상 2개 이상의 자식 Node 를 갖는다.
4. 모든 Leaf Node 들은 항상 같은 Level 에 있어야 한다.

B tree

B-트리는 데이터를 저장하고 검색하기 위한 트리 자료 구조로, 데이터베이스의 인덱스와 파일 시스템 등에서 널리 사용됩니다. B-트리는 각 노드에 여러 개의 자식을 가질 수 있으며, 이를 통해 대량의 데이터를 효율적으로 저장할 수 있습니다.

B-트리는 일반적으로 다음과 같은 특징을 가집니다.

• 균형 트리: B-트리는 노드의 균형을 유지하여 검색, 삽입, 삭제 연산에 대한 시간 복잡도를 보장합니다. 각 노드는 여러 개의 자식을 가지며, 자식 노드의 개수가 비슷한 것이 특징입니다.
• 다단계 인덱스: B-트리는 매우 높은 성능으로 인덱스 검색을 수행하므로 대부분의 데이터베이스에서 인덱스 구조로 사용됩니다. B-트리는 다단계 인덱스를 구성하여 빠른 검색 성능을 제공합니다.
• 블록 단위 입출력: B-트리는 블록 단위로 입출력을 수행하여 입출력 연산을 최소화합니다. 이는 데이터베이스나 파일 시스템에서 대량의 데이터를 다룰 때 매우 효과적입니다.
• 삽입, 삭제 연산: B-트리는 노드의 균형을 유지하여 삽입, 삭제 연산의 시간 복잡도를 로그 시간으로 보장합니다. 이는 대규모 데이터를 다룰 때 매우 효과적입니다.

B-트리는 데이터베이스, 파일 시스템, 검색 엔진 등에서 널리 사용되는 자료 구조입니다. 또한 B+트리와 같은 변형 형태도 있으며, 이러한 변형 형태는 대규모 데이터를 다룰 때 더욱 효과적입니다.

B tree 검색 알고리즘

1. 루트 노드에서 시작합니다.
2. 현재 노드에서 키 값을 검색합니다.
3. 검색한 키 값이 현재 노드에 있으면 해당 포인터를 따라 해당 자식 노드로 이동합니다.
4. 검색한 키 값이 현재 노드에 없으면, 키 값이 들어갈 위치를 찾고 해당 위치의 자식 노드로 이동합니다.
5. 자식 노드로 이동한 후, 2단계로 돌아가서 검색을 계속합니다.

B tree 에서 삽입 알고리즘은 다음과 같습니다.

1. 삽입할 키 값을 루트 노드에서부터 검색합니다.
2. 키 값을 삽입할 위치를 찾습니다.
3. 해당 위치에 새로운 키 값을 삽입합니다.
4. 노드의 키 값이 오름차순으로 유지되도록 키 값을 정렬합니다.
5. 노드의 키 개수가 최대치를 초과하면 노드를 분할합니다.
6. 분할된 노드의 중간 값은 부모 노드에 삽입됩니다.
7. 부모 노드의 키 값도 오름차순으로 유지되도록 키 값을 정렬합니다.
8. 삽입이 완료됩니다.

B-트리에서 삭제 알고리즘

1. 삭제할 키 값을 루트 노드에서부터 검색합니다.
2. 삭제할 키 값을 찾습니다.
3. 삭제할 키 값을 가진 노드가 리프 노드인 경우, 해당 키 값을 삭제합니다.
4. 삭제할 키 값을 가진 노드가 리프 노드가 아닌 경우, 대체 키 값을 찾아서 삭제합니다.
5. 대체 키 값을 가진 노드로 이동하여 2단계로 돌아가서 삭제를 계속합니다.
6. 삭제 후, 노드의 키 개수가 최소치를 초과하지 않도록 노드를 조정합니다.
7. 노드의 키 값이 오름차순으로 유지되도록 키 값을 정렬합니다.
8. 삭제가 완료됩니다.

Key 검색 과정

Root Node 부터 시작해 하향식으로 검색을 수행한다.