[7주차] Data Structure (B-Tree, B+Tree)

B-Tree & B+Tree

이진트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어진다는 단점이 있다. 

하지만 이진트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 검색 모두 O(logN)의 성능을 보인다는 장점 때문에
개선시키기 위한 노력이 이루어지고 있다. 

B Tree = Balanced binary tree

 

이진트리

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조

정이진트리 : 트리의 모든 node가 0개 혹은 2개의 자식을 가지는 경우

포화이진트리 : leaf node가 끝까지 꽉 찬 트리

완전이진트리 : 마지막 레벨을 제외한 모든 레벨에서 순서대로 node가 꽉 채워진 트리

균형이진트리 : leaf node들의 레벨차이가 최대 1레벨까지만 나는 트리

균형 이진트리는 AVL 트리, 레드블랙 트리, B-Tree, B+Tree, B*Tree 등에서 자주 사용된다. 

 

B Tree (B트리)

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

이진 트리를 확장해서, 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수 있다. 

 

최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다. 

 

자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라

트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다. 

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

 

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

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

ex) 한 블럭이 1024 byte면, 2byte를 읽으나 1024byte를 읽으나 똑같은 입출력 비용이 발생한다. 

따라서 하나의 노드를 모두 1024byte로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다. 

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

2. 균형을 유지한다. → 아무리 최악의 경우라도 O(logN)의 검색 성능을 보인다. 

 

규칙

1. 노드에는 2개 이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다. 

 

2. 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 한다. 

3차 B-Tree

 

3. 특정 노드의 데이터가 K개라면, 자식 노드의 개수는 K+1개여야 한다. 

 

 

4. 특정 노드의 왼쪽 서브 트리는 특정 노드의 key보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다. 

B-Tree는 노드 개의 key 값이 2개 이상 들어갈 수 있기 때문에 자식 노드를 가리키는 포인터의 개수는 key의 개수보다 1개 더 많다. 

따라서, 노드 내에서 키가 2개(a1, a2) 존재한다면, a1의 왼쪽 서브 트리는 a1보다 작아야 하고, a1과 a2 사이의 서브트리는 a1보다는 크면서 a2봐는 작아야 한다. a2 오른쪽 서브트리는 a2보다 커야한다. 

 

5. 노드 내에 데이터는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다. 

M=3이기 때문에 한 노드 당 0~2개의 데이터를 가질 수 있다. 

 

6. 모든 리프 노드들이 같은 레벨에 존재한다. 즉 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다. 

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

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

 

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Visualization

---

B+ Tree

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있음

기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조

 

B-Tree의 변형 구조로, index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다. 

인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용한다. 

 

같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Sibling node 는 연결리스트 형태로 이어져 있음. 

leaf node가 아닌 자료는 인덱스 노드라고 부르고, leaf node 자료는 데이터 노드

 

인덱스 노드의 Value값에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재

데이터 노드의 Value값에는 데이터가 존재

 

 

 

https://ssocoit.tistory.com/217

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree