B트리

B Tree : Balanced Tree로 균형을 유지하는 트리

(Balanced Tree의 종류 : AVL 트리, 2-3 트리, 2-3-4 트리, Red-black 트리, B트리 등등)

만약 한 노드에 M개의 자료가 배치되면 M차 B 트리

 

출처: 위키

B Tree : 메모리의 저장 공간의 부족과, 저장장치에 효율적으로 대용량 처리 방식을 위해 고안된 알고리즘입니다.

검색시 검색키와 타 key들과의 연산을 줄이고 메모리에 올려져 있지 않은 데이터(B-Tree)를 조회하기 위해 Row를 최소한으로 접근할 수 있도록 합니다.

 

기존에 자식을 두개만 가질 수 있던 Binary Tree(이진 트리)를 확장하여 더 많은 자식을 가질 수 있게 고안한 것.

탐색시에는 이진트리와 동일한 방법으로 탐색을 합니다.

하향식으로 검색 대상의 값을 구분 값과 비교하여 자식포인터를 찾아가는 방식으로 진행됩니다.

 

이진 트리는 추가, 검색, 삭제 등에 O(NlogN)의 시간 복잡도를 가지지만,

 

좌우 균형이 맞지 않을 때는 매우 비효율적 -> 최악의 경우 O(N*N)의 시간복잡도를 가진다.

=> 이진 트리의 균형을 맞출 필요가 있다.

 

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

대량의 데이터는 메모리 보다는 하드디스크 혹은 SSD에 저장되어야 하는데 이들 외부 기억 장치들은 블럭 단위로 입출력을 하기 때문이다.

 

예를 들어 한 블럭이 1024 바이트라면 2바이트를 읽으나 1024 바이트를 읽으나 입출력에 대한 비용은 동일하다. 그렇다면 하나의 노드를 1024바이트가 되도록 조절한다면 입출력 면에서 매우 효율적인 구성이 된다. 이런 장점으로 실제 B-Tree는 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용되고 있다.

B-tree를 직접 해볼 수 있는 사이트

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