B- Tree

B-트리는 정렬된 데이터를 유지하고 대수 시간에 검색, 순차 액세스, 삽입 및 삭제를 허용하는 자체 균형 트리 데이터 구조입니다.
출처

AVL의 트리는 높이에 따라 수행시간이 결정된다.
O(log N)
하지만 이 시간도 줄일 수 있을까?
높이에 따라 결정되면 높이를 줄이자!!!

하는 아이디어에서 시작한것이 B- tree(B tree)의 시작이다.\
그 방법은 한 노드에 많은 데이터를 저장하는 것! 그렇게 된다면 당연히 노드의 높이가 줄어들 것이다.
당연히 이러한 트리에는 조건이 붙는다

조건
1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다.
2. 노드 안에 데이터는 정렬되어 있어야 한다.
3. 자식 노드의 데이터는 부모의 데이터 값에 따라 배치된다.
4. 루트 노드가 리프 노드가 아닌 경우 항상 2개 이상의 자식을 갖는다.
5. M차 B-Tree라면 루트 노드와 리프 노드를 제외하고 최소 M/2개 이상의 데이터를 가지고 있어야 한다.
6. 모든 리프 노드의 높이는 같아야 합니다.
7. 리프 노드의 데이터 수는 M-1 이하여야 한다.

이때 같은 노드의 있는 데이터는 디스크에 순차적으로 저장한다.
그렇기 때문에 인덱스 접근이 가능하여 한 노드에 데이터가 여러개여도 빠른 시간안에 데이터의 유무를 찾을 수 있다.

M차 B- Tree라면 O(log N + M)이라고 생각할 수 있다.
알고리즘적으로는 맞는 얘기이지만, 실제로 pointer로 다음 노드로 가는 것은 메모리적인 접근이라 실제로는 많은 시간이 걸린다.
참조포인터의 수는 실제로 많은 시간이 걸린다.

치명적인 단점

만약 모든 데이터를 다 봐야한다면 어떻게 될까요?
아니면 특정 범위의 데이터를 찾을 때는?

B+ Tree

B+ 트리(Quaternary Tree라고도 알려져 있음)는 컴퓨터 과학용어로, 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종이다.
이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 계층 인덱스(multilevel index)로 구성된다.
출처

B+ 트리는 internal node에 인덱스만 저장하고 모든 데이터는 리프노드에 블럭단위로 저장하므로써 문제를 해결했다.
이는 또 더 나은 disk utilization을 가지게 한다.

원래는 포인터에 접근을 하고 데이터를 읽기 위해 접근해야했던 포인터 연산을 줄이기 때문에 효율적이다.

그리고 범위 계산도 편하게 이뤄진다.
기존엔 전위순회를 하면서 값을 찾아야 했다면 지금은 log N의 연산으로 시작 범위를 찾고 읽기만 하면 된다.
또 삭제 삽입 연산에 대한 포인터 작업이 적어 리소스 부담이 준다.

Index
데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조로써
테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장한다.

이는 B+tree를 사용해서 구현되는 경우가 대부분이다.
이때 index는 정렬을 위해 순차적 계산이 필요하고 전체를 계산해야하기 때문에 B+ tree가 효율적이다.

BUT
원래 데이터가 루트로부터 가깝다면 B-tree가 조금더 빠르다. -> 즉 항상 B+가 좋은 것은 아니다.