[자료구조DataStructure]B-Tree(비트리)란, 개념,정의(최대한 쉽게)

DB 카디널리티 관련해서 구글링하다보니 B-Tree구조를 반복해서 보게되었다. 듣기만 들었지 정확히 어떤 것인지 궁금해서 정리해보았다.

카디널리티가 궁금하다면 블로그 글 - 카디널리티 개념,정의을 참고하면 된다.

B-Tree(B트리)가 뭐길래

전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성된다.
출처: 위키백과

뭐? 한글인데 너무 어렵다. 차근차근 살펴보자.
위키백과에 따르면 B-Tree(이하 B트리)는 트리 자료구조 중 이진트리를 확장한 구조이다.

자료구조란?

먼저 자료구조란 무엇일까?

• 자료구조(data structure) : 데이터를 효율적으로 사용하기 틀이다. 이러한 효율성은 시간 복잡도(time complexity)와 공간 복잡도(space complexity) 기준으로 평가된다.

추가로 블로그 글 - 자료구조와 알고리즘 차이를 참고하면 좋다.

트리자료구조란?

B트리는 이름에서도 알수있듯 트리 자료구조이다. 자료구조는 알았는데 트리자료구조는 또 뭘까?

트리 구조란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다.
트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다.
또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다.
자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*]) 또는 말단 노드 (terminal node)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.
출처: 위키백과

트리구조의 특징

1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖는다.
3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다.

트리구조 중 유명한 트리구조로는

• 자가 균형 이진 탐색 트리
• 최소 비용 신장 트리
• B-트리, 2-3 트리, B+ 트리, B*-트리

이진트리자료구조란?

컴퓨터 과학에서 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.
출처: 위키백과

즉, 이진트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 뜻한다. 따라서 각 노드는 자식이 없거나 한 개 이거나 두 개만을 가질 수 있다.

이진트리종류

• 정이진트리(full binary tree)
• 완전이진트리(complete binary tree)
• 균형이진트리(balanced binary tree) 등

B트리자료구조란?

보통 B트리라고 하면 B-트리를 의미한다. B-트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리이다.

B트리구조특징

• 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 크다.
• 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B 트리를 M차 B트리라고 한다.
• 정렬된 순서 보장
• 멀티레벨 인덱싱을 통한 빠른 검색 가능

실제 MySQLDB,MariaDB에서는 B트리에서 발전한 B+트리를 실제로 사용한다.

B+트리

왜 B+트리가 나왔을까? B-트리의 단점때문이다. B-트리는 삽입, 수정, 삭제에 따라 트리의 균형을 맞추는 작업이 필요해 성능에 문제가 발생할 수 있다.
이를 해결하고자 B+트리는 Leaf node끼리는 linked list을 사용해 최적화했다.

아래 사이트를 통해 B+트리구조를 직접 만들어볼 수 있다. 재밌다!

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

참고

• https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/
• https://velog.io/@emplam27/자료구조-그림으로-알아보는-B-Tree
• https://code-lab1.tistory.com/217
• https://velog.io/@emplam27/자료구조-그림으로-알아보는-B-Plus-Tree