B Tree & B+ Tree

검색을 위한 자료구조중에서 이진트리는 한 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형(O(n)) 급으로 떨어지지만, 균형이 잘맞으면 성능이 O(log N) 수준으로 보이는 장점이 있어 이를 바탕으로 개선하고자 하는 자료구조들이 나왔습니다.

B Tree는 이진트리를 확장해서 더 많은수의 자식을 가질 수 있고, 균형이 맞지 않는 편향트리가 되지 않도록 균형을 맞추는 구조를 갖고 있습니다.

데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종입니다.

단순하고 효율적이며 레벨로만 따지면 완전히 균형을 맞춘 트리입니다.

대량의 데이터를 처리할 때 하나의 노드에 많은 데이터를 가질 수 있으므로 큰 장점을 갖고 있습니다.

B Tree의 규칙

M차 트리일 때, 루트 노드와 리프노드 를 제외한 모든 node는 최소 [M/2, 천정함수], 최대 M개의 서브 트리를 갖는다.
- 최소의 [M/2 천정함수, ceil] : 반올림값 이라고 이해하면 편하다. 1.5 -> 2 / 2.5 ->3
- M = 자식수 * 2 - 1 (M = 2t -1)
루트 노드는 적어도 2개 이상의 자식을 가져야 한다.
- 노드의 데이터 개수가 n개라면 자식 노드의 개수는 n + 1
- 최소차수는 자식수의 하한값을 의미
- 자식 수가 t 이면 M = 2t - 1 (최소차수가 2라면 M은 3이고, 이 트리는 3차 B tree )
각 노드의 자료수가 N이면 자식 수는 N+1 이여야 한다.
- key 수 = 자료(data) 수
- 노드에 2개의 키가 있으면 자식 수는 2 + 1 = 3이다.
- 아래 그림에서는 9, 11 노드가 8, 10, 12,14 노드를 가리켜서 4개 같지만 4개가 아니다.
- 8 노드, 10 노드, 그리고 12와 14가 묶은 한 노드인 총 3개의 노드를 가리키고 있는것이다.
각 노드의 자료는 정렬된 상태여야 한다.
각 노드에는 key 값이 2개 이상 들어갈 수 있다.
최대 M개의 자식을 가질 수 있는 B 트리를 M차 B트리라고 한다.
- M : 자식을 가질수 있는 숫자 = B트리의 차수
외부 노드로 가는 경로의 길이는 모두 같다. - 외부 노드는 모두 같은 레벨에 있다.
입력 자료는 중복될 수 없다.
키, 포인터를 가진다.
그림에서 숫자는 각 노드의 key이다
key 옆의 진한 주황색 부분은 각 자식들을 가르키는 포인터이다.
BST의처럼 각 노드의 왼쪽 자식 노드들의 key 값은 부모 노드보다 작으며 오른쪽 자식 노드들의 key값은 부모 노드보다 크다.

B Tree의 조회

루트노드에서 시작하여 이진트리와 같이 검색을 수행합니다.
- BST의 특성으로 자기자신보다 작은값은 왼쪽, 큰값은 오른쪽에 있습니다
- 하지만 B Tree는 한 노드에 2개이상의 키를 가지고 있을 수 있기 때문에 그 사이에 있는 값인지도 체크 해야합니다.
특정한 key들 사이에 찾는 값이 존재한다면 해당 key들 사이의 자식 노드로 내려갑니다.
- 위 그림에서 9를 찾는다면, 루트노드의 키인 7, 15중 7보단 크고 15보단 작으므로 가운데 노드로 내려가서 찾습니다.
해당 과정을 리프노드에 도달할 때 까지 반복. 만일 리프노드에서도 키가 없다면 검색은 실패.

B Tree의 삽입

자료는 항상 리프 노드에만 삽입된다.
리프 노드의 선택은 루트 노드부터 시작해 하향식으로 탐색한다.
선택한 리프 노드에 여유가 있다면 그냥 삽입.
삽입하려는 위치의 노드가 가득 찼다면, 노드를 분할하고 생성
노드가 분할되는 경우 노드의 중앙값을 기준으로 분할.
- 중앙값은 부모 노드로 합쳐지거나 새로운 노드로 생성된다.
- 중앙값을 기준으로 왼쪽의 key는 왼쪽 자식, 오른쪽 key는 오른쪽 자식으로 삽입.

B Tree의 삭제

리프 노드와 리프 노드가 아닐 경우 두가지로 나뉘고, 두 가지 경우 내에서 또 여러 가지 경우로 나뉩니다.

노드를 찾았다면 데이터 삭제 후, 노드에 너무 적은 수의 데이터가 남지 않도록 해야 합니다. (M/2 이상 보장) 만일 데이터 수가 부족하다면 형제에게서 데이터를 빌리거나 형제와 결합합니다.

B Tree 성능

B Tree의 탐색 시간복잡도는 O(lonN)

B-트리는 자동으로 균형을 잡기 때문에 최악의 경우에도 O(logN) 성능을 보장합니다.
노드의 삽입/삭제 후에도 균등한 응답 속도를 보장합니다
단점 : 삽입/ 삭제시 균형 유지를 위해 복잡한 연산이 필요합니다.

데이터 로드 효율성 측면은 대량의 데이터로 트리를 구성할 때, 진가를 발휘합니다. 
데이터가 많은경우 메모리에 트리 구조를 유지하기 보다는 외부장치에 데이터를 저장해야 합니다. 
각 노드의 값을 파일로 저장한 후, 파일 정보만 저장하고 있다면 메모리에서도 충분히 트리를 유지할 수 있게 됩니다. 
외부장치에서 데이터를 읽어올때 데이터가 크던 작던 블럭 크기 만큼 읽어옵니다. 
즉 노드의 데이터를 특정 블럭 크기 만큼 지정하여 저장 할 수 있다면 효율적으로 데이터를 읽어올 수 있다는 장점이 생깁니다.

B+ Tree

B Tree의 변형된 형태로, 특정 데이터를 탐색할경우 빠르게 탐색할 수 있지만,

전체 데이터를 차례대로 처리해야 할 경우(linear, 선형) 중위 탐색을 수행하게 되어 트리 전체를 탐색하게 되면 성능 저하가 발생한다.

BTree의 순차 접근 문제를 해결하기 위해 제시된 자료구조이다.

B-Tree에서는 비단말노드(리프 노드가 아닌 중간노드, 인덱스노드라고도 함)에 key와 data를 담을 수 잇지만

B+Tree에서는 비단말노드에는 key만 담아두고 data는 담지 않는다.

오직 리프노드에만 key와 data를 같이 저장하고 리프 노드끼리는 LinkedList로 연결되어 있다.

B-Tree에서는 중복값 없이 한 개의 노드에만 key가 유일하게 존재했으나 B+Tree는 leaf 노드와 그 외 노드에 공존할 수 있다.
B+Tree의 리프 노드 끼리는 연결리스트로 구성되어 있으며 순차 집합(Sequence Set)이라고도 한다.
리프 노드가 아닌 비단말 노드는 인덱스 집합(Index Set)이라고 부르며 데이터로의 빠른 접근을 위한 인덱스 역할만 하기 때문에 키와 포인터로만 구성된다.
따라서 기존 B-Tree의 데이터를 모두 리프 노드로 내려서 리프 노드를 B-Tree의 구조 + 연결리스트로 구현된 색인 구조로 구성하여 순차적인 탐색에 유리하다.

B+Tree의 성질

1. 모든 데이터는 리프 노드에만 존재한다.
1. 리프 노드가 아닌 비단말 노드는 key값만 담는다.
1. 모든 리프 노드는 연결리스트로 구성된다. (리프 노드들 끼리)
1. 데이터의 삽입/삭제 연산은 리프 노드에서만 발생한다.
1. 키 값은 중복될 수 있다.
1. 모든 리프노드의 첫번째 key는 index set (비단말 노드들)에 존재한다.
1. 모든 리프노드는 같은 레벨에 있다.
1. 데이터 노드의 자료들은 정렬되어 있다.

B+Tree에서의 검색

B-Tree의 경우 최상의 케이스에서는 루트에서 끝날 수 있지만

B+Tree의 경우 모든 데이터가 리프노드에 있기 때문에

모든 경우에 대해 리프 노드로 가서 순차 탐색함으로 데이터를 찾아야한다.

B+Tree의 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
1. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
1. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다.

B+Tree의 단점