Computer Science/Data Structure

B Trees (B-Tree & B+ Tree & B* Tree)

비소_ 2022. 6. 2.

B Trees

B Trees는 데이터 탐색을 더 빠르게 하기 위한 자체 균형 트리(Self-Balanced Tree) 중 하나이다.

트리 종류 중 편향 트리(Skewed Tree)는 최악의 경우 시간 복잡도가 O(N)으로 늘어난다.

따라서, 트리는 편향되지 않도록 균형을 맞추면서 데이터를 저장하는 것이 중요하다.

균형 트리들은 각 트리마다 균형을 맞추는 방법이 조금씩 다르다.

B Trees는 주로 디스크를 이용하는 파일 시스템(File System)이나 데이터베이스(RDBMS)에서 인덱스를 통한 빠른 데이터 조회를 위해 사용되는 자료구조이다.

데이터를 빨리 찾기위해 인덱스를 작성하기 시작했으며, 데이터가 많아지자 인덱스 양도 늘어나게 됐다.

인덱스의 효용성을 늘리기 위해 인덱스의 인덱스가 작성됨에 따라 인덱스들이 계층 구조를 이루게 되었다.

이것이 B Trees의 기원이다.

B-Tree, B+ Tree, B* Tree 이렇게 3가지가 존재하며, 기본적인 틀은 같고 특징과 조건만 조금씩 다르다.

B-Tree

B 트리라고 부르며, 차수가 2로 고정된 이진 탐색 트리(BST, Binary Search Tree)와 다르게 차수가 정해져 있지 않기 때문에 M차 탐색 트리 (MST, Multi-way Search Tree)라고도 한다.

각 노드들은 Key, Data, Pointer로 구성되어있다.

B-Tree의 조건은 다음과 같다.

조건

1. 노드의 Key 개수가 K개라면, 자식 노드 수는 K+1개이다. (차수가 M이면, Key 개수는 최대 M-1개)
2. 노드의 Key는 반드시 정렬된 상태여야 한다.
3. 자식 노드들의 Key는 현재 노드의 Key를 기준으로 크기 순으로 나뉜다.
4. 루트 노드는 항상 2개 이상의 자식 노드를 갖는다. (루트 노드가 리프 노드인 경우 제외)
5. M차 탐색 트리일 때, 루트 노드와 리프 노드를 제외한 모든 노드는 최소 $\lceil\frac{M}{2}\rceil$, 최대 M개의 서브 트리를 갖는다.
6. 모든 리프 노드들은 같은 레벨에 있어야한다.

위 3차 탐색 트리의 경우 차수가 3이므로, 각 노드의 Key 개수는 최대 2개 존재할 수 있다. (조건 1)

중위 순회 탐색(In-order Traversal)으로 읽으면 Key가 정렬되어 있음을 알 수 있다. (조건 2)

탐색

Key가 정렬되어 있기 때문에 루트 노드에서부터 크기를 비교하며 내려가면 된다.

Key가 14인 Data를 읽기 위해서 다음과 같이 진행된다.

루트 노드의 다음 Key인 15보다 작으므로 가운데 포인터를 통해 다음 레벨로 이동

자식 노드의 Max Key보다 크므로 오른쪽 포인터를 통해 다음 레벨로 이동

삽입

B-Tree는 균형 트리이기 때문에 삽입/삭제가 발생하더라도 균형을 유지할 수 있어야한다.

따라서, 다음과 같은 방식으로 삽입 과정을 진행해 균형을 유지한다.

1. 빈 트리인 경우 루트 노드를 만들어 Key 삽입. 루트 노드가 가득 찬 경우 노드를 분할하여 리프 노드 생성
2. Key가 들어갈 위치를 위와 같은 과정으로 탐색
3. 해당 노드에 들어갈 수 있다면 정렬이 유지되도록 삽입, 꽉차 있다면 삽입 후 해당 노드 분할
4. 노드가 분할 되는 경우 노드의 중앙값을 기준으로 분할. 분할된 Key는 부모 노드로 합쳐지거나 새로운 노드로 생성

삭제

삭제의 경우 어느 레벨의 어떤 노드냐에 따라 삭제과정이 조금씩 다르다.

큰 틀은 힙(Heap)처럼 삭제하면서 정렬을 유지함과 동시에 균형까지 유지하는 것이다.

1. 삭제할 Key가 리프 노드에 있는 경우

해당 노드를 지웠을때 어떠한 Key도 남지 않는다면 모든 리프노드의 레벨이 같아야한다는 조건6이 깨진다.

1-1) 현재 노드의 Key 개수가 최소보다 큰 경우

이 경우 Key를 하나 지워도 해당 노드에 다른 Key가 남아있기 때문에 단순히 삭제해도 무방하다.

1-2) 현재 노드의 Key 개수가 최소이고, 형제 노드의 Key 개수가 최소보다 큰 경우

1-3) 현재 노드와 형제 노드의 Key 개수가 최소이고, 부모 노드의 Key 개수가 최소보다 큰 경우

17로 대체하고 19를 부모노드로 올리려고 했으나, 19를 가진 노드도 Key 개수가 최소

1-4) 현재 노드와 형제 노드, 부모 노드 모두 Key 수가 최소인 경우

이 경우 해당 서브트리의 높이가 줄어들어 반드시 리프 노드의 레벨이 달라지므로 트리를 재구조해야함.
2-2)와 동일

2. 삭제할 key가 내부 노드에 있는 경우

2-1) 현재 노드 또는 자식 노드의 Key 개수가 최소보다 큰 경우

Key 보다 작으면서 최대값인 Key 또는 크면서 최소값인 Key와 자리를 바꾼다.
이후 리프노드에서의 Key 삭제와 동일하다.

15보다 작으면서 최대값인 14와 자리를 변경. 이후 리프노드에서의 Key 삭제 과정 수행

2-2) 현재 노드, 자식 노드 모두 Key 개수가 최소인 경우

1-4)와 마찬가지로 이 경우 트리를 재구조화 해야한다.
삭제하려고 하는 Key를 타겟(Target)이라 하자

Target = 4를 삭제하려 함. 현재노드/자식노드 모두 Key 개수가 최소

타겟을 가리키고 있던 포인터의 오른쪽 Key값(7)을 타겟의 형제노드에 합침

B+ Tree

B+ Tree는 B-Tree를 개량한 자료구조이다.

가장 큰 차이점은 B-Tree에서는 각 Key가 Data를 포함하고 있지만,

B+ Tree는 리프 노드만이 Data를 포함하고 있기 때문에 모든 Key가 리프노드에 저장되어 있다.

또한, 리프 노드들은 LinkedList로 모두 연결되어 있다.

B+ Tree는 리프 노드만 데이터를 가지고 있기 때문에 내부 노드는 인덱스 노드, 리프 노드는 데이터 노드라고도 한다.

이렇게 만들어 놓은 이유는 B-Tree에 비하여 비교적 쉬운 순회가 가능하게 하기 위함이다.

만약 Full Scan Table이 이뤄지는 경우 리프 노드끼리 LinkedList로 연결되어 있으므로 $O(N)$이지만 B-Tree에선 $O(N log N)$이 소요된다.

반면, B-Tree는 상위 레벨에서 Key를 찾을 수 있다면, 리프노드까지 가야하는 B+Tree보다 더 빠르게 data를 획득할 수 있다.

하지만, 실제 데이터베이스 인덱스에서는 B+ Tree를 주로 사용한다.

그 이유는 특정 구간의 데이터를 가져오는 순차 검색 연산이 자주 발생하기 때문이다.

삽입

1. Key의 개수가 최대보다 적은 리프 노드에 삽입하는 경우

해당 노드의 앞에 삽입하는 경우가 아니라면, 단순히 삽입하면 된다.
리프 노드의 가장 앞에 삽입되는 경우, 해당 노드를 가리키는 포인터의 오른쪽에 위치한 Key를 삽입하려는 K로 바꿔준다.
이후 리프 노드끼리 LinkedList로 이어줘야 하므로 삽입된 Key를 LinkedList로 연결한다.

2. Key의 개수가 최대인 리프 노드에 삽입하는 경우

Key의 개수가 최대라면 중앙값을 분할한다.
중간 노드에서 분할이 일어나는 경우는 B-Tree와 동일하다.
리프 노드에서 분할이 일어나는 경우, 중앙값을 부모노드로 올린다.
이후 분할된 리프 노드를 LinkedList로 연결한다.

Key = 12를 추가 했으나 해당 리프 노드의 Key 개수가 최대치를 초과함

삭제

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

B-Tree와 동일한 과정으로 삭제된다.

2. 삭제할 Key가 리프 노드 가장 앞에 위치한 경우

이 경우 리프노드가 아닌 노드에 Key가 중복으로 존재하게 된다.
따라서 해당 Key를 노드보다 오른쪽에 있으면서 가장 작은 값으로 바꿔야한다.

B* Tree

B-Tree의 단점 중 하나는 균형을 유지하기 위해 추가적인 연산이 수행되거나 새로운 노드가 생성되는 것이다.

따라서, 이러한 과정을 최소화하기 위해 몇 가지 규칙이 추가된 B* Tree가 등장했다.

바로 최소 $\lceil\frac{M}{2}\rceil$개의 키 값을 가져야 했던 조건5에서 $\lceil\frac{2M}{3}\rceil$로 늘렸으며, 노드가 가득 차면 분할 대신 이웃한 형제 노드로 재배치를 하게된다. (더 이상 재배치를 할 수 없는 시점이 되어야 분할한다.)

다만, B+ Tree를 주로 사용하기 때문에 기반이 되는 B-Tree를 확실히 아는 것이 더 중요하다.

Ref.

https://blog.yugabyte.com/a-busy-developers-guide-to-database -storage-engines-the-basics/

https://ssocoit.tistory.com/217

https://rebro.kr/169?category=484170

https://rebro.kr/167?category=484170

저작자표시 비영리 변경금지

'Computer Science > Data Structure' 카테고리의 다른 글

레드-블랙 트리 (Red-Black Tree) (0)	2022.06.05
해시 테이블(Hash Table) (0)	2022.06.01
그래프(Graph) (0)	2022.05.31
트리(Tree) & 이진탐색트리(BST) & 힙(Heap) (0)	2022.05.30
스택(Stack) & 큐(Queue) & 덱(Deque) (0)	2022.05.27