[자료구조] B-Tree

B-Tree란?

자식 노드의 개수가 2개 이상인 트리.

• 노드 내의 데이터가 1개 이상일 수 있다.
• 노드 내 최대 데이터 수가 2개이면 2차 B-Tree, 3개면 3차 B-Tree .... M개면 M차 B-Tree

 

B-Tree 성립 조건

1. 노드의 데이터 수가 n개면 노드의 개수는 n+1

노드의 데이터 수가 3이므로 노드의 개수는 4개

 

2. 노드의 데이터는 반드시 정렬된 상태

 

3. 노드의 자식노드 데이터들은 노드 데이터를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값.

 

8보다 작은 수는 가장 왼쪽 자식 노드, 8과 13 사이의 수는 가운데 자식 노드, 13보다 큰 수는 가장 오른쪽 노드

 

4. 루트 노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 가져야 한다.

4차 B-Tree에서 최소 2개의 데이터를 가져야 한다.

5. Leaf 노드로 가는 모든 경로의 길이가 같아야 한다. 즉, Leaf 노드는 모두 같은 레벨에 존재

Leaf 노드가 다른 레벨에 존재하므로 B-Tree의 조건 성립x

6. 데이터 중복x

7. 루트 노드가 자식이 있다면 2개 이상의 자식을 가져야 한다.

 

삽입

1. 데이터를 탐색해 해당하는 leaf 노드에 데이터 삽입

2. leaf 노드 데이터가 가득 차있으면 노드 분리 ( 노드 데이터 개수 == M (차수))

- 중간 값을 부모 노드로 트리 구성

3. 분리한 서브 트리가 B-Tree 조건에 맞지 않는다면 부모노드로 올라간다. 

- ex) leaf 노드가 모두 같은 레벨에 존재하지 않는다.

 

삭제

1. Leaf 노드 삭제하는 경우

1-1. 삭제해도 B-Tree 유지하는 경우

 

Leaf 노드인 10을 삭제해도 B-Tree 유지.

 

1-2. 삭제하면 B-Tree가 깨지는 경우

 

Leaf 노드인 1을 지우면 B-Tree가 깨진다.

1. 1을 삭제하면 B-Tree 구조가 깨진다.
2. 삭제한 노드의 부모노드에서 데이터를 가져온다.
3. 부모노드에서 가져온 데이터와 형제 노드와 merge한다.
4. 루트까지 올라가면 B-Tree 조건이 맞을때까지 반복한다.

 

2. Leaf 노드가 아닌 노드를 삭제하는 경우

Leaf노드가 아닌 데이터 삭제.

1. 18 데이터 삭제
2. 왼쪽 서브트리에서 최대값을 노드에 위치시킨다.
3. 1-2 방법과 마찬가지로, 부모노드에서 데이터를 가져와 형제노드와 merge하는 작업 진행한다.
4. B-Tree 조건이 맞을때까지 반복

 

사용예제 - Index

Index란? 데이터베이스 테이블의 동작속도를 높여주는 자료구조.

- 책에 있는 목차와 비슷한 개념.

- 자주 사용된느 칼럼 값을 해당 주소값과 같이 보관한다.

- 인덱스로 저장된 값들은 정렬하여 저장된다.

 

Linked List 형태로 데이터가 저장되어 있다면 - O(n)

Binary Tree 형태로 데이터가 저장되어 있다면 - O(logn)

 

단, Binary Tree는 한쪽 branch에만 데이터가 몰릴수도 있기 떄문에 

데이터 높이를 자동으로 잡아주는 Balanced Tree 즉, B-Tree 를 index의 자료구조로 사용한다.

 

[참고]

hyungjoon6876.github.io/jlog/2018/07/20/btree.html

B-Tree 개념 정리

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

[자료구조] 그림으로 알아보는 B-Tree