1. B-Tree란?
전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B-트리를 M차 B-트리라고 한다.
- 노드는 최대 M개의 자식 노드를 가질 수 있다. ex) 3차 B-트리라면 최대 3개의 자식 노드를 가질 수 있다.
- 노드에는 최대 M-1개의 KEY를 가질 수 있다. ex) 3차 B-트리라면 최대 2개의 KEY를 가질 수 있다.
- 각 노드는 최소 ⌈M/2⌉개의 자식 노드를 가진다. (루트 노드와 leaf 노드 제외) ex) 3차 B-트리라면 각 노드는 최소 2개의 자식 노드를 가진다.
- 각 노드는 최소 ⌈M/2⌉-1개의 키를 가진다. (루트 노드 제외) ex) 3차 B-트리라면 각 노드는 최소 1개의 키를 가진다.
- internal 노드의 KEY가 x개라면 자녀 노드의 수는 언제나 x+1 개다.
노드가 최소 하나의 KEY는 가지기 때문에 몇 차 인지에 상관없이 internal 노드는 최소 두개의 자녀는 가진다.
( m이 정해지면 root노드를 제외하고 internal 노드는 최소 ⌈M/2⌉개의 자녀 노드를 가질 수 있게 된다. )
- 노드에 KEY들은 항상 정렬된 상태로 저장된다.
2. B+Tree 란?
B+tree는 B-tree의 확장개념으로,B-tree의 경우, internal 또는 branch 노드에 key와 data를 담을 수 있다. 하지만,B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다.
2.1 B+Tree 의 장점
- 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
- 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다.
- 리프 노드끼리 Linked List 로 연결되어 있기 때문에 범위 탐색, 범위 쿼리에 유리하다.
2.2 InnoDB의 B+Tree
- InnoDB에서 B+tree는 단순하게 설명한 B+tree보다 더 복잡하게 구현된 것 같다.
- 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List를 사용했고, 자식 노드로는 Single Linked List로 연결되어있다.
- key의 범위마다 찾아가야할 페이지 넘버(포인터)가 있는데, 해당 페이지 넘버를 통해 곧바로 다음 노드로 넘어간다.
- 리프 노드에 다다랐을 때 디스크에 존재하는 데이터의 주소값을 구할 수 있고, Linked List를 통해 탐색도 가능하다.
3. B-Tree vs B+Tree
