[자료구조] B-Tree, B+Tree

B-Tree, B+Tree는 학부때 공부하면서 배우지만 내용을 다시 정리하는 이유는 

InnoDB 의 엔진이 B+Tree로 이루어져 있고 B+Tree는 B-Tree 의 확장된 개념으로 

InnoDB에 대해 공부할 겸 두개의 내용에 대해서 정리하고자 한다. 

 

 

B-Tree

B트리라고 부르고, 트리 자료 구조의 일종으로

이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 

B-Tree는 자료를 정렬된 상태로 유지되어 있는것이 특징이다. 

key값을 이용해 찾고자 하는 데이터를 트리 구조를 이용해 찾는 것이다. 

B-Tree의 장점으로는 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다.(균일성) 

 

https://iq.opengenus.org/b-tree-search-insert-delete-operations/

사각형으로 표시된 한개 한개를 '노드(Node)' 라고 한다.

가장 상단의 노드를 루트 노드(Root Node)

중간 노드를 브랜치 노드(Branch Node)

가장 아래 노드를 리프 노드(Leaf Node) 라고 한다. 

 

 

 

예시 

• Index Table 에서 where에 포함된 값 찾기 
• 해당 값의 table_id(PK) 가져오기
• 가져온 table_id(PK) 값으로 원본 테이블에서 값 조회하기

https://iq.opengenus.org/b-tree-searching-insertion/

 

 

B+Tree

B+Tree는 B-Tree의 확장 개념이다. 

B+Tree는 브랜치 노드에 key만 담아두고 data는 담지 않는다.

리프 노드에만 key와 data를 저장하고 리프 노드 끼리는 Linked list로 연결되어 있다. 

 

탐색을 위해서 노드를 찾아서 이동해야 한다는 단점이 있다. 

이러한 단점을 해소하기 위해 B+tree는 같은 레벨의 모든 키값들이 정렬되어 있고 

같은 레벨의 sibiling node는 연결 리스트 형태로 이루어져 있다.  (같은 레벨의  sibiling node는 모두 연결되어 있어 키값이 중복되지 않는다) 

 

특정값을 찾아야 하는 상황이 된다면 leaf node에 모든 자료들이 존재하고,

그 자료들이 연결리스트로 연결되어 있어 탐색에 있어 유리하다. 

 

 

예시

https://iq.opengenus.org/b-tree-search-insert-delete-operations/

 

 

 

 

 

 

B-Tree 생성하기

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

 

그래프 참고

https://zorba91.tistory.com/293