읽고 나면 진짜 쉬워지는 자료 구조 - 12. B-트리

개별 값에 접근하는 문제를 확장해 데이터 블록에 접근하는 비용을 다루고, 이런 상황을 다룰 수 있는 새로운 자료 구조인 B-트리

🔖 B-트리 구조

개요

• 한 노드에 여러 데이터 조각을 저장해서 비싼 탐색 비용을 한 번만 지불하면 같은 노드 안에 있는 모든 값을 추출할 수 있게 해준다.

• 일단 노드가 지역 메모리에 저장되면 그 값에 빠르게 접근할 수 있다.

• B-트리는 인덱싱과 키를 결합하면서 탐색 비용을 최소화하는 창의적인 방법을 제공한다.

• B-트리는 트리가 많이 치우치는 경우가 생기지 않도록 트리 연산을 정의하는 방법을 보여주는 예제이기도 하다.

B-트리 구조

• B-트리는 트라이나 쿼드 트리에서 본 개별 키를 저장하는 다중 분기 구조를 응용한다.

• 이 말은 B-트리 내부 노드에 2개보다 훨씬 더 많은 가지를 허용한다는 뜻이다.

• B-트리는 균형 잡힌 자료구조다. 모든 리프 노드는 루트로부터 같은 깊이에 있다.

🔖 12.2 B-트리 탐색하기

탐색 방법

• B-트리와 이진 탐색 트리의 중요한 차이점은 한 노드에서 하나 이상의 키를 확인해야 할 수도 있다는 점이다.

• 각 노드에서 키들을 스캔하면서 원하는 키를 찾거나 목표보다 큰 값을 가진 최초의 키를 찾을 때까지 진행한다.

• 내부 노드에서 목표보다 큰 키를 찾았다면, 적절한 자식으로 이동해 탐색을 계속한다.

🔖 12.3 키 삽입하기

키 삽입 알고리즘

• 알고리즘의 첫 단계에서는 트리를 재귀적으로 탐색하면서 새로운 키를 삽입할 위치를 찾는다.

• 그 과정에서 일치하는 키를 발견하면 해당 키의 데이터를 갱신할 수 있다.

• 일치하는 키가 없으면 리프 노드까지 내려가서 키를 배열에 삽입한다.

🔖 12.4 키 제거하기

키 제거 알고리즘

• 키를 제거하는 건 추가할 때와 비슷하다.

• 우선 트리 아래로 내려간 후, 키를 찾으면 찾은 키를 제거한다. 그리고 트리를 다시 올라가면서 키가 너무 적게 들어 있는 노드를 확인하고 복구한다.

• 빈 루트 노드를 제거하는 경우를 제외하면 어떤 노드도 제거하지 않기 때문에 트리가 항상 균형잡힌 상태를 유지할 수 있다.

🔖 12.5 B-트리가 중요한 이유

• 다른 노드에 대한 메모리 접근이 노드 내 내용에 접근하는 것보다 비용이 더 많이 드는 경우를 다루기 위해 이미 알고 있는 자료 구조의 동작을 어떻게 적응시킬 수 있는지 보여준다.

• B-트리는 인덱싱과 저장을 결합해 필요한 접근 횟수를 최소화하는 방식으로 동작한다. 이는 디스크나 외부 서버에 저장하는 큰 데이터 집합에 중요하다.

• 그리고 B-트리는 저장하는 데이터의 분포에 맞춰 균형을 유지하기 위해 구조를 지속적으로 재배치한다.