[TIL] 크래프톤 정글 2주차 - 자료구조(B-Tree)

알고리즘 주간에는 그래도 전공자고 밖에서도 알고리즘 공부를 꾸준히 해왔기 때문에 따로 공부를 할 필요가 없다고 생각했는데 갑자기 공부 키워드로 밖에서 쓴 적이 없어 기억에서 사라진 B-Tree가 있었다..

 

그래서 B-Tree를 아주 자세히까지는 아니어도 어떤 자료 구조이고 어떤 곳에서 쓰이고 왜 쓰는지, 어떤 방식으로 쓰이는 지 등을 간략하게 공부하고 정리했다.

B-tree의 구성 요소

1. entry

entry는 일반 트리에서의 노드와 같다.

entry는 data와 rightptr(오른쪽 자식을 향하는 포인터)를 가지고 있다.

2. node

node는 일반 트리와 다르다.

node는 firstptr(왼쪽 자식을 향하는 포인터), numEntries(노드에 속하는 entry의 개수), entry(array의 형태로 entry들을 저장)들로 구성되어있다.

B-tree의 규칙

B-tree란, 다음 규칙을 가지고 있는 m-way search tree이다.

 

1. root는 그 자체로 leaf거나, 2 ~ m개의 subtree를 가지고 있다.(1개의 자식을 갖고 있는 것은 불가능)

2. internal node(root도, leaf도 아닌 중간 노드)들은 최소 ┌m/2┐(ceiling 함수가 입력이 안돼서 이런 식으로 입력하겠다...)개, 최대 m개의 null이 아닌 subtree들을 가진다.

3. 모든 leaf 노드들은 같은 레벨이 존재한다. 즉, tree는 perfectly balanced된 상태이다.

4. leaf 노드는 최소 ┌m/2┐- 1, 최대 m - 1개의 entry들을 가지고 있다.

B-tree의 형태

 

B-tree는 차수에 따라서 각 노드에 들어갈 수 있는 entry의 개수가 정해져있다.

 

차수는 위 B-tree의 규칙에서 m에 해당하는 숫자로, 위 그림의 경우 m = 5인 B-tree의 형태이다.

B-tree의 입력, 삭제 과정에는 들어갈 수 있는 node를 탐색하는 과정과 그 노드를 쪼개는 과정이 포함되어있다. 입력과 삭제를 설명하며 해당 과정도 포함시켜 설명하도록 하겠다.

B-tree의 입력 과정

입력 과정을 간단하게 설명하면, bottom-up 방식으로 balance를 맞추며 자라는 형식으로 입력이 이뤄진다.

만약 root노드가 overflow(규칙에 나와있는 entry 제한 개수를 넘어서는 것)될 경우, 가운데 있는 entry가 위로 올라가게 되어 해당 entry가 새로운 root가 되고, tree의 level이 1 늘어나게 된다.

 

먼저 입력과정이 어떤 형태로 이루어져 있는지 그림으로 보도록 하자.

그림만 봐서는 이해가 안되는게 당연하다

 

과정이 복잡하므로 수도 코드 없이 다음 그림을 보며 말로 설명하겠다.

1. 먼저 넣으려는 data가 들어갈 노드와 entry의 index를 찾는다.

2. 찾았다면 해당 index에 data 삽입

3-1. 만약 노드에 overflow가 일어나지 않는다면 그대로 끝

3-2. 노드에 overflow가 일어난다면 node를 split하는 과정을 갖는다.

4. 이 과정에서 가운데낀 entry가 위로 올라가며 tree의 level이 올라간다.

4-1. 만약 해당 entry가 위로 올라가서 overflow가 일어난다면 거기서도 split이 일어나서 tree의 level이 올라가는 과정에 한 번 더 일어난다.

 

혹시 수도코드와 과정을 더 자세하게 알고 싶은 사람들을 위해 수도코드와 사진을 조금 남겨두겠다.

입력 과정을 표로 표현한 그림의 함수 - 1(BTreeInsert)

입력 과정을 표로 표현한 그림의 함수 - 2(insertNode)

입력 과정을 표로 표현한 그림의 함수 - 3(searchNode)

입력 과정을 표로 표현한 그림의 함수 - 4(splitNode)

splitNode 함수의 과정을 나타낸 그림(삽입한 데이터가 중간 값보다 작거나 같은 경우)

splitNode 함수의 과정을 나타낸 그림(삽입한 데이터가 중간 값보다 큰 경우)

B-tree의 생성과정 - 1

B-tree의 생성과정 - 2

B-tree의 삭제 과정

B-tree에서의 삭제 과정은 입력 과정보다 복잡하다.

 

먼저, 세가지 고려할 것이 있다.

 

1. 삭제할 데이터가 확실히 tree 안에 있다는 것을 보장해야한다.

2. 엔트리가 삭제된 노드에 충분한 개수의 엔트리가 남아있지 않으면 적절한 조치를 취해 구조를 맞춰줘야한다.

(이런 상황을 underflow라 하고 구조를 맞춰주는 것을 reflow라 한다.)

3. 만약 삭제된 데이터가 internal node에 있다면 그 자리를 대신할 데이터를 찾아줘야 한다.

 

이러한 것을 유의하고 진행해보도록 하자.

 

입력 과정과 마찬가지로 삭제 과정에서의 함수의 흐름을 그림을 보도록 하자.

이거보고 바로 이해하는 사람이 있다면 이상한 사람이니 도망(?)가도록 하자

 

과정이 복잡하지만 어떻게든 글로 먼저 표현해보겠다.

1. 삭제할 데이터가 있는 노드를 (root에서부터 subtree로 내려가며)찾는다.

2. 노드에서 삭제할 데이터가 있는 엔트리를 찾는다.

3-1. 해당 엔트리가 root에 있는 경우, 엔트리 삭제 후 underflow가 발생했는지 확인하고 발생했다면 reflow를 실행시킨다.(reflow과정은 이후 설명)

3-2. 해당 엔트리가 internal node에 있는 경우, 엔트리 삭제 후 reflow 과정을 거쳐 balance와 b-tree 구조를 지킨다.

3-3. 해당 엔트리가 leaf node에 있는 경우, 엔트리 삭제 후 underflow가 발생했는지 확인하고 발생했다면 reflow를 실행시킨다.

 

※ reflow : underflow가 일어난 위치에 따라 실행 방법이 다르지만 전체적인 아이디어는 동일하다.

underflow는 B-tree의 규칙에 맞지 않게 노드에 엔트리 개수가 부족한 경우를 말하는데, underflow가 발생하면, 같은 레벨의 이웃 노드에서 엔트리를 빌려오거나 부모 노드에서 엔트리를 내려보내는 등, 여러 과정을 거쳐 balance를 맞춘다.

 

또는 subtree의 부모 노드를 바꾸는 방식으로 일어나기도 한다.

internal node를 delete했을 때 reflow하는 과정

underflow가 발생했을 때, 이웃 노드에서 엔트리를 빌려주는 과정

underflow가 발생했을 때, subtree의 부모를 옮기는 방식(combine)을 통해 reflow를 하는 과정

 

자세한 과정은 아래 블로그에 자세하게 나와있다.

https://rebro.kr/169

B-tree의 전체적인 삭제 과정(그림)

B-tree 사용처와 사용하는 이유(복잡도 관련)

B-tree의 경우, 데이터베이스에서 많이 사용된다고 한다.

사실 데이터베이스 탐색의 경우 해시 테이블을 사용하는 경우가 복잡도가 O(1)로 더 유리할 수 있다.

 

하지만 해시는 등호(=) 연산에만 특화되어있기 때문에 부등호 연산이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블 보다는 B-tree가 더 유리하다.

 

B-tree는 노드 하나에 여러 개의 데이터가 저장될 수 있으며, 각 노드 내의 데이터는 항상 정렬된 상태이다. 또, 그 데이터들의 사이 범위를 이용하여 자식 노드를 갖게 된다.

 

또 같은 노드 공간의 데이터들은 메모리 상에서 차례대로 저장이 되어있어 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다. 따라서 참조 포인터 접근의 횟수가 다른 자료구조(Red-Black Tree)보다 적다는 장점이 있다.

 

참조 포인트 접근의 횟수가 늘어난다는 것은 메모리가 아닌 디스크로의 접근 횟수가 늘어난다는 것과 동일하다.

디스크 접근은 메모리에 비해 매우 많은 비용을 소모하기 때문에 같은 노드 상에서 디스크 접근은 한 번 뿐이고 한 node에 들어가는 data 수의 늘리고 자식의 수를 늘려 tree의 height를 줄여 디스크 접근 횟수를 줄인 B-tree가 유리한 것이다.

 

B-tree를 사용하는 이유를 요약하자면

1) 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.

2) 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.

3) 데이터 탐색 뿐만 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.

이 세가지가 된다.

그 외

B-tree 외에 B+tree, B*tree 라는 구조도 있다.

 

B+tree는 B-tree와 다르게 leaf 노드에만 데이터가 저장되고, leaf 노드들끼리 Linked List로 연결된 구조이다.

 

B*tree는 B-tree와 다르게 삽입 과정에서 overflow가 일어났을 때, 바로 split하여 balance를 조절하는 것이 아닌, 삽입 노드의 sibling 노드로의 엔트리 재분배 과정이 먼저 일어나게 된다.

(※ sibling 노드 : 형제 노드라 하여, 해당 노드의 같은 level에 있는 노드들)

 

split은 모든 sibling들이 꽉차게 되었을 때 발생한다. 이 때, 꽉찬 두 개의 sibling 노드에서 온 데이터들은 두 개의 꽉찬 노드와 새롭게 만들어진 노드, 총 3개의 노드로 재분배가 되어 각각 2 / 3이 차있는 상태가 된다.