[데이터베이스] - B-Tree & B+Tree

B-Tree란?

데이터가 정렬된 상태로 유지되어 있는 트리로 일반적인 이진 트리와 비슷하지만 한 노드 당 자식 노드가 2개 이상 가능한 트리. 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있는 것이 장점.

트리란? 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프

B tree

사각형으로 표시된 한 개의 데이터를 노드(node)

가장 상단의 노드를 루트 노드(root node)

중간 노드들을 브랜치 노드 (branch node)

가장 아래 노드 리프 노드(leaf node)

특징

 

 

1. 균일성 : 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다.
   (트리 높이가 다를 경우, 약간의 차이는 있지만 O(logN))
2. 균형트리 : 루트로 부터 리프까지의 거리가 일정한 트리 구조. 성능이 안정화 되어 있음.
   (처음 생성 당시는 균형 트리이지만 갱신이 반복되면 서서히 균형이 깨지고, 성능도 약화 됨.
3. 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.

데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가리킨다.
노드 내 데이터들은 항상 정렬된 상태. 각 노드는 여러 개의 key를 가지고 있고 각 key에 대응하는 data도 가지고 있다.

데이터 삽입

• 추가는 항상 Leaf Node에 한다.

Node가 넘치면 가운데 Key를 기준으로 좌우Key들을 분할하고 가운데 Key는 승진

 

🤔노드가 넘친다?
👉M차 b-tree에서 M은 최대로 가질수있는 노드의 수, M트리에서 각 노드가 가질수 있는 최대 키의 수 = M - 1 즉, M -1 보다 크면 노드가 넘친다고 볼 수 있다.
🤔🤔ex) 3차 bTree에서 데이터를 삽입한다면?

👉 3차 btree에서 3은 최대로 가실수 있는 노드의 수. 각 노드가 가질수 있는 최대 키의 수는 : 3-1인 2가 최대 키값이다. 즉, 노드가 2개보다 크면 노드가 넘쳤다라고 할 수 있다.

데이터 삭제

※ 삭제도 항상 Leaf Node에서 발생
※ 삭제 후 최소 key 수 보다 적어졌다면 재조정
1. key 수가 여유있는 형제의 지원 받는다
2. 1번 불가능하면 부모의 지원을 받고 형제와 합친다.
3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정

Internal 노드 데이터 삭제

※ leaf노드에서 삭제하고 필요하면 재조정
인터널 노드에있는 데이터를 삭제하려면 leaf노드에 있는 데이터와 위치를 바꾼후 삭제
🤔어떤 데이터와 바꿀건지?
- 삭제할 데이터의 선임자나 후임자와 위치를 바꾼다.

선임자 : 나보다 작은 데이터들 중 가장 큰 데이터
후임자 : 나보다 큰 데이터들 중 가장 작은 데이터

---

B+Tree란?

B Tree를 확장한 것으로 Leaf Node에만 데이터를 가지고 있고 나머지 노드들은 데이터를 위한 Key만을 갖는다.

특징

1. 오직 리프노드에만 데이터 저장 가능
2. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기 때문에 트리의 높이가 낮아진다.
3. 중복된 키를 가질 수 있다.
4. 리프 노드끼리 링크드리스트로 연결되어 있다.
5. 풀 스캔 시, B+tree는 리프노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B tree에 비해 빠르다.

데이터 삽입

1. key의 수가 최대보다 적은 leaf node에 삽입하는 경우
   • 노드의 가장 앞이 아닌 곳에 삽입되는 경우 단순히 삽입.
   • 앞에 삽입되는 경우 해당 노드를 가리키는 부모 노드의 포인터의 오른쪽에 위치한 key로 바꿔준다. 그리고 리프노드끼리 링크드 리스트로 이어줘야 하므로 삽입된 key에 링크드 리스트로 연결한다.
2. key의 수가 최대인 leaf node에 삽입하는 경우
   • ey의 수가 최대이므로 분할을 해야한다. 중간 node에서 분할이 일어나는 경우는 B tree와 동일하다.
   • 리프노드에서 분할이 일어나는 경우 중간 key를 부모 node로 올려주는데 이때, 오른쪽 node에 중간 key를 붙여 분할한다. 그리고 분할된 두 노드를 링크드 리스트로 연결한다.
     

데이터 삭제

1. 삭제할 key가 리프노드의 가장 앞에 있지 않은 경우
   • B tree와 동일하다.
2. 삭제할 key가 리프노드의 가장 앞에 위치한 경우
   • 리프노드가 아닌 노드에 key가 중복해서 존재한다. 해당 key를 노드보다 오른쪽에 있으면서 가장 작은 값으로 바꿔줘야 한다.
     

 

출처

• github.com/devSquad-study/2023-CS-Study
• youtube.com/@ez