[DB] B-tree, B+tree

1. B-tree

 

- 정의

데이터가 정렬된 상태로 유지되어 있는 트리로 일반적인 이진 트리와 비슷하지만 노드 당 자식 노드가 2개 이상 가능한 트리

트리 관련 용어

• 노드: 사각형으로 표시된 한 개의 데이터
• 루트 노드: 가장 상단의 노드
• 브랜치 노드: 중간 노드
• 리프 노드: 가장 아래 노드

 

---

 

- 특징

: 균일성, 균형트리, 정렬된 상태

균일성

어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있음

트리 높이가 다를 경우, 약간의 차이는 있지만 O(logN)

 

균형트리

루트로부터 리프까지의 거리가 일정한 트리 구조

성능이 안정화되어 있음

처음 생성 당시는 균형 트리이지만 갱신이 반복되면

서서히 균형이 깨지고, 성능도 약화됨

 

정렬된 상태

항상 정렬된 상태로, 특정 값보다 크고 작은

부등호 연산에 문제가 없음

각 노드는 여러 개의 key를 가지고 있고

각 key에 대응하는 data도 가지고 있음

 

---

 

- 삽입

1) 빈 트리일 경우 root node를 만들어 삽입함. root node가 가득 찬 경우 노드를 분할해 리프노드를 생성

2) key가 들어갈 리프노드를 탐색함

3) 해당 리프 노드에 자리가 남아있다면 정렬을 유지하도록 알맞은 위치에 삽입하고, 리프 노드가 꽉 차 있다면 key를 삽ㄷ입 후 해당 노드를 분할함

4) 노드가 분할되는 경우 노드의 중앙값을 기준으로 분할함. 중앙값은 부모 노드로 합쳐지거나 새로운 노드로 생성되고, 중앙값을 기준으로 왼쪽의 키는 왼쪽 자식, 오른쪽의 키는 오른쪽 자식으로 생성됨

 

---

 

- 삭제

1) 삭제할 key가 리프노드에 있는 경우

• 현재 노드의 key 수가 최소보다 큰 경우
  👉 단순히 삭제해도 무방
• 현재 노드의 key 수가 최소이고, 왼쪽 또는 오른쪽 형제 노드의 key 수가 최소보다 큰 경우

삭제 전	삭제 후

 

• 현재 노드와 왼쪽, 오른쪽 형제 노드의 key 수가 최소이고, 부모 노드의 key 수가 최소보다 큰 경우
  

  

• 현재 노드와 왼쪽, 오른쪽 형제 노드, 부모 노드 모두 key 수가 최소인 경우
  👉 부모 모드가 루트인 경우 서브트리의 높이가 줄어들기 때문에 트리의 재구조화가 필요함

 

2) 삭제할 key가 리프 노드를 제외한 노드에 있는 경우

• 현재 노드 또는 자식 노드의 key 수가 최소보다 큰 경우
  

  

• 현재 노드와 자식 노드 모두 key 수가 최소인 경우

삭제 전	삭제 후

 

---

 

2. B+tree

 

- 정의

B-tree를 확장한 것으로 leaf node에만 데이터를 가지고 있고 나머지 노드들은 데이터를 위한 key만을 가짐

 

---

 

- 특징

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

 

---

 

- 삽입

1) key의 수가 최대보다 적은 leaf node에 삽입하는 경우

• 해당 노드의 가장 앞이 아닌 곳에 삽입되는 경우 단순 삽입
• 가장 앞에 삽입되는 경우 해당 노드를 가리키는 부모 노드의 포인터의 오른쪽에 위치한 key로 바꿔줌
  그리고 리프노드끼리 링크드 리스트로 이어줘야 하므로 삽입된 key에 링크드 리스트로 연결함

 

2) key의 수가 최대인 leaf node에 삽입하는 경우

• key의 수가 최대이므로 분할을 해야 함. 중간 node에서 분할이 일어나는 경우는 B tree와 동일함
• 리프노드에서 분할이 일어나는 경우 중간 key를 부모 node로 올려주는데 이때, 오른쪽 node에 중간 key를 붙여 분할함. 그리고 분할된 두 노드를 링크드 리스트로 연결함

 

---

 

- 삭제

1) 삭제할 key가 리프노드의 가장 앞에 있지 않은 경우

B-tree와 동일함

 

2) 삭제할 key가 리프노드의 가장 앞에 위치한 경우

리프노드가 아닌 노드에 key가 중복해서 존재함. 해당 key를 노드보다 오른쪽에 있으면서 가장 작은 값으로 바꿔줘야 함

 

---

 

출처

https://github.com/devSquad-study/2023-CS-Study/blob/main/DB/db_b_tree_b%2Btree.md