[알고리즘/자료구조] B트리에 대한 이해

이진트리의 높이를 줄이기 위한 방법으로 AVL 트리를 만드는 방법이 있었다.

https://pastapeter.tistory.com/41?category=953294 

[알고리즘/자료구조] AVLtree (python)

이진탐색트리를 쓰는 방법을 제외하는 방법도 존재한다. 그 방법 중에 하나가 B트리이다. B트리의 맴버 중 하나인 2-3트리를 먼저 살펴본다.

2-3 트리

차수가 2 또는 3 노드를 갖는 트리이다. 특히 3 노드의 경우는 2개의 데이터, 3개의 자식노드를 가진다고 볼 수 있다.

2-3 트리에 데이터를 삽입할 때, 삽입과 분라가 일어난다. 

2-3 트리에는 데이터는 2개까지만들어간다. 그렇다면, 2개의 데이터가 존재할 때, 하나의 노드가 삽입된다면, 우리는 트리를 분리해줘야한다. 위에 경우 20이 추가되었다. 이럴때, 가운데 데이터를 부모로 보내고, 20과 60을 자식으로 분리한다.

하지만, 여기서 부모가 있고, 아래 자식 노드의 분리가 필요할 경우에는, 2가지로 변한다. 자식 노드를 첫번째 경우로 나누는 경우와, 자식 노드의 가운데 값을 위로 올리는 것이다. 1번째 경우는 트리의 높이가 올라간다는 단점을 가진다. 하지만, 2번째 경우는, 트리의 높이가 그대로이다. 이 경우는 부모의 노드가 1개일때 가능하다.

이번에는 자식 노드에 오버플로우가 일어나서 중간값을 부모로 올려보내야할 상황이 생겼다. 하지만 위로 올려도, 결국 부모 노드측에서 오버플로우가 나기 마련이다. 이럴 경우에 먼저 자식노드에서 올려보내고 부모 노드도 맨 처음 경우와 같이 중간값을 올려 새로운 부모노드를 생성한다.

B 트리

B 트리의 특징으로는 다방향 탐색이 가능한 균형트리이다. 모든 리프노드는 동일한 깊이를 가지고, 각 노드의 자식의 수는 [M/2] 이상 M 이하이다. 대용량 데이터베이스에서 사용한다. 이진탐색트리는 하나의 노드에 2개의 자식만 달 수 있다. 그래서 대용량 데이터베이스로 사용하기에는 AVL 트리를 사용하더라도 한계가 존재한다. 이를 해결하는 트리가 B 트리라고 생각하면된다. 즉, 노드에 많은 키를 두어 트리의 높이를 낮춘다.

B-트리 탐색/삽입

탐색: 탐색할 키와 노드의 키를 비교한다. 이떄 key들은 당연히 정렬되어있는 상태이기에, 이진탐색을 실행해서 원하는 키를 찾는다. 

삽입: 삽입은 두가지 케이스로 나뉜다. 1. 리프노드에 넣을 수 있으면 넣고, 리프노트가 가득차면 리프를 2개로 분리하는 것이다.

1단계 : 31의 노드를 추가 시도를 하지만, 이미 가득찬 상태

2단계 : 1. 일단 노드를 추가한다. 2. 오버플로우가 났기 때문에, 중간값을 위로 올린다. 3. 하지만 위로 올렸을때, 부모키가 초과되었다는 것을 알 수 있다. 4. 그래서 부모키를 split 한다.

3단계 : 부모키가 초과되었기에, 2분할로 split하면서 가운데 값(20)을 위로 올린다. 그리고 28, 32를 합쳐준다. 

B트리의 삭제

삭제의 경우, 리프의 경우는 그냥 삭제해주면 된다. 하지만 키가 리프에 있지 않은다면, 리프의 가까운 데이터와 교환한 후 삭제해야한다. 이때 이동, 통합 연산이 수행된다.

이동 : 삭제 후 키의 개수가 작아지면, 좌우 형제로부터 1개의 키를 빌려온다.

통합 : 이동이 불가할 경우 형제와 통합하는 방식을 사용할 수 있다. 

1단계: 그림의 5를 삭제한다고 할때, 가장 가까운노드와 변경해준다. 변경을 한다면 7과 11사이에 5가 있다는 것과 같은 그림이 나오지만 어차피 5는 삭제할 것이기 때문에 신경 쓰지 않는다. 

2단계: 그리고 5를 삭제한다면, 노드의 언더플로우가 난다. 이럴 때, 양 옆의 형제 노드에서 키 한개를 들고 와야한다. 

3단계: 들고 올때는 부모를 통해서 들고 와야한다. 왜냐면 그냥 13을 때다가 9에다 붙여줄 경우, 7과 11사이의 값이 아니기에 B 트리가 성립하지 않는다. 

리프노드를 삭제할 경우, 만약 옆에서 빌려올 수 없을 경우는 어떻게 할까?

1단계: 7을 삭제한다음, 노드 언더플로우가 나서 형제들로부터 키를 받아야한다. 하지만 양쪽에서 빌려오기를 실패한다. 

2단계: 빌려오지 못할때, B트리에서는 통합을 실행할 수 있다. 이럴 경우, 부모를 데리고 와서 합쳐야한다. 그래서 5가 내려와서 1-3-5-9가 된다. 하지만 이럴 경우 부모 노드가 언더플로우가 된다. 하지만 또 옆에 형제를 보니 빌려올 수가 없다.

3단계: 이도 마찬가지로 부모를 데리고 와서 통합을 한다. 

B+트리와 B* 트리

B+트리

• 가장 널리 활용되는 B트리
• 키만으로 트리를 만들고 리프 노드에 키와 관련된 정보를 저장
• 키로 구성된 B트리는 리프 노드를 빨리 찾기 위한 수단
• 리프 노드들은 연결리스트로 구현

B* 트리

• 루트를 제외한 다른 노드의 자식 수가 2/3M - M
• B트리에 비해 B*트리는 공간을 효율적으로 활용