[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

위 글을 보고 정리를 하지 않을 수 없었습니다. 가슴이 시키네요;;
그렇다면 바로 B-Tree, B*Tree, B+Tree의 특징에 대해서 알아봅시다.

 

목차

---

0. 이진트리

B-Tree, B*Tree, B+Tree에 대해서 알아보자면서 갑자기 이진트리가 왜 냐오냐.. 싶을 수 있습니다만!!

B Trees는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 균형이진트리의 확장판입니다.
이진트리를 모른다면 당연히 B Trees도 쉽게 이해할 수 없는 것이죠.

서론이 길었네요... 이진트리 뭐 다 아시겠지만 간단히 체크하고 넘어갑시다.


이진트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다.

출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진트리에는 몇 가지 종류가 있는데요!
정이진트리(Full binary tree), 포화이진트리(Perfect binary tree), 완전이진트리(Complete binary tree), 균형이진트리(Balanced binary tree) 등이 있습니다.

 

정이진트리는 트리의 모든 node가 0개 혹은 2개의 자식을 가지는 경우를 의미합니다.
포화이진트리는 leaf node가 끝까지 정말 꽉 찬 트리를 의미합니다.
완전이진트리는 마지막 레벨을 제외한 모든 레벨에서 순서대로 node가 꽉 채워진 트리를 의미합니다.
균형이진트리는 leaf node들의 레벨차이가 최대 1레벨까지만 나는 트리를 뜻합니다. (이 말은 균형이 깨지면 별도의 로직을 통해 다시 균형을 유지하게 된다는 이야기죠!!)

말만 들어서는 대부분의 경우 포화이진트리나 완전이진트리, 혹은 경우에 따라 정이진트리로 표현하면 될 것이지 굳이 균형이진트리가 왜 필요한가 싶을 수 있습니다. (약간 이도저도 아닌 포지션같은 느낌??)

하지만 실제로는 균형이진트리를 굉장히 많이 사용합니다.

오히려 포화이진트리나 완전이진트리, 그리고 정이진트리는 이상적인 경우인 만큼 현실에서는 잘 등장하지 않는 편이지만, 균형이진트리는 한 쪽으로 쏠릴 수 있는 어지러운 현실세계에서도 트리의 높이를 균형적으로 유지시켜줄 수 있기 때문이죠. (검색할 때 최악의 경우에도 O(logN)의 안정성을 유지합니다!)

그리고 균형이진트리는 AVL 트리, 레드블랙 트리, 우리가 앞으로 배울 B-Tree, B+Tree, B*Tree 등에서 주로 사용됩니다.

(앞으로 이야기할 내용들은 균형이진"탐색"트리의 일종인 B-Trees입니다. "탐색"이 붙었기 때문에 자동으로 정렬도 이루어집니다!!)

---

1. B-Tree

B-Tree는 B트리라고 부르고, 이진 트리와는 다르게 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수도 있습니다.
이렇게 하나의 노드에 여러 정보를 담게 되고, 여러 자식을 가질 수 있게 되면서 차수라는 개념이 등장합니다.

최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부르게 된 것이죠.

그리고 그 규칙에 맞게 정해진 범위만큼의 키가 하나의 노드에 포함될 수 있게 되었습니다.

이와 관련해서 B-Tree만의 몇 가지 수학적인 특징이 존재합니다. (하단에 서술했습니다)

이렇게 하나의 노드에 여러 자료를 배치하게 되면서 이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담을 수 있게 되었습니다.

하드디스크나 SSD와 같은 외부 기억장치는 블럭단위로 파일을 입출력합니다. 이때 발생하는 입출력의 비용은 파일의 크기와는 상관 없이 동일합니다. 입출력에 있어서는 1KB짜리 블럭에 1byte짜리 알파벳 하나가 들어가 있어도 1KB가 꽉 차있는 블럭과 차이가 없다는 것이죠.
이 떄 하나의 블럭에 여러 데이터들을 동시에 저장할 수 있다면 블럭을 보다 효율적으로 사용할 수 있겠죠?
그래서 많은 데이터베이스들은 B-Tree를 애용합니다.

또한 B-Tree는 균형이진트리의 연속이라고 했었죠? 당연히 균형도 유지합니다. 따라서 아무리 최악의 경우라도 O(logN)의 검색 성능을 보여줍니다.

출처 : https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

직접 B-Tree를 생성하는 것을 눈으로 보고 싶다면 아래 사이트에서 가능합니다 :)
=> https://www.cs.usfca.edu/~galles/visualization/BTree.html

1.0. B-Tree 특징

• 각 노드의 자료는 정렬되어 있습니다.
• 자료는 중복되지 않습니다.
• 모든 leaf node는 같은 레벨에 있습니다.
• root node는 자신이 leaf node가 되지 않는 이상 적어도 2개 이상의 자식을 가집니다.
• root node와 leaf node를 제외한 노드들은 최대 M개부터 최소 ⌈M/2⌉개 까지의 자식을 가질 수 있습니다.
• 노드의 키는 최대 M-1개부터 최소 ⌈M/2⌉ - 1개의 키가 포함될 수 있습니다.
• 자식 수의 하한값을 t라고 하면, M = 2t - 1 을 만족합니다.

---

2. B*Tree

B-Tree의 단점 중 하나는 구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성된다는 것입니다. (이진트리가 균형을 유지하기 위해 했던 것들.. 기억하시죠?!)

노드의 추가적인 생성과 추가적인 연산의 최소화를 위해서 B-Tree에서 몇 가지 규칙이 추가된 B*Tree가 등장하게 되었습니다.

B-Tree와 B*Tree의 가장 대표적인 차이점이라면 최소 M/2개의 키값을 가져야 했던 기존 노드의 자식 노드 수 최소 제약조건이 2M/3개로 늘어났고, 노드가 가득 차면 분열 대신 이웃한 형제 노드로 재배치를 하게 됩니다. (더이상 재배치를 할 수 없는 시점이 되어서야 분열을 하게 됩니다.)

2.0 B*Tree 특징

• 각 노드의 자료는 정렬되어 있습니다.
• 자료는 중복되지 않습니다.
• 모든 leaf node는 같은 레벨에 있습니다.
• root node는 자신이 leaf node가 되지 않는 이상 적어도 2개 이상의 자식 노드를 가집니다.
• root node가 아닌 노드들은 적어도 2⌈(M-2)/3⌉+1개의 자식 노드를 가지고 있습니다. (최대 M개)

 

---

3. B+Tree

B-Tree는 탐색을 위해서 노드를 찾아서 이동해야 한다는 단점을 가지고 있습니다.
이러한 단점을 해소하고자 B+Tree는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Sibiling node는 연결리스트 형태로 이어져 있습니다.

(같은 레벨의 Sibiling node는 모두 연결되어 있어서 키값이 중복되지 않습니다!)

만약 특정 값을 찾아야 하는 상황이 된다면 leaf node에 모든 자료들이 존재하고, 그 자료들이 연결리스트로 연결되어 있으므로 탐색에 있어서 매우매우 유리합니다.

탐색하는 과정 예시

leaf node가 아닌 자료는 인덱스 노드라고 부르고, leaf node 자료는 데이터 노드라고 부릅니다.


인덱스 노드의 Value값에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재합니다.
데이터 노드의 Value값에 데이터가 존재하는 것이죠.

따라서 키값은 중복될 수 있고 (인덱스 노드와 데이터 노드에서 동시에 등장 가능!!!), 데이터 검색을 위해서는 반드시 leaf node까지 내려가야 한다는 특징을 가지고 있습니다.

오늘날 데이터베이스에서 가장 중요한 것은 검색속도이기 때문에 대부분의 데이터베이스 시스템은 B+Tree구조를 채택하고 있습니다.

출처: https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/

직접 B+Tree를 생성하는 것을 눈으로 보고 싶다면 아래 사이트에서 가능합니다 :)
=> https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

3.0. B+Tree 특징

• 데이터 노드의 자료는 정렬되어 있습니다.
• 데이터 노드에서는 데이터가 중복되지 않습니다.
• 모든 leaf node는 같은 레벨에 있습니다.
• leaf node가 아닌 node의 키값의 수는 그 노드의 서브트리수보다 하나가 적습니다.
• 모든 leaf node는 연결리스트로 연결되어 있습니다.

 

---

4. 참고문헌

이진 트리 - 위키백과, 우리 모두의 백과사전

탐색자료구조(Binary Tree, B-Tree, B+ Tree, B* Tree, Bitmap Index) - 정보관리기술 위키 - 위키독

[알고리즘] B* 트리, B+ 트리

[File System] ::B* tree, B+ tree

[DB] 10. B-Tree (B-트리)

[자료구조] 그림으로 알아보는 B-Tree