검색을 위한 자료구조 중에서 이진 트리는 비록 하나의 부모가 두개의 자식밖에 가지질 못하고 자칫 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어지지만 잠재력이 가장 크다. 그렇지만 이진 트리는 구조의 간결함과 균형만 맞다면 검색,삽입,삭제 모두 O(logN)의 성능을 보이는 장점이 있어서 이를 바탕으로 개선하고자 하는 노력이 많이 있어 왔다.
그중에서도 B-Tree는 이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화하였다. B-트리는 자식 수에 대한 일반화를 하면서 하나의 레벨에 더 많이 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞추는 로직까지 갖추었다. 게다가 이 균형 로직은 단순하면서도 효율적이다. 그래서 B-트리는 레벨로만 따지면 완전히 균형을 맞춘 트리이다.
대량의 데이터를 처리해야 하는 검색 구조인 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 큰 장점이다. 대량의 데이터는 메모리 보다는 하드디스크 혹은 SSD에 저장되어야 하는데 이들 외부 기억 장치들은 블록 단위로 입출력을 하기 때문이다.
예를 들어 한 블럭이 1024 바이트라면 2바이트를 읽으나 1024바이트를 읽으나 입출력에 대한 비용을 동일하다. 그렇다면 하나의 노드를 1024바이트가 되도록 조절한다면 입출력 면에서 매우 효율적인 구성이 된다. 이런 장점으로 실제 B 트리는 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용되고 있다.
B-Tree 란?
하나의 노드에 여러 자료가 배치되는 트리 구조. 한 노드에 M개의 자료가 배치되면 M차 B-Tree라고 한다. B-Tree는 스스로 균형을 맞추는 트리이다. 그래서 최악의 경우에도 O(logN)의 검색 성능을 보인다.
규칙
-
하나의 노드에 여러자료가 배치되는 트리 구조
-
한 노드에 M개의 자료가 배치되면 M차 B-Tree
( M이 짝수냐 홀수냐에 따라 알고리즘이 다르다.)
-
노드안의 자료수가 N이라면, 자식의 수는 N + 1 이어야한다.
-
루트노드는 적어도 2개이상의 자식을 가져야 한다.
-
각 노드의 자료는 정렬된 상태여야 한다.
-
노드의 자료 Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고, Dk의 오른쪽 서브트리는 Dk보다 큰 값들이어야 한다.
-
Root 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야한다.
ex) 5차 B - Tree 인 경우 루트 노드를 제외한 모드 노드는 적어도 2개의 자료를 가지고 있다
-
외부노드로 가는 경로의 길이는 모두 같다. ( 외부노드는 모두 같은 레벨에 있다. )
-
입력자료는 중복될 수 없다.
B+Tree 란?
B+Tree는 B-Tree의 확장 개념으로, B-Tree의 경우, internal 또는 branch(중간) 노드에 key와 data를 담을 수 있다. 하지만, B+tree의 경우 브랜치 노드에 key만 두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다.
MySQL의 InnoDB는 B+tree로 이루어져 있다.
장점
-
리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.
-
풀 스캔시, B+Tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-Tree에 비해 빠르다. B-Tree의 경우에는 모든 노드를 확인해야 한다.
B-tree VS B+tree
참고자료
https://wangin9.tistory.com/entry/B-tree-B-tree
https://zorba91.tistory.com/293
