B Tree & B+ Tree
이진 트리는 하나의 부모가 두 개의 자식밖에 가지지 못하고, 균형이 맞지 않으면 검색 효율이 선형 검색 급으로 떨어진다. 하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있기 때문에 계속 개선시키기 위한 노력이 이루어진다.
B Tree
B Tree는 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다. 이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화시킨 것이 B Tree이다.
자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 많은 데이터를 저장할 수 있을 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다. 단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리이다.
B Tree의 장점
대량의 데이터를 처리할 때, 하나의 노드에 많은 데이터를 저장할 수 있다는 점은 큰 장점이다. 대량의 데이터는 메모리보다 블록 단위로 입출력하는 하드디스크 또는 SSD에 저장해야 하기 때문이다. 한 블록이 1024 바이트이면, 2바이트를 읽으나 1024바이트를 읽으나 동일한 입출력 비용이 발생한다. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다. 이러한 이유로 B-Tree는 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용된다.
B Tree의 규칙
- 노드의 자료수가 N이면, 자식 수는 N+1이어야 한다.
- 각 노드의 자료는 정렬된 상태여야 한다.
- 루트 노드는 적어도 2개 이상의 자식을 가져야 한다.
- 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
- 외부 노드로 가는 경로의 길이는 모두 같다.
- 입력 자료는 중복될 수 없다.
예제
예를 들어, M=4인 B-Tree를 생각해보자. 각 노드는 최대 3개의 자료를 가질 수 있고, 각 자료는 정렬된 상태를 유지해야 한다.
[30]
/ \
[10,20] [40,50]
이와 같은 구조에서 자료가 추가되거나 삭제될 때마다 트리는 자동으로 균형을 맞춘다.B+ Tree
B+ Tree는 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드가 추가된 트리 구조이다. 기존의 B-Tree와는 다르게 데이터의 연결리스트로 구현된 색인구조를 갖추고 있다. B-Tree의 변형 구조로 index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다. 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용된다.
B+ Tree의 장점
- 블록 사이즈를 더 많이 이용할 수 있다. (Key 값에 대한 하드디스크 액세스 주소가 없기 때문)
- Leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리하다.
B+ Tree의 단점
B-Tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+ Tree는 무조건 leaf 노드까지 내려가봐야 한다.
예제
예를 들어, B+ Tree는 다음과 같은 구조를 가질 수 있다.
Index Node:
[30]
/
[10,20] [40,50]
Leaf Node:
[10] -> [20] -> [30] -> [40] -> [50]
이 구조에서는 모든 데이터가 leaf 노드에만 저장되며, leaf 노드들은 연결 리스트로 연결되어 있다.B Tree와 B+ Tree 비교
- B-Tree: 각 노드에 데이터가 저장된다. 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있다.
- B+ Tree: index 노드와 leaf 노드로 분리되어 저장된다. 각 노드에서 key만 들어간다. 따라서 data는 leaf 노드에만 존재한다. add, delete 연산 모두 leaf 노드에서만 이루어진다. 또한, leaf 노드는 서로 연결되어 있어서 임의 접근이나 순차 접근 모두 성능이 우수하다.
결론
B Tree와 B+ Tree는 각각의 장단점을 가지고 있으며, 대량의 데이터를 효율적으로 관리하기 위한 중요한 트리 구조이다. 데이터베이스 시스템에서는 이러한 트리 구조를 통해 데이터의 검색, 삽입, 삭제 성능을 최적화하고, 대용량 데이터를 효율적으로 관리할 수 있다.
