[DataStructure] B-Tree 쉽게 이해하기

B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지

*B-Tree를 이해하려면 Binary트리에 대해서도 알아야한다.


이진탐색트리 BST

• binary tree라고도 한다.
• 모든노드는 왼쪽서브트리는 해당 노드의 값보다 작은 값을 가지고 모든 노드의 오른쪽 서비 트리는 해당노드값보다 큰 갑만 가진다

B-Tree소개

BST에서 응용된 버전인 B-tree 특징과 배경

• 자녀노드는 최대 2개, 그래서 binary인것
• 만약 자녀노드는 3개로 하고 싶다면??? 부모노드값에따라 왼, 오른쪽 노드값이 배열되면 안된다. 자녀노드가 3개이므로
• ? < k1, k1 < ? < k2, ? > k2 로 자녀노드를 배치하기로 정함.
• 이떄 k1, k2값이 필요하게 되는데, 부모노드에 k1, k2 2개 값이 들어가도록 한다.
• 이 2개의 값을 기준으로 자녀노드가 3개일 경우 --? ? < k1, k1 < ? < k2, ? > k2 로 배치한다.
• 왼자녀 : ? < k1
• 가운데 자녀 : k1 < ? < k2
• 오른쪽 자녀 : ? > k2 로 설정하면 된다.
  
  

이걸 차원을 확장시켜서 생각해보면 아래와 같다.

• 왼쪽 자녀노드를 부모노드로 하는 서브트리의 모든 노드는 ? < k1
• 가운데 자녀노드를 부모노드로 하는 서브트리의 모든 노드는 k1 < ? < k2
• 오른쪽 자녀노드를 부모노드로 하는 서브트리의 모든 노드는 ? > k2 로 확장사고 할 수 있다.
  
  

결론

• 이진트리에서 자녀노드의 최대가수를 늘리기 위해서는 부모노드에 값을 2개의 키 값을 저장하기하고
• 이 키를 오름차순으로 정렬한다.
• 정렬된 순서에 따라 자녀노드들의 키 값이 정해진다. 또한 이떄 자녀노드의 서브트리는 값의 범위를 가지게 된다.

이걸 B트리라고 한다.

장점

• 이런방식을 사용하면 자녀노드의 최대 개수를 취향껏 결정해서 사용할 수 있다.
• 이진트리BST와 비교하면 가질 수 있는 자녀노드의 개수가 다르다.
• 그래서 b트리를 BST를 일반화한 tree라고 부른다.
  
  

그래서

• b트리를 사용할 떄 최대 몇개의 자녀노드를 가질 수 있을 것인지가 핵심이다.
• b트리르 사용할 떄 중요한 파라미터 M
• M : 각 노드의 최대 자녀 노드 수 (가장 중요)
• 최대 M개의 자녀르 ㄹ가질 수 ㅅ있는 b트리를 m차 BTree라고 한다.
  
  

b트리의 4개의 파라미터들

• m : 각 노드의 최대 자녀 노드 수, 근본값
• M - 1: 각 노드의 최대 key수
• 예를들어보자. 3차 비트리라고 가정했을 때, m = 3, m - 1 = 2이다. 노드가 최대로 가질 수 있는 키 값의 개수가 2개인것이다.
• 따라서 한 노드는 2개의 값을 가지고, 3개의 자녀노드를 가질 수 있다. 너무 당연한 것
• 3개의 자녀노드를 가지려면 부모노드는 키를 2개가 있어야 한다.
• ⌈ m / 2⌉ : 각 노드의 최소 자녀 노드 수, m=3이면 3/2= ⌈1.5⌉ = 2이다. 각 노드의 최소 자녀 노드의 수는 2개이다. 이 조건에서 주의할 점은 root, leaf노드는 해당이 안되는조건이다. 하지만 두 노드가 아닌 모든 노드는 b트리에서 이 조건을 무조건 충족해야한다.
• ⌈ m / 2⌉ - 1 : 각 노드의 최소 key수이다. 보면 이해할 수 있다. m만 알면 밑에서 2개의 조건은 정해지는 조건이다. 그래서 m이 중요한 파라미터인 것이다. 이 때 중요한 것은 root노드는 이 조건에서 제외. 나머지 노드는 무조건 충족해야한다.
• 위 2개는 최대와 관련된 파라미터이고, 아래 2개는 최소와 관련된 파라미터이다. 또한 m만 알면 아래 3개조건은 알아서 정해지는 조건이다. 라고 이해하면 쉽다.

출처 : https://www.youtube.com/watch?v=bqkcoSm_rCs

btree

• internal 노드의 key수가 x개라면 자녀 노드의 수는 언제나 x + 1개이다.
• leaf제외한 interna 노드의 key수가 x개라면 자녀 노드의 수는 언제나 x + 1개이다.
• key가 1개이면 자녀노드는 2개⌉
• key가 2개이면 자녀노드는 3개
• 결론
  각 노드마다 최소 하나의 키를 가지기 떄문에 몇 차 비트리인지와 상관없이 interanl노드는 최소 2개의 자녀 노드를 가진다.
  m 이 정해지면 root를 제외하고 internal노드는 최소 ⌈m /2⌉ 개의 자녀 노드를 가질 수 있게 된다
  
  

b트리의 데이터 삽입

• 데이터 추가는 항상 리프노드에서 한다.
• 노드가 넘치면 가운데 키 값을 기준으로 좌우 키들을 분하랗고 가운데 키는 승진한다.
• 여기서 노드가 넘친다? m차 비트리라면 최대 키의 수는 m - 1이고,
• 하나의 노드보다 m-1보다 키의 수를 더 가지고 잇다라는 말이다.
  예시를 통해 이해하는 것이 중요하다.
  
  

예 : 3차 비 트리 데이터 삽입
1. 1추가 : 루트노드됨, 3차비트리이므로 최대 키 값은 2개이다.
2. 15추가 : 추가느느 항상 리프노드에다. 루트노트 키 값으로 15를 넣음
3. 2추가 : 추가는 항상 리프노트에 한다. 아직 루트논드노 리프이므로 추가, 키값은 정렬되어야한다. (1, 2, 15)
그러나 노드가 가질 수 있는 최대 키 값은 2개인데 3개이다... 노드가 넘쳤다... 분할한다.
왼(1, x) 오(15, x), 루트(2, x)로 분할한다. 이떄 (2, x)인 노드를 승진시켜서 루트노드로 만들어야 한다. (중간값이므로)
4. 5추가 : 리프노드에 넣어야 한다. 이때 비트리에서 리프노트를 탐색해야한다. 이때 탐색은 루트에서 시작한다. 2 < 5 이므로
오른쪽 자녀노드(15, x) 에 들어간다. 그리고 키는 오름차순정렬이 룰이므로 (5, 15)가 되어야 한다.
5. 30추가 : 위 단게와 똑같이 진행한다. (5, 15, 30)이 된다. 노드가 넘쳤다... 중간값을 기준으로 좌우 자녀노드로 분할한다.
먼저 30을 떼어내 (30, x)을 오른쪽에 둔다. 15를 부모노드로 승진시킨다.근데 부모노드에 키 값 자리가 있다. 거기로 넣는다. 5는 그대로 둔다.
6. 90추가 : 리프노드를 탐색한다. 루트(2, 15)에서 15보다 크다. 오른쪽 서브트리 탐색한다. (30, x)는 리프노드이므로 에 넣는다. (30, 90)으로 되고 오름차순정렬이므로 냅둔다.
7. 20추가 : 20과 2를 비교, 20과 15를 비교(루트가 (2, 15))했는데 큼 (30, 90)에 넣고 오름차순 정렬(20, 30, 90)...근데 노드가 넘친다... 가운데 값은 승진하고 나머지는 좌우로 분할한다. (20, x), (90, x)로 분할된다. 이때 가운데값은 30이 되어 부모노드로 승진시킨다.
근데 (2, 15)로 보냈더니 (2, 15, 30)이 되어버려..노드가 넘친다...또 중간값을 부모노드로 승격시키고 좌우자녀노드로 분할한다.
분할스텝은 먼저 우측 자녀부터이다. (2, 15, 30)에서 (30, x)으로 분할하여 자녀노드로 만들고
그다음 스템은 중간값 15를 부모노드로 승격시켜야하는데 이는 루트노드이므로 앞으로 루트노드가 될 새로운 노드를 생성한다. (15, x)가 새로운 루트노드가 되고 (2, x)는 냅둔다.
8. 7추가 : 15>7이므로 7는 좌측서브트리 탐색, 2 < 7이므로 우측서브트리로 (5, x)에 7을 넣는다.(5, 7)
9. 9추가 : 15 > 9이므로 9는 좌측서브트리 타맷ㄱ, 2 <9 이므로 우측서브트리로 (5, 7)에 9를 넣는다. (5, 7, 9)
근데 노드가 넘친다. 가운데를 부모로 하고 좌우로 분할한다.
우측부터 (9, x)하고 7은 가운데값이므로 부모로 승격한다. 부모노드(2, x)가 있으므로 여기에 넣는다. (2, 7)이되고 좌측 서브트리는 냅둔다.
10. 8추가 : 15 > 8이므로 좌측서브트리탐색한다. (2, 7)에서 2<8, 7<8이므로 우측 서브트리탐색한다. (9, x)가 있다. (9, x)에 8을 넣는다. 오름차순정렬하여 (8, 9)가 된다.
11. 10추가 : 15> 10이므로 좌측서브트리탐색, (2, 7)에서 2<10, 7<10이므로 우측 서브트리탐색한다. (8, 9)가 리프노트이므로 여기 넣는다. (8, 9, 10)이 되어.... 노드가 넘친다... 중간값을 승격하고 나머지는 좌우로 분할하낟.
이때 스텝대로 우측(10, x)로 우측 자녀노드를 생성한다.(8, 9) 9는 승격시켜야한다. 근대 (2, 7, 9)로 또 노드가 넘친다.
또 분할한다. (2, 7, 9) -> (2, 7)하고 (9, x)를 하위 자녀노드로 만든다. 그리고 (2, 7)에서 7을 승격시킨다. 근데 위 부모노드에 자리가 남는다. (15, 7)에 넣고 오름차순정렬(7, 15)가 된다.
결국 (2, x), (7, 15), (9, x)가 된다.
12. 50추가 : 탐색진행(7, 15)가 루트노드이므로 비교 <50이므로 우측서브트리탐색한다.
(30, x) 에서 30보다 크다. 우측 서브트리로 탐색한다. (90, x)이 리프노드이므로 넣고 오름차순으로 정렬한다.
(50, 90)이 된다.
13. 70추가 : 12번과 같다. (50, 90)가 리프노드인데 추가 (50, 70, 90)이 되어....넘친다. 분할
먼저 우측90을 분할(90, x)가 되고, 70을 승진하여 위 노드가 비어있으므로 (30, 70)된다.
14: 60추가 : (7, 15) <60이다. (30, 70)에서는 30<60<70이므로 중간에 있는 리프노트(50,x)에 넣고 오름차순정렬한다.
결국에 (50, 60)이 된댜.

결론

• b-tree는 모든 리프노드들은 같은레벨에 있다.
• 그래서 balanced tree이다.
• 검색에서 평균, 워스트케이스시간복잡도 O(logN) 이다.

데이터삭제동작

B-tree 데이터삭제
식제도 항상 리프노드에서 발생한다.
삭제후 최소 key수보다 적어졌다면 재조정한다.
1. key수가 여유있는 형제의 지원을 받는다.
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합치낟.
3. 2번후 부모에 문제가 있다면 거기서 다시 재조정한다.

삭제 후 최소 키수보다 적다면?
1. key수가 여우있는 형제의 지원을 받는다.
1.1좌측 형제 노드에서 도움을먼저 받는다.
동생이 여유가 있으면
-> 동생의 가장 큰 key를 부모노드의 나와 동생 사이에 둔다
-> 원래 자리에 있던 key는 나의 가장 왼쪽에 둔다.

1.2 동생이 여유가 없고 형(우측형제)가 여유가 있다면
-> 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다.
-> 원래 그 자리에 있던 key는 나의 가장 오른쪽에 둔다.

2. 형제의 지원이 불가능하다면 부모의 지원을 받고 형제와 합친다.
   2.1 동생이 있으면 동생과 나 사이의 key를 부모로 부터 받는다
   -> 그 key와 나의 key를 차례대로 동생애게 합친다.
   -> 나의 노드를 삭제한다.

2.2 동생이 없므면 형과 나 사이의 key를 부모로부터 받는다.
-> 그 key와 형의 Key를 차례대로 나에게 합친다.
-> 형의 노드를 삭제한다.

(합칠때는 왼쪽으로 합친다)

3. 부모가 지원한 후 부모에 문제가 있다면 상황에 맞게 대응한다.
   3.1 부모가 루트노드가 아니라면
   -> 그 위치에서 부터 다시 1번부터 재조정을 시작한다.

3.2 부모가 루트노드이고 비어있다면
-> 부모 노드를 삭제한다.
-> 직전에 합쳐진 노드가 루트노드가 된다.

Internal 노드 데이터삭제하기

• 리프노드에서 삭제하고 필요하면 재조정
• internal 노드에 있는 데이터를 삭제하려면 leaf노드에 있는 데이터와 위치를 바꾼후 삭제한다.
• 이때 리프노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿀 것인지가 이슈
• 삭제할 데이터의 선임자와 후임자와 위치를 바꿔준다.
  선임자 : 나보다 작은애들중에 제일 큰애
  후임자 : 나보다 큰 애들중에 제일 작은애
• 선임자와 후임자는 항상 리프노드에 위치한다.
  *여기서는 선임자로 한다.

*삭제는 항상 leaf노드에서

• internal 노드의 경우 선임자와 위치 바꾼후 삭제하나.
• 삭제후 최소 key수보다 적어진다면 재조정해야한다.
• 형제지원 -> 부모지원받고 형제 합침 -> 부모 도움후 부모도 문제 시 재차 조정