B-tree 와 B+ tree

"B-tree와 B+tree의 차이는 무엇인가요?"

예전 모회사 면접을 갔을 때 나왔던 질문이었다. 

 

나는 마침 그 때 배웠던 학부 수업에서 나왔던 터라 외웠던 내용을 얘기했다. 

근데 단순 외웠던 거라 그런지, 제대로 된 답변을 못했다. 

 

기술 면접을 준비하고 있는 요즘, 다시 공부해본다. 

 

B-tree 

 "데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. " by wiki 

 

음.. 정리해보자면 이진 트리와 유사한 트리 자료구조 인데, 노드의 자식 노드의 최대 숫자가 2보다 큰 트리를 말하는 거라고 말할 수 있다. 

 또 구글링을 해보니, 하나의 노드에 여러자료가 배치되는 트리 구조라고 한다. 상용 DBMS에서 내부적으로 쓰이는 검색 구조가 B-tree라고 한다. B-tree는 외부검색에 아주 적절한 구조를 가지고 있다. (외부검색 : 외부 장치(하드 디스크 등)에 있는 자료를 검색하는 것)

 

 B-tree을 알기전에 먼저 Balanced Tree 알고 있어야 한다. 

Balanced Tree는 노드 삽입 및 삭제 시 스스로 균형을 맞춰주는 트리를 말한다. 기존 이진 트리의 문제점은 좌우 균형이 맞지 않는 것이었다.  트리가 좌우 불균형 하면 높이가 커서 검색하는데 상당히 비효율적으로 시간이 걸릴 수가 있다. (최악의 경우 O(N).. 선형검색이랑 똑같...) 이를 어느 경로를 가더라도 높이가 같도록 해주면 효율적으로 해줄 수 있다(O(logN). 이를 위해 균형적으로 트리를 만들어준다. Balance 트리에는 AVL 트리, Red-Black Tree, B-Tree가 있다. 

 

B+tree 

 B+tree는 B-tree의 확장개념으로, b-tree와 달리 모든 노드에 key, data가 있지 않으며, leaf 노드에만 key, data가 있다. 그리고 leaf 노드끼리는 연결리스트로 연결되어 있다. 

 

---

B-tree Vs B+tree

구분	B-tree	B+tree
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	높음	낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔 시, 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

 

참고 :

- ddmix.blogspot.com/2015/01/cppalgo-18-b-tree-search.html

- zorba91.tistory.com/293