[Database] B-Tree 와 B+Tree 데이터베이스

참고

https://gyoogle.dev/blog/computer-science/data-structure/B%20Tree%20&%20B+%20Tree.html

https://8iggy.tistory.com/191

https://algopoolja.tistory.com/122

https://code-lab1.tistory.com/217

B-Tree 와 B+Tree 의 차이점

B- tree

B-tree는 Binary 가 아니라 Balanced 다. 이전의 Binary Tree 는 2개의 자식노드만 가지기 때문에 높이가 늘어날 수 밖에 없었다. B-Tree 에서는 자식 노드를 여러개 가짐으로써 높이를 줄여줄 수 있는 자료구조다.

 

B-tree

• 노드에는 2개 이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다. 그림를 보면 각 노드는 ascending 순서로 정렬되어 있다.
• M차 B 트리라고 하면 최대 M 개의 자식을 가질 수 있는 B 트리를 뜻한다. 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다.
• 특정 노드의 데이터가 K개라면, 자식 노드의 수는 K+1개여야한다. 
• 특정 노드의 왼쪽 서브 트리는 특정 노드의 Key 보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다.
• 데이터가 추가된다면 높이를 Balance 하는 알고리즘이 적용된다. 

4-way tree

루트 노드는 3개의 데이터를 갖는다.

• 자식 노드의 수는 최대 4개
• 루트 노드 100를 기준으로 보면 왼쪽 서브 트리는 100보다 작고, 오른쪽 서브 트리는 100 보다 크다

대량의 데이터를 처리해야 할 때, 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 상당히 큰 장점이다.

대량의 데이터는 메모리보다 블럭 단위로 입출력하는 하드디스크 or SSD에 저장해야하기 때문!

ex) 한 블럭이 1024 바이트면, 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용 발생. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다.

→ B-Tree는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용하고 있음

B+ Tree

B- Tree와는 달리 리프 노드에만 데이터를 저장한다. 리프 노트가 아닌 곳에는 인덱스가 저장된다.

• B+ 트리의 리프 노드들은 LinkedList 로 구현되어 있는 순차 집합이다. 리프 노드끼리 연결되어 있기 때문에 범위 탐색에 유용하다
• key 값에 대한 정보가 이미 자료구조에 적혀있다. 즉, 다음 노드가 어디있는지 포인터를 찾아 저장할 필요가 없기 때문에 IO 블록을 더 크게 잡을 수 있다.
• 리프 노드가 아닌 노드는 인덱스 집합으로 빠른 접근을 위한 역할만 한다.