CS 자료구조 B-Tree와 B+Tree

Data structure

차가운개발 2024. 10. 10. 01:35

B-트리는 균형이진탐색트리에서 파생된 자료구조다. 데이터베이스와 파일 시스템에서 대용량 데이터를 효율적으로 관리하는데 사용된다. B-트리는 2개 이상의 더 많은 자식 노드를 가질 수 있으며, 디스크 I/O를 최소화하도록 설계되었다.

B-트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 하며 다음과 같은 특징을 갖는다.

규칙

노드는 최대 M개부터 M/2개의 자식을 가질 수 있다.
노드에는 최대 M - 1부터 M/2 -1개의 키가 포함될 수 있다.
노드의 키가 n개라면 자식의 수는 n + 1이다.
최소차수는 자식의 하한값을 의미하며 최소차수가 t라면 M = 2t - 1을 만족한다.
(최소차수 t가 2라면 3차 B트리이며, 키의 하한은 1이다.)

특징

모든 노드가 정렬된 키를 포함
각 노드에는 키들이 오름차순으로 정렬되어있다. 이 키들은 하위 트리로 가는 경로를 결정하는데 사용된다.
자식 노드 개수가 여러 개일 수 있다
이진 탐색 트리와 달리 B-트리의 노드는 여러 개의 자식을 가질 수 있다. M차 B-트리
균형성
B-트리는 항상 균형 트리다. 모든 리프노드가 같은 깊이에 있다. 이로 인해 탐색, 삽입, 삭제 작업이 일정한 시간복잡도를 갖는다.
노드가 꽉 차면 분할
노드에 저장할 수 있는 키의 최대 개수를 초과하면 해당 노드를 분할하여 두 개의 노드로 나누고 중간 값을 부모 노드로 올린다. 이 과정을 통해 항상 균형을 유지한다.
디스크 I/O 최적화
B-트리는 대용량 데이터를 관리할 때 효율적이다. 한 노드에 여러 키와 자식 노드를 저장할 수 있기 때문에, 한 번의 디스크 접근으로 많은 데이터를 읽어올 수 있다. 데이터베이스나 파일 시스템처럼 대용량 데이터를 다룰 때 매우 효율적이다.

탐색
키를 찾기 위해, 루트 노드부터 시작해 각 노드의 키를 순차적으로 비교하며 내려간다. 각 노드에서 키를 찾거나 해당 키가 있는 하위 트리로 이동한다. 높이가 낮기 때문에 O(log n)의 시간복잡도를 가진다.
삽입
새로운 키를 삽입할 때는 키가 들어갈 위치를 탐색 후 해당 위치에 키를 삽입한다. 노드가 가득 차 있다면 분할을 수행하여 노드를 두 개로 나누고 중간 값을 부모 노드로 올린다.
삭제
삭제할 키를 찾은 후 리프 노드에서 삭제하거나, 내부 노드에서 삭제할 경우 자식 노드에서 대체할 키를 찾아 치환한다. 삭제 후 너무 적은 키가 남으면, 이웃한 노드와 병합하거나 키를 빌려오는 과정을 통해 트리의 균형을 유지한다.

디스크 I/O 최소화
B-트리는 한 노드에 많은 키와 자식 노드를 저장할 수 있기 때문에, 한 번의 디스크 접근으로 많은 데이터를 읽을 수 있다. 데이터베이스와 파일 시스템에서 매우 유리하다.
균형 유지
모든 리프 노드가 동일한 깊이에 있으므로, 항상 균형을 유지한다. 이로 인해 삽입, 삭제, 탐색 연산의 시간이 일정하게 유지된다.
대규모 데이터 처리에 효율적
B-트리는 자식 노드를 많이 가질 수 있어 트리의 높이가 낮고, 대규모 데이터를 빠르게 처리할 수 있다.

데이터베이스 인덱스
데이터베이스의 인덱스 구조로 자주 사용된다. B-트리를 변형한 B+트리를 사용하여 효율적인 검색, 삽입, 삭제 작업을 지원한다.
파일 시스템

B+Tree

B+트리는 B-트리의 변형된 형태로 B-트리의 모든 특성을 가지면서도 몇가지 중요한 개선을 통해 더 빠르고 효율적인 검색과 순차 탐색을 지원한다.

데이터는 리프 노드에만 저장
B+트리에서는 실제 데이터를 포함하는 키 값은 리프 노드에만 저장한다. 내부 노드는 탐색을 위한 경로 정보만 담고있고, 데이터를 저장하지 않는다. B-트리와 가장 큰 차이점 중 하나다.
리프 노드간 연결
B+트리의 리프 노드들은 연결 리스트 형태로 되어있다. 이로 인해 순차적 탐색이 매우 효율적이다. 리프 노드 사이를 왼쪽에서 오른쪽으로 순차적으로 이동하며 데이터를 쉽게 찾을 수 있다.
균형 트리 유지
항상 균형을 유지하며 모든 리프 노드가 같은 깊이에 있다. 삽입, 삭제, 탐색 연산이 일정한 시간안에 이루어진다.

탐색
루트 노드에서 시작하여 리프노드에 도달할 때까지 이루어진다. 내부 노드는 경로만 제공하기 때문에 데이터를 찾기 위해선 리프 노드까지 내려가야한다. 리프 노드들은 연결 리스트로 연결되어 있어 순차 검색도 쉽게 가능하다.
삽입
새로운 키를 삽입할 위치를 찾고, 리프 노드에 도달한 후 데이터를 삽입한다. 리프가 가득차면 분할을 수행하여 중간값을 부모로 올린다(균형유지).
삭제
삭제할 데이터를 리프 노드에서 찾고 삭제 후 키의 개수가 너무 적으면 병합 또는 재분배 작업을 통해 균형을 유지한다.

효율적인 순차 검색
리프 노드들이 연결 리스트로 연결되어 있어 순차적으로 데이터를 탐색하거나 범위 검색에 매우 효율적이다.
더 많은 키 저장 가능
내부 노드에 데이터를 저장하지 않고 탐색을 위한 경로 정보만 저장하기 때문에, 한 노드에 더 많은 키를 저장할 수 있다. 트리의 높이를 낮게 유지하는데 도움이 되어 연산이 더 빠르게 수행된다.
디스크 I/O 효율성
B+트리 한번의 디스크 접근으로 많은 데이터를 처리할 수 있는 구조를 가지며 대규모 데이터 저장소에서 매우 유리하다. 데이터는 리프 노드에 집중적으로 저장되므로, 내부 노드를 거치지 않고 빠르게 순차적으로 접근할 수 있다.
(최초는 루트에서 리프까지 내부를 거치지만 연결리스트 때문에 리프에서 리프로 갈때 내부를 거치지 않는다.)

데이터 저장 위치:
- B-트리: 데이터는 내부 노드와 리프 노드에 모두 저장
- B+트리: 데이터는 리프 노드에만 저장
리프 노드 간 연결:
- B-트리: 리프 노드 간에 특별한 연결 X
- B+트리: 리프 노드들이 연결 리스트로 연결되어 있어, 순차 검색이 더 빠르다.
순차 검색:
- B-트리: 순차적으로 데이터를 검색하려면 트리 탐색을 반복해야한다.
- B+트리: 리프 노드 간 연결 리스트 덕분에 한 번의 탐색 후 순차적으로 데이터를 쉽게 검색할 수 있다.