핵심 내용
- B-Tree란 무엇인지
- B-Tree 특징 및 장단점
- MySQL에서 B-Tree 역할은?
B-Tree란
B-Tree란 하나의 노드에 여러자료가 배치되는 트리구조의 일종으로써 Binary 트리와 다르게 좌우가 항상 균형적으로 유지되고 노드 데이터는 정렬된 상태로 존재합니다. 예를 들면, 아래 그림과 같습니다.
위의 그림과 같이 어느 한쪽으로 트리구조가 쏠려있지 않고 같은 높이에 존재하는 것을 확인 할 수 있습니다. 이외에도 몇가지 B-Tree의 특징이 존재합니다.
1) 노드의 자료수가 N이라면 자식(Child) 노드 수는 N + 1이어야 합니다. 위의 그림을 예로 들면, 각 노드에 2개의 데이터가 존재하기 때문에 자식 노드가 3개씩 존재하는 것을 알 수 있습니다.
2) 각 노드 데이터에서 작은 것은 왼쪽 / 높은 것은 오른쪽으로 나뉘어 분류됩니다. 즉, 노드와 데이터는 항상 정렬된 상태로 존재합니다.
3) 모든 노드는 적어도 M/2개의 자료를 갖고 있어야 합니다.(루트 노드 제외)
4) 루트 노드는 적어도 2개 이상의 자식을 가져야 합니다.
5) 입력자료는 중복될 수 없습니다.
여기서 중요한 점은 노드 데이터가 항상 정렬되며, 트리 구조가 균형을 이루고 있다는 점입니다. 왜냐하면, 다른 특징들보다 트리 구조에 데이터 삽입(insert), 삭제(delete)가 발생하는 경우 해당 조건들을 만족시키기 위해 많은 연산이 필요하기 때문입니다.
(삽입 삭제 과정은 아래 참고 사이트를 확인 해주시기 바랍니다)
이처럼 삽입(insert), 삭제(delete) 작업 시 많은 연산이 필요한데 어떠한 장점 때문에 계속해서 사용될까요?
B-Tree 장점은 균등한 검색 속도라고 볼 수 있습니다.
- 검색하고자 하는 데이터 크기와 상관없이 균등한 검색 속도를 제공합니다. 위의 그림을 기준으로 [4, 8, 11, 13 ... 80, 88, 89, 98] 의 데이터가 하나의 배열로 저장되어 있다고 가정한다면, 13과 98을 검색했을 때 속도 차이는 굉장히 클 것입니다. 순차적으로 해당 데이터를 검색한다면 숫자가 작은 13이 상대적으로 98보다 빠르게 검색될 수 있기 때문입니다. 하지만 B-Tree의 경우 동일한 깊이에 데이터가 위치하여 균등한 검색 속도 결과를 제공합니다.
- 저장되어 있는 데이터가 늘어나도 검색 시간이 크게 증가하지 않습니다. 배열에 데이터가 추가되어 98이 아닌 130까지의 숫자가 저장된 경우 데이터 크기가 늘어남에 따라 연산 작업이 정비례함으로 시간복잡도가 O(n)과 같습니다. 반면 B-Tree 구조로 저장될 경우 데이터 증가에 따른 연산 작업이 크게 늘어나지 않아 균등한 속도로 검색 결과를 제공합니다.
MySQL에서 B-Tree는?
그렇다면 B-Tree는 어떻게 사용될까? 아래 그림을 살펴보자.
MySQL에서 DB에 저장된 데이터를 빠르게 불러오기 위해 인덱스와 데이터 파일을 따로 관리합니다. 이때 인덱스는 테이블에서 원하는 데이터를 빠르게 갖고오기 위해 사용되며 해당 목적을 달성시키기 위해 B-Tree구조로 관리됩니다. B-Tree 구조로 관리되는 이유는 인덱스 자체가 원하는 데이터를 테이블에서 빠르게 갖고 오기 위함인데, B-Tree가 해당 목적을 달성시켜주기 때문입니다. 따라서 테이블에 존재하는 인덱스를 따로 관리해 데이터의 크기나 양에 상관없이 일관된 속도를 보장해주고 빠르게 결과를 추출하기 위해 사용됩니다.
참고
- https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC
- B-Tree 삽입, 삭제 과정 : https://potatoggg.tistory.com/174
- 서적 : Real MySQL
'Computer Science' 카테고리의 다른 글
| B+Tree란 무엇일까요 (0) | 2020.05.11 |
|---|---|
| 자료구조와 알고리즘의 이해 (0) | 2019.06.09 |