(아래 내용은 B-Tree 내용을 안다는 전제하에 작성하였습니다. B-Tree에 대해 알고싶은신 경우 해당 글을 참고해주시면 감사합니다.)
핵심 내용
- B-Tree의 한계점은 무엇이고 왜 B+Tree가 생겨났는지
- B+Tree란 무엇인지
- B-Tree vs B+Tree 비교
- MySQL에서 B+Tree는?
B-Tree 한계점
B+Tree를 설명하기 전에 B-Tree의 한계점이 무엇인지 생각해보자. B-Tree는 검색 속도가 빠르지만, 순차적으로 데이터를 불러오는 경우 리프, 브랜치, 루트 노드에 각각 저장된 데이터 주소를 불러와야 하기 때문에 매우 복잡합니다. 해당 내용이 왜 중요하냐면, 데이터베이스에 저장된 테이블 로우 정보는 입력된 순서대로 차근차근 저장되어 있지 않고 랜덤한 주소에 각각 저장되어 있습니다. 따라서 클라이언트 호출 시 한번에 정렬된 테이블 정보가 보여지는 것이 아니라 흩어져있는 데이터 주소를 정렬된 형태로 보여주는 것이기 때문입니다. 이런 경우 인덱스 기준으로 데이터를 정렬한다고 가정했을 때, 아래 그림과 같이 각각의 노드에 저장된 데이터 주소를 0001 -> 0002 -> 0003 -> 0004 ... 순서대로 불러온다면 매우 복잡합니다.
이외에도 삽입(insert) / 삭제(delete) 시 정렬된 균형 트리 구조를 유지하기 위해 각 노드별로 데이터 주소를 비교하며 컴퓨터 리소스를 많이 사용하게 됩니다.
B+Tree 란
아래 그림과 같이 B+Tree는 기본적으로 B-Tree와 구조가 동일합니다. 다만, 차이점으로는 데이터 주소가 각 노드별로 저장된 것이 아니라 마지막 리프 노드에만 저장되어 있으며, 브랜치와 루트 노드는 다음 자식 노드의 페이지 값만 가지고 있습니다. 또한 리프 노드의 경우 각각의 노드들이 연결 리스트로 정렬되어 있어 순차 접근 시 B-Tree 보다 빠르게 데이터에 접근 할 수 있습니다.
삭제(delete) 작업에 있어서는 B-Tree 보다 분할(Split) / 합병(Merge) 작업이 적어 리소스 부담을 줄이고, (위의 B-Tree와 B+Tree 예시 그림들을 기준으로 숫자 4를 삭제 할 경우 분할 / 합병 차이가 어떻게 나타나는지 확인해보자) 각 브랜치 및 루트 노드에서 데이터 주소 값을 저장하지 않고, 다음 자식 노드의 페이지 값만 저장하고 있기 때문에 한정된 노드 크기에서 B-Tree보다 상대적으로 깊이가 낮습니다.
그렇다면, B+Tree가 모든 면에서 B-Tree보다 성능이 좋을까? 아닙니다. 왜냐하면 만약 찾는 데이터 값이 루트 노드에 위치해 있을 경우 B-Tree는 바로 데이터에 접근 할 수 있지만, B+Tree의 경우 리프 노드까지 접근해야 해당 데이터 값을 호출 할 수 있기 때문입니다. 상대적으로 B+Tree의 장점이 많을 뿐이지 절대적으로 좋다라고 말할 수는 없습니다.
MySQL과 B+Tree
그렇다면 MySQL에서 B+Tree는 어떻게 사용될까? InnoDB에서 인덱스를 관리하는 구조로 사용되며, 이것은 앞서 설명했던 것처럼 B-Tree와 비교했을 때 많은 이점이 있습니다. 하지만 인덱스 사용 시 성능에 영향을 미치는 몇가지 중요한 점이 있는데 그것은 인덱스 키 크기와 트리 구조 깊이 입니다. InnoDB는 모든 노드(페이지)가 16KB로 고정되어 있는데, 키 값이 커질 경우 자식 노드가 발생하며 이것은 디스크 접근이 늘어나는 것을 뜻합니다. 또한 트리 구조의 깊이가 깊어질수록 같은 레코드 건수라 하더라도 깊이가 깊어져서 디스크 읽기가 더 많이 필요하기 때문에 해당 부분을 고려해 인덱스를 활용해야 합니다.
이외에도 인덱스(B+Tree를 활용한) 검색 시 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용 할 수 있으며, 부등호 비교나 값의 뒷부분이 일치하는 경우에 대한 검색은 B+Tree 인덱스를 이용한 검색이 불가능합니다.
참고
- Real MySQL
- B+Tree 삽입 삭제 : https://potatoggg.tistory.com/174
- B+Tree 만들어보는 사이트 : https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
- B-Tree 만들어보는 사이트 : https://www.cs.usfca.edu/~galles/visualization/BTree.html
'Computer Science' 카테고리의 다른 글
| MySQL에서 활용되는 B-Tree구조 (0) | 2020.05.04 |
|---|---|
| 자료구조와 알고리즘의 이해 (0) | 2019.06.09 |