B-tree, B+tree

B-tree

하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 자체 균형 트리

특징

1. 하나의 노드에 최대 M개의 자식을 가질 수 있음(M차 B tree)
2. 루트 노드는 최소 두개의 자식 필요
3. 루트를 제외한 노드는 최대 M−1개부터 최소 ⌈M/2⌉−1개의 키를 가짐
4. n개의 키를 가진 노드는 n+1개의 자식을 가짐
5. 각 노드의 키는 정렬되어 있음
6. 왼쪽 서브트리의 키 값 < 부모 노드의 특정 키 < 오른쪽 서브트리의 키 값
7. 모든 리프 노드들의 레벨은 같다.

삽입

1. 트리를 내려가면서 해당 키를 삽입할 위치를 탐색
2. 해당 노드에 공간이 있다면 삽입
3. 노드에 공간이 없다면 노드의 중간값을 부모로 올리고, 노드를 분할하는 것을 반복

삭제

1. 트리를 내려가면서 삭제할 키의 위치를 탐색

    2-1.리프 노드 키 삭제: 리프 노드에서 키를 제거, 삭제한 노드가 최소한의 키를 가지고 있지 않을 경우

                                       형제 노드나 부모 노드에서 키를 가져옴

    2-2-1.내부 노드 키 삭제: 내부 노드에서 키를 제거, 좌측 최대값 키나 우측 최소값 키를 가져옴

                                           자식 노드의 키값이 모두 최소일 때 삭제할 노드의 부모의 키를 한 레벨 내리고

                                           자식의 키 합쳐를 그 자식으로 만듬

 

시간복잡도

1. 탐색,삽입, 삭제: O(log N)

B+tree

B-tree의 변형으로 단말 노드만 데이터를 가지며 링크드 리스트로 연결되어 있는 자료구조

 

 

1. 리프 노드끼리 연결 리스트로 연결되어 있어서 순차적 탐색에 유리
2. B-tree와는 달리 무조건 리프 노드까지 탐색해야 함