B-Tree
트리의 일종으로, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
B-Tree의 특징은 다음과 같다.
1. 각 노드에는 2개 이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.
2. 노드의 자료 수가 N개이면 자식 수는 N + 1개여야 한다.
3. 루트 노드는 적어도 2개의 자식을 가져야 한다.
4. 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
여기서 M은 노드가 가질 수 있는 최대 자식 노드의 개수이다.
5. 리프 노드로 가는 경로의 길이는 모두 같다.
6. 입력 자료는 중복될 수 없다.
B-Tree의 핵심 원리
B-Tree의 가장 큰 장점은 항상 균형을 유지한다는 점이다. 모든 리프 노드가 같은 레벨에 있기 때문에, 어떤 데이터를 찾더라도 탐색 시간이 로그 n으로 일정하게 유지된다.
B+Tree
동작 방식은 B-Tree와 비슷하지만, B+Tree의 다른점은 리프 노드들이 연결 리스트로 되어있어 선형 검색이 가능해 굉장히 작은 시간복잡도에 검색 작업을 수행할 수 있다는 점이다.
B-Tree와 B+Tree의 차이점
- 모든 Key, data가 리프노드에 모여있다. B-Tree는 리프노드가 아닌 각자 Key마다 data를 가진다면, B+Tree는 리프 노드에만 data가 존재한다.
- 모든 리프노드가 연결리스트로 이루어져 있다. B-Tree는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+Tree는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.
- 리프노드의 부모 Key는 리프노드의 첫 번째 Key보다 작거나 같다. 또한, Key값이 부모 노드와 리프 노드에 공존할 수 있다.
- B+Tree의 삽입, 삭제 연산은 leaf에서만 이루어진다.
B*Tree
B*Tree는 B-Tree의 단점 중 하나인 노드 분할이 너무 자주 일어나서 트리가 깊어지는 현상을 해결하기 위해 등장한 개선된 버전이며, 가장 핵심적인 차이는 노드가 꽉 찼을 때 바로 쪼개지 않고, 옆 형제 노드를 살펴보고 여유가 있다면 재정렬하여 빈 공간에 채워넣는다는 점이다.
이러한 방식은 B-Tree보다 효율적으로 저장공간을 활용할 수 있다는 장점이 있다.
.